05进程管理三互斥和同步一.ppt

1、1,2.3 进程互斥和同步,临界资源、临界区定义 记录型的信号量内部成员 的意义 signal wait操作含义 怎样利用信号量解决进程之间的前趋关系？,2,2.3 进程互斥和同步,在多道程序的环境中，系统中的多个进程可以并发执行，同时它们又要共享系统中的资源，这些资源有些是可共享使用的，如磁盘，有些是以独占方式使用的，如打印机。由此将会引起一系列的矛盾，产生错综复杂的相互制约的关系。 产生这种错综复杂的相互制约关系的原因有二： 资源共享 进程合作,返回,3,共享变量的修改冲突,4,2.3 进程同步,2.3.1 基本概念 2.3.2信号量(semaphore) 2.3.3信号量机制,返回,5,

2、2.3.1 基本概念,1 临界资源、临界区 2 临界区的访问过程 3 同步机制应遵循的准则 4 进程互斥的软件方法 5 进程互斥的硬件方法,6,2.3.1 基本概念-临界资源,引例 宿舍电话的使用 打印机的使用 1. 临界资源：一次仅允许一个进程使用的资源称为临界资源。 引例中的电话和打印机都属于临界资源。除此之外，还有内存变量、指针、数组等等也是临界资源。,7,2.3.1 基本概念-临界区,2、临界区：每个进程中访问临界资源的那段程序段称为临界区（临界段）。,8,2.3.1 基本概念-临界区的访问过程,临界区的访问过程,返回,进入区,退出区,临界区,9,临界区(critical sectio

3、n)：进程中访问临界资源的一段代码。 进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应正在访问临界区标志 退出区(exit section)：用于将正在访问临界区标志清除。 剩余区(remainder section)：代码中的其余部分。,返回,10,同步机制应遵循的准则,空闲让进：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能死等； 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）,返回,11,实现进程互斥的硬件方法,完全利用软件方法，有很大局限性（如不适于多

4、进程），现在已很少采用。 可以利用某些硬件指令其读写操作由一条指令完成，因而保证读操作与写操作不被打断；,Test-and-Set指令,该指令读出标志后设置为TRUE boolean TS(boolean *lock) boolean old; old = *lock; *lock = TRUE; return old; lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲,12,互斥算法（TS指令）,利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE 在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；,13,硬件

5、方法的优点 适用于任意数目的进程，在单处理器或多处理器上 简单，容易验证其正确性 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量 硬件方法的缺点 等待要耗费CPU时间，不能实现让权等待 可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上,返回,14,2.3.2 信号量(semaphore),需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhoge

6、n)），是一种卓有成效的进程同步机制。 信号量是一个被保护的变量，被初始化之后，只有wait操作、signal操作才能访问和改变它的值。信号量代表可用资源实体的数量。 wait操作、signal操作又称为P、V操作。它们都是原子操作（原语）,15,2.3.2 信号量(semaphore),一、整型信号量 整型信号量是表示共享资源状态且只能由特殊的原子操作改变的整型量。 想法：定义一个整型变量，用整形变量值来标记资源 使用情况：如整型量0,说明有可用资源;整型量0说明资源忙，进程必须等待。 对于一次只允许一个进程访问的临界资源，可定义一个用于互斥的整型信号量，并初始化为1。,16,2.3.2 信

7、号量(semaphore),一、整型信号量 整型信号量的wait和signal操作 Wait(s):while s0 do no-op 对CS的互斥访问。 s:=s-1. Signal(s): s:=s+1 实现对资源的释放 注：wait(s)和 signal(s)都是原子操作(原语）,17,2.3.2 信号量(semaphore),一、整型信号量 利用整型信号量实现互斥方法： 想法：为必须互斥访问的CS定义一个互斥信号量mutex，初始值为1，然后将CS放入wait(mutex)和signal(mutex)之间，当CS可访问时，wait(mutex)才能正常结束使进程进入CS。,18,2.3

8、.2 信号量(semaphore),二、利用整型信号量实现互斥,while mutex0 do no-op mutex:=mutex-1.,mutex:=mutex+1,Begin Repeat wait(mutex); Critical section Signal(mutex) Remainder section Until false; end,19,三、利用信号量来协调进程执行的顺序 例1：P1、P2两个进程，要求P2必须在P1结束后执行,为此，设置一个信号量S,初始值为0。 parbegin begin P1;Signal(s);end begin Wait(s);P2 ;end p

9、arend,20,三、利用信号量来描述前趋关系 例2：有P1，P2两个进程：S1，S2，SS6分别是P1、P2中的语句，我们要求它们的执行顺序如下图所示 :,21,22,利用信号量来描述前趋关系-例2 var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0; begin prabegin begim s1;signal(a);signal(b);end; begin wait(a);s2;signal(c);signal(d);end; begin wait(b);s3;signal(g);end; begin wait(c);s4;signal(e);end; be

10、gin wait(d);s5;signal(f);end; begin wait(e); wait(f); wait(g);s6;end. parend end.,23,2.3.2 信号量(semaphore),信号量是一个被保护的变量，只有wait操作、signal操作和初始化操作才能访问和改变它的值。信号量代表可用资源实体的数量。 wait操作、signal操作又称为P、V操作。 整型信号量机制存在的问题：忙等 当 信号量S0时，wait(S): while S=0 do no-op; S:=S-1;,24,记录型信号量和wait、signal原语,信号量是一个确定的二元组（value,

11、L），value 是一个具有非负初值的整型变量，L 是一个初始状态为空的队列。 value代表资源的实体。在实际应用中应准确地说明s的意义和初值，每个信号量都有一个队列，其初始状态为空。 初始化指定一个非负整数值，表示空闲资源总数（又称为资源信号量）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数,25,2.3.2.1 信号量和wait、signal原语,信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断 在实际操作系统中，一般情况下是由机器硬件提供P、V操 作的指令，当然是原子操作，若机器不提供P、V操作的指 令，则操作系统提供P、V

12、操作原语。 信号量的形式化定义： type semaphore=record value: integer; L: listofprocess; end,1. P原语(wait),26,procedure wait(S) var S：semaphore； begin S.value:=S.value-1； /表示申请一个资源; if S.value0 then block(S.L)； /如果没有空闲资源，调用进程进入和信号量S相关的等待队列 s.L; 阻塞调用wait 的进程 end,2. V原语(signal),procedure signal(S) var S: semaphore； be

13、gin S.value:=S.value+1； /表示释放一个资源； if S.value=0 then wakeup(S.L)；/如果有进程处于阻塞状态，从等待队列s.L中取出一个进程P，将其唤醒; end,27,V原语通常唤醒进程等待队列中的头一个进程,28,3. 利用信号量实现互斥,为临界资源设置一个互斥信号量mutex(MUTual Exclusion)，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间 必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗

14、漏,29,用信号量实现进程互斥,用两个进程共享打印机的例子 设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有一台打印机)。 (print是用于互斥的信号量，教材上常设置为mutex。),30,用信号量实现进程互斥,31,4 用信号量实现进程的同步,共享缓冲区的合作进程的同步 设有一个缓冲区buffer，大小为一个字节，CP进程不断产生字符，送buffer，IOP进程从buffer中取出字符打印。如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。,32,4 用信号量

15、实现进程的同步,要保证打印结果的正确， CP、IOP必须遵循以下同步规则： (1)当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待； (2)当IOP从buffer中取走数据后， CP才能将新产生数据送buffer，否则也必须等待。,CP,IOP,33,4 用信号量实现进程的同步,解决这个问题的步骤： (1)分析问题，弄清楚同步关系，如上分析； (2)设置信号量 ，说明含义、初值； (3)写出程序描述。 两个信号量控制两个进程依次运行。 信号量Sa：表示缓冲区是否有数据可供打印； 初值为0，表示刚开始时候没有数据 信号量Sb：表示是否可以向缓冲区放新数据； 初值为

16、1，表示刚开始时候可以放数据。,34,4 用信号量实现进程的同步,CP( )/计算进程 计算，得到一个结果; 将结果送到缓冲区; ,IOP( )/打印进程 从缓冲区中取出一个数据； 打印取出的数据; ,wait(sb);,signal(sa);,wait(sa);,signal(sb);,35,4 用信号量实现进程的同步,36,补充题1：,三个进程：输入、计算、打印,写出同步算法。,缓冲区a,缓冲区b,输入,输出,计算,37,经典进程同步问题,生产者消费者问题 有界缓冲区问题的建模 哲学家进餐问题 多进程同步问题的建模 读者写者问题 数据库互斥访问问题的建模 理发师睡觉问题 CS模式进程同步问

17、题的建模,进程通信,38,4 用信号量实现进程的同步- 生产者消费者问题,我们把上面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。 在我们生活中有很多这样的例子。,39,问题描述 一个有限空间的共享缓冲区，负责存放货物 生产者向缓冲区中放物品，缓冲区满则不能放 消费者从缓冲区中拿物品，缓冲区空则不能拿,（如何体现进程的同步）,40,4 用信号量实现进程的同步- 生产者消费者问题P48,对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲

18、区，并通知消费者进程；否则，等待； 对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。 这种相互等待，并互通信息就是典型的进程同步。 同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，因此，还有个互斥的问题。,41,4 用信号量实现进程的同步- 生产者消费者问题,互斥关系分析 任何时刻，只能有一个进程在缓冲区中操作 引入互斥信号量（mutex） 信号量为0，表明已有进程进入临界区； 同步关系分析 对于“生产者”而言，缓冲区满则应等待 引入同步信号量“empty”，为0表示缓冲区满 对于“消费者”而言，缓冲区空则

19、应等待 引入同步信号量“full”，为0表示缓冲区空,42,4 用信号量实现进程的同步- 生产者消费者问题,43,4 用信号量实现进程的同步- 生产者消费者问题,44,4 用信号量实现进程的同步- 生产者消费者问题,思考1：mutex和empty两个信号量之间有什么区别吗？ 思考2：多信号量的操作顺序有要求吗？,互斥信号量 mutex：防止多个进程同时进入临界区 同步信号量 empty和full：保证事件发生的顺序 缓冲区满时，Producer停止运行 缓冲区空时，Consumer停止运行 概念差别互斥与同步（并发的两个要素） 互斥：保护临界区，防止多个进程同时进入 同步：保证进程运行的顺序合

20、理,45,同步/互斥信号量的使用方法,互斥信号量 必定成对出现：进入临界区临界区退出临界区 同步信号量 未必成对出现，依赖于同步关系的性质 同步信号量和互斥信号量的操作顺序 基本原则：互斥信号量永远紧邻临界区:同步在前，互斥在后。,46,2.4.2 信号量集,一段处理代码需要同时获取两个或多个临界资源可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，各不相让 基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(Simultaneous Wait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是

21、由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。,信号量集用于同时需要多个资源时的信号量操作；,1. AND型信号量集,AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；,47,Swait(S1, S2, , Sn)/P原语； while (TRUE) if (S1 =1 将调用进程的PC置为swait操作开头 ,48,Ssignal(S1, S2, , Sn) for (i = 1; i = n; +i) +Si;/释放占用的资源； for (each process P waiting in Si.L) /检查每种资源的等待队列的所

22、有进程； 从等待队列Si.L中取出进程P; 进程P进入就绪队列; ,需要注意： 原先处于阻塞状态的进程，被唤醒后，从何处开始执行？ 与 记录型信号量机制有何不同？,49,2. 一般“信号量集”,一次需要N个某类临界资源时，就要进行N次wait操作低效又可能死锁 基本思想：在AND型信号量集的基础上进行扩充：进程对信号量Si的测试值为ti（用于信号量的判断，即Si = ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si = Si - di和Si = Si + di） Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1;

23、 .; Sn, dn);,一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；,50,一般信号量集的几种特定情况： Swait(S, d, d)表示每次申请d个资源，当少于d个时，便不分配； Swait(S, 1, 1)表示互斥信号量； Swait(S, 1, 0)作为一个可控开关 当S=1时，允许多个进程进入临界区； 当S=0时，禁止任何进程进入临界区； 一般信号量集未必成对使用Swait和Ssignal：如：一起申请，但不一起释放；,51,1. 生产者消费者问题(the producer-consumer problem),问题描述：若干进程通过有

24、限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,52,生产者消费者问题 AND型信号量,若不愿意考虑wait操作的先后顺序，也可用AND型信号量来实现。 生产者进程中： 用Swait(empty,mutex)代替wait(empty)和wait(mutex), 用Ssignal(mutex,full)代替signal(mutex)和signal(full) 消费者进程中 用Swait(full,mutex)代替wait(full)和wait(mutex), 用Ssignal(mutex,empty)代替

25、signal(mutex)和signal(empty),53,2. 读者写者问题(the readers-writers problem),问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个 “读写”互斥， “写写”互斥， 读读允许,54,采用信号量机制： Wmutex表示允许写，初值是1。 公共变量Rcount表示“正在读”的进程数，初值是0； Rmutex表示对Rcount的互斥操作，初值是1。,55,采用一般信号量集机制：问题增加一个限制条件：同时读的读者最多R个 Wmutex表示允许写，初值是1 Rcount表示允许读者数目，初值为R,56,3. 哲学

26、家进餐问题(the dining philosophers problem),问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；,57,58,1.利用记录型信号量机制解决 2.利用AND型信号量机制解决,2.4.2哲学家就餐问题,59,哲学家就餐问题,问题分析： 筷子是临界资源：每根有多于一个哲学家要用，而且同时只能有一个哲学家使用 5根筷

27、子可以用5个信号量表示。形成信号量数组： var chopstick:array0,4of semaphore； 所有信号量初值为1，表示未被使用。,60,哲学家就餐问题,第i位哲学家的活动描述为： Repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1)mod 5); think; Until false;,parbegin philosopher (0)； philosopher (1)； philosopher (2)； philosopher (3

28、)； philosopher (4)； parend,61,哲学家就餐问题,可能产生死锁： 五位哲学家同时饥饿，各自拿起左边的筷子时，会使得所有信号量的值为0，再试图拿起右边的筷子时，都将拿不到筷子。 解决死锁的方法： 至多允许四个哲学家同时进餐。 仅当哲学家的左右两支筷子均可用时，才进餐。（用AND信号量机制解决哲学家进餐问题。） 奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子。,62,AND型信号量机制解决哲学家就餐问题,要求哲学家同时获得两根筷子，否则一根也不拿。 var chopstick:array0,4of semaphore:=(1,1,1,1,1); Repeat th

29、ink; Sswait(chopstick(I+1)mod 5),chopstickI); Eats; Ssignal(chopstick(I+1)mod 5),chopstickI); until false;,63,思考： 用其余两种思路，怎样解决哲学家就餐问题？,64,经典问题：睡眠理发师问题,问题描述 一把理发椅，N把等待座位 理发师为理发椅上的顾客理发，没有顾客就在理发椅上睡觉 有一个顾客时需要叫醒理发师 多个顾客时需要在等待座位上等候,进程通信,65,管程(monitor),用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机

30、制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。,66,1. 信号量同步的缺点,同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏） 易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序； 不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局； 正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；,67,2. 管程的引入,1973年，Hoare和Hanson所提出；其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。 管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过