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

进进程程管管理理3.4.6 进程的挂起和激活进程的挂起和激活 当出现了引起进程挂起的事件时，用户请求将自己当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，应该利用挂起，或者父进程请求挂起自己的子进程，应该利用挂起原语挂起原语suspend()挂起原语的执行过程挂起原语的执行过程：检查被挂起进程的状态；如果处：检查被挂起进程的状态；如果处于活动就绪状态，就将它改为静止就绪；如果处于活于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。动阻塞，则改为静止阻塞。进程的激活过程进程的激活过程当发生激活事件后，系统利用激活原语当发生激活事件后，系统利用激活原语Active()将指定进将指定进程激活。激活原语先将进程从外存调入内存，然后检程激活。激活原语先将进程从外存调入内存，然后检查进程的状态。查进程的状态。静止就绪静止就绪 活动就绪活动就绪 静止阻塞静止阻塞 活动阻塞活动阻塞1进进程程管管理理执行活动就绪活动阻塞静止就绪静止阻塞请求I/O激活释放挂起释放激活挂起挂起2进进程程管管理理创建和撤销阻塞和唤醒挂起和激活3进进程程管管理理3.5 进程的同步与互斥进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。进程互斥 进程同步 利用信号量机制解决具体问题4进进程程管管理理并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系：1 间接制约关系（进程互斥）由于共享资源而引起的暂临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约2 直接制约关系（进程同步）由于并发进程互相共享对方的私有资源所引起的直接制约。5进进程程管管理理什么叫互斥？什么叫互斥？一一组组并并发发进进程程中中的的一一个个或或多多个个程程序序段段，因因共共享享某某一一公公有有资资源源而而导导致致它它们们必必须须以以一一个个不不允允许许交交叉叉执执行行的的单单位位执执行行。即即不不允允许许两两个个以以上上的的共共享享该该资资源源的的并并发发进程同时进入临界区称为互斥。进程同时进入临界区称为互斥。临界资源临界资源:一次仅允许一个进程使用的资源一次仅允许一个进程使用的资源。临界区：每个进程中访问临界资源的那段代码（critical section）。（不允许多个并发进程交叉执行的那段程序)6进进程程管管理理 临界区的管理临界区的管理 计计算算机机专专家家DijkstraDijkstra 19651965年年提提出出临临界界区区设设计原则，即一组并发进程互斥执行时必须满足：计原则，即一组并发进程互斥执行时必须满足：每次至多有一个进程处于临界区每次至多有一个进程处于临界区当当若若干干进进程程同同时时要要求求进进入入它它们们的的临临界界区区时时，应应在在有有限限时时间间内内使使一一进进程程进进入入临临界界区区，而而不不应应相相互堵塞而致使彼此不能进入临界区互堵塞而致使彼此不能进入临界区进程仅在临界区内逗留有限的时间。进程仅在临界区内逗留有限的时间。简言之，同步机制的准则有：1 空闲让进；2 忙则等待；3 让权等待；4 有限等待；7进进程程管管理理 一种可能的办法是对临界区加锁以实一种可能的办法是对临界区加锁以实现互斥。现互斥。设临界区的类名为，为了保证每一次设临界区的类名为，为了保证每一次临界区中只能有一个程序段被执行，又设临界区中只能有一个程序段被执行，又设锁定位锁定位KeySKeyS，KeySKeyS表示锁定位属于类表示锁定位属于类名为的临界区名为的临界区。加锁后的临界区程序描。加锁后的临界区程序描述如下：述如下：lock (keyS)lock (keyS)unlock(keyS)unlock(keyS)加锁法加锁法8进进程程管管理理 设设keyS=1keyS=1时表示类名为时表示类名为S S的临界区可用，的临界区可用，keyS=0keyS=0时表示类名为的临界区不可用。时表示类名为的临界区不可用。则，则，unlock(keyS)unlock(keyS)只用一条语句即可实现。只用一条语句即可实现。即：即：keyS keyS 1 1 不过，由于不过，由于lock(keyS)lock(keyS)必须满足必须满足keyS=0keyS=0时，不允许任何进程进入临界区，时，不允许任何进程进入临界区，而而keyS=1keyS=1时仅允许一个进程进入临界区的时仅允许一个进程进入临界区的准则，因而实现起来较为困难。准则，因而实现起来较为困难。9进进程程管管理理一种简便的实现方法是：一种简便的实现方法是：lock(x)=begin local v repeat v x until v=1(临界资源成为可用）临界资源成为可用）x 0end10进进程程管管理理 不过，这种方法是不过，这种方法是不能保证并发进程互斥执不能保证并发进程互斥执行所要求的准则（行所要求的准则（3 3）的（只允许一个进程进入）的（只允许一个进程进入临界区）。临界区）。为了解决这个问题，有些机器在硬件为了解决这个问题，有些机器在硬件中设置了中设置了“测试与设置测试与设置(test and set)test and set)指令指令”。此外此外，有一点有一点需要注意的是：需要注意的是：在系统试验时锁定在系统试验时锁定为为keySkeyS总是设置在公有资源所对应的数据结构总是设置在公有资源所对应的数据结构中的。中的。11进进程程管管理理Test-and Set指令定义了一个boolean变量，lock当lock=false时，表示该资源空闲；当lock=true时，表示改资源正被使用12进进程程管管理理加锁法和、原语法：加锁法是采用反复测试lock而实现互斥的，存在CPU浪费和不公平现象；而、原语法是采用信号量来管理相应的临界区的共有资源，信号量的值只能由、原语操作来改变，克服了加锁法的弊端。13进进程程管管理理 3.6 进程同步概念：指多个合作进程为了完成同一个任务，它们在执行速度上必须相互协调，即一个进程的执行依赖于另一个进程的消息，当没有消息时要等待，直到消息到达被唤醒。具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。14进进程程管管理理 到站停车到站停车 开开 车车 开开 车车 门门 关关 车车 门门 售售 票票 正常行车正常行车。售票员售票员司机司机15进进程程管管理理进程同步的传送消息实现如果对一个事件或消息赋以唯一的消息名，则过程wait(消息名）表示进程等待合作进程发来消息，功能是等待到消息名为true的进程继续执行；过程signal (消息名）表示向合作进程发送消息，功能则是向合作进程发送所需要的消息名，并将其值置为true。16进进程程管管理理例：计算进程和打印进程的同步关系.设消息名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)17进进程程管管理理进程同步和互斥间的关系相似处：进程的互斥实际上是进程同步的一种特殊情况；进程的互斥和同步统称为进程同步。差别：进程互斥是进程间共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时在归还；而进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。18进进程程管管理理利用信号量机制解决问题信号量机制：由Diskstra提出的一种解决进程的同步与互斥的工具。信号量信号量用于表示用于表示资源数目资源数目或请求使或请求使用用某一资源的进程个数的整形量某一资源的进程个数的整形量.S是与临界区内所使用的公用资源有关的是与临界区内所使用的公用资源有关的信号量。信号量。S0 可供并发进程使用的资源数可供并发进程使用的资源数S0 正在等待使用临界区的进程数正在等待使用临界区的进程数19进进程程管管理理P原语操作的主要动作nS1n如果S1以后仍大于等于零，则进程继续进行n如果S1以后小于等于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度V原语操作的主要动作nS1n如果相加后结果大于零，则继续进行n相加后结果小于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。20入口s.value=s.value-1s.value0调度进程入等待队列转进程调度入口s.value=s.value1s.value0唤醒等待队列中的一个进程返回或转进程调度返回返回s.value0是是否P原语操作功能流程图V原语操作功能流程图21进进程程管管理理记录型的信号量机制是一个记录型的数据结构，包含两个数据项，一是记数值域，另一是等待该信号量的进程队列首指针域。描述如下：typedef struct semaphore int value;PCB*p;22进进程程管管理理P(s)和V(s)操作原语void P(s)struct semaphore s;s.value=s.value-1;if(s.value0)block(s.p);void v(s)struct semaphore s;s.value=s.value+1;if(s.value0数值时，表示某类可用资源的数量。而当s.value0数值时，表示该类资源已分配完。若有进程请求该类资源，则被阻塞，其绝对值等于等待该类资源的进程数。每次的P(s)操作，意味着进程请求分配该类资源的一个单位资源。相反，执行一次V(s)操作意味着进程释放相应资源的一个单位资源。当值小于等于0时，表明有进程被阻塞，需要唤醒。24进进程程管管理理利用P、V原语实现进程互斥设mutex为互斥信号量，取值范围为（1，0，-1），有两个并发的进程PA、PBmutex 1表示进程PA、PB都没有进入类名为S的临界区mutex 0表示进程PA、PB中的一个已经进入临界区mutex-1表示进程中，一个进程已经进入临界区，另一个进程阻塞，等待进入临界区25进进程程管管理理mutexmutex:integer:=1:integer:=1；cobegincobeginp1:p2:p1:p2:while(true)while(true)while(true)while(true)p(p(mutexmutex)p(p(mutexmutex)临界区代码临界区代码 临界区代码临界区代码 v(v(mutexmutex)v(v(mutexmutex)coendcoend26进进程程管管理理用信号量解题的关键步骤：信号量的设置；给信号量赋初值（常用的互斥和同步信号量值的大小）；P、V操作安排的位置（其中，P的顺序不能颠倒，V的顺序任意）注意区分注意区分1 1）公用信号量公用信号量,互斥时使用的信号量互斥时使用的信号量（二元（二元信号量）：它仅允许取值为信号量）：它仅允许取值为“”与与“”，用作互，用作互斥。它联系着一组共行进程，初值为，每个进程均斥。它联系着一组共行进程，初值为，每个进程均可对之施加、操作。可对之施加、操作。2 2）私用信号量：私用信号量：一般信号一般信号量量（资源信号量）：它联系着一组共行进程，但其初（资源信号量）：它联系着一组共行进程，但其初值为，或为某个正整数，表示资源的数目，主要值为，或为某个正整数，表示资源的数目，主要用于进程同步。用于进程同步。只允许拥有它的只允许拥有它的进程对之施加操作进程对之施加操作。27进进程程管管理理用信号量机制解决前趋图问题方法：若图中存在结点S1指向结点S2的有向边，表示进程P1中的程序段S1应该先执行，而进程P2中的程序段S2后执行。设置一个信号量s,初值为0，将V(s)放在S1后面，而在S2前面先执行P(s)。进程P1的语句序列为：S1;V(s)进程P2的语句序列为：P(s);S2 S1S1S2s28S1S3S2S4S5S6S7S8例1 利用信号量来描述前趋图关系29进进程程管管理理 具具有有8个个结结点点的的前前趋趋图图。图图中中的的前前趋趋图图中中共共有有有有向向边边10条条，可可设设10个个信信号号量量，初初值值均均为为0；有有8个个结结点点，可可设设计计成成8个个并并发发进程，具体描述如下：进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhij30进进程程管管理理Struct smaphore a,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;coendS1S3S2S4S5S6S7S8agefbcdhij31进进程程管管理理例例 2：已已 知知 一一 个个 求求 值值 公公 式式（A2+3B）/(B+5A),若若A,B已已赋赋值值，试试画画出该公式求值过程的前趋图。出该公式求值过程的前趋图。解解：在在该该公公式式的的求求值值过过程程中中，有有些些运运算算分分量量的的执执行行是是可可以以并并发发执执行行的的。为为了了描描述述方方便便，可可设设置置一一些些中中间间变变量量保保存存中中间间结结果果，并并给给每每个个语语句句命命名名，其其求求值值过过程程如下：如下：32S1S4S6S5S3S2S1:x1=A*AS2:x2=3*BS3:x3=5*AS4:x4=x1+x2S5:x5=B+x3S6:x6=x4/x5开始结束（A2+3B）/(B+5A)33作业如下图具有6个节点的前驱图，利用信号量机制来解决该前驱图所描述的并发执行的过程。S1S1S1S1S1S134进进程程管管理理1 1：生产者消费者生产者消费者的同步问题的同步问题举例：举例：生产者把产品生产出来，送入仓库。给生产者把产品生产出来，送入仓库。给消费者发信号，消费者得到信号后，到仓库消费者发信号，消费者得到信号后，到仓库取产品，取走产品后给生产者发信号取产品，取走产品后给生产者发信号产品仓 库一个生产者一个消费者35进进程程管管理理Beginprocedurecs1,s2:sem;begins1:=1;s2:=0;L2:想取产品CobeginP(s2);procedurep取产品；beginV(s1);L1:生产产品；gotoL2;p(s1);end放产品；CoendV(s2);EndgotoL1;end36进进程程管管理理BUF1BUFnBUF2.Pb Pa2 2）发送进程和接收进程的同步问题发送进程和接收进程的同步问题 利用信号量可以解决合作进程之间的同步。利用信号量可以解决合作进程之间的同步。例：设进程例：设进程Pa,Pa,PbPb通过缓冲区队列传送数通过缓冲区队列传送数据据 37进进程程管管理理 发送和接送过程满足的条件是发送和接送过程满足的条件是：1)1)在在PaPa至少送一块数据入一个缓冲区之至少送一块数据入一个缓冲区之前前,PbPb不可能从缓冲区中取出数据不可能从缓冲区中取出数据(假定数据假定数据块长等于缓冲区长度块长等于缓冲区长度););2)2)PaPa往缓冲队列发送数据时往缓冲队列发送数据时,至少有一个至少有一个缓冲区是空的缓冲区是空的;3)3)由由PaPa发送的数据块在缓冲队列中按先发送的数据块在缓冲队列中按先进先出进先出(FIFO)FIFO)方式排列方式排列.描述发送过程描述发送过程deposit(data)deposit(data)和接受过和接受过程程remove(data).remove(data).38进进程程管管理理 1)1)BufemptyBufempty进程进程PaPa的私用信号量的私用信号量,BuffullBuffull 进程进程PbPb的私用信号量的私用信号量;2)2)BufemptyBufempty的初始值的初始值为为n(n n(n 为缓冲队列的为缓冲队列的缓冲区个数缓冲区个数),BuffullBuffull的初始值为的初始值为0;0;发送过程发送过程Deposit(data),Deposit(data),接送过程接送过程Remove(data),Remove(data),这两个过程必须同步，因为这两个过程必须同步，因为,因因为过程为过程deposit(data)deposit(data)的执行结果是过程的执行结果是过程remove(data)remove(data)的执行条件的执行条件,而当缓冲队列全部而当缓冲队列全部装满数据装满数据时时,remove(data)remove(data)的执行结果又是的执行结果又是deposit(data)deposit(data)的执行条件。的执行条件。39进进程程管管理理 Pa:deposit(data)Pb:remove(data)begin local x begin local x P(Bufempty)P(Buffull)按按FIFO方式选择一个方式选择一个 按按FIFO方式选择一个方式选择一个 空缓冲空缓冲Buf(x);装满数据的缓冲装满数据的缓冲Buf(x)Buf(x)-data data-Buf(x)Buf(x)置满标记置满标记 Buf(x)置满标记置满标记 V(Buffull)V(Bufempty)end end40进进程程管管理理123.nP1P2P3.Pn.C1C2C3.Cn DijkstraDijkstra把同步问题抽象成一种生产者和消把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者。我们可以通过一是生产者，计算进程是消费者。我们可以通过一个缓冲区把生产者和消费者联系起来个缓冲区把生产者和消费者联系起来41进进程程管管理理 设生产者进程和消费者进程是互相等效的，设生产者进程和消费者进程是互相等效的，其中各生产者进程使用的过程其中各生产者进程使用的过程deposit(data)deposit(data)和和消费者进程使用的过程消费者进程使用的过程remove(data)remove(data)可描述如下：可描述如下：首先，上述生产者首先，上述生产者-消费者问题是一个同步消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：问题。即生产者和消费者之间满足如下条件：1)1)消费者想接收数据时，有界缓冲区中至少消费者想接收数据时，有界缓冲区中至少有一个单元是满的；有一个单元是满的；2)2)生产者想接收数据时，有界缓冲区中至少生产者想接收数据时，有界缓冲区中至少有一个单元是空的。有一个单元是空的。42进进程程管管理理 另外，由于有界缓冲区是临界资源，因此，另外，由于有界缓冲区是临界资源，因此，各生产者进程和消费者进程之间必须互斥执行。各生产者进程和消费者进程之间必须互斥执行。有以上分析我们设公用信号量有以上分析我们设公用信号量mutexmutex保证生保证生产者进程和消费者进程之间的互斥产者进程和消费者进程之间的互斥,设信号量设信号量 availavail表示有界缓冲区中的空单元数表示有界缓冲区中的空单元数,初值初值为为n;n;信号量信号量fullfull表示有界缓冲区中的非空单元表示有界缓冲区中的非空单元数数,初值初值为为0.0.信号量信号量mutexmutex表示有界缓冲区中的表示有界缓冲区中的个数个数,初值为初值为1.1.从而有从而有:43进进程程管管理理 deposit(data);remove(data);begin begin p(avail)p(full)p(mutex)p(mutex)送数据入缓冲区某单元送数据入缓冲区某单元 取缓冲区中某单元数据取缓冲区中某单元数据V(full)V(avail)V(mutex)V(mutex)end end44进进程程管管理理几个经典的进程同步问题v生产者消费者问题v哲学家进餐问题v读者写者问题v图书馆阅览室问题v理发师问题 v吃水果问题v司机售票员问题v过河问题45进进程程管管理理生产者消费者问题一个最著名的进程同步问题问题描述：一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者存入消息，消费者从中取得消息。46进进程程管管理理例：利用信号量解决读者和写者问题例：利用信号量解决读者和写者问题 一一个个文文件件可可能能被被多多个个进进程程共共享享，为为了了保保证证读读写写的的正正确确性性和和文文件件的的一一致致性性，系系统统要要求求，当当有有读读者者进进程程读读文文件件时时，不不允允许许任任何何写写者者进进程程写写，但但允允许许多多读读者者同同时时读读；当当有有写写者者进进程程写写时时，不不允允许许任任何何其其它它写写者者进程写，也不允许任何读者进行读。进程写，也不允许任何读者进行读。为为了了解解决决读读者者和和写写者者问问题题，需需设设置置两两个个信信号量：号量：（1 1）读读互互斥斥信信号号量量rmutexrmutex,用用于于使使读读者者互互斥斥 地地 访访 问问 共共 享享 变变 量量 readcountreadcount,这这 里里readcountreadcount是记录有多少读者正在读是记录有多少读者正在读;47进进程程管管理理（2 2）写写互互斥斥信信号号量量wmutexwmutex,用用于于实实现现读读写写互互斥斥和和写写写写互互斥斥地地访访问问共共享享文文件件。读读者者写者问题进行如下描述：写者问题进行如下描述：struct semapore rmutexstruct semapore rmutex,wmutexwmutex=1,1;=1,1;int readcountint readcount:=0;:=0;48进进程程管管理理cobegincobeginvordvord readerireaderi(vordvord)(i=1,2,)(i=1,2,k)k)while(true)while(true)p(p(rmutexrmutex)；ifif readcountreadcount=0 then=0 then ifif readcount readcount=0 then v(=0 then v(wmutexwmutex););p(p(wmutexwmutex);v();v(rmutexrmutex););readcountreadcount:=:=readcountreadcount+1;+1;v(v(rmutexrmutex););读文件；读文件；p(p(rmutexrmutex)；readcount readcount:=:=readcountreadcount-1;-1;49进进程程管管理理vordvord writerjwriterj(vordvord)(j=1,2,)(j=1,2,m),m)while(true)while(true)p(p(wmutexwmutex););写写文件；文件；v(v(wmutexwmutex)；CoendCoend50进进程程管管理理 作业作业图书馆阅览室问题问题描述：假定阅览室最多可同时容纳100个人阅读，读者进入时，必须在阅览室门口的一个登记表上登记，内容包括姓名、座号等，离开时要撤掉登记内容。用P、V操作描述读者进程的同步算法。51进进程程管管理理理发师问题(Dijkstra 1965)问题描述：一个理发店由一个有几张椅子的等候室和一个放有一张理发椅的理发室组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待；若理发师在睡觉，则顾客就唤醒他，设计一个协调理发师和顾客的程序。52进进程程管管理理 作业作业吃水果问题问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用PV操作实现四人正确活动的程序。53进进程程管管理理四人之间的关系爸爸，妈妈要互斥使用盘子，所以两者之间是互斥关系；爸爸放的苹果，女儿吃，所以两者是同步关系；妈妈放的桔子，儿子吃，所以两者也是同步关系。54进进程程管管理理 作业作业1.司机售票员问题2.设公共汽车上，司机和售票员的活动分别是：司机：售票员：启动车辆 上下乘客 正常行车 关车门 到站停车 售票 开车门 上下乘客 在汽车不断到站，停车，行驶过程中，这两个活动的同步关系。55