1、第第3章章 进程管理进程管理3.1 进程的概述进程的概述3.2 进程的引入和定义进程的引入和定义3.3 进程的状态和进程控制块进程的状态和进程控制块3.4 进程控制进程控制3.5 线程的基本概念线程的基本概念3.6 进程调度进程调度3.7 进程同步与互斥进程同步与互斥 3.8 进程通信进程通信3.9 死锁问题死锁问题本章学习目标本章学习目标在多道程序环境下，程序不能独立运行。作为资源分配和在多道程序环境下，程序不能独立运行。作为资源分配和独立运行的基本单位是进程。操作系统所有的特征都是基独立运行的基本单位是进程。操作系统所有的特征都是基于进程而体现的。所以，本章的主要问题是：于进程而体现的。所
2、以，本章的主要问题是：进程的概念进程的概念进程的实体、状态及状态的演变进程的实体、状态及状态的演变进程的控制与调度进程的控制与调度进程之间的关系协调进程之间的关系协调进程的通信进程的通信死锁问题及解决死锁问题及解决返回本章首页返回本章首页3.1 进程的概述进程的概述 处理机管理是操作系统的基本管理功能之一，它所关心的处理机管理是操作系统的基本管理功能之一，它所关心的是处理机的分配问题。也就是说把是处理机的分配问题。也就是说把CPU（中央处理机）中央处理机）的使用权分给某个程序，通常把这个正准备进入内存的程的使用权分给某个程序，通常把这个正准备进入内存的程序称为作业，当这个作业进入内存后我们把它
3、称为进程。序称为作业，当这个作业进入内存后我们把它称为进程。处理机管理分为作业管理和进程管理两个阶段去实现处理处理机管理分为作业管理和进程管理两个阶段去实现处理机的分配，常常又把直接实行处理机时间分配的进程调度机的分配，常常又把直接实行处理机时间分配的进程调度工作作为处理机管理的主要内容。工作作为处理机管理的主要内容。进程通常具有三种状态：运行状态（正在使用进程通常具有三种状态：运行状态（正在使用CPU）、）、阻塞状态（等待输入阻塞状态（等待输入/输出）和就绪状态（等待分配输出）和就绪状态（等待分配CPU）。）。返回本章首页返回本章首页3.2 进程的引入和定义进程的引入和定义3.2.1 进程的
4、引入进程的引入3.2.2 进程的定义进程的定义返回本章首页返回本章首页3.2.1 进程的引入进程的引入1程序的顺序执行及其特性程序的顺序执行及其特性2资源共享资源共享3程序的并发执行及其特性程序的并发执行及其特性 1程序的顺序执行及其特性程序的顺序执行及其特性 由于各类软件的出现及日益复杂化，使得程序设由于各类软件的出现及日益复杂化，使得程序设计的概念和方法有了很大的发展，在单道程序工计的概念和方法有了很大的发展，在单道程序工作环境中，我们把一个作环境中，我们把一个“程序程序”理解为理解为“一个在一个在时间上按严格次序前后相继的操作序列时间上按严格次序前后相继的操作序列”。一切顺序执行的程序都
5、具有下列特性：一切顺序执行的程序都具有下列特性：（1）顺序性。）顺序性。（2）资源独占。）资源独占。（3）结果的无关性。）结果的无关性。2资源共享资源共享 操作系统提供了两种实现资源共享的方法。操作系统提供了两种实现资源共享的方法。（1）由操作系统统一管理和分配。）由操作系统统一管理和分配。（2）由进程自行使用。）由进程自行使用。3程序的并发执行及其特性程序的并发执行及其特性 无论是操作系统自身的程序还是用户程序，通常无论是操作系统自身的程序还是用户程序，通常总是存在一些相对独立、但又能并发执行的程序总是存在一些相对独立、但又能并发执行的程序段。由于这些程序段可以被多个用户作业调用，段。由于这
6、些程序段可以被多个用户作业调用，因此可在同一时间间隔内发生。这样一来，某个因此可在同一时间间隔内发生。这样一来，某个程序段可能对应多个程序段可能对应多个“计算计算”，于是程序与，于是程序与“计计算算”已不具有一一对应关系了。这些已不具有一一对应关系了。这些“并发程序并发程序”就构成了一个就构成了一个“并发环境并发环境”。图3.2 并行计算的先后次序程序的制约方式有如下两种程序的制约方式有如下两种 ：（1）间接制约方式。）间接制约方式。这是由于竞争相同资源而引起的，得到资源的程序段可以这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获投入运行，而
7、得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行得可用资源时再继续运行 。（2）直接制约方式。）直接制约方式。这通常是在那些逻辑上相关的程序段之间发生的。一般是这通常是在那些逻辑上相关的程序段之间发生的。一般是由于各种程序段要求共享信息引起的由于各种程序段要求共享信息引起的 。返回本节目录返回本节目录3.2.2 进程的定义进程的定义 进程与程序的区别和相互关系进程与程序的区别和相互关系 ：（1）动态性和静态性。）动态性和静态性。（2）从结构上看每个进程的实体都是由程序段和相应的数据）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。段两部分构
8、成的，这一特征与程序的含义相近。（3）一个进程可以涉及到一个或几个程序的执行；反之一程）一个进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程可构成不同的进程 。（4）并发性。）并发性。（5）进程具有创建其他进程的功能。）进程具有创建其他进程的功能。（6）操作系统中的每一个程序都是在一个进程现场中运行的。）操作系统中的每一个程序都是在一个进程现场中运行的。返回本节目录返回本节目录3.3 进程的状态和进程控制块进程的状态和进程控制块 3.3.1 进程的状态及状态变化图进程的状
9、态及状态变化图 3.3.2 进程控制块进程控制块 返回本章首页返回本章首页3.3.1 进程的状态及状态变化图进程的状态及状态变化图 （1）运行状态：进程正在处理机上运行的状态，该进程）运行状态：进程正在处理机上运行的状态，该进程已获得必要的资源，也获得了处理机，用户程序正在处理已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。机上运行。（2）阻塞状态：进程等待某种事件完成（例如，等待输）阻塞状态：进程等待某种事件完成（例如，等待输入入/输出操作的完成）而暂时不能运行的状态，处于该状输出操作的完成）而暂时不能运行的状态，处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理态的进程
10、不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。机，它也不能运行。（3）就绪状态：该进程运行所需的一切条件都得到满足，）就绪状态：该进程运行所需的一切条件都得到满足，但因处理机资源个数少于进程个数，所以该进程不能运行，但因处理机资源个数少于进程个数，所以该进程不能运行，而必须等待分配处理机资源，一旦获得处理机就立即投入而必须等待分配处理机资源，一旦获得处理机就立即投入运行。运行。图图3.3 典型的进程状态演变图典型的进程状态演变图状态变化状态变化 ：（1）就绪状态变化到运行状态）就绪状态变化到运行状态 。（2）运行状态变化到就绪状态。）运行状态变化到就绪状态。（3）运行状态变化到阻
11、塞状态。）运行状态变化到阻塞状态。（4）阻塞状态变化到就绪状态。）阻塞状态变化到就绪状态。返回本节目录返回本节目录3.3.2进程的结构、进程控制块及进程的结构、进程控制块及组织方式组织方式 为了刻画进程的动态变化，通常把进程表示为由为了刻画进程的动态变化，通常把进程表示为由程序段、私有数据块和进程控制块组成，如图程序段、私有数据块和进程控制块组成，如图3.4（a）所示。程序部分描述进程本身所要完成的所示。程序部分描述进程本身所要完成的功能，而功能，而“私有数据块私有数据块”是接受程序规定操作的是接受程序规定操作的一组存储单元的内容，是操作的对象。进程控制一组存储单元的内容，是操作的对象。进程控
12、制块是在进程创建时产生的，当进程存在于系统时块是在进程创建时产生的，当进程存在于系统时（运行），进程控制块就标识了这个进程。如图（运行），进程控制块就标识了这个进程。如图3.4（b）所示。所示。进程控制块是进程存在的标志，当系统或父进程进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程创建一个进程时，实际上就是为其建立一个进程控制块。控制块。进程控制块既能标识进程的存在，又能刻画出进进程控制块既能标识进程的存在，又能刻画出进程的动态特征，它是一个进程仅有的被系统真正程的动态特征，它是一个进程仅有的被系统真正感知的部分。对操作系统而言，所有进程控制块感知的部分。
13、对操作系统而言，所有进程控制块将构成并发执行控制和维护系统工作的依据。将构成并发执行控制和维护系统工作的依据。进程控制块的作用：进程控制块的作用：返回本节目录返回本节目录进程控制块进程控制块PCBPCB的组织方式的组织方式:为了进行为了进行PCBPCB的有效管理，系统将的有效管理，系统将PCBPCB按照一定的方式按照一定的方式组织起来。组织起来。PCBPCB常用的组织方式有：常用的组织方式有：1 1）线性表方式：不论进程的状态如何，将所有的）线性表方式：不论进程的状态如何，将所有的PCBPCB连连续地存放在内存的系统区。这种方式适用于系统中进程数续地存放在内存的系统区。这种方式适用于系统中进程
14、数目不多的情况。这种方式实现简单，但检索速度慢。目不多的情况。这种方式实现简单，但检索速度慢。2 2）索引表方式：该方式是线性表方式的改进，系统按照）索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。进程的状态分别建立就绪索引表、阻塞索引表等。3 3）链接表方式：系统按照进程的状态将进程的）链接表方式：系统按照进程的状态将进程的PCBPCB组成组成队列，从而形成就绪队列、阻塞队列、运行队列等。队列，从而形成就绪队列、阻塞队列、运行队列等。3.4 进程控制进程控制 3.4.1 原语原语 3.4.2 进程控制原语进程控制原语 返回本章首页返回本章首页3.4.
15、1 原语原语 在操作系统中，某些被进程调用的操作，例如队在操作系统中，某些被进程调用的操作，例如队列操作、对信号灯的操作、检查启动外设操作等，列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行就不能被中断，否则就会出现操作一旦开始执行就不能被中断，否则就会出现操作错误，造成系统混乱。原语就是为实现这些操作错误，造成系统混乱。原语就是为实现这些操作而设置的。而设置的。图图3.5 进程家族示例进程家族示例返回本节目录返回本节目录3.4.2 进程控制原语进程控制原语创建原语撤消原语阻塞原语唤醒原语挂起原语 激活原语返回本节目录返回本节目录3.5 线程的基本概念线程的基本概念3.5.1 3.5.
16、1 线程线程的引入的引入3.5.2 3.5.2 线程与进程的关系线程与进程的关系3.5.3 3.5.3 线程的类型线程的类型3.5.4 3.5.4 线程的特点线程的特点 返回本章首页返回本章首页3.5.1 线程的引入线程的引入（1 1）创建进程。系统在创建进程时，必须为之）创建进程。系统在创建进程时，必须为之分配其所必需的、除处理机以外的所有资源。如分配其所必需的、除处理机以外的所有资源。如内存空间、内存空间、I/OI/O设备以及建立相应的设备以及建立相应的PCBPCB结构。结构。（2 2）撤消进程。系统在撤消进程时，又必须先）撤消进程。系统在撤消进程时，又必须先对这些资源进行回收操作，然后再
17、撤消对这些资源进行回收操作，然后再撤消PCBPCB结构。结构。（3 3）进程切换。在对进程进行切换时，由于要）进程切换。在对进程进行切换时，由于要保留当前进程的保留当前进程的CPUCPU环境和设置新选中进程的环境和设置新选中进程的CPUCPU环境，为此需花费不少处理机时间。环境，为此需花费不少处理机时间。返回本节目录返回本节目录3.5.2 线程与进程的比较线程与进程的比较1调度调度：在传统的操作系统中，拥有资源的基本单位和独立调度、在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。分派的基本单位都是进程。2并发性：并发性：在引入线程的操作系统中，不仅进程之间可以并发在引
18、入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。高系统吞吐量。3拥有资源：拥有资源：不论是传统的操作系统，还是设有线程的操作系不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。4系统开销：系统开销：由于在创建或撤消进程时，系统都要为之分配或由于在创建或撤消进程时
19、，系统都要为之分配或回收资源，如内存空间、回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。销将明显地大于在创建或撤消线程时的开销。返回本节目录返回本节目录3.5.3 线程的类型线程的类型 对于线程来说，则可分成两类。对于线程来说，则可分成两类。一类是内核支持线程，它们是依赖于内核的。即无论是在一类是内核支持线程，它们是依赖于内核的。即无论是在用户进程中的线程，还是系统进程中的线程，它们的创建、用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换都由内核实现。在内核中保留了一个线程控制撤销和切换都由内核
20、实现。在内核中保留了一个线程控制块，内核根据该控制块而感知该线程的存在并对线程进行块，内核根据该控制块而感知该线程的存在并对线程进行控制。控制。另一类是用户级线程。它仅存在于用户级中，对于这种线另一类是用户级线程。它仅存在于用户级中，对于这种线程的创建、撤销和切换，都不利用系统功能调用来实现，程的创建、撤销和切换，都不利用系统功能调用来实现，因而这种线程与内核无关。相应地，内核也并不知道有用因而这种线程与内核无关。相应地，内核也并不知道有用户级的线程存在。户级的线程存在。返回本节目录返回本节目录比较两种线程的优缺点比较两种线程的优缺点 ：1线程的调度与切换速度：线程的调度与切换速度：内核支持线
21、程的调度和切换与进内核支持线程的调度和切换与进程的调度和切换十分相似。程的调度和切换十分相似。2系统功能调用：系统功能调用：当传统的用户进程调用一个系统功能调用当传统的用户进程调用一个系统功能调用时，要由用户态进入核心态，用户进程将被阻塞。当内核完成时，要由用户态进入核心态，用户进程将被阻塞。当内核完成系统调用而返回时，才将该进程唤醒，继续执行。系统调用而返回时，才将该进程唤醒，继续执行。3线程执行时间线程执行时间 ：对于只设置了用户级线程的系统，调度是对于只设置了用户级线程的系统，调度是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流以进程为单位进行的。在采用轮转调度算法时，各个进程轮
22、流执行一个时间片，这对诸进程而言似乎是公平的。执行一个时间片，这对诸进程而言似乎是公平的。3.5.4 线程的特点操作系统为每个被创建的进程分配需要的资源，一个进程操作系统为每个被创建的进程分配需要的资源，一个进程内的各个线程共享进程的资源。多线程技术有以下明显的内的各个线程共享进程的资源。多线程技术有以下明显的优越性：优越性：（1 1）创建线程无需另外分配资源，因而创建线程的速度）创建线程无需另外分配资源，因而创建线程的速度比创建进程的速度快，且系统开销小。比创建进程的速度快，且系统开销小。（2 2）线程间的互操作在同一地址空间中进行，故在交换）线程间的互操作在同一地址空间中进行，故在交换信息
23、中不需要其他的通信机制，信息传递的速度更快。信息中不需要其他的通信机制，信息传递的速度更快。（3 3）线程能独立执行，能充分利用和发挥处理器和外围）线程能独立执行，能充分利用和发挥处理器和外围设备并行工作的能力。设备并行工作的能力。3.6 进程调度进程调度 3.6.1 3.6.1 进程调度进程调度的职能的职能3.6.2 3.6.2 进程调度所用的主要数据结构进程调度所用的主要数据结构3.6.3 3.6.3 进程调度的方式进程调度的方式3.6.4 3.6.4 进程调度算法进程调度算法3.6.5 3.6.5 综合的调度策略综合的调度策略调度用的进调度用的进程状态切换图程状态切换图返回本章首页返回本
24、章首页3.6.1 进程调度的职能进程调度的职能 （1）记录系统中所有进程的有关情况。）记录系统中所有进程的有关情况。（2）确定分配处理机的原则。）确定分配处理机的原则。（3）分配处理机给进程。）分配处理机给进程。（4）从进程收回处理机。）从进程收回处理机。返回本节目录返回本节目录3.6.2 进程调度所用的主要数据结构通过通过3.3.23.3.2节的学习我们知道操作系统对进程的节的学习我们知道操作系统对进程的管理具体体现在对进程的管理具体体现在对进程的PCBPCB的管理。同时我们的管理。同时我们也了解到也了解到PCBPCB的几种组织方式：线性表方式、索的几种组织方式：线性表方式、索引表方式和链接
25、表方式。一般情况下，引表方式和链接表方式。一般情况下，PCBPCB的组的组织方式采用的是链接表方式。因此，在进程调度织方式采用的是链接表方式。因此，在进程调度中所用的主要数据结构是队列（中所用的主要数据结构是队列（PCBPCB的链接方式的链接方式在这里就不详细介绍了，若需要了解请参见在这里就不详细介绍了，若需要了解请参见3.3.23.3.2节）。节）。3.6.3 进程调度的方式进程调度的方式可分为非剥夺式和剥夺式。进程调度的方式可分为非剥夺式和剥夺式。剥夺式调度是指当系统按照某种原则发现一个比现运行进程更合剥夺式调度是指当系统按照某种原则发现一个比现运行进程更合适、更应该占用适、更应该占用CP
26、UCPU的进程时，系统将强迫处于运行状态的进程将的进程时，系统将强迫处于运行状态的进程将CPUCPU的使用权交给这个更适合的进程。常见的剥夺原则有优先权原的使用权交给这个更适合的进程。常见的剥夺原则有优先权原则、短进程优先原则和时间片原则。采用剥夺式调度的系统能够及时则、短进程优先原则和时间片原则。采用剥夺式调度的系统能够及时处理紧急事件，它反映出了进程的优先级特征，但这势必会带来较大处理紧急事件，它反映出了进程的优先级特征，但这势必会带来较大的系统开销，调度算法也会相对复杂一些。的系统开销，调度算法也会相对复杂一些。非剥夺式调度是指一旦某个进程占用了非剥夺式调度是指一旦某个进程占用了CPUC
27、PU，除非是由于它自，除非是由于它自身原因自动放弃身原因自动放弃CPUCPU，否则它将一直运行下去直到完成。这种调度，否则它将一直运行下去直到完成。这种调度方式算法简单，系统开销也较小，但它不能反映出进程的优先级特征。方式算法简单，系统开销也较小，但它不能反映出进程的优先级特征。3.6.4 进程调度算法进程调度算法 1先来先服务先来先服务 2轮转调度轮转调度 3分级轮转法分级轮转法4优先数法优先数法 5 5多级反馈队列调度算法多级反馈队列调度算法1先来先服务先来先服务 这种调度算法按照进程进入就绪队列的先后顺序这种调度算法按照进程进入就绪队列的先后顺序来调度进程，到达得越早，其优先数越高。获得
28、来调度进程，到达得越早，其优先数越高。获得处理机的进程，未遇到其他情况时，一直运行下处理机的进程，未遇到其他情况时，一直运行下去，系统只需具备一个先进先出的队列，在管理去，系统只需具备一个先进先出的队列，在管理优先数的就绪队列时，这种方法是一种最常见策优先数的就绪队列时，这种方法是一种最常见策略，并且在没有其他信息时，也是一种最合理的略，并且在没有其他信息时，也是一种最合理的策略。策略。2轮转调度轮转调度 先来先服务的一个重要变形，就是轮转规则。轮转调度算先来先服务的一个重要变形，就是轮转规则。轮转调度算法是系统把所有就绪进程按先后次序排队，处理机总是优法是系统把所有就绪进程按先后次序排队，处
29、理机总是优先分配给就绪队列中的第一个就绪进程，并分配它一个固先分配给就绪队列中的第一个就绪进程，并分配它一个固定的时间片（如定的时间片（如100毫秒）。当该运行进程用完规定的时毫秒）。当该运行进程用完规定的时间片时，被迫释放处理机给下一个处于就绪队列中的第一间片时，被迫释放处理机给下一个处于就绪队列中的第一个进程，分给这个进程相同的时间片，每个运行完时间片个进程，分给这个进程相同的时间片，每个运行完时间片的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，的进程，当未遇到任何阻塞时，就回到就绪队列的尾部，并等待下次转到它时再投入运行。于是，只要是处于就绪并等待下次转到它时再投入运行。于是，只要是
30、处于就绪队列中的进程，按此种算法迟早总可以分得处理机投入运队列中的进程，按此种算法迟早总可以分得处理机投入运行。行。3分级轮转法分级轮转法所谓分级轮转法就是将先前的一个就绪队列。根所谓分级轮转法就是将先前的一个就绪队列。根据进程的优先数不同划分两个或两个以上的就绪据进程的优先数不同划分两个或两个以上的就绪队列，并赋给每个队列不同的优先数。以两个就队列，并赋给每个队列不同的优先数。以两个就绪队列为例，一个具有较高优先数，另一个具有绪队列为例，一个具有较高优先数，另一个具有较低优先数，前者称为前台队列，后者称为后台较低优先数，前者称为前台队列，后者称为后台队列。队列。4优先数法优先数法 根据已占有
31、处理根据已占有处理 机的进程是否可被剥夺而分为优先占有机的进程是否可被剥夺而分为优先占有法和优先剥夺法两种法和优先剥夺法两种 。优先占有法的原理是：一旦某个最高优先数的就绪进程分优先占有法的原理是：一旦某个最高优先数的就绪进程分得处理机之后，只要不是其自身的原因被阻塞（如要求得处理机之后，只要不是其自身的原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运操作）而不能继续运行时，就一直运行下去，直至运行结束。行结束。优先剥夺法的原理是：当一个正在运行的进程即使其时间优先剥夺法的原理是：当一个正在运行的进程即使其时间片未用完，无论什么时候，只要就绪队列中有一个比它的片未用完，无
32、论什么时候，只要就绪队列中有一个比它的优先数高的进程，优先数高的进程就可以取代以前正在运优先数高的进程，优先数高的进程就可以取代以前正在运行的进程，投入运行行的进程，投入运行 。确定进程的优先数通常应考虑如下确定进程的优先数通常应考虑如下几个因素：几个因素：（1）进程类型。）进程类型。（2）运行时间。）运行时间。（3）作业的优先数。）作业的优先数。（4）动态优先数。）动态优先数。5 5 多级反馈队列调度算法多级反馈队列调度算法 多级反馈队列（多级反馈队列（Multi-level Feedback Multi-level Feedback Queues,MFQQueues,MFQ）调度算法，不必
33、事先知道各种）调度算法，不必事先知道各种进程所需的执行时间、优先级等，而且可以满足进程所需的执行时间、优先级等，而且可以满足不同类型进程的需要，它采用动态分配优先数，不同类型进程的需要，它采用动态分配优先数，调度策略实质上是抢占式的。调度策略实质上是抢占式的。它的调度策略如图它的调度策略如图3.83.8所示。所示。图图3.8 3.8 多级反馈队列调度策略多级反馈队列调度策略 返回本节目录返回本节目录3.6.5 3.6.5 综合的调度策略综合的调度策略调度用的调度用的进程状态切换图进程状态切换图 图图3.6 调度用的进程状态切换图调度用的进程状态切换图返回本节目录返回本节目录3.7 进程同步与互
34、斥进程同步与互斥 3.7.1 3.7.1 进程互斥进程互斥3.7.2 3.7.2 互斥用的硬件机制互斥用的硬件机制3.7.3 3.7.3 进程同步进程同步3.7.4 3.7.4 用信号量实现进程同步用信号量实现进程同步3.7.5 3.7.5 经典的同步经典的同步/互斥问题互斥问题3.7.6 3.7.6 结构化的同步结构化的同步/互斥机制互斥机制管程管程返回本章首页返回本章首页3.7.1 进程互斥 几个进程若共享同一临界资源，它们必须以几个进程若共享同一临界资源，它们必须以互斥的方式使用这个临界资源，即当一个进程正互斥的方式使用这个临界资源，即当一个进程正在使用临界资源且尚未使用完毕时，则其他进
35、程在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的必须推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资使用完成之前，不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。源，否则将会造成信息混乱和操作出错。临界区是一个进程访问临界资源的那段程序临界区是一个进程访问临界资源的那段程序代码。代码。有了临界资源和临界区的概念，进程间的互有了临界资源和临界区的概念，进程间的互斥可以描述为禁止两个或两个以上的进程同时进斥可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。入访问同一临界资源的临界区。几个并行进程
36、对变量和队列等临界资源的互几个并行进程对变量和队列等临界资源的互斥共享，可借助进程同步通信机构来完成。信号斥共享，可借助进程同步通信机构来完成。信号灯和灯和P/VP/V操作常用来实现进程对临界资源的互斥操作常用来实现进程对临界资源的互斥共享。共享。返回本返回本节目录节目录3.7.2 互斥用的硬件机制 在许多系统中，都提供了专门用于解决临界区问题的在许多系统中，都提供了专门用于解决临界区问题的硬件指令硬件指令Test and SetTest and Set（简称（简称TSTS）。在不同的系统中，）。在不同的系统中，TSTS指令有所不同，但其基本功能是相同的。指令有所不同，但其基本功能是相同的。定
37、义定义TSTS指令为：指令为：function TS(var lock:boolean):boolean;function TS(var lock:boolean):boolean;begin begin TS:=lock;TS:=lock;lock:=true;lock:=true;end end 为了实现用硬件指令为了实现用硬件指令TSTS实现进程互斥共享临界资源，实现进程互斥共享临界资源，系统为每个临界资源设置一个变量系统为每个临界资源设置一个变量locklock，该变量如上述，该变量如上述有两种状态，其初始值为有两种状态，其初始值为falsefalse，表示该资源空闲，进程，表示该资源
38、空闲，进程可以对其进行访问。用可以对其进行访问。用TSTS指令实现互斥的循环进程可描指令实现互斥的循环进程可描述如下：述如下：repeatrepeat while TS(lock)do skipwhile TS(lock)do skip;critical section;critical section;lock:=false;lock:=false;remainder sectionremainder section;until falseuntil false返回本节目录返回本节目录3.7.3 进程同步 并发执行的多个进程，看起来好像是异步前并发执行的多个进程，看起来好像是异步前进的，彼此
39、之间都可以互不相关的速度向前推进，进的，彼此之间都可以互不相关的速度向前推进，而实际上每一个进程在其运行过程中并非相互隔而实际上每一个进程在其运行过程中并非相互隔绝。一方面它们相互协作以达到运行用户作业所绝。一方面它们相互协作以达到运行用户作业所预期的目的，另一方面它们又相互竞争使用系统预期的目的，另一方面它们又相互竞争使用系统中有限的资源。所以它们总是存在着某种间接或中有限的资源。所以它们总是存在着某种间接或直接的制约关系。直接的制约关系。同步：同步：我们把进程间的这种必须互相合作的协同我们把进程间的这种必须互相合作的协同工作关系，称为进程同步。工作关系，称为进程同步。返回本节返回本节目录目
40、录3.7.4 用信号量实现进程同步lock和unlock大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（进程通信原语中关锁（lock）和开锁（和开锁（unlock）是最简单的原语。在是最简单的原语。在这两个原语中设置一个公共变量这两个原语中设置一个公共变量x代表某个临界资源的状态。如：代表某个临界资源的状态。如：x=0，表示资源可用，表示资源可用，x=1，表示资源正在使用。表示资源正在使用。关锁原语关锁原语1ock（x）：）：L：if x1 then goto L else x：=1；开锁原语开锁原语u
41、nlock（x）：）：x：=0；图图3.10 开锁和关锁程序流程图开锁和关锁程序流程图P/VP/V操作操作P/VP/V操作由操作由P P操作原语和操作原语和V V操作原语组成，其意义操作原语组成，其意义是指，在一个整型变量是指，在一个整型变量S S（亦称信号灯或信号量）（亦称信号灯或信号量）上定义的两个操作。现欲向缓冲区上定义的两个操作。现欲向缓冲区BuflBufl输入输入/输出输出信息。设信息。设s1s1、s2s2初值为初值为0 0，用，用P/VP/V操作实现上述操作实现上述同步模型如下：同步模型如下：返回本节目录返回本节目录3.7.5 3.7.5 经典的同步经典的同步/互斥问题互斥问题 1
42、生产者与消费者问题生产者与消费者问题 2读者与写者问题读者与写者问题3.哲学家进餐问题哲学家进餐问题1生产者与消费者问题生产者与消费者问题 Dijkstra把广义同步问题抽象成一种把广义同步问题抽象成一种“生产者与消费者问生产者与消费者问题题”（Producer-consumer-relationship）的抽象模型。事的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组）联系起来，
43、环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。次从缓冲池中取出一个产品。图图3.8 环形缓冲池环形缓冲池下面给出基于环形缓冲区的生产者与消费者关系的下面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：形式描述，设：（1）公用信号量）公用信号量mutex：初值为初值为1，用于实现临界区，用于实现临界区互斥。互斥。（2）生产者私用信号量）生产者私用信号量empty：初值为初值为n，
44、指示空缓指示空缓冲块数目。冲块数目。（3）消费者私用信号量）消费者私用信号量full：初值为初值为0，指示满缓冲，指示满缓冲块数目。块数目。（4）整型量）整型量i和和j初值均为初值均为0，i指示首空缓冲块序号，指示首空缓冲块序号，j指示首满缓冲块序号。指示首满缓冲块序号。v模块模块 设计如下：设计如下：Var mutex，empty，full：semaphore;i,j:integer；buffer：array 0n一一1 of item；Procedure producer;生产者进程生产者进程 begin while true do begin produce a product;P(em
45、pty);P(mutex);Buffer(i)：Product;i：(i+1)mod n；V(mutex);V(full)end end;procedure consumer;消费者进程消费者进程 begin While true do begin P(full)；P(mutex)goods：buffer(j);j：(j+1)mod n;V(mutex);V(empty);Consume a product;end end;begin seminitial;i:j:0;cobegin producer；consumer；coend end2读者与写者问题读者与写者问题 设某航空公司有设某航空公
46、司有2个售票处，它们通过远程终端个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库修改系统中记录所有班机当前订票数的数据库B。设设Bi为某班机的当前订票数，为某班机的当前订票数，P1和和P2分别代表分别代表2个个售票处的售票进程，售票处的售票进程，R1和和R2为进程执行时使用的为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访工作寄存器。由于售票进程并发执行，且各自访问数据库问数据库B的时间是随机的，故有可能出现下面的时间是随机的，故有可能出现下面的访问序列（假定的访问序列（假定Bi的
47、当前值为的当前值为x）：）：P1:R1:=Bi;R1:=R1+1P2:R2=Bi;R2:=R2+1;P1:Bi:=R1;P2:Bi:=R2可见，可见，Bi的新值是的新值是X+1，而不是而不是X+2。这里的这里的P1和和P2均为写者，显然，对于写者均为写者，显然，对于写者Bi为临界资源，为临界资源，因此写者应该互斥。因此写者应该互斥。下面给出读者进程与写者进程的一般结构。下面给出读者进程与写者进程的一般结构。var mutex,wrt:semaphore;readcount:integer;begin seminit;readcount:=0cobeginprocedure reader;beg
48、inP(mutex);Readcount:=readcount+1;If readcount=1 then P(wrt);V(mutex);Reading is performing;P(mutex);readcount:=readcount-1if readcount=0 then V(wrt);V(mutex);End Procedure writer;Begin P(wrt);writing is performing;V(wrt);EndCoendEnd;3.哲学家进餐问题哲学家进餐问题五个哲学家围坐在一张圆桌周围，每个哲学家面五个哲学家围坐在一张圆桌周围，每个哲学家面前都有一碟通心面
49、，由于面条很滑，所以要两把前都有一碟通心面，由于面条很滑，所以要两把叉子才能夹住。相邻两个碟子之间有一把叉子，叉子才能夹住。相邻两个碟子之间有一把叉子，餐桌如图餐桌如图3.123.12所示。所示。哲学家的生活包括两种活动：即吃饭和思考(这只是一种抽象，即对本问题而言其他活动都无关紧要)。当一个哲学家觉得饿时，他就试图分两次去取他左边和右边的叉子，每次拿一把，但不分次序。如果成功地获得了两把叉子，他就开始吃饭，吃完以后放下叉子继续思考。这里的问题就是：为每一个哲学家写一段程序来描述其行为，要求不能死锁。下面给出了最浅显的解法下面给出了最浅显的解法#define N 5#define N 5 /*
50、哲学家数目哲学家数目 */void philoiopher(int i)void philoiopher(int i)/*哲学家号从哲学家号从0 0到到4 4号号 */while(TRUE)while(TRUE)think();think();/*哲学家正在思考哲学家正在思考 */take_fork(i);take_fork(i);/*取左面叉子取左面叉子 */take-fork(i+1)%N);take-fork(i+1)%N);/*取右面叉子取右面叉子,%,%为取余为取余*/eat();eat();/*吃面吃面 */put_fork(i);put_fork(i);/*放回左面叉子放回左面叉
