2第二章进程管理(2)

1第二章进程管理（2）张琦[e-mail]2内容2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5进程通信2.6线程3本章节要讨论的问题如何控制和协调并发进程异步执行的时序？进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作。进程的同步机制42.3进程同步2.3.1进程同步的基本概念1.两种形式的制约关系当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种制约关系。(1)间接相互制约关系---同处于一个系统的进程，通常都共享着某种系统资源。(2)直接相互制约关系---主要源于进程间的合作。52.3进程同步2.临界资源(CriticalResource)凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。3.临界区(CriticalSection)把每个进程中访问临界资源的那段代码称为临界区。repeatentrysectioncriticalsection;exitsectionremaindersection;untilfalse;进入区---申请进入临界区临界区---访问临界资源退出区---退出对临界资源的访问剩留区---进程的其他代码62.3进程同步4.同步机制应遵循的规则空闲让进无进程处于临界区内时，可让一个申请进入该临界区的进程进入。忙则等待临界区内有进程时，申请进入临界区的进程必须等待。有限等待进程进入临界区的请求，必须在有限的时间内满足。让权等待等待进入临界区的进程，必须立即释放CPU。72.3进程同步2.3.2信号量机制1.什么是信号量(semaphore)并发进程间的相互制约关系从本质上说是由于争夺和共享资源而产生的。将资源抽象为信号量，在信号量基础上引入同步操作原语：P操作、V操作。2.整形信号量整形信号量用于表示资源数目，用S表示。除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wait(S):whileS≤0dono-opS∶=S-1;signal(S):S∶=S+1;P操作：申请资源V操作：释放资源82.3进程同步3.记录型信号量在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。其中：信号量值—表示某种资源的数量。等待队列指针—当信号量值为负时，表示该类资源已分配完，等待该类资源的进程排在等待队列中。L为指向该信号量等待队列的指针。记录型信号量是由于它采用了记录型的数据结构而得名的。上述两个数据项可描述为：92.3进程同步typesemaphore=recordvalue:integer;L:listofprocess;endP操作(wait原语)每执行一次P操作，即申请分配一个单位的资源。P(S)—表示对信号量S进行P操作。①S.value:=S.value–1②若S.value≥0进程继续执行。若S.value0进程阻塞，并进入等待队列（L）。102.3进程同步V操作(signal原语)V(S)—表示对信号量S进行V操作，即释放一个单位的资源。①S.value：=S.value+1；②若S.value0进程继续执行。若S.value≤0则释放S等待队列中的一个进程，使之转为就绪状态。相应地，wait(S)和signal(S)算法可描述为：112.3进程同步procedurevarS:semaphore;beginS.value:=S.value-1;ifS.value＜0thenblock(S,L)endprocedurevarS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S,L);end当该资源已经分配完毕时，进程调用block原语，自我阻塞，并将该进程插入到等待队列中。说明有进程在等待队列中，应唤醒它们。wait(S)signal(S)122.3进程同步Vars:semaphore:=3;Printer:repeatwait(s);printthedocumentonthepaper;signal(s);untilfalseP1P2P3P4阻塞210S-1P10记录型信号量的应用132.3进程同步AND型信号量假定有两个进程A和B，他们都要访问共享数据D和E。分别设置用于互斥的信号量Dmutex和Emutex,并令它们的初值都是1。processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行waitprocessA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1AprocessB:wait(Dmutex);于是Dmutex=-1B阻塞当进程同时要求的共享资源愈多时，发生进程死锁的可能性也就愈大。142.3进程同步AND同步机制的基本思想将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。即:对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)定义如下：Swait152.3进程同步Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endforelse将进程放入第一个Si1的等待队列中,并且将程序指针指向该进程的Swait操作开始处；endifSsignal(S1,S2,…,Sn)fori:=1tondoSi=Si+1;将与Si相关的等待队列中的进程移到就绪队列；endfor;162.3进程同步信号量集如果一次需要N个某类临界资源，在记录型信号量机制中，wait(S)或signal(S)操作每次只能获得或释放一个单位的临界资源，从而要进行N次wait(S)操作，显然这是低效的。在AND信号量机制基本上的扩充。在每次分配资源之前，都必须测试该资源的数量，看其是否大于其下限值。操作可描述如下，其中Swait(S1,t1,d1,…Sn,tn,dn)S为信号量，d为需求值，而t为下限值。172.3进程同步2.3.3信号量的应用1.利用信号量实现进程互斥当访问临界资源的进程在进入临界区之前，都要先对mutex(互斥信号量)执行wait操作，保证该临界资源能被互斥地访问。利用信号量实现进程互斥的进程可描述如下：当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。182.3进程同步Varmutex:semaphor:=1beginparbeginprocess1:beginrepeatwait(mutex)criticalsectionsignal(mutex);remaindersectionuntilfalse;endprocess2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endparend注意：wait(mutex)和signal(mutex)必须成对地出现。192.3进程同步2.利用信号量实现前趋关系Vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;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;parendendS1S2S3S4S5S6abcdegf202.3进程同步例子已知一个求值公式(A2＋3B)/(B+5A)，若A、B已赋值，试画出该公式求值过程的前趋图，并使用信号量描述这些前趋关系。S6S4S2S3S5S1abcdeS1:X1=A*AS2:X2=3*BS3:X3=5*AS4:X4=X1+X2S5:X5=B+X3S6:X6=X4/X5212.3进程同步beginS1;signal(a);end;beginS2;signal(b);end;beginS3;signal(c);end;beginwait(a);wait(b);S4;signal(d);endbeginwait(c);S5;signal(e);endbeginwait(d);wait(e);S6;endS6S4S2S3S5S1abcde222.3进程同步2.3.4管程机制1.为什么要引入管程信号量机制的缺点：进程自备同步操作，wait(S)和signal(S)操作大量分散在各个进程中，不易管理，易发生死锁。管程特点：管程封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用界面。引入管程机制的目的：把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作;便于用高级语言来书写程序，也便于程序正确性验证232.3进程同步2.定义代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据”。一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据”。242.3进程同步共享数据…一组操作过程初始化代码进入队列条件(不忙)队列管程示意图3.组成①管程的名称；②局部于管程内部的共享数据结构说明；③对该数据结构进行操作的一组过程；④对局部于管程内部的共享数据设置初始值的语句。252.3进程同步function函数名(形式参数表)：值类型；beginend；begin管程的局部数据初始化语句序列；endProcedure过程名(形式参数表)：beginend；管程的语法typemonitor_name=MONITOR；共享变量说明；define(能被其他模块引用的)过程名列表；use(要调用的本模块外定义的)过程名列表；............262.3进程同步5.管程的特性(1)模块化。管程是一个基本程序单位，可以单独编译。(2)抽象数据类型。管程中不仅有数据，而且有对数据的操作。(3)信息掩蔽。管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。272.3进程同步6.管程与进程的比较主要体现在以下几个方面：(1)进程定义的是私有数据结构PCB，管程定义的是公共数据结构；(2)进程是由顺序程序执行有关的操作，而管程主要是进行同步操作和初始化操作；(3)设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题；(4)管程为被动工作方式，进程则为主动工作方式；(5)进程之间能并发执行，而管程则不能与其调用者并发；(6)进程具有动态性，而管程则是操作系统中的一个资源管