第4章-进程同步与通信-(2)-课件

1、进程的同步与互斥？采用多道程序设计技术的操作系统，允许多个进程同时驻留内存并发执行。？如何协调多个进程对系统资源，如内存空间、外部设备等的竞争和共享？如何解决多个进程因为竞争资源而出现执行结果异常，甚至导致系统不稳定、失败等问题。？例如，多个进程同时申请文件打印，如何有效分配打印机？例银行的联网储蓄业务允许储户同时用储蓄卡和存折对同一帐户进行存取款操作，如果某储户同时（在ATM机和营业柜台）办理两笔存款业务（假设分别为1000和2000元）从系统的角度看，有两个进程将同时对储户余额等数据进行修改。如果两个进程同时读出原余额（假设为5000元），两个进程分别将最新余额修改为6000(5000+1

2、000)和7000(5000+2000).分析及措施最后，储户余额可能是6000，或者7000，显然都不正确。原因：两个进程同时修改同一数据，而没有进行有效控制。正确的方法：如果有多个进程需要同时修改某一数据，系统必须控制，一次仅允许一个进程完成读数据，并修改数据两件事以后，才允许别的进程对同一数据的读和修改操作。例假设系统中有3个进程P1、P2、P3，其中P1和P2是计算进程，P3是打印进程，每当P1或P2计算出一个结果以后，将计算结果送到缓存区中，以便P3进程从中取出数据打印。假设缓冲区被划分为0、1、2n-1共n个单元。有两个指针：In指针用于计算进程存放数据，指向缓冲区中下一个空闲的单

3、元，Out指针用于打印进程取数据，指向缓冲区中下一个将取走数据的单元。例假设某时刻，0到3号单元空闲，4到6号单元被占用，这时候P1、P2进程都准备将数据送入缓冲区。如下多个进程同时访问共享区可能发生的情况进程P1需要向缓冲区存储数据，并知道In指针当前指向7号空闲缓冲单元。若这时进程P1的时间片用完，被中断，调度程序调度进程P2执行。P2正好也需要向缓冲区存放数据，首先获取In指针位置，同样也是7，于是，P2将数据送入7号单元，并将In指针移动一格，指向8号单元，然后继续执行其他操作。可能发生的情况当进程P1再次被调度执行时，将从上次的断点继续执行，即将数据送入7号单元（覆盖进程P2的数据）

4、，并移动In指针指向8号单元，然后继续执行其他操作。进程P3不会发现上述错误，继续从缓冲区取数据，进行打印，显然，进程P2的相应计算结果不会被打印输出。分析该例中，由于进程P1和P2共享缓冲区和位置指针，而未对这种共享进行有效控制，导致打印数据的丢失。如果控制进程P1、P2互斥地访问缓冲区和修改位置指针，将避免这种因为并发执行而导致的程序执行结果的不确定性。并发控制竞争资源当并发进程竞争使用同一资源时，它们之间就会发生冲突。如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就

5、绪队列，阻塞队列等。一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁。并发控制竞争资源进程竞争资源首先必须解决“互斥”问题，某些资源必须互斥使用，如打印机、共享变量、表格、文件等。这类资源又称为临界资源，访问临界资源的那段代码称为临界区。任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。进程互斥进入临界区阻塞队列进程进入区临界区退出区唤醒互斥使用临界资源当进程需要使用临界资源时，通过获得临界区的使用权实现的。首先，在“进入区”判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区，后来的进程通过查看临界区使用标志，知道自己不能进

6、入临界区，就进入阻塞队列，将自己阻塞。当临界区内的进程使用完毕，退出临界区时，即在“退出区”修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。互斥使用临界资源由于同一个临界资源在多个共享它的进程中将对应多个临界区，那么怎样才能保证诸进程间互斥地执行临界区呢？这就必须保证“临界区使用标志”是可被系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。临界区使用原则（也称互斥条件）每次只允许一个进程处于临界区（忙则等待）；进程只能在临界区内逗留有限时间，不得使其它进程在临界外无限期等待（有限等待）；如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）；进入临

7、界区的进程，不能在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待）不能限制进程的执行进度及处理机的数量。竞争资源可能引起死锁例如：两个进程P1、P2，竞争资源R1、R2.假设，现在P1已经占用了R1，且P2占用了R2，如果此时P1申请R2，且P2申请R1。会怎么样？结果是P1、P2双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是死锁。进程因竞争资源而死锁竞争资源饥饿假设有3个进程P1、P2、P3，每个进程都需要周期性的使用资源R。如果当前P1正在使用临界资源R，P2和P3因为等待R而阻塞。当P1退出临界区时，P2立即进入临界区执行，若P2还未退出临界区时，P1又

8、申请使用临界资源R。假设P2退出临界区后，系统将R分给了P1，然后，当R空闲时，又将其分给P2，如此反复。竞争资源饥饿使P1、P2都能正常执行，而P3被长时间饥饿。这种情况不是死锁，但是对P3不公平，也是系统应该避免的。并发控制共同协作多个进程常常需要共同修改某些共享变量、表格、文件数据库等，协作完成一些功能。必须确保它们对共享变量的修改是正确的，保证数据的完整性。共享协作同样涉及到互斥、死锁和饥饿问题，但更强调对数据的写操作必须互斥地进行。必须保证数据一致性。前面列举了银行联网储蓄的例子，除了必须保证储户余额的正确性以外，还必须使银行储蓄总余额、当日发生额、流水账等数据得到一致的修改。一般通

9、过事务处理来保证数据的一致性，可以将对储户余额、储蓄总余额、当日发生额、流水账等数据的修改放到一个临界区中，进入临界区的进程必须一次性完成对这一系列数据的修改操作。只有该进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致性。并发控制通信协作当进程进行通信合作时，各个进程之间需要建立连接，进程通信需要同步和协调，进程通信的方式很多，包括消息传递、管道、共享存储区等。通过消息传递实现进程通信时，由于没有共享资源，故无须互斥，但仍可能出现死锁和饥饿。并发控制通信协作例如，两个进程相互等待对方发来的数据而永久阻塞，即死锁。又如，3个进程P1、P2、P3，其中P1不断尝试与P2或

10、P3通信，P2和P3又不断尝试与P1通信，如果P1与P2总能成功建立连接进行通信，而P3一直阻塞等待P1，这样P3被长时间饥饿。互斥与同步的解决策略软件方法硬件方法信号量方法管程方法消息传递方法软件方法软件方法是指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互斥，无须专门的程序设计语言或操作系统的支持。实践证明，该方法很难正确控制进程间的同步与互斥，而且可能会大大地增加系统的额外开销。硬件方法为了解决软件方法存在的不足，有人提出了硬件解决方法，通过屏蔽中断或采用专门的机器指令控制同步与互斥。与软件解决方法比较，这种方法减少了系统额外开销，但由于需要太强的硬件约束条件，以及可能导致

11、进程饥饿与死锁现象，一直没有成为通用的解决方法。另一类解决方法是由操作系统，或专门的程序设计语言提供的特别支持，包括信号量方法、管程方法和消息传递方法。其中，信号量方法已经成为控制进程同步与互斥的通用方法。互斥与同步解决方法之一软件方法软件解决方法有很多种，比较有代表性的软件方法有荷兰数学家Dekker提出的Dekker算法和科学家G.L.Peterson提出的Perterson算法。为了说明设计并发程序时可能出现的典型错误，下面以Dekker算法为例，分析如何设计并改进一个互斥算法的过程。互斥与同步解决方法之一：软件方法初步设想为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区。当

12、一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。Var turn:0.1;/*共享的全局变量*/ P0 P1 While turn 0 donothing; while turn 1 do nothing; Turn:=1; turn:=0; 互斥算法：初步设想分析：初步设想保证了互斥问题1：“忙等”现象问题2：进程严格交替进入临界区。如果进程需要多次使用临界区，那么，使用临界区频率低的进程严重制约着使用临界区频率高的进程的执行进度。分析：初步设想例如，P0需要每10分钟使用一次临界区，P1需要每1分钟使用一次临界区。假设turn的初值为0，进程P0正好先请求进入临界区

13、，并成功进入临界区执行，这时，如果P1申请进入临界区，循环检测turn=0，不可以进入，只能“空”循环，等待。当P0退出临界区时，修改turn的值为1，P1循环检测到turn=1时，就可以进入临界区执行，退出临界区时，修改turn=0.分析：初步设想根据假设，P1很快又需要进入临界区，但是P0却只能在10分钟之后，按照turn规定的顺序，进入临界区执行，退出时修改turn=1.即，P1必须在临界区空闲的情况下，等待10分钟，才能使用临界区。这不符和互斥原则，降低了系统性能。分析：初步设想问题3：任何进程在临界区内或外失败，其他进程将可能因为等待使用临界区，而无法向前推进。因为两个进程相互依赖对

14、方将临界区的使用权（顺序）进行修改，一旦这种修改不能进行，对方都将因为等待临界区而无法推进。互斥与同步解决方法之一：软件方法第一次改进可以为临界区设置一个状态标志，标明临界区是否可用。当临界区空闲时，任何一个进程都能进入，但此时必须修改临界区标志为“被占用”，别的进程就不能进入临界区，当临界区使用完毕，必须修改该标志为“空闲”。这样就不再使诸进程严格交替使用临界区，而且，如果某进程在临界区外失败，也不会影响其它进程。Var flag:array0.1of boolean:false;/*共享的全局变量*/ P0 P1 While flag1 do nothing; while flag0 do

15、 nothing;Flag0:=true; flag1:=true; Flag0:=false; flag1:=false; 互斥算法：第一次改进问题：假若你是软件测试人员，请问第一次改进有没有问题？分析：第一次改进如果进程在临界区外失败，其他进程不会阻塞。问题1：“忙等”问题2：若进程在临界区内失败且相应的Flag为true，则其他进程永久阻塞。问题3：不能保证进程互斥进入临界区。互斥与同步解决方法之一：软件方法第二次改进互斥算法的第一次改进不能实现“互斥”。因为，进程首先检测到临界区状态，若“被占用”则“忙等”，否则就直接进入临界区。从而，可能出现同时进入临界区的现象。能否让进程预先表明“

16、希望进入临界区的态度”，然后，再检测临界区状态。Var flag:array0.1of boolean:false;/*共享的全局变量*/ P0 P1 Flag0:=true; flag1:=trueWhile flag1 do nothing; while flag0 do nothing; Flag0:=false; flag1:=false; 互斥算法：第二次改进分析：第二次改进假设P0需要进入临界区，首先执行flag0:=true，再执行while flag1,若P1正在占用临界区，则P0忙等；否则，P0进入临界区。但是，如果此时P1未占用临界区，而与P0几乎同时需要使用临界区。互斥与

17、同步解决方法之一：软件方法第三次改进互斥算法的第二次改进可能导致死锁，因为0、都“坚持自己的权利，执意进入临界区，且互不谦让”可以考虑，允许进程既表明需要进入临界区的“态度”，又能相互“谦让”，即首先表示自己需要使用临界区，再检测临界区的状态，若临界区“被占用”，可以等一小段时间再申请。Var flag:array0.1of boolean:false;/*共享的全局变量*/ P0 Flag0:=true;While flag1 doBegin flag0:=false; ; flag0:=true;End;Flag0:=false; P1 Flag1:=true;While flag0 do

18、Begin flag1:=false; ; flag1:=true;End;Flag1:=false;分析：第三次改进P0、P1的“谦让”可能使它们都不能进入临界区。这种现象不是死锁，因为这种僵局不会是永久行为，某一时刻可能会自动解除。但是，这种现象也是不希望出现的。互斥与同步解决方法之一:软件方法-Dekker互斥算法该算法既允许进程“谦让”地申请进入临界区,又通过给定序号避免“过分谦让”。Procedure P0;Begin Repeat flag0:=true; while flag1 do if turn=1 then begin flag0:=false; while turn=1

19、do nothing; flag0:=true; end;Turn:=1;flag0:=false; foreverEnd;Var flag:array0.1 of boolean:false;/*共享的全局变量，表示临界区状态*/Turn:0.1; /*共享的全局变量，表示进入临界区的顺序*/Procedure P1;Begin Repeat flag1:=true; while flag0 do if turn=0 then begin flag1:=false; while turn=0 do nothing; flag1:=true; end;Turn:=0;flag1:=false;

20、 foreverEnd;begin /*主程序 */ flag0:=false; flag1:=false;turn:=1;parbeginP0;P1;parendendbegin /*主程序 */ flag0:=false; flag1:=false;turn:=1; parbegin P0;P1; parendendVar flag:array0.1 of boolean:false;/*共享的全局变量，表示临界区状态*/Turn:0.1; /*共享的全局变量，表示进入临界区的顺序*/Procedure P0;Begin Repeat flag0:=true; while flag1 do

21、 if turn=1 then begin flag0:=false; while turn=1 do nothing; flag0:=true; end;Turn:=1;flag0:=false; foreverEnd;Procedure P1;Begin Repeat flag1:=true; while flag0 do if turn=0 then begin flag1:=false; while turn=0 do nothing; flag1:=true; end;Turn:=0;flag1:=false; foreverEnd;P0执行的流程图Procedure P0;Begi

22、n Repeat flag0:=true; while flag1 do if turn=1 then begin flag0:=false; while turn=1 do nothing; flag0:=true; end;Turn:=1;flag0:=false; foreverEnd;互斥与同步解决方法之二：硬件方法采用软件方法实现进程互斥使用临界资源是很困难的，它们通常实现两个进程互斥，很难控制多个进程互斥。算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。软件方法始终不能解决“忙等”现象，降低系统效率。硬件方法包括屏蔽中断和专用机器指令。互斥与同步解决方法之二：硬件方法

23、-屏蔽中断由于进程切换需要依赖中断来实现，如果屏蔽中断，则不会出现进程切换。因此，为了实现对临界资源的互斥使用，可以在进程进入临界区之前，屏蔽中断，当进程退出临界区时，打开系统中断。中断被屏蔽以后，系统时钟中断也被屏蔽，处理机将不会被切换到其他进程。于是，一旦屏蔽中断，进程就可以检查和修改共享内存区中的数据，而不必担心其他进程介入。互斥与同步解决方法之二：硬件方法-屏蔽中断Repeat ; ; ; Forever.互斥与同步解决方法之二：硬件方法-屏蔽中断这种方法的约束条件太强，付出的代价太大。因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应当前执行进程的任何异常及系统故障，严重地降

24、低了处理机性能。这种方法仅对单处理机系统有效，如果系统有两个或多个共享内存的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其它处理机仍将能继续运行，并可以访问共享内存空间。互斥与同步解决方法之二：硬件方法-专用机器指令利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到其它指令的干扰，也不会被中断。互斥与同步解决方法之二：硬件方法-testset指令function testset(var i:integer):boolean; begin if i=0 then begin i:=1; testset:=true; end else testset:=false; end

25、 program mutualexclusion;const n=; /*进程数*/var bolt:integer;begin repeatrepeat nothing until testset (bolt); ; bolt:=0; foreverend;begin /*主程序*/bolt:=0;parbegin P(1); P(2); P(n)parendend.互斥与同步解决方法之二：硬件方法-exchange指令procedure exchange(var r:register;var m:memory);var temp;begin temp:=m; m:=r; r:=temp;e

26、gram mutualexclusion;const n=;/*进程数*/var bolt:integer;proceduce P(I:integer);var key:integer;begin repeat key:=1; repeat exchange(key,bolt)until key=0; ; exchange(key,bolt); foreverend;begin /*主程序*/bolt:=0;parbegin P(1); P(2); P(n);parendEnd.互斥与同步解决方法之二：硬件方法-机器指令的优点非常简单，易于证明；同时适合于单处理机系统和共享内存的多

27、处理机系统中多个进程的互斥;可以分别为临界区设置属于它自己的变量，以实现对多个临界区的互斥访问。互斥与同步解决方法之二：硬件方法-机器指令的缺点“忙等”现象仍然存在。进程都需要循环检测，等待时机进入临界区。但是，由于采用了机器指令，这种“忙等”消耗的机器时间比软件方法小，属于“可接受的忙等”。可能出现饥饿现象。当临界区空闲时，执行循环检测的若干等待进程能进入临界区的机率是相等的，有的进程可能“运气”非常不好，很难有机会进入临界区，而饥饿。互斥与同步解决方法之二：硬件方法-机器指令的缺点还可能导致死锁。例如：进程P1的优先级低于P2的优先级，若P1通过执行专用的机器指令，进入临界区，且在临界区内

28、被中断，P2被调度执行。若P2也需要进入该临界区，由于临界区被P1占用，P2“忙等”。由于P1的优先级低于P2，调度程序不可能强行剥夺P2的执行而调度P1。这样，P1将一直占用临界区被中断，P2一直“忙等”，如果没有外力的作用，这种“僵持”状态将一直保持下去，即系统出现死锁。信号量(semaphore)方法软件方法和硬件方法都存在“忙等”问题，浪费了处理机时间。信号量方法能实现进程互斥与同步，而不必“忙等”。实例交通信号灯：红灯停，绿灯行。信号量实现互斥的基本原理两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒

29、）。相应地，将实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型、另一个域为队列，其元素为等待该信号量的阻塞进程（FIFO）。信号量定义Type semaphore=recordCount:integerQueue:list of processEnd;Var s:semaphore;定义对信号量的两个原子操作Wait(s)和signal(s)早期这两个原语被称作P(s)和V(s)Wait(s) s.count:=s.count-1; If s.count 0 then begin 进程阻塞； 进程进入s.queue队列； End;Signal(s)s.count:=s.c

30、ount+1;if s.count = 0 Thenbegin 唤醒队首进程； 将进程从s.queue阻塞队列中移出；End;Wait、singal的应用进程进入临界区之前，首先执行wait(s)原语，若s.count0,则进程调用阻塞原语，将自己阻塞，并插入到s.queue队列排列。注意，阻塞进程不会占用处理机时间，不是“忙等”，直到某个从临界区退出的进程执行signal(s)原语，唤醒它。一旦其它某个进程执行了sigal(s)原语中的s.count+1操作后，发现s.count=0，即阻塞队列中还有被阻塞进程，则调用唤醒原语，把s.queue中第一个进程修改为就绪状态，送就绪队列，准备执行

31、临界区代码。program mutualexclusion;const n=; /*进程数*/*定义信号量s,s.count初始化为1*/var s:semaphore(:=1); Procedure P(i:integer);begin repeat wait(s); ; signal(s); foreverEnd;利用信号量实现互斥的通用模式begin /*主程序*/parbegin P(1);P(2);P(n)parendend信号量的类型信号量分为：互斥信号量和资源信号量。互斥信号量用于申请或释放资源的使用权，常初始化为1。资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示

32、系统中某类资源的可用个数。Wait操作用于申请资源（或使用权），进程执行wait原语时，可能会阻塞自己；Signal操作用于释放资源（或归还资源使用权），进程执行signal原语时，有责任唤醒一个阻塞进程。信号量的物理意义s.count = 0表示还可执行wait(s)而不会阻塞的进程数（可用资源数），每执行一次wait(s)操作，就意味着请求分配一个单位的资源。当s.count 0时，表示已无资源可用，因此请求该资源的进程被阻塞，此时，s.count的绝对值等于该信号量阻塞队列中的等待进程数。执行一次signal操作，就意味着释放一个单位的资源，若s.count0,表示s.queue队列中还

33、有被阻塞的进程，需要唤醒该队列中的第一个进程，将它转移到就绪队列中。s.Count的取值范围当仅有两个并发进程共享临界资源时，互斥信号量仅能取值0、1、-1，其中，s.count=1,表示无进程进入临界区s.count=0,表示已有一个进程进入临界区s.count=-1,则表示已有一进程正在等待进入临界区当用s来实现n个进程的互斥时，s.count 的取值范围为1 -(n-1)操作系统内核以系统调用形式提供wait和signal原语，应用程序通过该系统调用实现进程间的互斥。工程实践证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。 进程间的相互作用利用信号量实现进程互斥的过程描述 为使

34、多个进程互斥地访问某个临界资源，只需为该资源设置一个信号量，并设其初始值为1，此时的信号量可以称为“互斥信号量”。typedef int semaphore;semaphore mutex=1;void procedure1() while (1) wait(mutex); critical section signal(mutex); void procedure2() while (1) wait(mutex); critical section signal(mutex); main() cobegin procedure1(); procedure2(); 进程间的相互作用 利用信号量

35、来描述程序或语句之间的前趋关系 可以利用信号量，按照语句的前驱趋关系（如图所示），可写出一个可并发执行的程序，其描述如下例：有6个语句的前驱图main()semaphore a=b=c=d=e=f=g=0;cobegin T1;signal(a);signal(b); wait(a);T2;signal(c);signal(d); wait(b);T3;signal(e); wait(d);T4;signal(f); wait(c);T5;signal(g); wait(e);wait(f);wait(g);T6; 经典进程互斥与同步问题生产者/消费者问题读者/写者问题哲学家进餐问题生产者与消

36、费者问题生产者与消费者问题生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程。生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中取数据。假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out ,指向生产者将存放数据的存储单元和消费者将取数据的存储单元。生产者与消费者循环使用缓冲区?不控制生产者/消费者指针in和out初始化指向缓冲区的第一个存储单元。生产者通过In指针向存储单元存放数据，一次存放一条数据，且In指针向后移一个位置。消费者从缓冲区中逐条取走数据，一

37、次取一条数据，相应的存储单元变为“空”，每取走一条数据，out指针向后移一个存储单元位置。试想，如果不控制生产者与消费者，会产生什么结果？生产者/消费者必须互斥生产者和消费者可能同进进入缓冲区，甚至可能同时读/写一个存储单元，将导致执行结果不确定。这显然是不允许的，必须使生产者和消费者互斥进入缓冲区，即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。生产者/消费者必须同步生产者不能向满缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消费者必须同步。生产一条数据是否可用是否有空存储单元存入一条数据归还使用权数据单元加1，唤醒一个消费者有是阻塞等待资源

38、被唤醒阻塞等待使用权被唤醒否无生产者是否可用是否有数据单元取一条数据归还使用权空单元加1，唤醒一个生产者有是阻塞等待资源被唤醒阻塞等待使用权被唤醒否无消费数据消费者Program producer_consumer;Const sizeofbuffer=; /*缓冲区的大小*/Var s:semaphore(:=1); /*互斥信号量s,初始化为1 */ n:semaphore(:=0); /*资源信号量n，数据单元，初始化为0 */ e:semaphore(:=sizeofbuffer); /*资源信号量e，空存储单元*/Procedure producer:Begin repeat 生产一

39、条数据； wait(e); wait(s); 存入一条数据; signal(s); signal(n); foreverEnd;Procedure consumer:Begin repeat wait(n); wait(s); 取一条数据； signal(s); signal(e); 消费数据； foreverEnd;Begin /*主程序*/ parbegin producer:consumer; parendEnd.Program producer_consumer;Const sizeofbuffer=; /*缓冲区的大小*/Var s:semaphore(:=1); /*互斥信号量s,

40、初始化为1 */ n:semaphore(:=0); /*资源信号量n，数据单元，初始化为0 */ e:semaphore(:=sizeofbuffer); /*资源信号量e，空存储单元*/Procedure producer:Begin repeat 生产一条数据； wait(e);wait(s);存入一条数据; signal(s); signal(n); foreverEnd;Program producer_consumer;Const sizeofbuffer=; /*缓冲区的大小*/Var s:semaphore(:=1); /*互斥信号量s,初始化为1 */ n:semaphore

41、(:=0); /*资源信号量n，数据单元，初始化为0 */ e:semaphore(:=sizeofbuffer); /*资源信号量e，空存储单元*/Procedure consumer:Begin repeat wait(n); wait(s); 取一条数据； signal(s); signal(e); 消费数据；foreverEnd;注意进程应该先申请资源信号量，再申请互斥信号量，顺序不能颠倒。对同一个信号时的wait与signal可以不在同一个进程中。对任何信号量的wait与signal操作必须配对，同一进程中的多对wait与signal语句只能嵌套，不能交叉。Wait与signal语句

42、不能颠倒顺序，wait语句一定先于signal语句。2009下半年软件设计师考试上午试题进程P1、P2、P3和P4的前趋图如下：P1P4P3P2p1aP1执行p2bV(S3)P2执行p3cV(S4)P3执行p4dP4执行若用PV操作控制这几个进程的并发执行过程，则需要设置4个信号量S1、S2、S3和S4，且信号量初值都等于零。下图中a和b应分别填写 (25) ,c和d应分别填写 (26) .(25)A.P(S1)P(S2)和P(S3) B.P(S1)P(S2)和V(S1) C.V(S1)V(S2)和P(S1) D.V(S1)V(S2)和V(S3)(26) A.P(S1)P(S2)和P(S4)

43、B.P(S2)P(S3)和P(S4) C.V(S1)V(S2)和P(S4) D.V(S2)V(S3)和V(S4)P1P4P3P2答案(25): C(26): B2010年11月软考软件设计师考试上午试题 (23) A.P(S1)P(S2)和P(S3)P(S4) B.P(S1)V(S2)和P(S2)V(S1) C.V(S1)V(S2)和V(S3)V(S4) D.P(S1)P(S2)和V(S1)V(S2)(24) A.P(S1)P(S2)和V(S3)V(S4) B.P(S1)P(S3)和V(S5)V(S6) C.V(S1)V(S2)和P(S3)P(S4) D.P(S1)V(S3)和P(S2)V(S

44、4)(25) A.P(S3)P(S4)和V(S5)V(S6) B.V(S5)V(S6)和P(S5)P(S6) C.P(S2)P(S5)和P(S4)P(S6) D.P(S4)V(S5)和P(S5)V(S6)答案(23) C(24) B(25) C例题设有4个进程A、B、C、D共享一个缓冲区，进程A负责循环地从文件读出一个整数并放入缓冲区，进程B从缓冲区中循环读入MOD 3为0的整数并累计求和；C从缓冲区中循环地读入MOD 3为1的整数并累计求和；D从缓冲区中循环地读入MOD 3为2的整数并累计求和。请用P、V操作写出能够正确的执行的程序。分析进程A读入一个数如果这个数MOD 3得到0，那么通知进

45、程B去取，通知信号量为SB；如果这个数MOD 3得到1，那么通知进程C去取，通知信号量为SC；如果这个数MOD 3得到2，那么通知进程D去取，通知信号量为SD。题解程序如下：Begin Sempty,SB,SC,SD:Semaphore=1:0,0,0; Num:integer; Parbegin Process PA BeginP(Sempty);If(num MOD 3=0) V(SB)Else if (num MOD 3=1) V(SC)Else V(SD)End;Process PBBegin P(SB); V(Sempty);End;Process PCBegin P(SC); V(

46、Sempty);END;Process PDBegin P(SD); V(Sempty);END Parend;End;例题假设有3个并发进程P、Q、R。其中P负责从输入设备上读入信息并传递给Q；Q将信息加工后传送给R；R则负责将信息打印输出。进程P、Q共享一个由m个缓冲区组成的缓冲池；进程Q、R共享一个由n个缓冲区组成的缓冲池（假设缓冲区足够大，进程间每次传输信息的单位均小于等于缓冲区长度）。写出满足上述条件的并发进程。分析这是一个典型的生产者与消费者问题，本题中Q既作消费者又作为生产者。3个进程P、Q和R之间的关系：PQR进程P和Q之间存在着同步关系，进程Q和R之间也存在着同步关系，且进程

47、P和Q，Q和R都需要访问公有的缓冲池资源，因此，P和Q以及Q和R对各自缓冲池的使用应该互斥进行。题解设有两个信号量mutex_1、mutex_2分别用来实施对缓冲区的互斥访问，且其初值都为了1；设置私有信号量Sip、Siq用于进程P和Q之间的同步；设置私有信号量Soq、Sor用于进程Q和R之间的同步。并发程序如下所示：mutex_1,mutex_2,Sip,Siq,Soq,Sor:Semapahore=1,1,m,0,n,0;Process PBeginLoop: ; P(Sip); P(mutex_1); ; V(Siq); V(mutex_1); Goto loop;End;Process

48、 QBeginLoop: P(Siq); P(mutex_1); V(mutex_1); V(Sip); ; P(Soq); P(mutex_2); V(Sor); V(mutex_2);Goto Loop;End;Process RBeginLoop: P(Sor); P(mutex_2); V(mutex_2); V(Soq);Goto Loop;End; 例：在公共汽车上,司机和售票员各行其职,司机负责开车和到站停车;售票员负责售票和开、关门，当售票员关好车门后，驾驶员才能开车行驶。试用P、V操作实现司机与售票员间的同步。司机和售票员间的同步关系如下图所示：司机正常行车到站停车开车售票关

49、车门开车门售票员解析：设置两个信号量S1、S2，分别表示司机和售票员的私用信号量，其初值均为0。两者之间的同步关系描述如下所示： S1,S2:Semaphore S1:=0;S2:=0; /司机进程Process DriverBeginLoop: ; ; V(S2); P(S1); Goto Loop;End;/售票员进程Process BookingClerk;BeginLoop: ; P(S2); ; ; V(S1); Goto Loop;End;读者/写者问题问题描述该问题为多个进程访问一个共享数据区，如数据库、文件，内存区及一组寄存器等的数据问题建立了一个通用模型，其中若干读进程只能读

50、数据，若干写进程只能写数据。例如，一个联网售票系统，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形，多个进程同时读一条记录是可以的，但如果一个进程正在更新数据库中的某条记录，则所有其他进程都不能访问（读或写）的记录，否则可能会将同一个座位销售多次。读者/写者进程满足的条件允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据，即只能互斥写数据；若有写者进程正在写数据，则不允许读进程读数据。如何控制读者和写者如果采用生产者/消费者问题解决方法，严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。但是，对于若干读者进程，只不过希望查询售票情

51、况，却被严格互斥，严重影响了系统效率，显然应该让多个读者同时读数据。如果一个写者进程正在修改数据，别的写者以及任何读者都不能访问该数据。读者优先当一个读者正在读数据时，另一个读者也需要读数据，应允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。现在假设一个写者到来，由于写操作是排他的，所以它不能访问数据，需要阻塞等待，如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。该方法称为“读者优先”，即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。Program readers_writers;Const readcount:integer

52、; /*统计读者的个数*/Var x,wsem:semaphore(:=1); /*互斥信号量，初始化为1 */Procedure reader:Begin repeat wait(x); readcount:=readcount+1; If readcount=1 then wait(wsem); signal(x); 读数据； wait(x); readcount:=readcount-1; if readcount=0 then signal(wsem); signal(x);ForeverEnd;Procedure write:Begin repeat wait(wsem); 写数据：

53、 signal(wsem); foreverEnd;Begin /*主程序 */ readcount:=0; parbegin reader;writer; parendEnd.写者优先为了防止“读者优先”可能导致写者饥饿，可以考虑写者优先。即，当共享数据区被读者占用时，后续紧邻到达的读者可以继续进入，若这时有一个写者到来且阻塞等待，则写者后面到来的若干读者全部阻塞等待。换句话说，只要有一个写者申请写数据，则不再允许新的读者进入读数据。这样，写者只需等待先于它到来的读者完成其读数据任务，而不用等待其后到来的读者。这种方案解决了写者饥饿问题，但降低了并发程序，使系统的性能较差。Program r

54、eaders_writers:Const readcount,writecount:integer;Var x,y,z,rsem,wsem;semophore(:=1)Procedure reader:Begin repeat wait(z); wait(rsem); wait(x); readcount:=readcount+1;If readcount=1 then wait(wsem);Signal(x);Signal(rsem);Signal(z);读数据；Wait(x);Readcount:=readcount-1;If readcount=0 then signal(wsem);S

55、ignal(x);ForeverEnd.Procedure writer:Begin repeat wait(y); writecount:=writecount+1;If writecount=1 then wait(rsem); signal(y);Wait(wsem);写数据;Signal(wsem);Wait(y);Writecount:=writecount-1;If writecount=0 then signal(rsem)Signal(y)ForeverEnd;begin /*主程序*/ readcount:=0; writecount:=0; parbegin reader:

56、writer; parendend.管程管程是一种在程序设计级控制进程互斥与同步的机制，具有信号量的功能，且更容易使用和控制。目前已有很多程序设计语言支持管程机制，如并发Pascal、Pascal_Plus、Modula-2、Modula-3、Java等，并且还作为程序库提供服务。利用管程可以锁定任何对象，尤其是链表型数据结构，可以锁定整个链表，或链表中的某个元素。管程的结构管程是由过程、变量及数据结构等组成的集合。典型的管程包括三个部分： (1)对局部于管程的共享数据结构的说明； (2)对该数据结构进行操作的一组过程； (3)对该数据结构初始化的语句。管程有自己的名字，管程中的各个过程可以带

57、有自己的形式参数，与过程调用一样进行参数替换执行。管程的使用管程本身被作为一种临界区，因此，实现管程时，需要考虑互斥、同步和控制变量等问题。进程可在任何需要的地方调用管程中的过程，但不能在管程外直接访问管程内的数据结构。Type name=monitor /*管程命名 */Var i:integer; /*变最说明 */ c:condition;Procedure P1(x);BeginEnd;Procedure P2(x);BeginEnd;Procedure Pn(x);BeginEnd;Begin/*初始化语句 */End;用管程实现互斥当几个进程调用某个管程时，仅允许一个进程进入管程，

58、其他进程必须等待，即任何时刻，管程中只能有一个活跃进程。典型地，当一个进程调用管程中的过程时，若先检查管程中是否有其他的活跃进程，如果有，则阻塞调用进程、直到管程内的进程离开管程。管程的互斥操作通常由编译程序支持，编译时自动为每个管程建立一个初值为1的互斥信号量。用管程实现同步用管程实现进程同步，是指在管程中要设置一对同步操作原语，例如，wait(或block)和signal(或wakeup）。注意，这里的wait和signal与作用于信号量的wait和signal不同，后者作用于信号量。信号量具有累加功能，当信号量为负数时，其绝对值表示等待在该信号量上的阻塞进程数。这里的wait和signa

59、l作用于条件变量，条件变量不具有累加功能，如果管程中的进程发出了一个信号量，却没有在对应的条件变量上阻塞等待，则该信号量没有作用，会被丢失。由于进程阻塞等待的原因有多种，为了区别阻塞等待进程和不同的阻塞队列，管程中设置了不同的条件变量，将因为不同事件阻塞的进程组织在不同的队列中。当一个进程利用管程申请资源而未能满足时，将调用wait原语阻塞自己，并进入相应阻塞队列。当某进程释放出一个临界资源以后，将用signal原语唤醒等待在该临界资源上的一个阻塞过进程。消息传递进程通信的方式进程之间的通信内容包含两种类型：控制信息与大批量数据。低级通信：进程之间交换控制信息的过程。高级通信：进程之间交换批量

60、数据的过程。进程之间同步与互斥是一种低级通信，用来控制进程执行速度。发送进程 接收进程邮件邮件邮件接收进程发送进程终端用户发送进程接收进程终端用户发送进程接收进程邮件服务器邮件服务器电子邮件的发送与接收过程常用的进程通信机制基于共享存储区方式消息传递方式邮箱机制基于共享存储区方式生产者/消费者问题：生产者与消费者通过共享缓冲区，实现数据传递，属于基于共享存储区通信。这里的共享数据区属于每个互相通信进程的组成部分，这种通信方式不要求数据移动，一般用于本地通信。对于远程通信来说，每台计算机拥有各自的私有内存区，不易实现共享存储区的访问。？如何通过共享存储区通信通过程序设计来实现。程序员设计程序时，