操作系统课件-第三章进程管理4(同步和互斥1)

进程管理13.4.6进程的挂起和激活当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，应该利用挂起原语suspend()挂起原语的执行过程：检查被挂起进程的状态；如果处于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。进程的激活过程当发生激活事件后，系统利用激活原语Active()将指定进程激活。激活原语先将进程从外存调入内存，然后检查进程的状态。静止就绪活动就绪静止阻塞活动阻塞进程管理2执行活动就绪活动阻塞静止就绪静止阻塞激活释放挂起释放激活挂起挂起进程管理3创建和撤销阻塞和唤醒挂起和激活进程管理43.5进程的同步与互斥进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。进程互斥进程同步利用信号量机制解决具体问题进程管理5并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系：1间接制约关系（进程互斥）由于共享资源而引起的暂临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约2直接制约关系（进程同步）由于并发进程互相共享对方的私有资源所引起的直接制约。进程管理6什么叫互斥？一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。临界资源:一次仅允许一个进程使用的资源。临界区：每个进程中访问临界资源的那段代码（criticalsection）。（不允许多个并发进程交叉执行的那段程序)进程管理7临界区的管理计算机专家Dijkstra1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：①每次至多有一个进程处于临界区②当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区③进程仅在临界区内逗留有限的时间。简言之，同步机制的准则有：1空闲让进；2忙则等待；3让权等待；4有限等待；进程管理8一种可能的办法是对临界区加锁以实现互斥。设临界区的类名为Ｓ，为了保证每一次临界区中只能有一个程序段被执行，又设锁定位Key[S]，Key[S]表示锁定位属于类名为Ｓ的临界区。加锁后的临界区程序描述如下：lock(key[S])临界区unlock(key[S])加锁法进程管理9设key[S]=1时表示类名为S的临界区可用，key[S]=0时表示类名为Ｓ的临界区不可用。则，unlock(key[S])只用一条语句即可实现。即：key[S]1不过，由于lock(key[S])必须满足key[S]=0时，不允许任何进程进入临界区，而key[S]=1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。进程管理10一种简便的实现方法是：lock(x)=beginlocalvrepeatvxuntilv=1(临界资源成为可用）x0end进程管理11不过，这种方法是不能保证并发进程互斥执行所要求的准则（3）的（只允许一个进程进入临界区）。为了解决这个问题，有些机器在硬件中设置了“测试与设置(testandset)指令”。此外，有一点需要注意的是：在系统试验时锁定为key[S]总是设置在公有资源所对应的数据结构中的。进程管理12Test-andSet指令定义了一个boolean变量，lock当lock=false时，表示该资源空闲；当lock=true时，表示改资源正被使用进程管理13加锁法和Ｐ、Ｖ原语法：加锁法是采用反复测试lock而实现互斥的，存在CPU浪费和不公平现象；而Ｐ、Ｖ原语法是采用信号量来管理相应的临界区的共有资源，信号量的值只能由Ｐ、Ｖ原语操作来改变，克服了加锁法的弊端。进程管理143.6进程同步概念：指多个合作进程为了完成同一个任务，它们在执行速度上必须相互协调，即一个进程的执行依赖于另一个进程的消息，当没有消息时要等待，直到消息到达被唤醒。具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。进程管理15到站停车开车开车门关车门售票正常行车。。。。。。。。。。售票员司机进程管理16进程同步的传送消息实现如果对一个事件或消息赋以唯一的消息名，则过程wait(消息名）表示进程等待合作进程发来消息，功能是等待到消息名为true的进程继续执行；过程signal(消息名）表示向合作进程发送消息，功能则是向合作进程发送所需要的消息名，并将其值置为true。进程管理17例：计算进程和打印进程的同步关系.设消息名bufempty表示buf空,初始化bufempty=true,Pc:while(true){wait(bufempty)计算buf计算结果bufemptyfalsesignal(buffull)}设消息名buffull表示buf满.Buffull=false.Pp:while(true){wait(buffull)打印Buf中的数据清除Buf中的数据buffullfalsesignal(bufempty)}进程管理18进程同步和互斥间的关系相似处：进程的互斥实际上是进程同步的一种特殊情况；进程的互斥和同步统称为进程同步。差别：进程互斥是进程间共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时在归还；而进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。进程管理19利用信号量机制解决问题信号量机制：由Diskstra提出的一种解决进程的同步与互斥的工具。信号量——用于表示资源数目或请求使用某一资源的进程个数的整形量.S是与临界区内所使用的公用资源有关的信号量。S≥0可供并发进程使用的资源数S0正在等待使用临界区的进程数进程管理20P原语操作的主要动作S－1如果S－1以后仍大于等于零，则进程继续进行如果S－1以后小于等于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度V原语操作的主要动作S＋1如果相加后结果大于零，则继续进行相加后结果小于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。入口s.value=s.value-1s.value≥0调度进程入等待队列转进程调度入口s.value=s.value＋1s.value≤0唤醒等待队列中的一个进程返回或转进程调度返回返回s.value0是是否P原语操作功能流程图V原语操作功能流程图进程管理22记录型的信号量机制是一个记录型的数据结构，包含两个数据项，一是记数值域，另一是等待该信号量的进程队列首指针域。描述如下：typedefstructsemaphore{intvalue;PCB*p;}进程管理23P(s)和V(s)操作原语voidP(s)structsemaphores;{s.value=s.value-1;if(s.value0)block(s.p);}voidv(s)structsemaphores;{s.value=s.value+1;if(s.value=0)wakeup(s.p);}进程管理24s.value的物理含义当s.value0数值时，表示某类可用资源的数量。而当s.value0数值时，表示该类资源已分配完。若有进程请求该类资源，则被阻塞，其绝对值等于等待该类资源的进程数。每次的P(s)操作，意味着进程请求分配该类资源的一个单位资源。相反，执行一次V(s)操作意味着进程释放相应资源的一个单位资源。当值小于等于0时，表明有进程被阻塞，需要唤醒。进程管理25利用P、V原语实现进程互斥设mutex为互斥信号量，取值范围为（1，0，-1），有两个并发的进程PA、PBmutex＝1表示进程PA、PB都没有进入类名为S的临界区mutex＝0表示进程PA、PB中的一个已经进入临界区mutex＝-1表示进程中，一个进程已经进入临界区，另一个进程阻塞，等待进入临界区进程管理26mutex:integer:=1；cobeginp1:{p2:{while(true){while(true){p(mutex)p(mutex)临界区代码临界区代码v(mutex)v(mutex)……}}}}coend进程管理27用信号量解题的关键步骤：信号量的设置；给信号量赋初值（常用的互斥和同步信号量值的大小）；P、V操作安排的位置（其中，P的顺序不能颠倒，V的顺序任意）注意区分1）公用信号量,互斥时使用的信号量（二元信号量）：它仅允许取值为“０”与“１”，用作互斥。它联系着一组共行进程，初值为１，每个进程均可对之施加Ｐ、Ｖ操作。2）私用信号量：一般信号量（资源信号量）：它联系着一组共行进程，但其初值为０，或为某个正整数ｎ，表示资源的数目，主要用于进程同步。只允许拥有它的进程对之施加Ｐ操作。进程管理28用信号量机制解决前趋图问题方法：若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为0，将V(s)放在S1后面，而在S2前面先执行P(s)。进程P1的语句序列为：S1;V(s)进程P2的语句序列为：P(s);S2S1S1S2sS1S3S2S4S5S6S7S8例1利用信号量来描述前趋图关系进程管理30具有8个结点的前趋图。图中的前趋图中共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhij进程管理31Structsmaphorea,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0cobegin{S1;V(a);V(b);V(c);}{P(a);S2;V(d);}{P(b);S3;V(e);V(f);}{P(c);S4;V(g);}{P(d);P(e);S5;V(h);}{P(f);P(g);S6;V(i)}{P(h);P(i);S7;V(j);}{P(j);S8;}coendS1S3S2S4S5S6S7S8agefbcdhij进程管理32例2：已知一个求值公式（A2+3B）/(B+5A),若A,B已赋值，试画出该公式求值过程的前趋图。解：在该公式的求值过程中，有些运算分量的执行是可以并发执行的。为了描述方便，可设置一些中间变量保存中间结果，并给每个语句命名，其求值过程如下：S1S4S6S5S3S2S1:x1=A*AS2:x2=3*BS3:x3=5*AS4:x4=x1+x2S5:x5=B+x3S6:x6=x4/x5开始结束（A2+3B）/(B+5A)作业如下图具有6个节点的前驱图，利用信号量机制来解决该前驱图所描述的并发执行的过程。S1S1S1S1S1S1进程管理351：生产者－消费者的同步问题举例：生产者把产品生产出来，送入仓库。给消费者发信号，消费者得到信号后，到仓库取产品，取走产品后给生产者发信号……产品仓库一个生产者一个消费者进程管理36Beginprocedurecs1,s2:sem;begins1:=1;s2:=0;L2:想取产品CobeginP(s2);procedurep取产品；beginV(s1);L1:生产产品；gotoL2;p(s1);end放产品；CoendV(s2);EndgotoL1;end进程管理37BUF1BUFnBUF2.….PbPa2）发送进程和接收进程的同步问题利用信号量可以解决合作进程之间的同步。例：设进程Pa,Pb通过缓冲区队列传送数据进程管理38发送和接送过程满足的条件是：1)在Pa至少送一块数据入一个缓冲区之前,Pb不可能从缓冲区中取出数据(假定数据块长等于缓冲区长度);2)Pa往缓冲队列发送数据时,至少有一个缓冲区是空的;3)由Pa发送的数据块在缓冲队列中按先进先出(FIFO)方式排列.描述发送过程deposit(data)