1、第二章第二章 进程管理进程管理 1 1 进程的基本概念进程的基本概念 2 2 进程控制进程控制 3 3 进程同步进程同步 4 4 经典进程同步问题经典进程同步问题 5 5 管程机制管程机制 6 6 进程通信进程通信 7 7 线程线程 1 进程的基本概念 操作系统的特性之一是并发与共享，即在系统(内存)中同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。前趋图前趋图(Precedence Gra
2、ph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系。图中每个结点可用于描述一条语句、一个程序段或进程结点间的有向边则表示在两结点之间存在的偏序或前趋关系“”，=（Pi，Pj）|Pi must complete before Pj may start 如果（Pi，Pj），可写成 PiPj；，称Pi是Pj的直接前趋，而Pj是Pi的直接后继。在前趋图中，没有前趋的结点称为初始结点(Initial Node) ，没有后继的结点称为终止结点(Final Node) 。2.1.1前趋图前趋图(a) 程序的顺序执行(b) 三条语句的顺序执行I
3、1C1P1I2C2P2S1S2S3S1S2S3 每个结点还可具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。 前趋图前趋图 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九个结点的前趋图(b) 具有循环的有向图图2l示出的前趋图，存在下面的前趋关系：P1P2, P1P3，P1P4，P2P5，P3P5，P4P6, P5P7，P6P7或表示为： P = P1, P2, P3, P4, P5, P6, P7= (P1，P2) ， (P1， P3)， (P1， P4) ， (P2， P5) ， (P3， P5) ，(P4， P6) ， (P5， P7) ， (
4、P6， P7) 注意：前趋图中必须不存在循环。2.1.1前趋图前趋图一、概念 一个程序由若干个程序段组成，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一(程序段)执行完后，才能执行后继操作。这种程序执行的方式就称为程序的顺序执行程序的顺序执行。 例如： (a) 程序的顺序执行(b) 三条语句的顺序执行I1C1P1I2C2P2S1S2S32.1.2程序的顺序执行1.顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性 程序一旦开始执行，其执行结果不受外界的影响。3.可再现性 程序执行的结果与初始条件有关，而与执行时间无关。二、程序顺序执行的特点例
5、：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,.,n)。这些作业在系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。图中存在下面的前趋关系：IiCi, IiIi1, CiPi, CiCi1, PiPi1而Ii1和Ci及Pi1是重迭的 ，它们可以并发执行。P1P2P3P4I1I2I3I4C1C2C3C42.1.3程序的并发执行及其特征并发执行时的前趋图 例如:对于具有下列四条
6、语句的程序段：S1: a:=x+2;S2: b:=y+4;S3: c:=a+b;S4: d:=c+8;其前趋图如右图。 其中S1和S2可以并发执行。2.1.3程序的并发执行及其特征程序并发执行程序并发执行 （定义）（定义） 若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。PQR并发执行区2.1.3程序的并发执行及其特征程序并发执行的描述：程序并发执行的描述： parbegin S1;S2;S3;.;SN parend; Si(i=1,2,3,.,n)表示n个语句（程序段），这
7、n个语句用parbegin和parend括起来表示这n个语句是可以并发执行的。这是Dijkstra提出的。2.1.3程序的并发执行及其特征假设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的，程序如下： S0; parbegin S1;S2;S3;.;SN parend; Sn+1;2.1.3程序的并发执行及其特征程序并发执行时的特征程序并发执行时的特征1、间断性(执行暂停执行)2、失去了程序的封闭性3、不可再现性(失去封闭性引起)2.1.3程序的并发执行及其特征 例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时， 都要
8、执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。 可能出现以下三种情形： (1) N=N+1在Print(N)和N=0之前，此时得到的N值分别为n+1, n+1, 0。 (2) N=N+1在Print(N)和N=0之后，此时得到的N值分别为n, 0, 1。 (3) N=N+1在Print(N)和N=0之间，此时得到的N值分别为n, n+1, 0。 结论：程序在并发执行时， 由于失去了封闭性，其计算结果与并发程序的执行速度有关，使程序执行失去可再现性。 进程的特征与状态进程的特征与状态 在单道程序设计环境下，CPU被一道程序独占，CPU严格按程序的指令顺序来执行，程序
9、具有顺序性、封闭性和可再现性特征。 在多道程序设计的环境下，系统中有多个程序同时运行。此时的程序具有间断性、失去了程序的封闭性、不可再现性等特征。 程序一旦运行起来，它不但与程序本身有关，而且与它运行时所处的运行环境有关，程序的活动不再是静态的、封闭的，而显现出并发性、动态性以及相互制约的关系。所以用程序的概念已经不能描述上述这些特征，于是引入进程进程的概念。 进程的概念来自于麻省理工的MULTICS、IBM的 TSS/360，在IBM的OS/360/370系统中也曾叫过任务(task)。进程的特征进程的特征（1）结构特征：从结构上看，进程实体是由程序段、相关的数据段和进程控制块(PCB，pr
10、ocess control block)三部分组成。（2）动态性：进程的实质是进程实体的一次执行过程，它有着创建、活动、暂停、终止等过程，具有一定的生命期，是动态地产生、变化和消亡的。（3）并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。（4）独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。（5）异步性：各个并发进程按照各自独立的、不可预知的速度向前推进。2.1.4 进程的特征与状态进程的特征与状态 行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。 进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan
11、) 进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw) 进程是执行中的程序。（Ken Thompson and Dennis Ritchie ) 教材上给出的进程的定义： 进程进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程的定义1、程序是指令的集合，是静态的概念。 进程是程序在处理机上的一次执行过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并发活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为
12、多个进程的运行程序，一个进程也可以运行多个程序。进程与程序的区别与联系进程与程序的区别与联系 例子：光盘（CD、VCD） 光盘（程序） 放光盘的活动（进程）进程与程序的区别与联系进程与程序的区别与联系进程在系统中的活动规律是： 执行 暂停 执行(间断性)进程的三种基本状态： 就绪状态 执行状态 阻塞状态（又称等待，睡眠）进程的三种基本状态进程的三种基本状态1. 就绪状态(Ready)若进程已具备了运行条件，只因CPU被别的进程占用而不能被CPU执行，则称此时进程处于就绪状态。一旦把CPU分配给它，该进程就可以运行。从宏观上讲，它是一种逻辑上的可运行状态。系统中处于就绪状态的进程可能有多个，通常
13、将它们按某种策略（优先级）排成一个队列，称为就绪队列。 进程的三种基本状态进程的三种基本状态2. 执行状态(Running）当一个进程已分配到CPU，它的程序正在被CPU执行时进程所处的状态称执行状态，也称为运行状态。对于单CPU系统而言，处于执行状态的进程只可能有一个，多处理机系统中则有多个。进程的三种基本状态进程的三种基本状态3. 阻塞状态(Wait)正在执行的进程因等待某种事件的发生而暂时不能运行便放弃CPU的状态称阻塞状态(等待状态)，例如，等待输入/输出、等待进程间的同步/互斥等。一旦引起等待的原因消失，进程便转为就绪状态。以便在适当的时候占用CPU。系统中处于等待状态的进程可能有多
14、个，通常也将它们排成一个队列。有的系统按照进程不同的等待原因，把处于等待状态的进程排成多个队列。进程的三种基本状态进程的三种基本状态1就绪状态执行状态2执行状态阻塞状态3执行状态就绪状态4. 阻塞状态就绪状态时间片完时间片完进程状态的转换：进程的三种基本状态的转换进程的三种基本状态的转换 进程的动态性决定了它不会固定处于某个状态，系统中的进程由于各种不同的原因在以上各个状态之间变化。其状态变化及原因如图所示。 创建（新）状态和终止状态 （1）创建（新）状态：一个进程刚刚建立，但还未将它插入就绪队列时的状态。 （2）终止状态：一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它
15、撤消时的状态。进程状态的转换1创建(新)状态就绪状态2就绪状态执行状态3执行状态阻塞状态4执行状态就绪状态5执行状态终止状态 6阻塞状态就绪状态 时间片完时间片完进程状态变迁图进程状态变迁图进程的挂起状态进程的挂起状态 使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，我们把这种静止状态称为挂起状态挂起状态(静止状态)。引入挂起状态的原因有：1终端用户的需要终端用户在自己的程序运行期间发现有可疑问题，希望暂时使自己的程序静止下来。2父进程请求 父进程希望挂起自己的子进程，以便考查和修改子进程，或协调子进程的活动。3负荷调节的需要 当实时系统中的负载较重，影响
16、到实时任务的执行，可挂起不重要进程，保证系统正常运行。4操作系统的需要操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记帐。带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 所谓原语原语就是计算机机器指令的延伸，它是由若干条机器指令构成，并完成一种特定功能的程序段。 原语操作由操作系统内核提供。 为保证原语操作的正确性，还规定原语在执行期间必须一次执行完，中间不允许被中断。也就是说，原语具有原子性，即原语操作中的所有指令（动作）要么全做，要么全不做，不允许被分割。在单CPU系统中，在执行原语的过程中一般要关中断。1活动就绪静止就绪： 当进程处于未被挂起的就绪状态时，称此
17、为活动就绪状态，表示为Readya，此时进程可被调度。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys。处于Readys状态的进程，不再被调度执行。2活动阻塞静止阻塞： 当进程处于未被挂起的阻塞状态时，称为它处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds。 处于该状态的进程，在其所期待的事件出现后，它将从静止阻塞变为静止就绪。带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 3静止就绪活动就绪： 处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为
18、 Readya状态。4静止阻塞活动阻塞： 处于Blockcds状态的进程，若用激活原语Active激活后，进程将转变为Blockeda状态。 带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 具有挂起状态的进程状态图 活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 时间片完调度具有创建、终止和挂起状态的进程状态图 活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O带有挂起状态时的进程状态转换带有挂起状态时的进程状态转换 创建许可许可终止释放时间片完调度在系统中一个进程存在： 进程
19、控制块PCB(Process Control Block)(记录型数据结构) 进程的执行程序(一个可执行文件)进程执行时所需的数据 进程总是位于某个队列(就绪、阻塞某事件队列) 处于某种状态（执行、就绪、阻塞） 占用某些系统资源（内存，打开某些文件、处理机、外设）进程控制块进程控制块PCB中记录了操作系统所需的、用于描述进程的当前情况及控制进程运行所需的全部信息。1.进程标识符用于惟一标识一个进程。内部标识符操作系统为每一个进程赋予一个惟一的数字标识符(进程的序号)外部标识符由创建者提供，由字母、数字组成。为了描述进程的家族关系，还应设置父进程标识及子进程标识。还可设置用户标识。2.处理机状态
20、信息由处理机的各种寄存器(通用寄存器、指令计数器、程序状态字PSW、用户栈指针)中的内容组成。进程控制块中的信息进程控制块中的信息3.进程调度信息包括进程状态、进程优先级、进程调度所需的其它信息(与所采用的进程调度算法有关，如进程已等待CPU的时间总和、进程已执行的时间总和等)、事件(进程由执行状态转变为阻塞状态所等待发生的事件)。4.进程控制信息包括程序和数据的地址(进程的程序和数据所在的内存或外存地址)、进程同步和通信机制、资源清单(除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单)、链接指针等。进程控制块中的信息进程控制块中的信息 进程控制块PCB的作用是使一个多道环境下
21、不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个与其它进程并发执行的进程。 操作系统是根据PCB来对并发执行的进程进行控制和管理的。可以说PCB是进程存在的惟一标志。当进程被创建时，系统要为其建立一个PCB，在进程的整个生命期内系统利用该PCB对其进行控制，进程运行结束后要回收其PCB。(户口) 由于PCB经常被系统访问，故PCB应常驻内存。系统将所有的PCB组织成若干个链表(或队列)，存放在操作系统中专门开辟的PCB区内。进程控制块的作用进程控制块的作用进程控制块的组织方式进程控制块的组织方式1)1)线性方式线性方式即将系统中所有的PCB都组织在一张线性表中，将该表的首地址存
22、放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数量不多的系统。PCB1PCB2PCB3PCBn进程控制块的组织方式进程控制块的组织方式2)2)链接方式链接方式 系统把所有进程的PCB按其状态实行分类管理，每一类用一个队列来管理。一般来说，系统中的进程队列可分为三类，即就绪队列、若干个阻塞队列(根据阻塞原因的不同把处于阻塞状态的进程的PCB排成不同的队列)和空白队列 。PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针进程控制块的组织方式进程控制块的组织方式3)3)索引
23、方式索引方式系统根据所有进程的状态建立几张索引表(就绪索引表、阻塞索引表等)，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB区中的地址。执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指针 进程控制用于创建一个新进程，终止一个已完成的进程，或去终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。 进程控制一般由操作系统内核来实现。在操作系统内核中，有一组程序专门用于完成对进程的控制。 进程控制包括： 进程创建、 进程终止、 进程阻塞、 进程唤醒、进程挂起
24、、进程激活2.3 进程控制进程控制这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用(称为原语，一种特殊的系统调用)给用户提供进程控制的功能。进程图进程图(Process Graph)(Process Graph)是用于描述一个进程的家族关系的有向树。一个进程可以通过创建原语产生一个新进程 在进程Pi创建了进程Pj之后，称Pi是Pj的父进父进程程(Parent Process), Pj 是Pi的子进程子进程(Progeny Process)。用一条由进程Pi指向进程Pj的有向边来描述它们的父子关系。创建父进程的进程称为祖先进程祖先进程。这样便形成了一棵进程树进程
25、树，树的根结点作为进程家族的祖先(Ancestor)。进程树的特点：进程树的特点：资源分配严格，子进程可以继承父进程所拥有的资源；当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程；在撤消父进程时，也必须同时撤消其所有的子进程，便于管理；系统可根据需要赋予进程不同的控制权，并可以把一个任务分解成若干个进程来完成，具有较好的灵活性；树形结构层次清晰，关系明确。 进程的创建进程的创建ABCDIJEKGLMHNF图2-9进程树祖先父进程子进程 引起创建进程的事件引起创建进程的事件 1用户登录 2作业调度 3提供服务 4应用请求由系统内核创建由应用进程自已创建进程的创建进程的创建 创建进程的主
26、要工作创建进程的主要工作是申请一个进程控制块PCB，并向其中填入进程名、优先级等有关的参数。 创建进程的基本过程是：创建进程的基本过程是：(进程创建原语Creat() (1)申请空白PCB。从空闲的PCB集合中申请一个新的PCB，同时获得该进程的内部标识； (2)为新进程的程序和数据分配所需资源（内存、文件、I/O和CPU时间片）； (3)初始化进程控制块PCB。向该PCB中填写各种参数； (4)将新进程插入到就绪队列。把该进程的状态设置成就绪状态，并将该PCB插入到就绪队列中。 进程的创建进程的创建 引起进程终止的事件引起进程终止的事件 1正常结束进程任务已完成，退出运行。 2异常结束在进程
27、运行期间，由于出现异常事件而迫使进程终止。如：越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障等。 3外界干预进程应外界的请求而终止运行。包括：操作员或操作系统干预、父进程请求、父进程终止。进程的终止进程的终止 进程的终止过程是：进程的终止过程是： (进程终止原语Holt()(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其子孙进程予以终止，以防它们成为不可控的进程。(4)将
28、被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(其PCB)从所在队列中移出，等待其他程序来搜集信息。进程的终止进程的终止 引起进程阻塞和唤醒的事件引起进程阻塞和唤醒的事件1请求系统提供服务正在执行的进程请求操作系统提供服务，由于某种原因，操作系统并不立即满足该进程的要求。2启动某种操作进程启动某种操作后，必须在该操作完成之后才能继续执行。3新数据尚未到达对于相互合作的进程，如果其中一个进程需要先获得另一进程提供的数据才能运行，则只要其所需的数据尚未到达，该进程只有阻塞。4无新工作可做系统往往设置一些具有特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞
29、起来以等待新任务到来。正在执行的进程，当发生上述事件时，由于无法继续执行，于是进程便通过调用阻塞（等待）原语block把自己阻塞。可见，进程阻塞是进程自身的一种主动行为。进程的阻塞和唤醒进程的阻塞和唤醒进程的阻塞(等待)过程阻塞(等待)原语block (1)进程立即停止执行，把其PCB中的现行状态由“执行”变为阻塞； (2)将其PCB插入到相应的阻塞队列中去； (3)转调度程序进行重新调度，将处理机重新分配给另一就绪进程，并进行切换。进程的阻塞和唤醒进程的阻塞和唤醒 当被阻塞进程所期待的事件出现时，如I/O完成或所期待的数据已经到达，则由有关进程(如，用完并释放了该I/O设备的进程)调用唤醒原
30、语，将等待该事件的进程唤醒。 进程的唤醒过程 唤醒原语wakeup() (1)把被阻塞进程从等待该事件的阻塞队列中移出; (2)将其PCB中的现行状态由“阻塞”变为就绪; (3)该PCB插入到就绪队列中。注意：如果在某进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关进程中安排唤醒原语，以能唤醒阻塞进程；否则，被进程将会因不能被唤醒而长久地处于阻塞状态。进程的阻塞和唤醒进程的阻塞和唤醒 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或者父进程请求将自己的某个子进程挂起时，系统将利用挂起原语suspend（）将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程挂起原
31、语的执行过程是:(1)检查被挂起进程的状态：若正处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将其改为静止阻塞。(2)为了方便用户或父进程考查该进程的运行情况，而把该进程的 PCB复制到某指定的内存区域。(3)最后，如被挂起的进程正在执行，则转调度程序重新调度。进程的挂起与激活进程的挂起与激活 当发生激活过程的事件时，如用户进程或父进程请求激活指定进程，若进程驻留在外存而内存中已有足够的空间，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active()将指定进程激活。 激活原语的执行过程激活原语的执行过程是：先将进程从外存调入内存，检查该进程的现行状
32、态：若是静止就绪，便将其改为活动就绪；若为静止阻塞，便将其改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。进程的挂起与激活进程的挂起与激活2.4 2.4 进程同步进程同步进程同步的基本概念进程同步的基本概念两种形式的制约关系两种形式的制约关系在多道程序的环境中，系统中的多个进程可能存在着以下两种形式的制约关系： 直接相互制约关系并发进程在一些关键点上可能需要相互等待与互通消息，比如，当某进程运
33、行到某点时要求另一伙伴进程为它提供消息，在未得到对方的消息时，该进程必须处于等待状态，直到收到消息后被唤醒，这种进程之间的协同工作关系就是进程之间的直接相互制约关系，也称为进程同步关系。例如：输入进程A通过单缓冲向计算进程B提供数据 间接相互制约关系也称为进程互斥关系，是由各进程排它性使用共享资源(如共享CPU、I/O设备等)引起的。当某进程正在访问某临界资源时，就不允许其它进程进入，否则就会发生无法估计的错误，这种关系就是进程之间的互斥关系。例如：A、B两个进程共享一台打印机操作系统中一次仅允许一个进程访问的资源称为临界资源。例： 软件临界资源有内存变量、指针、数组等等 硬件临界资源有打印机
34、、磁带机等不论是硬件临界资源，还是软件临界资源，多个进程互斥地对它进行访问。临界资源临界资源 问题的描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区(每个缓冲区只能放一件产品)的缓冲池。生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品消费。分析： 同步关系同步关系：生产者进程和消费者进程之间必须保持同步，即：不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。 生产者进程的处理过程：生产一个产品，当要送入缓冲区时，要检查缓
35、冲区是否已满。若未满，则可将产品送入缓冲区；否则，等待。 消费者进程的处理过程：当它去取产品时，要检查缓冲区是否有产品。若有，则取走一个产品；否则，等待。例生产者消费者问题例生产者消费者问题著名的进程同步问题临界资源临界资源 分析：分析：用一个数组buffer来表示上述的具有n个(0，1，n-1)缓冲区的缓冲池。这里的缓冲池是组织成循环缓冲的。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。 当(in+1) mod n=out时表示缓冲池满；而in
36、=out则表示缓冲池空。引入了一个整型变量counter, 其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时， 使counter减1。生产者和消费者两进程共享下面的变量： int in=0, out=0, count=0;item buffern;Void producer()/生产者程序 Repeat produce an item in nextp;/ nextp用于暂时存放每次刚生产出来的产品 while counter=n do no-op;/表示重复地测试条件,no-op是一条空操作指令 bufferinin=next
37、p; in=(in+1)%n; counter+;Void consumer() /消费者程序 Repeat while counter=0 do no-op; nextc=bufferout; out=(out+1)%n; counter-; consumer the item in nextc;/ nextc用于存放每次要消费的产品两者在顺序执行时其结果会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时， 常可用下面的形式描述：register1:=counter; register
38、 2:=counter;register1:=register1+1; register 2:=register2-1;counter:=register1; counter:=register 2; 假设counter的当前值是5。如果按下述顺序执行： register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register
39、1; (counter=6) counter =register 2; (counter=4) 结论：变量count应作为临界资源，生产者和消费者进程互斥访问。不论是硬件临界资源，还是软件临界资源，并发进程必须互斥地对它进行访问。每个进程中访问临界资源的那段程序段称为临界区临界区(临界段)临界区临界区同一临界资源在多个共享它的进程中将对应多个临界区。 如果能保证诸进程互斥地进入自己的临界区，便可保证诸进程对临界资源的互斥访问。或者说：要临界资源互斥地被使用，就要保证临界区互斥地被执行。临界区临界区为了保证诸进程的临界区互斥地被执行，我们把一个访问临界资源的循环进程分成以下几部分：进入区进入区每
40、个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问，因此必须在临界区之前增加一段用于上述检查的代码，把这段代码称为进入区进入区。临界区临界区访问临界资源的那段程序段。退出区退出区在临界区后面增加一段用于将临界区正被访问的标志恢复为未被访问的标志的代码，把这段代码称为退出区退出区。剩余区剩余区进程除上述进入区、临界区、退出区之外的其它部分代码称为剩余区剩余区。可把一个访问临界资源的循环进程描述如下：While(TURE) 进入区 临界区 退出区 剩余区 临界区临界区进程互斥进入临界区的过程：进程互斥进入临界区的过程：临界区临界区 (1)在“进入区”判断是否可进入临界区。若可
41、以进入，则必须设置临界区使用标志，阻止其它进程进入临界区。 (2)后来的进程通过查看临界区使用标志，知道自己不能进入，就进入阻塞队列，将自己阻塞。 (3)当临界区的进程退出区时，即在“退出区”修改临界区使用标志，并负责唤醒一个进程，让其进入临界区。进入临界区的准则：进入临界区的准则：临界区临界区 (1)每次至多有一个进程处于临界区； (2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入； (3)进程在临界区内仅逗留有限的时间。同步机制同步机制同步机制用来协调诸进程间的运行，以实现进程互斥地进入自己的临界区。同步机制可以用软件方法，也可以用硬件方法。同步机制应遵循的规则：（1）空闲让进空
42、闲让进：无进程处于临界区内时，允许一个进程进入临界区；（2）忙则等待忙则等待：已有进程进入临界区时，其他欲进入进程必须等待；（3）有限等待有限等待：对要求访问临界区的进程，应保证在有限的时间内使其进入，以免陷入“死等”状态。那么，当一进程离开临界区时，若发现有进程正在等待进入临界区，则要唤醒这些进程。（4）让权等待让权等待：当进程不能进入临界区时，应立即释放CPU，以免进程陷入“忙等”状态。信号量机制信号量机制1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制经历了四种形式：整型信号量记录型信号量AND型信号量信号量集 整型信号量
43、(互斥信号量)最初信号量S是一个整型变量，表示资源数目，除初始化外，对信号量仅能通过两个标准的原子操作(即原语原语) wait(s)和signal(s)来访问。这两个原子操作一直被分别称为P（s）和V(s)操作。 wait(s)和signal(s)描述为：wait(s)：while s=0 do no-op s-;signal(s)： s+;存在的问题存在的问题：在wait操作中，只要是信号量Svalue-; s-value-; /表示进程请求一个单位的资源表示进程请求一个单位的资源 if (s-valuevaluelist) ; -list) ; /若资源分配完毕，就调用若资源分配完毕，就调
44、用blockblock原语自我阻塞，放弃处理机，并插入到信号量链表原语自我阻塞，放弃处理机，并插入到信号量链表s-lists-list中中 /遵循遵循“让权等待让权等待”准则，此时准则，此时s-values-value的绝对值表示在该信号量链的绝对值表示在该信号量链表中已阻塞进程的数目。表中已阻塞进程的数目。signal (semaphore signal (semaphore * *s)s) s-value +; s-value +; /表示执行进程释放一个单位的资源表示执行进程释放一个单位的资源 if (s-valuevaluelist) ; -list) ; /若还有等待资源的进程若还有
45、等待资源的进程被阻塞，则调用被阻塞，则调用wakeupwakeup原语，将原语，将s-lists-list链表中的第一个等待进程唤醒链表中的第一个等待进程唤醒。 /若若s-values-value的初值为的初值为1 1，表明只允许一个进程访问临界资源，此时，表明只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。的信号量转化为互斥信号量，用于进程互斥。记录型信号量在有些场合下，各进程之间要共享两个或多个共享资源在有些场合下，各进程之间要共享两个或多个共享资源( (各进程各进程一次请求两种或多种共享资源一次请求两种或多种共享资源) )后，方能执行其任务。后，方能执行其任务。假
46、定现有进程假定现有进程A A和和B B，都要访问共享数据，都要访问共享数据D D和和E(E(临界资源临界资源) )。因此。因此，为，为D D和和E E分别设置用于互斥的信号量分别设置用于互斥的信号量DmutexDmutex和和EmutexEmutex，并令它们的，并令它们的初值为初值为1 1。进程。进程A A和和B B中都包含两个对中都包含两个对DmutexDmutex和和EmutexEmutex的操作，即：的操作，即： Process A Process BProcess A Process B wait( wait(DmutexDmutex); wait(); wait(EmutexEmu
47、tex);); wait( wait(EmutexEmutex);); wait(wait(DmutexDmutex);); 若进程若进程A A和和B B 按下述次序交替执行按下述次序交替执行waitwait操作：操作：Process AProcess A： wait(wait(DmutexDmutex); ); DmutexDmutex0 0Process BProcess B： wait(wait(EmutexEmutex); ); EmutexEmutex0 0Process AProcess A： wait(wait(EmutexEmutex); ); EmutexEmutex-1-1
48、A A阻塞阻塞Process BProcess B： wait(wait(DmutexDmutex); ); DmutexDmutex-1-1B B阻塞阻塞进程进程A A和和B B处于处于僵持状态僵持状态。在无外界干预的情况下，两者都无法。在无外界干预的情况下，两者都无法从此状态中解脱出来。称此时的进程从此状态中解脱出来。称此时的进程A A和和B B已进入已进入死锁状态死锁状态。显然，当。显然，当进程同时要求的共享资源越多，发生死锁的可能性越大。进程同时要求的共享资源越多，发生死锁的可能性越大。ANDAND型信号型信号量机制量机制可以解决可以解决诸进程一次请求两个或多个共享资源诸进程一次请求两
49、个或多个共享资源的问题。的问题。AND型信号量AND型信号量 AND同步机制的基本思想同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它。也即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。 AND同步机制的做法同步机制的做法：在wait操作中，增加一个“AND”条件，故称为AND同步，或称为同时wait操作(Simultaneous wait,Swait)。Swait(S1, S2, , Sn) if Si1 and and Sn1
50、 then for (i=1;i=n;i+) Si-; /表示进程请求表示进程请求n种资源，每种资源一个种资源，每种资源一个 break; else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endifSsignal(S1, S2, , Sn) for (i=1;i=n;i+) Si+; Remove all the
