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

1,3.4.6 进程的挂起和激活 当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，应该利用挂起原语suspend( ) 挂起原语的执行过程：检查被挂起进程的状态；如果处于活动就绪状态，就将它改为静止就绪；如果处于活动阻塞，则改为静止阻塞。 进程的激活过程 当发生激活事件后，系统利用激活原语Active()将指定进程激活。激活原语先将进程从外存调入内存，然后检查进程的状态。 静止就绪 活动就绪 静止阻塞 活动阻塞,2,挂起,3,创建和撤销 阻塞和唤醒 挂起和激活,4,3.5 进程的同步与互斥,进程的同步和互斥机制的主要任务：控制并发执行的诸进程之间能有效地共享和相互协作，同时使并发执行的程序仍具有可再现性。 进程互斥 进程同步 利用信号量机制解决具体问题,5,并发系统中诸进程由于资源共享、进程合作，而产生进程之间的相互制约；又因共享资源的方式不同，而导致两种不同的制约关系： 1 间接制约关系（进程互斥） 由于共享资源而引起的暂临界区内不允许并发进程交叉执行的现象。由共享公有资源而造成的对并发进程执行速度的间接制约 2 直接制约关系（进程同步） 由于并发进程互相共享对方的私有资源所引起的直接制约。,6,什么叫互斥？ 一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。即不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。 临界资源:一次仅允许一个进程使用的资源。 临界区：每个进程中访问临界资源的那段代码（critical section）。 （不允许多个并发进程交叉执行的那段程序),7,临界区的管理 计算机专家Dijkstra 1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足： 每次至多有一个进程处于临界区 当若干进程同时要求进入它们的临界区时，应在有限时间内使一进程进入临界区，而不应相互堵塞而致使彼此不能进入临界区 进程仅在临界区内逗留有限的时间。 简言之，同步机制的准则有：1 空闲让进；2 忙则等待；3 让权等待；4 有限等待；,8,一种可能的办法是对临界区加锁以实现互斥。 设临界区的类名为，为了保证每一次临界区中只能有一个程序段被执行，又设锁定位KeyS，KeyS表示锁定位属于类名为的临界区。加锁后的临界区程序描述如下： lock ( keyS ) unlock( keyS ),加锁法,9,设keyS=1时表示类名为S的临界区可用，keyS=0时表示类名为的临界区不可用。则，unlock(keyS)只用一条语句即可实现。即： keyS 1 不过，由于lock(keyS)必须满足keyS=0时，不允许任何进程进入临界区，而keyS=1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。,10,一种简便的实现方法是： lock(x)= begin local v repeat v x until v=1 (临界资源成为可用） x 0 end,11,不过，这种方法是不能保证并发进程互斥执行所要求的准则（3）的（只允许一个进程进入临界区）。为了解决这个问题，有些机器在硬件中设置了“测试与设置(test and set)指令”。 此外，有一点需要注意的是：在系统试验时锁定为keyS总是设置在公有资源所对应的数据结构中的。,Test-and Set指令 定义了一个boolean变量，lock 当lock=false时，表示该资源空闲； 当lock=true时，表示改资源正被使用,13,加锁法和、原语法： 加锁法是采用反复测试lock而实现互斥的，存在CPU浪费和不公平现象；而、原语法是采用信号量来管理相应的临界区的共有资源，信号量的值只能由、原语操作来改变，克服了加锁法的弊端。,14,3.6 进程同步 概念：指多个合作进程为了完成同一个任务，它们在执行速度上必须相互协调，即一个进程的执行依赖于另一个进程的消息，当没有消息时要等待，直到消息到达被唤醒。 具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。,15,。 。 。 。 。 。,。 。 。 。,售票员,司机,16,进程同步的传送消息实现 如果对一个事件或消息赋以唯一的消息名，则过程wait (消息名）表示进程等待合作进程发来消息，功能是等待到消息名为true的进程继续执行； 过程signal (消息名）表示向合作进程发送消息，功能则是向合作进程发送所需要的消息名，并将其值置为true。,17,例：计算进程和打印进程的同步关系. 设消息名bufempty表示buf空, 初始化 bufempty =true, Pc: while(true) wait(bufempty) 计算 buf计算结果 bufempty false signal(buffull),设消息名buffull表示buf满. Buffull=false. Pp: while(true) wait(buffull) 打印Buf中的数据 清除Buf中的数据 buffull false signal(bufempty),18,进程同步和互斥间的关系 相似处：进程的互斥实际上是进程同步的一种特殊情况； 进程的互斥和同步统称为进程同步。 差别：进程互斥是进程间共享资源的使用权 ，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时在归还；而进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。,19,利用信号量机制解决问题,信号量机制：由Diskstra提出的一种解决进程的同步与互斥的工具。 信号量用于表示资源数目或请求使用某一资源的进程个数的整形量. S是与临界区内所使用的公用资源有关的信号量。 S0 可供并发进程使用的资源数 S0 正在等待使用临界区的进程数,20,P原语操作的主要动作 S1 如果S1以后仍大于等于零，则进程继续进行 如果S1以后小于等于零，则将该进程阻塞以后插入阻塞队列，然后转进程调度 V原语操作的主要动作 S1 如果相加后结果大于零，则继续进行 相加后结果小于零，则从该信号的等待队列中唤醒一个等待进程，然后返回原进程继续执行或者转进程调度。,入口,s.value=s.value-1,s.value0,调度进程入等待队列,转进程调度,入口,s.value=s.value1,s.value0,唤醒等待队列中的一个进程,返回或转进程调度,返回,返回,s.value0,是,是,否,P原语操作功能流程图,V原语操作功能流程图,22,记录型的信号量机制,是一个记录型的数据结构，包含两个数据项，一是记数值域，另一是等待该信号量的进程队列首指针域。描述如下： typedef struct semaphore int value; PCB *p; ,23,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.value=0) wakeup(s.p); ,24,s.value的物理含义,当s.value0数值时，表示某类可用资源的数量。而当s.value0数值时，表示该类资源已分配完。若有进程请求该类资源，则被阻塞，其绝对值等于等待该类资源的进程数。 每次的P(s)操作，意味着进程请求分配该类资源的一个单位资源。相反，执行一次V(s) 操作意味着进程释放相应资源的一个单位资源。当值小于等于0时，表明有进程被阻塞，需要唤醒。,25,利用P、V原语实现进程互斥,设mutex为互斥信号量，取值范围为（1，0，-1），有两个并发的进程PA、PB mutex 1表示进程PA、PB都没有进入类名为S的临界区 mutex 0表示进程PA、PB中的一个已经进入临界区 mutex -1表示进程中，一个进程已经进入临界区，另一个进程阻塞，等待进入临界区,26,mutex:integer:=1； cobegin p1: 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);S2,S1,S1,S2,s,例1 利用信号量来描述前趋图关系,30,具有8个结点的前趋图。图中的前趋图中共有有向边10条，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：,31,Struct smaphore a,b,c,d,e,f,g,h,I,j=0,0,0,0,0,0,0,0,0,0 cobegin 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; coend,32,例2：已知一个求值公式（A2+3B）/(B+5A),若A,B已赋值，试画出该公式求值过程的前趋图。 解：在该公式的求值过程中，有些运算分量的执行是可以并发执行的。为了描述方便，可设置一些中间变量保存中间结果，并给每个语句命名，其求值过程如下：,（A2+3B）/(B+5A),作业,如下图具有6个节点的前驱图，利用信号量机制来解决该前驱图所描述的并发执行的过程。,35,1：生产者消费者的同步问题 举例： 生产者把产品生产出来，送入仓库。给 消费者发信号，消费者得到信号后，到仓库 取产品，取走产品后给生产者发信号,产品,仓 库,一个生产者,一个消费者,36,Begin procedure c s1,s2:sem; begin s1:=1; s2:=0; L2: 想取产品 Cobegin P(s2); procedure p 取产品； begin V(s1); L1:生产产品； goto L2; p(s1); end 放产品； Coend V(s2); End goto L1; end,37,BUF1,BUFn,BUF2,.,Pb,Pa,2）发送进程和接收进程的同步问题 利用信号量可以解决合作进程之间的同步。 例：设进程Pa,Pb通过缓冲区队列传送数据,38,发送和接送过程满足的条件是： 1)在Pa至少送一块数据入一个缓冲区之前,Pb不可能从缓冲区中取出数据(假定数据块长等于缓冲区长度); 2)Pa往缓冲队列发送数据时,至少有一个缓冲区是空的; 3)由Pa发送的数据块在缓冲队列中按先进先出(FIFO)方式排列. 描述发送过程deposit (data)和接受过程remove (data) .,39,1)Bufempty进程Pa的私用信号量, Buffull 进程Pb的私用信号量; 2)Bufempty的初始值为n(n 为缓冲队列的缓冲区个数),Buffull的初始值为0; 发送过程Deposit(data),接送过程Remove(data),这两个过程必须同步，因为,因为过程deposit(data)的执行结果是过程remove(data)的执行条件,而当缓冲队列全部装满数据时,remove(data)的执行结果又是deposit(data)的执行条件。,40,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 end,41,P1 P2 P3 . Pn.,C1 C2 C3 . Cn,Dijkstra把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者。我们可以通过一个缓冲区把生产者和消费者联系起来,42,设生产者进程和消费者进程是互相等效的，其中各生产者进程使用的过程deposit (data)和消费者进程使用的过程remove(data)可描述如下： 首先，上述生产者-消费者问题是一个同步问题。即生产者和消费者之间满足如下条件： 1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的； 2)生产者想接收数据时，有界缓冲区中至少有一个单元是空的。,43,另外，由于有界缓冲区是临界资源，因此，各生产者进程和消费者进程之间必须互斥执行。 有以上分析我们设公用信号量mutex保证生产者进程和消费者进程之间的互斥,设信号量 avail表示有界缓冲区中的空单元数,初值为n;信号量full表示有界缓冲区中的非空单元数,初值为0.信号量mutex表示有界缓冲区中的个数,初值为1.从而有:,44,deposit (data); remove(data); begin begin p(avail) p(full) p(mutex) p(mutex) 送数据入缓冲区某单元 取缓冲区中某单元数据 V(full) V(avail) V(mutex) V(mutex) end end,45,几个经典的进程同步问题,生产者消费者问题 哲学家进餐问题 读者写者问题 图书馆阅览室问题 理发师问题 吃水果问题 司机售票员问题 过河问题,46,生产者消费者问题,一个最著名的进程同步问题 问题描述：一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者存入消息，消费者从中取得消息。,47,例：利用信号量解决读者和写者问题 一个文件可能被多个进程共享，为了保证读写的正确性和文件的一致性，系统要求，当有读者进程读文件时，不允许任何写者进程写，但允许多读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进行读。 为了解决读者和写者问题，需设置两个信号量： （1）读互斥信号量rmutex,用于使读者互斥地访问共享变量readcount,这里readcount是记录有多少读者正在读;,48,（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。读者写者问题进行如下描述： struct semapore rmutex,wmutex=1,1; int readcount:=0;,49,cobegin vord readeri(vord)(i=1,2,k) while(true) p(rmutex)； if readcount=0 then if readcount=0 then v(wmutex); p(wmutex); v(rmutex); readcount:=readcount+1; v(rmutex); 读文件；