操作系统原理：第02章 进程管理

2022/11/19第二章进程管理第二章

进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程

2.1进程的基本概念进程的概念是操作系统中最基本、最重要的概念。它是在多道程序系统出现后，为了刻划系统内部出现的情况，描述系统内部各作业的活动规律而引进的一个新的概念2.1.1程序的顺序执行及特征1.程序的顺序执行一个复杂的程序一般均含若干个程序段，并按一定先后顺序执行，每个操作必须在下一个操作开始之前结束。也即仅当前一个操作结束之后，后继操作才开始执行，此即程序的顺序执行性。

2.1.1程序的顺序执行及特征例如一般程序包括输入(I)、计算(C)、输出(P)三部分，而计算须在输入完成后方可开始，而输出须在计算完成后才能进行。I1C1P1I2C2P21.程序的顺序执行对一个程序段中的多条语句来说，也有一个执行顺序问题，例如对于下述三条语句的程序段:S1：a:=x+yS2：b:=a-5S3：c:=b+1

如下图，语句S2必须在a被赋值后才能执行；S3也只能在b被赋值后才能执行。S1S2S32.程序的顺序执行的特征顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行；封闭性：程序一旦开始执行，其执行结果不受外界因素影响。可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，将获得相同的结果。2.1.2.前趋图前趋图：用于描述一个程序的各部分（程序段或语句）间的执行顺序关系，或者是一个大的计算的各个子任务间的因果关系。是一个有向无循环图，每个结点用于表示一条语句、一个程序段或一个进程；结点间的有向边表示两个结点之间存在的偏序或前趋关系

“→”。2.1.2.前趋图结点间的有向边表示两个结点之间存在的偏序(Partial_Order)或前趋关系(Precedence_Relation)“→”＝{(Pi,Pj)|在Pj开始前Pi必须完成}，如果(Pi,Pj)∈→，可写成Pi→Pj，Pi是Pj的直接前趋，Pj是Pi的直接后继。每个结点还具有一个重量。2.1.2.前趋图2.1.2.前趋图该前趋图，存在下面的前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；或表示为：Ｐ={P1,P2,P3,P4,P5,P6,P7,P8,P9}

→={(P1,P2),(P1,P3),(P1,P4),

(P2,P5),(P3,P5),(P4,P6),

(P4,P7),(P5,P8),(P6,P8),

(P7,P9),(P8,P9)}例：下述几条语句的程序段画出前趋图P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P3→P6，P4→P6，2.1.2.前趋图2.1.3程序并发执行及特征并发环境：

在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的，就称这几个程序是并发执行的。1.程序的并发执行在对一批程序进行处理时，可以并发执行。例如，输入、计算、打印三个程序对一批作业进行处理时前趋关系图如下：在该例中存在下述前趋关系：

Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1在Pi-1和Ci以及Ii+1之间，可以并发执行。1.程序的并发执行对于具有下述四条语句的程序段：

S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b1.程序的并发执行假设有一个程序由S0～Sn+1个语句，其中S1～Sn语句是并发执行的，程序如下：

S0;cobeginS1;S2;S3;...;SNcoend;Sn+1;三个并发执行程序的誊抄假设有两个缓冲区，每个缓冲区只存放一个字符。

get程序负责从输入序列f中读取字符并送到缓冲区s中;copy程序把缓冲区s中的数据复制到缓冲区t中去;put程序从缓冲区t中取出数据打印。getcopyputfstg输入f输出g{If(f不为空）

{Get(s,f)while(誊写未完成）

{t=scobeginput(t,g)Get(s,f)coend}}}cpcgpcgpg并行环境下程序间的制约关系与时间有关的错误假定f系列中有记录

f=(R1,R2,...,Rn)g=()在誊抄完成后：

f=()g=(R1,R2,...,Rn)算法中的：copy≡t=sput≡put(t,g)get≡get(s,f)与时间有关的错误若程序错写成：while(誊抄未完成）{cobegincopy;put;get;coend}初始状态：

f=(R1,R2,...,Rn)s=()t=()g=()首先执行了get(s,f)f=(R1,R2,...,Rn)s=R1,t=(),g=()copy,put,get三个程序段并发执行，就有六种组合：1、copy;put;get导致结果：g=(R1,R2)2、copy;get;put导致结果：g=(R1,R2)3、put;copy;get导致结果：g=(R1,R1)4、put;get;copy导致结果：g=(R1,R1)5、get;copy;put导致结果：g=(R1,R3)6、get;put;copy导致结果：g=(R1,R1)这就是与时间有关的错误。与时间有关的错误2.程序的并发执行的特征1)间断性:程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。

2)失去封闭性:程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。

3)不可再现性:程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。2.程序的并发执行的特征并发程序A和B，共享变量n，程序A做n=n+1操作；程序B执行print（n）操作。两种情况：（假设当前变量n的值为100）执行方式1：

A：n=n+1；

B：print（n）；结果：B打印n的值为101。执行方式2：

B：print（n）；

A：n=n+1；结果：B打印n的值为100。2.1.4进程的特征与状态在多道程序环境下，程序具有了并行、制约和动态的特征，程序概念已刻划不清系统的这种并行情况，反映不了它们的活动规律和状态变化。为了动态地看待操作系统，则以进程作为资源分配和独立运行的基本单位，从进程观点来研究操作系统，操作系统所具有的所有特征也都是基于进程而形成的。1.进程的特征和定义进程：是指在系统中能独立运行并作为资源分配的基本单位，是一个活动实体。也可以说，进程是程序在数据集合上的一次运行过程，是系统进行资源分配和调度的基本单位。进程是一个动态的概念，是一个运行过程。它不同于程序，但又依赖于程序。对不同的数据集合，依照一定的程序运行处理的每一个过程是每个不同的进程。在系统中同时有多个进程存在，但归纳起来有两大类：1、系统进程系统进程起着资源管理和控制的作用。

或者：执行操作系统核心代码的进程。2、用户进程执行用户程序的进程。一般来讲，在管态下执行的进程称为系统进程；在目态下执行的进程称为用户进程。进程的特征结构特征：为了控制和管理进程，系统为每个进程设立一个进程控制块－PCB。动态性：进程的实质是程序的一次执行过程， 进程是动态产生，动态消亡的，进程在其生命周期内，在三种基本状态之间转换并发性：任何进程都可以同其他进程一起向前推进独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位；异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进进程与程序的区别程序是静态的，进程是动态的;进程更能真实地描述并发,而程序不能;一个程序可对应多个进程，反之亦然;程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的；进程是系统分配调度的独立单位，能与其他进程并发执行;进程是由程序、数据和进程控制块组成进程具有创建其他进程的功能，而程序没有

2.进程的三种基本状态在进程运行过程中，由于系统中多个进程的并发运行及相互制约的结果，使得进程的状态不断发生变化。进程在系统中的活动规律是：执行暂停执行进程的三种基本状态：

运行状态就绪状态

阻塞状态

2.进程的三种基本状态1)就绪(Ready)状态

当进程已经分配到除CPU以外的所有必要的资源后，只要能获得处理机，就可以立即执行。这时的进程的状态称为就绪状态2)执行状态(Running)（运行状态）

指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程处于执行状态。（在多处理机中，可能有多个进程处于执行状态）

2.进程的三种基本状态3)阻塞状态(Block)

进程因发生某个事件而暂停执行时的状态（如：请求I/O、申请缓冲空间等），也就是说，进程受到阻塞，所以称这种暂停状态为阻塞状态，有时也称“等待”状态或“睡眠”状态。进程的状态及其转换运行就绪等待

2.进程的三种基本状态进程状态转换条件在进程运行过程中，由于自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换：就绪-->运行调度程序选择一个新的进程运行运行-->就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态进程状态转换条件运行-->阻塞当一进程必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O且必须等待结果等待某一进程提供输入(IPC)等待-->就绪当所等待的事件发生时3.挂起状态在某些系统中，为了更好地管理和调度进程及适应系统的功能目标，引入了挂起状态。1)引入挂起状态的原因(1)终端用户的需要(2)父进程请求。(3)负荷调节的需要。(4)操作系统的需要。3.挂起状态具有挂起和解挂功能的系统进程状态中，新增加了两个状态：挂起就绪（ReadySuspend）挂起阻塞（BlockedSuspend）为了易于区分，将原来的就绪状态和阻塞状态分别称为：活动就绪（ReadyActive）活动阻塞（BlockedActive）2)进程状态的转换在引入挂起状态后，又将增加从挂起状态到非挂起状态的转换。或者相反，可以有以下几种情况：

(1)活动就绪静止就绪

(2)活动阻塞静止阻塞

(3)静止就绪活动就绪

(4)静止阻塞活动阻塞3.挂起状态执行静止就绪活动阻塞活动就绪静止阻塞挂起释放激活挂起激活挂起释放请求I/O调度创建状态终止状态创建一个进程一般要通过两个步骤：首先，为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列之中。4．创建状态和终止状态创建状态OS已完成为创建一进程所必要的工作已构造了进程标识符已创建了管理进程所需的表格但还没有允许执行该进程(尚未同意)

因为资源有限终止状态终止状态的进程不再有执行资格进程的终止也要通过两个步骤：首先等待操作系统进行善后处理；然后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。五态模型

引进创建和终止状态后，在进程状态转换时，需要增加考虑下面的几种情况。(1)NULL→创建：(2)创建→活动就绪(3)创建→静止就绪(4)执行→终止七态模型

2.1.5进程控制块（PCB）系统为了管理进程设置的一个专门的数据结构，用来记录进程的外部特征，描述进程的变化过程。进程的静态描述(进程映像)：由三部分组成1)

PCB(ProcessControlBlock)2)程序段3)数据段用于描述进程情况及控制进程运行所需的全部信息。是进程中能被进程调度程序在CPU上执行的程序代码段。一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行后产生的中间或最终数据。1．进程控制块的作用系统利用PCB来控制和管理进程，进程控制块既能标识进程的存在，又能刻画出进程的动态特征，所以PCB是系统感知进程存在的唯一标志进程与PCB是一一对应的当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。2.进程控制块中的信息1)进程标识符进程标识符用于惟一地标识一个进程。内部标识符外部标识符家族联系2.进程控制块中的信息

2)处理机状态说明进程当前所处的状态。处理机状态信息主要是由处理机的各种寄存器中的内容组成的。通用寄存器指令计数器程序状态字PSW

用户栈指针2.进程控制块中的信息3)进程调度信息存放一些与进程调度和进程对换有关的信息。①进程状态②进程优先级③进程调度所需的其它信息④事件2.进程控制块中的信息4)进程控制信息①程序和数据的地址；②进程同步和通信机制；③资源清单；④链接指针。

3.进程控制块的组织方式为了方便进程的调度和管理，需要将各进程的进程控制块用适当的方法组织起来，常用的组织方式有两种：链接方式索引方式执行指针就绪队列指针阻塞队列指针空闲队列指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB94308

7900……PCB链接队列示意图(a)阻塞队列分开PCB5执行队列

就绪队列………

阻塞队列1

阻塞队列2………队列表头PCB8PCB1PCB4PCB3PCB2PCB7…(b)阻塞队列不分开

就绪队列

阻塞队列…………PCB1PCB7PCB2PCB3………PCB8PCB4…执行指针就绪索引表等待索引表PCB3PCB4PCB5PCB7PCB6PCB2PCB1按索引方式组织PCB就绪索引表等待索引表2.2进程控制进程的创建、撤销以及完成进程各状态之间的相互转换。这些操作都要对应地执行一个特殊的程序段（原语），同时系统也通过系统调用给用户提供进程控制的功能。进程控制原语：进程创建、进程终止、进程阻塞、进程唤醒、进程挂起、进程激活。原语(Primitive)原语：是机器指令的延伸，由若干条指令构成的，系统状态下执行的某些具有特定功能的程序段。原语操作：一个操作中的动作要么全做，要么全不做。2.2.1进程的创建1进程图进程图是用来描述进程家族关系的有向树。结点代表进程。一棵树表示一个家族，根结点为该家族的祖先(Ancestor)。ABCDMEIJHGFLK进程树1.进程图关系子进程可以继承父进程的所有资源子进程撤销时，向父进程归还资源父进程撤销时，所有子进程也被撤销进程图和前趋图之间的差异前趋图描述的是任务(或进程)之间的前趋关系；只有在前趋进程完成后，其后继进程才能运行；进程图描述的是进程家族关系，创建者和被创建者可以并发执行，也可以父进程等待其所有的子进程结束后再执行，这完全取决于创建原语和创建者的需要。2引起创建进程的事件1.用户登录：为终端用户建立一进程2.作业调度：（不是进程调度）为被调度的作业建立进程3.提供服务：如要打印时建立打印进程4.应用请求：由应用程序建立多个进程3进程的创建（creat）操作系统发现要求创建新进程的事件后，调用进程创建原语Creat()创建新进程。。创建原语Creat()功能：创建一个具有指定标识符进程入口信息：进程标识符、优先级、进程开始地址、初始CPU状态、资源清单等。3进程的创建（creat）创建过程：

1.申请空白PCB（一个系统的PCB是有限的）2.为新进程分配资源3.初始化PCB4.将新进程插入就绪队列。入口查PCB链表有同名?将PCB入就绪队列将PCB入总链将入口信息填入PCB相应项向系统申请一个空的PCB结构返回出错有无有空PCB?出错无有2.2.2进程的终止1．引起进程终止的事件正常结束

表示进程已经运行完成的指示。如Halt、logoff2)异常结束 越界错误、保护错、非法指令、特权指令错、运行超时等3)外界干预操作员或操作系统干预父进程请求父进程中止2进程终止过程进程的终止过程（1）检查进程状态；（2）执行态――>终止，且置调度标志为真。（3）有无子孙需终止。（4）归还资源给其父进程或系统。（5）从PCB队列中移出PCB.

入口返回查进程链表或进程家族有此PCB吗？该PCB有子进程吗？释放该进程所占有的资源释放该PCB结构本身出错处理有无有无2.2.3进程的阻塞1.引起进程阻塞和唤醒的事件请求系统服务：而得不到满足时，如问系统请求打印。启动某种操作：如该操作和请求该操作的进程需同步运行（即非异步操作）。新数据尚未到达：如进程A写，进程B读，则A未写，完B不能读。无新工作可做。2．进程阻塞过程调block原语停止执行，修改PCB入阻塞队列（一个或多个）转调度程序。是进程自身的一种主动行为入口将现行进程的CPU信息送该进程的PCB现场保护区置该进程状态为“等待”把该进程插入相应的等待队列转进程调度阻塞原语执行过程3．进程唤醒过程进程所等待的事件发生时，则调用唤醒原语将等待该事件的进程唤醒。唤醒进程有两种方法：（1）由系统进程唤醒。（2）由事件发生进程唤醒。一个处于阻塞状态的进程不可能自己唤醒自己。3．进程唤醒过程

唤醒原语执行的过程首先把被阻塞进程从等待该事件的阻塞队列中移出，将其PCB中的阻塞状态改为就绪状态，然后把该进程插入到就绪队列中。阻塞原语和唤醒原语是一对作用刚好相反的原语。入口将被唤醒进程从相应的等待队列中移出将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列转进程调度唤醒原语执行过程2.2.4进程的挂起与激活1.进程的挂起当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程。挂起的实现方式有多种：（1）把发出挂起原语的进程自身挂起。（2）挂起具有指定标识名的进程。（3）把某进程及其全部或部分（例如具有指定优先数的）子孙进程挂起。1.进程的挂起挂起原语的主要操作过程首先检查该进程的状态（1）若状态为就绪，则改为挂起就绪；（2）若状态为阻塞，则改为挂起阻塞；（3）若状态为执行，则中断处理机，把状态改为挂起就绪。被挂起进程PCB的非常驻部分要交换到磁盘交换区2．进程的激活过程进程的激活过程:当发生激活事件后，系统利用激活原语Active()将指定进程激活。激活原语先将进程从外存调入内存，然后检查进程的状态。静止就绪活动就绪静止阻塞活动阻塞2.3进程的同步多道程序环境下由于资源共享或进程合作，进程在活动中会相互制约所有进程都是相互独立的进程以异步方式并发执行直接制约：相互制约关系源于进程合作，表现为：进程---进程（同步）间接制约：相互制约关系源于资源共享,表现为：进程---资源---进程（互斥）1．两种形式的制约关系用进程互斥与同步机制来协调两种制约关系。2.3进程的同步进程同步的主要任务：并发进程在执行次序上的进行协调，以达到有效的资源共享和相互合作，使程序执行有可再现性。同步是进程间共同完成一项任务时直接发生相互作用的关系同步举例同步进程间具有合作关系在执行时间上必须按一定的顺序协调进行互斥互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系互斥进程彼此在逻辑上是完全无关的它们的运行不具有时间次序的特征打印机编号分配标志用户名用户定义的设备名01LiLPT11021MengLPT2打印机分配表

假定进程P1负责为用户作业分配打印机，进程P2负责释放打印机，上图为某时刻打印机的使用情况。互斥举例P1：分配过程检查标志位，找0；将01；将用户名和打印机名填入表格。P2：释放过程找用户名与打印机名与要释放的名字相同切标志位为1的表项；将10；将用户名和打印机名清空。具体操作互斥举例P1、P2顺序执行时，一切正常！当P1、P2交替执行时（B先做前2步，A做完3步，B再做第3步），可能会出现以下现象：打印机编号分配标志用户名用户定义的设备名01

1021MengLPT22.临界资源系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量硬临界资源：打印机、输入机、磁带机等软临界资源：多个进程共享的变量、数据、表格、队列等例1：有两个进程A、B，它们共享一个变量x，且两个进程按以下方式对变量x进行访问和修改：A：R1=x；

R1=R1+1；

x=R1B：R2=x；

R2=R2+1；

x=R22.临界资源其中：R1和R2为处理机中的两个寄存器。这里，两个进程各自对x作了加1操作，相应地，x增加了2。若按A、B交替执行：A：R1=x；B：R2=x；A：R1=R1+1；

x=R1B：R2=R2+1；

x=R2虽然两个进程也各自对x作了加1操作，但x却只增加了1。为了防止这种错误的发生，变量x应按临界资源处理，即让两个进程顺序使用变量x。2.临界资源例2：生产者—消费者问题：

有一群生产者进程生产产品供给消费者进程消费，为使两者并发执行，在两者之间设置具有n个缓冲区的缓冲池，生产者进程所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区中取走产品去消费。

生产者进程和消费者进程都以异步方式运行，但它们之间必须保持同步。2.临界资源例：生产者—消费者问题环型缓冲池2.临界资源2.临界资源生产者进程和消费者进程共享的变量：Varn,integer;typeitem=……;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;初始值为0，放入产品使其加1，取出产品使其减1注意：缓冲池组织为循环缓冲，输入指针加1表示为in:=(in+1)modn，输出指针加1表示为out:=(out+1)modn，当(in+1)modn=out时表示缓冲池满，in=out表示缓冲池空。用数组表示具有n个缓冲区的缓冲池输入指针in指示下一个可投放产品的缓冲区，输出指针out指示下一个可从中获取产品的缓冲区，初值均为0。Producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=in+1modn;counter:=counter+1;untilfalse;Consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=out+1modn;counter:=counter-1;consumertheiteminnextc;untilfalse;空操作指令重复的测试条件2.临界资源2.临界资源并发执行出错—counter生产者对它加1，消费者对它减1机器语言实现：register1:=counter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register2-1;counter:=register2;register1:=counter;(register1=5)register1:=register1+1;(register1=6)register2:=counter;(register2=5)register2:=register2-1;(register2=4)counter:=register1;(counter=6)counter:=register2;(counter=4)counter应当为5解决方法：把counter作为临界资源，对其互斥访问临界区(互斥区)：每个进程中访问临界资源的那段程序段称为临界区(criticalsection)。3．临界区对欲访问的临界资源进行检查，………………进入区若此刻未被访问，设正在访问的标志访问临界资源………………临界区将正在访问的标志恢复为未被访问的标志……退出区其余部分………………剩余区repeat

entrysection

criticalsection

exitsection

remaindersectionuntilfalse3．临界区

4．同步机制应遵循的规则空闲让进忙则等待有限等待让权等待2.3.2信号量机制人们从交叉路口的交通管理中使用的信号灯上得到启发，通过信号灯的状态(或颜色)实现交通管理。操作系统中引进信号灯(通常人们叫信号量)的概念既可用来解决同步问题，也可解决互斥问题。1965年荷兰Dijkstra提出的进程同步工具2.3.2信号量机制信号量：除初始化外,仅能由同步原语对其进行操作的整型变量。同步原语：

P/wait操作；

V/signal操作；信号量机制目前已经发展成多种类型，主要有：整型、记录型、AND型和信号量集机制。1．整型信号量整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。Wait(S)和signal(S)操作可描述为：

wait(S)：

whileS<=0dono-op；

S:=S-1；

signal(S)：

S:=S+1；信号量的物理意义

wait原语和signal原语的执行都必须是一个不可被中断的整体。(1)物理意义：S>0时，S为可用资源量；S=0时，可用资源量正好用完；S<0时，|S|为等待资源的队列长度，即还欠资源数(在信号量上等待的进程数)例：S=4S=0S=–2P1

P2

wait(S)：表示请求分配一个资源

S>0立即可得S0要排队(2)wait(S)Lock(S)S为二元信号量signal(S)unlock(S)signal(S)：表示释放资源信号量的初值应该大于等于0对应2．记录型信号量记录型信号量：一般是由两个成员组成的数据结构，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L。整型信号量未遵循“让权等待”原则，导致“忙等”。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。信号量是一种数据结构一般由两个成员组成：数值指针2．记录型信号量4∧PCB2∧PCB1指针-2指针有四个资源可用！有两个进程等待使用资源！2．记录型信号量typesemaphore=record

value:integer；

L:listofprocess；

end记录型信号量数据结构2．记录型信号量相应地，wait(S)和signal(S)操作可描述为：（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程阻塞。procedurewait(S)

varS：semaphore；

begin

S.value:=S.value-1；

ifS.value<0thenblock(S.L)；

end2．记录型信号量（1）s值加1；（2）若相加结果大于0，进程继续执行；（3）否则，唤醒一个（或多个）等待该信号量的进程，然后本进程继续执行。proceduresignal(S)

varS:semaphore；

begin

S.value:=S.value+1；

ifS.value<=0thenwakeup(S.L)；

end2．记录型信号量3.AND型信号量前面介绍的进程互斥问题，属于多个进程共享一个临界资源。假如：两个进程A和B，共享数据D和E，为其分别设置互斥信号量Dmutex和Emutex，初值为1。ProcessA：

wait(Dmutex);wait(Emutex);ProcessB：

wait(Emutex);wait(Dmutex);ProcessA：wait(Dmutex);于是Dmutex=0ProcessB：wait(Emutex);于是Emutex=0ProcessA：wait(Emutex);于是Emutex=-1A阻塞ProcessB：wait(Dmutex);于是Dmutex=-1B阻塞设执行过程为共享的资源越多，死锁的可能越大！3.AND型信号量AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源，也不分配给它。即对临界资源的分配采取原子操作。Swait(S1,S2,…,Sn)ifS1>=1and…andSn>=1thenfori:=1tondoSi:=Si-1;endforelsePlacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor

4．信号量集在记录型信号量机制中每次只能获得或释放一个单位的临界资源。而当需要N个某类临界资源时，便要进行N次操作，低效。一般信号量集在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请。信号量Si测试值为ti要求Si>=ti；即当资源数量低于ti时，便不予分配占用值为di表示资源的申请量，即Si=Si-di对应的P、V原语格式为：

4．信号量集Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);Swait(S1,t1,d1,…,Sn,tn,dn)ifS1>=t1and…andSn>=tnthenfori:=1tondoSi:=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitOperationendifSsignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor4．信号量集一般信号量集的几种特殊情况Swait(S,d,d):表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1):表示互斥信号量Swait(S,1,0):可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）2.3.3信号量的应用

1．利用信号量实现进程互斥为该每个临界资源设置一互斥信号量mutex，并设其初始值为1将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。对同一信号量操作的wait与signal操作在进程中必须成对出现。Wait、Signal原语不能次序错误、重复或遗漏mutex的取值范围为1,0,-1,-2，……,-nSignal(mutex);criticalsectionremaindersectionWait(mutex);1．利用信号量实现进程互斥Wait、Signal原语不能次序错误、重复或遗漏Varmutex:semaphore:=1；

begin

parbegin

process1:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remainderseetion

untilfalse；

end1．利用信号量实现进程互斥process2:begin

repeat

wait(mutex)；

criticalsection

signal(mutex)；

remaindersection

untilfalse；

end

parendend1．利用信号量实现进程互斥例：打印机分配表的使用问题（P87）：设互斥信号量mutex（初值为1）Pa为分配进程Pb为释放进程1．利用信号量实现进程互斥Pa：...Wait（mutex）分配打印机（读写分配表）Signal（mutex）...Pb：...Wait（mutex）释放打印机（读写分配表）Signal（mutex）...1．利用信号量实现进程互斥设有两个并发执行的进程P1和P2，P1中有语句S1，P2中有语句S2，希望在S1执行后再执行S2。使进程P1和P2共享一个公用信号量S，并赋予其初值为0。进程P1：S1；signal(S)；进程P2：wait(S)；S2；

2．利用信号量实现前趋关系S1S2S3S4S5S6

2．利用信号量实现前趋关系abcdefgVara,b,c,d,e,f,g：semaphore:=0,0,0,0,0,0,0；

begin

parbegin

beginS1；signal(a)；signal(b)；end；

beginwait(a)；S2；signal(c)；signal(d)；end；

beginwait(b)；S3；signal(e)；end；

beginwait(c)；S4；signal(f)；end；

beginwait(d)；S5；signal(g)；end；

beginwait(e)；wait(f)；wait(g)；S6；end；

parend

end2．利用信号量实现前趋关系3.利用信号量实现进程同步公共汽车司机与售票员之间的活动。司机负责开车，售票员负责开、关车门及售票，其活动如下图所示。虽然各负其责，但必须互相配合、协调活动，他们之间存在如下同步关系：3.利用信号量实现进程同步设置信号量close（同步信号量）表示车门是否关好，初值为0，表示门未关好，不允许司机启动汽车；设置信号量stop（同步信号量）表示汽车是否停稳，初值为0，表示未停稳，售票员不能开车门。3.利用信号量实现进程同步Varstop,close:Semaphore:=0,0BeginparbeginDriver():beginrepeatwait(close);//先测试车门是否关好启动汽车;

正常开车;

到站停车;signal(stop);//发送可开门信息

untilfalseend3.利用信号量实现进程同步busman():beginRepeat

关车门；

signal(close);//发送门已关的同步信息售车票；

wait(stop);//开门前先测试是否停车开车门；乘客上下车；

untilfalseendparend3.利用信号量实现进程同步2.3.4管程机制信号量机制存在下列3点不足：3、wait和signal操作的错误使用（次序错误、重复、遗漏等），编译程序和操作系统都无法发现、纠正，可导致死锁。1、criticalsection、entrysection和exitsection都由用户编写；2、信号量操作原语分散在各程序代码中，由进程来执行，系统无法有效控制、管理；2.3.4管程机制70年代初,ByE.W.Dijkstra,C.A.R.Hoare,P.B.Hansen.背景:Structuredprogramming管程的定义：管程是关于共享资源的数据结构及针对该资源的可以并发执行的一组操作。Java:synchronizedmethod1.管程定义将所有进程对某一临界资源的同步操作都集中起来，构成所谓的“秘书”进程，凡要访问该临界资源的进程，都需先报告“秘书”，由其实现诸进程的同步。能同步进程和改变管程中的数据，是进程间同步的机制，它保证进程互斥地使用临界资源。1.管程定义管程的四个组成部分：管程的名称：数据结构说明：一组局部于管程的共享变量过程：对共享变量进行操作的一组原语过程（程序代码）初始化代码：对共享变量进行初始化的代码管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来。图2-13管程的示意图1.管程定义

typemonitor_name=MONITOR；<共享变量说明>；define<(能被其他模块引用的)过程名列表>；use<(要调用的本模块外定义的)过程名列表>；procedure<过程名>(<形式参数表>)；begin

end;……管程的语法描述如下：1.管程定义function<函数名>(<形式参数表>)：值类型；begin

end；

begin<管程的局部数据初始化语句序列>；end……1.管程定义

模块化:一个管程是一个基本程序单位，可以单独编译

抽象数据类型:管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码

信息掩蔽:管程是半透明的，管程中的内部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的。管程的三个主要的特性管程和进程的比较主要体现在以下几个方面：(1)数据结构；(2)操作；(3)目的；(4)工作方式；(5)并发；(6)动态性。2．条件变量管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作；为此在管程内部可以说明和使用一种特殊类型的变量----条件变量。每个条件变量表示一种等待原因，并不取具体数值－－相当于每个原因对应一个队列。urgentqueue2．条件变量Varx，y：condition。①x.wait：如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权;执行此操作的进程（线程）进入x链尾。x.signal：如c链空，相当空操作。否则唤醒第一个，执行此操作的进程（线程）进入紧急队列。

当一个进入管程的进程执行唤醒操作时（如Ｐ唤醒Ｑ），管程中便存在两个同时处于活动状态的进程。处理方法有三种：2．条件变量

Ｐ等待Ｑ继续，直到Ｑ退出或等待Ｑ等待Ｐ继续，直到Ｐ等待或退出规定唤醒为管程中最后一个可执行的操作2.4经典进程的同步问题三个经典的进程同步问题：1、生产者--消费者问题；

(TheProducer-ConsumerProblem)2、哲学家进餐问题；

(TheDiningPhilosophersProblem)3、读者--写者问题；

(TheRead-WriteProblem)2.4.1生产者—消费者问题问题：有若干生产者、消费者，共享使用n个缓冲区组成的缓冲池：

生产者：每次产生一个数据，放入一个空缓冲区。若无空缓冲区，则阻塞；

消费者：每次从有数据的缓冲区取一个数据消费。若所有缓冲区皆为空，则阻塞；01……k-1箱子，容量kB:Array[0..k-1]Ofitem生产者消费者生产物品放入B中B中取物品消费之2.4.1生产者—消费者问题InOut分析：同步：若所有缓冲区皆空，消费者等待生产者生产；若所有缓冲区皆满，生产者等待消费者消费。1.利用记录型信号量解决生产者—消费者问题定义变量：itemTYPEbuffer[n];表示各缓冲区；

integerin=0,out=0;生产、消费缓冲区指针；设置同步信号量：

empty表示现有空缓冲区数，初值=nfull表示现有满缓冲区数，初值=0

互斥：生产者、消费者对缓冲池的操作必须互斥。设置互斥信号量mutex，初值=1

1.利用记录型信号量解决生产者—消费者问题Varmutex，empty，full:semaphore:=1,n,0；

buffer:array[0，…，n-1]ofitem；

in，out:integer:=0，0；

begin

parbegin

proceducer:begin

repeat

produceranitemnextp；

wait(empty)；

wait(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

signal(mutex)；

signal(full)；

untilfalse；

end

consumer:begin

repeat

wait(full)；

wait(mutex)；

nextc:=buffer(out)；

out:=(out+1)modn；

signal(mutex)；

signal(empty)；

consumertheiteminnextc；

untilfalse；

end

parend

end1.利用记录型信号量解决生产者—消费者问题1.如果对调两个wait原语，当按如下顺序执行时：1.利用记录型信号量解决生产者—消费者问题消费者:wait(mutex);/*执行语句后mutex为0*/消费者:wait(full);/*full为-1，消费者等待*/生产者:wait(empty);/*empty为k-1*/生产者:wait(mutex);/*mutex为-1，生产者等待*/2.如果对调两个signal原语呢？结果：导致死锁。所以wait原语的次序不能颠倒!3.在每个程序中的多个wait操作顺序不能颠倒，应先执行对资源信号量wait操作，然后再执行对互斥信号量wait操作。注意1.利用记录型信号量解决生产者—消费者问题1.在每个程序中用于实现互斥的wait和signal必须成对地出现；2.对资源信号量的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。2．利用AND信号量解决生产者—消费者问题在上面的解决方法中，进程中的两个wait原语的位置不能颠倒，否则，可能导致死锁，使用AND信号量机制来实现，将对信号量empty与mutex的两个wait操作用一个swait(empty,mutex)操作来实现，将对信号量full与mutex的两个wait操作用一个swait(full,mutex)操作来实现，就可以避免死锁的产生。实现如下：2．利用AND信号量解决生产者—消费者问题Varmutex，empty，full:semaphore:=1，n，0；

buffer:array[0，…，n-1]ofitem；

inout:integer:=0，0；

begin

parbegin

producer:begin

repeat

produceaniteminnextp；

Swait(empty，mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

Ssignal(mutex，full)；

untilfalse；

end…… consumer:begin

repeat

Swait(full，mutex)；

Nextc:=buffer(out)；

Out:=(out+1)modn；

Ssignal(mutex，empty)；

consumertheiteminnextc；

untilfalse；

end

parend

end2．利用AND信号量解决生产者—消费者问题3．利用管程解决生产者—消费者问题建立一个管程ProclucerConsumer，包括两个过程：(1)put(item)

。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目。(2)get(item)

。消费者利用该过程从缓冲池中取出一个产品。typeproducer-consumer=monitor

Varin,out,count:integer；

buffer:array[0,…,n-1]ofitem；

notfull，notempty:condition；

procedureentryput(item)

begin

ifcount>=nthennotfull.wait；

buffer(in):=nextp；

in:=(in+1)modn；

count:=count+1；

ifnotempty.queuethennotempty.signal；

end3．利用管程解决生产者—消费者问题 procedureentryget(item)

begin

ifcount<=0thennotempty.wait；

nextc:=buffer(out)；

out:=(out+1)modn；

count:=count-1；

ifnotfull.quenethennotfull.signal；

end

beginin:=out:=0；

count:=0end3．利用管程解决生产者—消费者问题

producer:begin

repeat

produceaniteminnextp；

PC.put(item)；

untilfalse；

end

consumer:begin

repeat

PC.get(item)；

consumetheiteminnextc；

untilfalse；

end生产者和消费者可描述为：3．利用管程解决生产者—消费者问题2.4.2哲学家进餐问题问题：五个哲学家同座一张圆桌，每人一个碗，左右各一只筷子；其习惯为：思考-吃饭-思考......；只有拿到左右两只筷子才开始吃饭，吃完后继续思考......。哲学家进餐问题

哲学家思考问题时，并不影响他人；只有当他就完餐后才放下筷子重新开始思考问题。只有当哲学家饥饿的时候，他才试图拿起左、右两根筷子；如果筷子已在他人手上，则需等待；只有当饥饿的哲学家同时拿到了两根筷子，他才可以开始就餐；2.4.2哲学家进餐问题思考思考思考思考思考准备进餐进餐准备进餐进餐分析1．利用记录型信号量解决哲学家进餐问题放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组：Varchopstick:array[0，…，4]ofsemaphore所有信号量均被初始化为1，第i位哲学家的活动可描述为：

repeat

wait(chopstick[i])；

wait(chopstick[(i+1)mod5])；

eat；

signal(chopstick[i])；

signal(chopstick[(i+1)mod5])；

think；

untilfalse；………1．利用记录型信号量解决哲学家进餐问题哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子分析：假设5个哲学家同时拿起他们各自左边（右边）筷子，就会使五个信号量chopstick均为0；那么，他们都只能拿到一支筷子而等待右边的人放下筷子，谁也不能拿到一双筷子来吃饭，这种等待状态将一直保持下去，产生了死锁。1．利用记录型信号量解决哲学家进餐问题哲学家进餐问题分析死锁思考思考思考思考思考准备进餐准备进餐准备进餐准备进餐准备进餐思考Wait（left_stick）Wait（right_stick)Signal（left_stick）eatSignal（right_stick)解决方法：1.至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。---限制并发执行的进程数2.仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。---采用信号量集3.规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。---保证总会有一个哲学家能同时获得两只筷子而进餐2.4.2哲学家进餐问题2315423154方法3第一种方法来解决实现没有死锁的哲学家问题：至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用完时能放下他用过的两支筷子，从而使其他的哲学家能够进餐。在实现时只需增加一个限定就餐人数的信号量num（互斥信号量），其初值设为4。任何哲学家拿筷子前先检测num，算法如下：2.4.2哲学家进餐问题Varnum:semaphore:=4;chopstick:array(0,…4)ofemaphore:=(1，1，1，1，1)；processirepeatthink;wait(num); wait(chopstick［i］);wait(chopstick［(i+1)%5］);…eat;…signal(num);signal(chopstick［i］);signal(chopstick［(i+1)%5］);…Untilefalse2．利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Varchopsiickarrayofsemaphore:=(1,1,1,1,1)；

processi

repeat

think；

Sswait(chopstick[(i+1)mod5]，chopstick[i])；

eat；

Ssignat(chopstick[(i+1)mod5]，chopstick[i])；

untilfalse；2．利用AND信号量机制解决哲学家进餐问题2.4.3读者—写者问题描述：在计算机系统中，读数据(文件)及修改、写数据(文件)是经常的，并要求对数据(文件、记录)进行共享。也就是说，多个进程同时读／写(共享数据)。而对于读／写数据，会有几种情况发生：1)同时读，不会发生副作用。2)有一个写，其它读、写，会产生副作用。3)读时，出现写，也会产生副作用。2.4.3读者—写者问题1．利用记录型信号量解决读者—写者问题分析：2、由于允许有多个读者，为了解目前的读者数量，设置一读者计数变量readcount,初值为0。多个读者都对readcount进行操作，须设置对其操作的互斥信号量Rmutex，初值为1.1、为保证写者进程与其它进程互斥访问共享对象，设置互斥信号量Wmutex，初值为1：

读者—写者问题可描述如下:Varrmutex，wmutex:semaphore:=1,1；

Readcount:integer:=0；

begin

parbegin

Reader:begin

repeat

wait(rmutex)；

ifreadcount=0thenwait(wmutex)；

Readcount:=Readcount+1；

signal(rmutex)；

performreadoperation；……1．利用记录型信号量解决读者—写者问题

wait(rmutex)；