第三章并发进程

1、广州商学院计算机系广州商学院计算机系 kyykyyn3.1 并发进程并发进程 n3.2 临界区管理临界区管理 n3.3 信号量与信号量与PV操作操作 n3.4 管程管程 n3.5 进程通信进程通信 n3.7 死锁死锁 第第3 3章章 并发进程并发进程 广州商学院计算机系广州商学院计算机系 kyykyyn3.1.1顺序程序设计顺序程序设计n3.1.2并发程序设计并发程序设计n3.1.3进程的交互进程的交互：竞争和协作竞争和协作3.1 并发进程并发进程 广州商学院计算机系广州商学院计算机系 kyykyy3.1.1顺序程序设计顺序程序设计n程序执行的顺序性程序执行的顺序性n程序在处理器上执行时严格有

2、序的，即只有当一个操作程序在处理器上执行时严格有序的，即只有当一个操作结束后，才能开始后继操作，这称为结束后，才能开始后继操作，这称为程序内部的顺序性程序内部的顺序性n如果完成一个任务需要若干个不同的程序，这些不同程如果完成一个任务需要若干个不同的程序，这些不同程序在时间上按调用次序严格有序执行，这称为序在时间上按调用次序严格有序执行，这称为程序外部的程序外部的顺序性顺序性n传统的程序设计方法是顺序程序设计传统的程序设计方法是顺序程序设计, ,即把一个程序设计即把一个程序设计成一个顺序执行的程序模块，不同程序也是按序执行的成一个顺序执行的程序模块，不同程序也是按序执行的广州商学院计算机系广州商

3、学院计算机系 kyykyy顺序程序设计的特点顺序程序设计的特点n执行的顺序性执行的顺序性n环境的封闭性环境的封闭性n结果的确定性结果的确定性n过程的可再现性过程的可再现性广州商学院计算机系广州商学院计算机系 kyykyy3.1.2 并发程序设计并发程序设计n1.程序并发执行程序并发执行n进程的并发性进程的并发性:一组进程的执行在时间上是重叠的一组进程的执行在时间上是重叠的n所谓执行在时间上是重叠的所谓执行在时间上是重叠的，是指一个进程执行的第一条，是指一个进程执行的第一条指令是在另指令是在另一个进程执行的最后一条指令完成之前开始的一个进程执行的最后一条指令完成之前开始的n例如：有两个进程例如：

4、有两个进程A和和B，进程进程A执行操作执行操作a1、a2、a3，进程进程B执行操作执行操作b1、b2、b3n进程进程A和和B顺序（串行）执行的情况：在单处理器上，顺序（串行）执行的情况：在单处理器上，进程进程A执行完，进程执行完，进程B才开始执行，它们的操作次序为：才开始执行，它们的操作次序为：a1、a2、a3、b1、b2、b3n进程进程A和和B并发执行的一种情况：在单处理器上，进程并发执行的一种情况：在单处理器上，进程A和和B交替（交叉）执行，它们交替（交叉）执行的操作交替（交叉）执行，它们交替（交叉）执行的操作次序可能为：次序可能为：a1、b1、b2、a2、a3、b3广州商学院计算机系广州

5、商学院计算机系 kyykyy进程进程的并发性的并发性n从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上处于运行还未运行结束的状态n从微观上看，任一时刻仅有一个进程在处理器上运行n并发的实质是一个处理器在几个进程之间的多路复用n并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率 n在采用多道程序设计的系统中，利用了处理器与外围设备、外围设备与外围设备之间的并行工作能力，提高了计算机的工作效率。广州商学院计算机系广州商学院计算机系 kyykyy进程进程的并发性的并发性( (续续) )n例如：程序例如：程序P=while(ICount) input

6、(dataI，process dataI，output dataI )对一批数据（对一批数据（Count组）进行处理组）进行处理nInput涉及对输入设备的操作涉及对输入设备的操作nprocess涉及处理器的计算工作涉及处理器的计算工作noutput涉及对输出设备的操作涉及对输出设备的操作n程序的编制决定了程序的执行一次仅能操作一台物理设备，设程序的编制决定了程序的执行一次仅能操作一台物理设备，设备之间存在等待现象，循环迭代一次仅能处理一组数据备之间存在等待现象，循环迭代一次仅能处理一组数据n程序程序P属于串行执行的程序属于串行执行的程序 广州商学院计算机系广州商学院计算机系 kyykyy进程

7、进程的并发性的并发性( (续续) )n若对这个计算问题改用三个程序来实现：（若对这个计算问题改用三个程序来实现：（I=J=K=1）n输入程序输入程序PI：while(ICount) input(dataI+)，sendn计算程序计算程序PC：while(JCount) receive，process(dataJ+)，sendn输出程序输出程序PO：while(K=1) a1 = a1-1; /售出一张票售出一张票 n = a1; a2 = n /n表示剩余的票数表示剩余的票数if (a2=1) a2 = a2-1; /售出一张票售出一张票 n = a2; 因为这种错误和相对执因为这种错误和相对

8、执行速度有关，因此称为行速度有关，因此称为与时间有关的错误。与时间有关的错误。服务器服务器售票员售票员A售票员售票员B与时间有关的错误与时间有关的错误- -结果不唯一结果不唯一广州商学院计算机系广州商学院计算机系 kyykyy与时间有关的错误与时间有关的错误 - -永远等待永远等待 例：内存管理问题：有例：内存管理问题：有2个并发进程个并发进程borrow和和return分别负责申分别负责申请和归还主存资源，下面算法中，请和归还主存资源，下面算法中，x表示现有空闲主存容量，表示现有空闲主存容量，B表示申请或归还的主存量。并发进程的算法及执行描述如下：表示申请或归还的主存量。并发进程的算法及执行

9、描述如下： void borrow (int B) while（BX） 进程进入等待队列等主存资源进程进入等待队列等主存资源 X=X-B; 修改主存分配表，进程获得主存资源修改主存分配表，进程获得主存资源;void return (int B) X=X+B; 修改主存分配表修改主存分配表 释放等主存资源的进程释放等主存资源的进程 int X=memory;cobeginrepeat borrow(B);repeat return (B);coend广州商学院计算机系广州商学院计算机系 kyykyy3.1.3 进程的交互进程的交互：竞争和协作竞争和协作n1.并发进程之间的竞争关系并发进程之间的竞

10、争关系n系统中的多个进程之间彼此无关，相互并不知道其它进程的系统中的多个进程之间彼此无关，相互并不知道其它进程的存在，相互之间并不交换信息。但是由于这些进程共用了一存在，相互之间并不交换信息。但是由于这些进程共用了一套计算机系统资源，因而必然产生竞争资源的问题，一个进套计算机系统资源，因而必然产生竞争资源的问题，一个进程的执行可能影响到同其竞争资源的其它进程。操作系统必程的执行可能影响到同其竞争资源的其它进程。操作系统必须协调好诸进程对资源的争用。一旦一个进程要使用已分配须协调好诸进程对资源的争用。一旦一个进程要使用已分配给另一个进程的资源，则该进程必须等待给另一个进程的资源，则该进程必须等待

11、n2.并发进程之间的协作关系并发进程之间的协作关系n某些进程为完成同一任务需要分工协作，由于合作的每一个进某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当协作进程中的一个到达程在某些协调点上协调各自的工作。当协作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后才被唤醒并塞自己，直到其他合作进程发来协调信号或消息后才被唤醒并继续执行

12、。这种协作进程之间相互等待对方消息或信号的协调继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步关系称为进程同步广州商学院计算机系广州商学院计算机系 kyykyy竞争（互斥）关系定义：当多个进程因为争夺临界资源而互斥执行称为进程的互斥。临界资源：也称独占资源，是指在一段时间内只允许一个进程访问的资源。例如打印机，磁带机，也可以是进程共享的数据、变量等。广州商学院计算机系广州商学院计算机系 kyykyy竞争关系竞争关系 n资源竞争产生两个问题： n一个是死锁(Deadlock)问题，就是一组进程如果都获得了部分资源，还想要得到其他进程所占用的资源，最终所有进程都将陷入死锁n一

13、个是饥饿(Starvation) 问题，是指一个进程由于其它进程总是优先于它而被无限期拖延n既要解决饥饿问题，又要解决死锁问题。广州商学院计算机系广州商学院计算机系 kyykyy协作（同步）关系data定义：进程之间这种相互合作、协同工作的关系称为进程的同步。简单说来就是：多个相关进程在执行次序上的协调。广州商学院计算机系广州商学院计算机系 kyykyy实例实例有有2 2个进程个进程P1P1、P2P2，其中，其中P1P1是计算进程，是计算进程，P2P2是打印进程，每当是打印进程，每当P1P1计算出一个结果以后，将计算结果送到缓冲区，以便计算出一个结果以后，将计算结果送到缓冲区，以便P2P2进程

14、进程从中取出数据打印。假设缓冲区被划分为从中取出数据打印。假设缓冲区被划分为0 0、1 1、2k-12k-1共共k k个个单元。还设置了两个指针：单元。还设置了两个指针：inin指针用于计算进程存放数据，指指针用于计算进程存放数据，指向缓冲区下一个空闲的单元；向缓冲区下一个空闲的单元；outout指针用于打印进程取数据，指针用于打印进程取数据，指向缓冲区下一个将要取走数据单元。指向缓冲区下一个将要取走数据单元。.0 1 2 3 4 5 6 7 8 9 k-1inout广州商学院计算机系广州商学院计算机系 kyykyyn3.2.1 互斥与临界区互斥与临界区n3.2.2 临界区管理的尝试临界区管理

15、的尝试n3.2.3 实现临界区管理的软件方法实现临界区管理的软件方法n3.2.4 实现实现临界区管理的硬件设施临界区管理的硬件设施 3.2 临界区管理临界区管理 广州商学院计算机系广州商学院计算机系 kyykyya1 = n /n表示剩余的票数表示剩余的票数if (a1=1) a1= a1-1; /售出两张票售出两张票 n = a1; a2 = n /n表示剩余的票数表示剩余的票数if (a2=1) a2 = a2-1; /售出一张票售出一张票 n = a2; 服务器服务器售票员售票员A售票员售票员B临界资源临界资源临界区：与临界资源操作相临界区：与临界资源操作相关的程序段。关的程序段。3.2

16、.1互斥与临界区互斥与临界区广州商学院计算机系广州商学院计算机系 kyykyyn与同一变量有关的临界区分散在各进程的程序段中，与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知而各进程的执行速度不可预知n如果能保证进程在临界区执行时，不让另一个进程进如果能保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误不会造成与时间有关的错误 广州商学院计算机系广州商学院计算机系 kyykyy临界区的调度原则临界区的调度原则 n一次至多允许一个进程进入临界区内；一次至多允许一个进程

17、进入临界区内；n如果已有进程在临界区中，试图进入此临界区的其他进程应如果已有进程在临界区中，试图进入此临界区的其他进程应等待；等待；n进入临界区的进程应在有限时间内退出，以便让等待队列中进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入的一个进程进入n临界区调度原则可总结成三句话：临界区调度原则可总结成三句话：互斥使用互斥使用、有空让进有空让进；忙忙则等待则等待、有限等待；择一而入、有限等待；择一而入、让权等待让权等待、算法可行。、算法可行。n算法可行是指不能因为所选的调度策略造成进程饥饿甚至算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁死锁 。广州商学院计算机系广州商

18、学院计算机系 kyykyy3.2.2 临界区管理的尝试临界区管理的尝试n下面的程序是采用标志方法实现互斥的一种尝试 boolean inside1 = false; /* P1不在其临界区内不在其临界区内 */boolean inside2 = false; /* P2不在其临界区内不在其临界区内 */cobeginprocess P1 while inside2 do ;inside1 = true;临界区临界区;inside1 = false;coendprocess P2 while inside1 do ;inside2 = true;临界区临界区; ;inside2 = false;

19、 广州商学院计算机系广州商学院计算机系 kyykyy临界区管理的尝试临界区管理的尝试( (续续) ) n下面是第二个尝试：boolean inside1 = false; /* P1不在其临界区内不在其临界区内 */boolean inside2 = false; /* P2不在其临界区内不在其临界区内 */cobeginprocess P1 inside1 := true;while inside2 do ;临界区临界区;inside1 := false; coend process P2 inside2 := true; while inside1 do ; 临界区临界区; inside2

20、 := false; ;广州商学院计算机系广州商学院计算机系 kyykyy进程交替进入临界区。当进程交替进入临界区。当turn=0时，时，P1必须等待必须等待P0进入临进入临界区执行，退出后，才能进入临界区；即使此时临界区空闲，界区执行，退出后，才能进入临界区；即使此时临界区空闲，不符合空闲让进不符合空闲让进任何进程在临界区内或外失败，其它进程将可能因为等待任何进程在临界区内或外失败，其它进程将可能因为等待使用临界区而无法向前推进使用临界区而无法向前推进广州商学院计算机系广州商学院计算机系 kyykyyprocess P0 inside0=true; turn=1; while (inside

21、1 & turn=1)do nothing; 临界区临界区; inside0=false;boolean inside 2 ;int turn = 0 or 1; inside0=false;inside1=false; cobegin coendprocess P1 inside1=true; turn=0; while (inside0 & turn=0) do nothing; 临界区临界区; inside1=false;3.2.3 实现临界区管理的软件方法实现临界区管理的软件方法Peterson算法 广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的软件

22、方法实现临界区管理的软件方法 ( (续续) )n当一个进程没有意图进入临界区时，另一个进程可以当一个进程没有意图进入临界区时，另一个进程可以立即进入临界区。当两个进程都想进入临界区时，如立即进入临界区。当两个进程都想进入临界区时，如果果turn=i，则只有第，则只有第i个进程可以进入临界区。一次只个进程可以进入临界区。一次只有一个进程可以进入临界区，因为在该进程退出之前有一个进程可以进入临界区，因为在该进程退出之前turn的值是不会改变的的值是不会改变的n该算法虽然能解决互斥问题但是算法复杂难以理解该算法虽然能解决互斥问题但是算法复杂难以理解n忙等忙等广州商学院计算机系广州商学院计算机系 ky

23、ykyy3.2.4 实现临界区管理的硬件设施实现临界区管理的硬件设施 n使用软件方法实现进程互斥使用临界资源是很困难的，使用软件方法实现进程互斥使用临界资源是很困难的，他们通常能实现两个进程之间的互斥，很难控制多个他们通常能实现两个进程之间的互斥，很难控制多个进程的互斥进程的互斥n程序设计时应该非常注意，否则就会产生死锁和不能程序设计时应该非常注意，否则就会产生死锁和不能解决互斥解决互斥n软件方法始终不能解决忙等，系统效率不高软件方法始终不能解决忙等，系统效率不高n用来实现互斥的硬件设施主要有：关中断、测试并建用来实现互斥的硬件设施主要有：关中断、测试并建立指令、对换指令立指令、对换指令广州商

24、学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区管理的硬件设施 ( (续续) ) n1.关中断关中断 n关中断是实现互斥的最简单方法之一关中断是实现互斥的最简单方法之一n进程在测试标志之前，首先关中断，直到测试完并设置标进程在测试标志之前，首先关中断，直到测试完并设置标志之后才开中断志之后才开中断n进程在临界区执行期间，计算机系统不响应中断进程在临界区执行期间，计算机系统不响应中断n因此，不会转向调度，也就不会引起进程或线程切换，正因此，不会转向调度，也就不会引起进程或线程切换，正在执行标志测试和设置的进程或线程不会被打断，从而保在执行标志测试和设置的进程或线程不

25、会被打断，从而保证了互斥证了互斥 广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区管理的硬件设施 ( (续续) )n关中断方法的缺点：关中断方法的缺点：n关中断时间过长会影响系统效率，限制处理器交叉关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力执行程序的能力n关中断方法也不适用于多关中断方法也不适用于多CPU系统，因为，在一个系统，因为，在一个处理器上关中断，并不能防止进程在其他处理器上处理器上关中断，并不能防止进程在其他处理器上执行相同临界区代码执行相同临界区代码广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界

26、区管理的硬件设施 ( (续续) ) n2. 测试并建立指令（专用的机器指令）测试并建立指令（专用的机器指令）n硬件提供的测试并建立指令的执行过程如下：硬件提供的测试并建立指令的执行过程如下： nTS(x): 若若x=true，则则x=false；return true；否则否则 return false； nTS指令管理临界区时，可把一个临界区与一个布尔变指令管理临界区时，可把一个临界区与一个布尔变量量s相连，由于变量相连，由于变量s代表了临界资源的状态，可把它代表了临界资源的状态，可把它看成一把锁看成一把锁 广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区

27、管理的硬件设施 ( (续续) )n用用TS指令实现临界区管理（互斥）的算法如下：指令实现临界区管理（互斥）的算法如下： boolean s = true;/没有进程在临界区内没有进程在临界区内process Pi () /* i = 1,2,n */ while(! TS(s)；/上锁上锁 临界区临界区; s = true； /开锁开锁 广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区管理的硬件设施 ( (续续) )n3.对换指令对换指令 n对换（对换（Swap）指令的功能是交换两个字的内容，处理过指令的功能是交换两个字的内容，处理过程如下：程如下： voi

28、d Swap (boolean &a, boolean &b) temp=a; a=b; b=temp;n在在Intel 80 x86中，对换指令称为中，对换指令称为XCHG指令指令广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区管理的硬件设施 ( (续续) )n用对换指令实现进程互斥的程序如下：用对换指令实现进程互斥的程序如下： boolean lock ;lock = false;/无进程在临界区无进程在临界区process Pi () /* i = 1,2,n */ boolean keyi= true; doSwap(keyi,loc

29、k); /上锁上锁while(keyi);临界区；临界区；Swap(keyi,lock); /开锁开锁广州商学院计算机系广州商学院计算机系 kyykyy实现临界区管理的硬件设施实现临界区管理的硬件设施 ( (续续) )n导致饥饿：临界区空闲时，执行循环检测的若干进程能进入临界区的几率是相等的，有的进程可能运气很不好，很难有机会进入临界区，因而饥饿n软件方法和硬件方法都存在忙等问题，浪费了处理器的时间n不会成为一种通用的方法广州商学院计算机系广州商学院计算机系 kyykyyn3.3.1同步与同步机制n3.3.2信号量与PV操作n3.3.3信号量实现互斥n3.3.4信号量解决5位哲学家吃通心面问题

30、n3.3.5信号量解决生产者-消费者问题n3.3.6信号量解决读者-写者问题n3.3.7信号量解决理发师问题3.3 3.3 信号量及其操作信号量及其操作 广州商学院计算机系广州商学院计算机系 kyykyy3.3.1 同步与同步机制同步与同步机制n著名的生产者著名的生产者-消费者问题是计算机操作系统中并发进消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决而消费者进程可以是打印进程

31、、接收进程等等。解决好生产者好生产者-消费者问题就解决好了一类并发进程的同步消费者问题就解决好了一类并发进程的同步问题问题 n生产者生产者-消费者问题表述：有一环形缓冲池，包含消费者问题表述：有一环形缓冲池，包含k个个缓冲区（缓冲区（0k-1）。）。有两类进程：一组生产者进程和一有两类进程：一组生产者进程和一组消费者进程，生产者进程向空的缓冲区中放产品，组消费者进程，生产者进程向空的缓冲区中放产品，消费者进程从满的缓冲区中取走产品消费者进程从满的缓冲区中取走产品 广州商学院计算机系广州商学院计算机系 kyykyy生产者生产者- -消费者必须同步消费者必须同步.0 1 2 3 4 5 6 7 8

32、 9 k-1inout.0 1 2 3 4 5 6 7 8 9 k-1inout生产者不能向满缓冲区写数据，消费者不能从空缓冲区生产者不能向满缓冲区写数据，消费者不能从空缓冲区取数据，即生产者与消费者必须同步取数据，即生产者与消费者必须同步广州商学院计算机系广州商学院计算机系 kyykyy同步与同步机制同步与同步机制 ( (续续) ) n生产者进程和消费者进程共享下面的变量生产者进程和消费者进程共享下面的变量int k ;typedef anyitem item;item buffer k ;/所有生产者进程和消费者进程共享所有生产者进程和消费者进程共享bufferint in , out,

33、counter;/所有生产者进程共享变量所有生产者进程共享变量in/所有消费者进程共享变量所有消费者进程共享变量out/所有生产者进程和消费者进程共享所有生产者进程和消费者进程共享counter广州商学院计算机系广州商学院计算机系 kyykyy 生产者进程：生产者进程：process producer (void) while(true) produce an item in nextp ;if (counter = k) sleep(producer) ;bufferin = nextp ;in = （in + 1）%k；counter = counter + 1 ;if(counter=1

34、)wakeup(consumer); 消费者进程：消费者进程：process consumer(void)While(true)if (counter = 0) sleep(consumer);nextc = bufferout ;out = （ out + 1）%k；counter = counter - 1 ;if(counter=k-1)wakeup(producer)consume the item in nextc; 广州商学院计算机系广州商学院计算机系 kyykyy同步与同步机制同步与同步机制 ( (续续) )n出现错误结果的原因在于各个进程访问缓冲区的速率不同，要得到正确结果，需

35、要调整并发进程的速度，这需要通过在进程间交换信号或消息来调整相互速率，达到进程协调运行的目的。这种协调过程称为进程同步n操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成n常用的同步机制有：n信号量与PV操作n管程n消息传递 广州商学院计算机系广州商学院计算机系 kyykyy3.3.2 信号量与信号量与PV操作操作n1.前面种种方法解决临界区调度问题的缺点前面种种方法解决临界区调度问题的缺点 n1)对不能进入临界区的进程，采用忙等测试法，浪费对不能进入临界区的进程，采用忙等测试法，浪费CPU时间时间n2)将测试能否进入临界区的责任推给各个竞争的进程会削将测试能否进入临界区的责任推给各

36、个竞争的进程会削弱系统的可靠性，加重了用户编程负担弱系统的可靠性，加重了用户编程负担 n2.信号量同步机制的提出信号量同步机制的提出 n1965年荷兰计算机科学家年荷兰计算机科学家E.W.Dijkstra提出了新的同步工具提出了新的同步工具-信信号量和号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收到一个对互。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是

37、信号量应的特殊变量值，这种特殊变量就是信号量(Semaphore)。进程进程可以使用可以使用P、V两个特殊操作来发送和接收信号两个特殊操作来发送和接收信号 广州商学院计算机系广州商学院计算机系 kyykyy广州商学院计算机系广州商学院计算机系 kyykyy信号量与信号量与PV操作（续操作（续）n起信号灯作用的变量称为信号量起信号灯作用的变量称为信号量n操作系统中，信号量是用来表示物理资源的实体操作系统中，信号量是用来表示物理资源的实体,信信号量是一种软资源号量是一种软资源n除赋初值外，信号量仅能由同步原语除赋初值外，信号量仅能由同步原语P、V操作对其操作对其进行操作。进行操作。nP、V操作的不

38、可分割性确保执行时的原子性及信号操作的不可分割性确保执行时的原子性及信号量值的完整性。量值的完整性。n利用信号量和利用信号量和P、V操作既可以解决并发进程的竞争操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题问题，又可以解决并发进程的协作问题广州商学院计算机系广州商学院计算机系 kyykyy一般信号量一般信号量结构型信号量结构型信号量 typedef struct semaphore int value;/可用资源数可用资源数struct pcb *list ;/阻塞队列阻塞队列void P(semaphore &s)s. value- ; /信号量值减一信号量值减一if

39、 (s . value 0) sleep (s. list) ;/若信号量值小于若信号量值小于0， 阻塞当前进程。阻塞当前进程。void V (semaphore &s)s . value + ; /信号量值加一信号量值加一 if (s . value 0) wakeup(s. list) ;/若信号量值小于等于若信号量值小于等于0， /唤醒唤醒s. list 中一个进程。中一个进程。广州商学院计算机系广州商学院计算机系 kyykyyP P、V V操作的应用操作的应用 用用P P操作和操作和V V操作实现同步与互斥。操作实现同步与互斥。s.values.value初值表示初值表示系统中

40、某类资源的数目。进程进入临界区之前，首先系统中某类资源的数目。进程进入临界区之前，首先执行执行P P操作原语，若操作原语，若s.value0,s.value0,则进程调用则进程调用sleep()sleep()内内核函数，将自己阻塞，并插入到核函数，将自己阻塞，并插入到s.lists.list队列排队。所队列排队。所以如果以如果s.value0s.value0，|s.value|s.value|表该信号量链表中已阻表该信号量链表中已阻塞进程的数目。当其它进程执行了塞进程的数目。当其它进程执行了V V操作原语，若操作原语，若s.value=0s.value=0，说明阻塞队列中还有被阻塞的进程，则，

41、说明阻塞队列中还有被阻塞的进程，则调用调用wakeup()wakeup()内核函数，把内核函数，把s.lists.list中第一进程修改为中第一进程修改为就绪状态，送到就绪队列，准备执行临界区代码。就绪状态，送到就绪队列，准备执行临界区代码。广州商学院计算机系广州商学院计算机系 kyykyypropgram mutualexclusion;propgram mutualexclusion;int n=.;/int n=.;/* *进程数进程数* */ /semaphore mutex=1;/semaphore mutex=1;/* *定义信号量定义信号量mutexmutex， mutex.va

42、lue mutex.value初始化为初始化为1 1* */ /cobegincobeginprocess Pi()/i=1,2,nprocess Pi()/i=1,2,n P(mutex); P(mutex); ; V(mutex); V(mutex); ;coendcoendvoid P(semaphore &s)s. value- ; if (s . value =0时，时， s. value值表示还可以执行值表示还可以执行P而不会而不会被阻塞的进程数，每执行一次被阻塞的进程数，每执行一次P就意味着一次分配一个单位就意味着一次分配一个单位的资源的资源n推论推论2：当：当 s. v

43、alue0，表示没有可用资源，请求该资源的进，表示没有可用资源，请求该资源的进程被阻塞。程被阻塞。 s. value的绝对值表示被阻塞的进程数，执行一的绝对值表示被阻塞的进程数，执行一次次V就意味着释放一个资源。若就意味着释放一个资源。若s. value0表示还有被阻塞的表示还有被阻塞的进程，需要唤醒一个被阻塞的进程，使他到就绪队列中排队进程，需要唤醒一个被阻塞的进程，使他到就绪队列中排队n推论推论3：通常，：通常，P操作意味着请求一个资源，操作意味着请求一个资源，V操作意味着释操作意味着释放一个资源；特定条件下放一个资源；特定条件下P操作代表阻塞进程的操作，操作代表阻塞进程的操作，V操操作代

44、表唤醒被进程的操作。作代表唤醒被进程的操作。广州商学院计算机系广州商学院计算机系 kyykyy信号量的分类信号量的分类 n信号量按其用途分为两种：信号量按其用途分为两种： n公用信号量：初值常常为公用信号量：初值常常为1，用来实现进程间的互斥。相，用来实现进程间的互斥。相关进程均可对其执行关进程均可对其执行P、V操作操作 n私有信号量：初值常常为可用资源数，多用来实现进程私有信号量：初值常常为可用资源数，多用来实现进程同步。拥有该信号量的一类进程可以对其执行同步。拥有该信号量的一类进程可以对其执行P操作，而操作，而另一类进程可以对其执行另一类进程可以对其执行V操作操作 n信号量按其取值分为两种

45、：信号量按其取值分为两种： n二元信号量：仅取二元信号量：仅取0和和1 ，主要用于解决进程互斥问，主要用于解决进程互斥问题题n一般信号量：允许取值为非负整数，主要用于解决进一般信号量：允许取值为非负整数，主要用于解决进程同步问题程同步问题广州商学院计算机系广州商学院计算机系 kyykyy信号量的应用信号量的应用n我们将分析这样几个经典进程的同步问题：我们将分析这样几个经典进程的同步问题：n（1）哲学家进餐问题）哲学家进餐问题n（2）读者）读者-写者问题写者问题n（3）生产者）生产者-消费者问题消费者问题n（4）理发师问题）理发师问题广州商学院计算机系广州商学院计算机系 kyykyy3.3.4

46、哲学家进餐问题哲学家进餐问题n五位哲学家围坐一张圆桌，桌上放五根筷子，每位哲学家只能拿起与他相邻的两根筷子吃饭n哲学家的生活方式是交替地进行思考和进餐 哲学家筷子0011223344广州商学院计算机系广州商学院计算机系 kyykyy哲学家进餐问题（续）哲学家进餐问题（续）n1 .利用结构型信号量解决哲学家进餐问题利用结构型信号量解决哲学家进餐问题 n数据结构：每根筷子都是一个临界资源，都应定义一个信数据结构：每根筷子都是一个临界资源，都应定义一个信号量，为五根筷子定义一个信号量数组，每个信号量的初号量，为五根筷子定义一个信号量数组，每个信号量的初值为值为1n算法分析：算法分析：n若每个哲学家都

47、各自拿起他左边的一根筷子，然后再去拿若每个哲学家都各自拿起他左边的一根筷子，然后再去拿他右边的筷子时，将都拿不到右边的筷子，大家又都不会他右边的筷子时，将都拿不到右边的筷子，大家又都不会放下手中的筷子，大家在相互等待别人释放筷子，系统于放下手中的筷子，大家在相互等待别人释放筷子，系统于是进入死锁状态是进入死锁状态 广州商学院计算机系广州商学院计算机系 kyykyyn操作描述：第i位哲学家的活动如下： Semaphore fork5;for (int i=0;i5;i+) forki.value=1; cobeginProcess philosopher_i() while(true) thin

48、k();P(fork i );P(fork (i+1) mod 5);eating ;V(fork i );V(fork (i+1)mod 5); coend哲学家筷子0011223344广州商学院计算机系广州商学院计算机系 kyykyy哲学家进餐问题（续）哲学家进餐问题（续）n死锁问题解决方案：死锁问题解决方案： n1）至多允许有四位哲学家同时去拿左边的筷子，最终）至多允许有四位哲学家同时去拿左边的筷子，最终保证至少有一位哲学家能够进餐，（至多可以有两位哲保证至少有一位哲学家能够进餐，（至多可以有两位哲学家能够进餐）学家能够进餐）n2）规定奇数号哲学家先拿他左边的筷子，然后再去拿）规定奇数号

49、哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家先拿他右边的筷子，然后再右边的筷子；偶数号哲学家先拿他右边的筷子，然后再去拿左边的筷子去拿左边的筷子n3)每个哲学家取到手边的两把筷子才开始进餐，否则一每个哲学家取到手边的两把筷子才开始进餐，否则一根也不要根也不要 广州商学院计算机系广州商学院计算机系 kyykyy3.3.5多缓冲区多缓冲区生产者生产者- -消费者问题消费者问题n对于对于m个生产者和个生产者和n个消费者，它们共享可存放个消费者，它们共享可存放k件产件产品的缓冲区品的缓冲区n操作要求：多个生产者进程之间、多个消费者进程之操作要求：多个生产者进程之间、多个消费者进程之间、生

50、产者进程与消费者进程之间均能正确同步间、生产者进程与消费者进程之间均能正确同步广州商学院计算机系广州商学院计算机系 kyykyy生产者生产者/ /消费者必须同步消费者必须同步.0 1 2 3 4 5 6 7 8 9 k-1inout.0 1 2 3 4 5 6 7 8 9 k-1inout广州商学院计算机系广州商学院计算机系 kyykyy生产者生产者/ /消费者必须互斥消费者必须互斥.0 1 2 3 4 5 6 7 8 9 k-1inoutP1将计算出来的数据放将计算出来的数据放入入in指针指向的指针指向的6号单号单元，然后将元，然后将in指向下个指向下个空闲单元空闲单元-7号单元。号单元。P

51、2将计算出来的数据将计算出来的数据放入放入in指针指向的指针指向的7号单元，号单元，P2被中断。被中断。P1将计算出来的数据将计算出来的数据放入放入in指针指向的指针指向的7号单元，覆盖了号单元，覆盖了P2存存放的数据，出错！放的数据，出错！广州商学院计算机系广州商学院计算机系 kyykyy生产一条数据生产一条数据是否有空是否有空存储单元存储单元是否可用是否可用存入一条数据存入一条数据归还使用权归还使用权数据单元加数据单元加1，唤醒一个消费者，唤醒一个消费者等待资源，等待资源，阻塞阻塞被唤醒被唤醒等待使用权，等待使用权，阻塞阻塞被唤醒被唤醒无无否否有有是是生产者生产者 消费者消费者空空单元加单

52、元加1，唤醒一个生产者，唤醒一个生产者是否有数是否有数据单元据单元是否可用是否可用取走一条数据取走一条数据归还使用权归还使用权消费数据消费数据等待资源，等待资源，阻塞阻塞被唤醒被唤醒等待使用权，等待使用权，阻塞阻塞被唤醒被唤醒无无否否有有是是广州商学院计算机系广州商学院计算机系 kyykyy生产者生产者- -消费者问题消费者问题n1.1.利用记录型信号量解决生产者利用记录型信号量解决生产者-消费者问题消费者问题 n数据结构：数据结构： n1 1）含有）含有k k个缓冲区的公用缓冲池个缓冲区的公用缓冲池n2 2）互斥）互斥信号量信号量mutex：实现诸进程对缓冲池的互斥使用，实现诸进程对缓冲池的

53、互斥使用，一次仅允许一个进程读或写公用缓冲池，初值为一次仅允许一个进程读或写公用缓冲池，初值为1n3）资源信号量）资源信号量empty：记录空缓冲区个数，初值为记录空缓冲区个数，初值为kn4）资源信号量资源信号量full：记录满缓冲区个数，初值为记录满缓冲区个数，初值为0 0n操作要求：多个生产者进程之间、多个消费者进程之操作要求：多个生产者进程之间、多个消费者进程之间、生产者进程与消费者进程之间均能正确同步间、生产者进程与消费者进程之间均能正确同步广州商学院计算机系广州商学院计算机系 kyykyyitem Bk;Semaphore empty, full, mutex;empty=k; fu

54、ll=0; mutex=1;Int in=0; out=0;cobeginprocess producer_i () while(true) produce(); P(empty); P(mutex); append to Bin; in= (in+1)%k; V(mutex); V(full);process consumer_j() while(true) P(full); P(mutex); take() from Bout; out=(out+1)%k; V(mutex); V(empty); consume();coend广州商学院计算机系广州商学院计算机系 kyykyy生产者生产者

55、- -消费者问题（续）消费者问题（续）n注意：注意：n1）在每个程序中用于互斥的）在每个程序中用于互斥的P(mutex)和和V(mutex) 必须成必须成对出现对出现n2）对资源信号量）对资源信号量empty和和full的操作也同样必须成对出现，的操作也同样必须成对出现，但它们在不同的程序中但它们在不同的程序中n3）在每个程序中的多个）在每个程序中的多个P操作顺序不能颠倒，否则容易操作顺序不能颠倒，否则容易引起死锁引起死锁 广州商学院计算机系广州商学院计算机系 kyykyy3.3.6 读者写者问题读者写者问题n该问题为多个进程访问一个共享数据区，如数据库、文件、该问题为多个进程访问一个共享数据

56、区，如数据库、文件、内存区、内存区、寄存器等数据问题建立了一个通用模型，其中读进寄存器等数据问题建立了一个通用模型，其中读进程只能读数据，写进程只能写数据。程只能读数据，写进程只能写数据。n多个多个Reader进程同时读一条数据可以的，但如果一个进程同时读一条数据可以的，但如果一个Writer进程正在更新数据时，则所有其他进程都不能访问进程正在更新数据时，则所有其他进程都不能访问（读或写）该记录。（读或写）该记录。data读者读者读者读者写者写者写者写者广州商学院计算机系广州商学院计算机系 kyykyy读者优先读者优先v当一个读者正在读数据时，另一个读者也需要读数当一个读者正在读数据时，另一个

57、读者也需要读数据，应该允许第二个读者进入，同理第三个及随后更据，应该允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。多的读者都被允许进入。v现在假设一个写者到来，由于写操作时排他的，所现在假设一个写者到来，由于写操作时排他的，所以它不能访问数据，需要阻塞等待。如果一直都有新以它不能访问数据，需要阻塞等待。如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。的读者陆续到来，写者的写操作将被严重推迟。v该方法称为该方法称为“读者优先读者优先”。即，一旦有读者正在读。即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读数据，允许多个读者同时进入读数据，只有当全部读者退出

58、，才允许写者进入写数据。者退出，才允许写者进入写数据。广州商学院计算机系广州商学院计算机系 kyykyy读者写者问题（续）读者写者问题（续）n1 1.利用记录型信号量解决读者利用记录型信号量解决读者-写者问题写者问题 n数据结构：数据结构： n1）互斥信号量）互斥信号量writeblock：用于用于Reader与与Writer、Writer与与Writer之间的互斥，初值为之间的互斥，初值为1；n2）ReadCount：正在读的进程数目，初值为正在读的进程数目，初值为0n3）互斥信号量）互斥信号量mutex：用于用于Reader与与Reader 互互斥访问整型量斥访问整型量ReadCount

59、，初值为初值为1 广州商学院计算机系广州商学院计算机系 kyykyysemaphore mutex=1 , writeblock= 1 ;int ReadCount = 0;cobeginprocess reader_i P(mutex ); if ReadCount=0 then P(writeblock); ReadCount := ReadCount + 1 ; V(mutex); 读文件读文件 ; P(mutex); ReadCount := ReadCount - 1 ; if ReadCount=0 then V(writeblock ); V(mutex); coendproce

60、ss writer_j() P(writeblock); 写文件写文件 ; V(writeblock); 广州商学院计算机系广州商学院计算机系 kyykyy3.3.7 信号量解决理发师问题信号量解决理发师问题n理发店有一位理发师、一把理发椅和理发店有一位理发师、一把理发椅和n n把供等候理把供等候理发的顾客坐的椅子。发的顾客坐的椅子。n如果没有顾客，理发师便在理发椅上睡觉。如果没有顾客，理发师便在理发椅上睡觉。n当一个顾客到来时，它必须叫醒理发师。当一个顾客到来时，它必须叫醒理发师。n如果理发师正在理发时又有顾客来到，则如果有空如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等待，否则就离开。椅子可坐，他们就坐下来等待，否则就