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

《第4章进程同步与通信2课件》由会员分享，可在线阅读，更多相关《第4章进程同步与通信2课件（241页珍藏版）》请在金锄头文库上搜索。

1、进程的同步与互斥进程的同步与互斥？采用多道程序设计技术的操作系统，允许采用多道程序设计技术的操作系统，允许多个进程同时驻留内存并发执行。多个进程同时驻留内存并发执行。？如何协调多个进程对系统资源，如内存？如何协调多个进程对系统资源，如内存空间、外部设备等的竞争和共享？空间、外部设备等的竞争和共享？如何解决多个进程因为竞争资源而出现？如何解决多个进程因为竞争资源而出现执行结果异常，甚至导致系统不稳定、失执行结果异常，甚至导致系统不稳定、失败等问题。败等问题。？例如，多个进程同时申请文件打印，如？例如，多个进程同时申请文件打印，如何有效分配打印机？何有效分配打印机？例例银行的联网储蓄业务允许储户同

2、时用储蓄卡和存银行的联网储蓄业务允许储户同时用储蓄卡和存折对同一帐户进行存取款操作，如果某储户同时折对同一帐户进行存取款操作，如果某储户同时（在在ATM机和营业柜台）办理两笔存款业务（假机和营业柜台）办理两笔存款业务（假设分别设分别为为1000和和2000元）元）从系统的角度看，有两个进程将同时对储户余额从系统的角度看，有两个进程将同时对储户余额等数据进行修改。如果两个进程同时读出原余额等数据进行修改。如果两个进程同时读出原余额（假设（假设为为5000元），两个进程分别将最新余额修元），两个进程分别将最新余额修改改为为6000(5000+1000)和和7000(5000+2000).分析及措施

3、分析及措施最后，储户余额可能最后，储户余额可能是是6000，或者，或者7000，显然都不正确。显然都不正确。原因：两个进程同时修改同一数据，而没原因：两个进程同时修改同一数据，而没有进行有效控制。有进行有效控制。正确的方法：如果有多个进程需要同时修正确的方法：如果有多个进程需要同时修改某一数据，系统必须控制，一次仅允许改某一数据，系统必须控制，一次仅允许一个进程完成读数据，并修改数据两件事一个进程完成读数据，并修改数据两件事以后，才允许别的进程对同一数据的读和以后，才允许别的进程对同一数据的读和修改操作。修改操作。例例假设系统中假设系统中有有3个进程个进程P1、P2、P3，其中其中P1和和P2

4、是计算进程是计算进程，P3是打印进程，每当是打印进程，每当P1或或P2计计算出一个结果以后，将计算结果送到缓存区中，算出一个结果以后，将计算结果送到缓存区中，以便以便P3进程从中取出数据打印。进程从中取出数据打印。假设缓冲区被划分假设缓冲区被划分为为0、1、2n-1共共n个单元。个单元。有两个指针有两个指针：In指针用于计算进程存放数据，指指针用于计算进程存放数据，指向缓冲区中下一个空闲的单元向缓冲区中下一个空闲的单元，Out指针用于打指针用于打印进程取数据，指向缓冲区中下一个将取走数据印进程取数据，指向缓冲区中下一个将取走数据的单元。的单元。例例假设某时刻，假设某时刻，0到到3号单元空闲号单

5、元空闲，4到到6号单号单元被占用，这时候元被占用，这时候P1、P2进程都准备将数进程都准备将数据送入缓冲区。如下据送入缓冲区。如下多个进程同时访问共享区可能发生的情况可能发生的情况进程进程P1需要向缓冲区存储数据，并知道需要向缓冲区存储数据，并知道In指针当前指向指针当前指向7号空闲缓冲单元。若这时进号空闲缓冲单元。若这时进程程P1的时间片用完，被中断，调度程序调的时间片用完，被中断，调度程序调度进程度进程P2执行。执行。P2正好也需要向缓冲区存放数据，首先获正好也需要向缓冲区存放数据，首先获取取In指针位置，同样也是指针位置，同样也是7，于是，于是，P2将数将数据送入据送入7号单元，并号单元

6、，并将将In指针移动一格，指指针移动一格，指向向8号单元，然后继续执行其他操作。号单元，然后继续执行其他操作。可能发生的情况可能发生的情况当进程当进程P1再次被调度执行时，将从上次的再次被调度执行时，将从上次的断点继续执行，即将数据送入断点继续执行，即将数据送入7号单元（覆号单元（覆盖进程盖进程P2的数据），并移动的数据），并移动In指针指向指针指向8号号单元，然后继续执行其他操作。单元，然后继续执行其他操作。进程进程P3不会发现上述错误，继续从缓冲区不会发现上述错误，继续从缓冲区取数据，进行打印，显然，进程取数据，进行打印，显然，进程P2的相应的相应计算结果不会被打印输出。计算结果不会被打印

7、输出。分析分析该例中，由于进程该例中，由于进程P1和和P2共享缓冲区和位共享缓冲区和位置指针，而未对这种共享进行有效控制，置指针，而未对这种共享进行有效控制，导致打印数据的丢失。导致打印数据的丢失。如果控制进程如果控制进程P1、P2互斥地访问缓冲区和互斥地访问缓冲区和修改位置指针，将避免这种因为并发执行修改位置指针，将避免这种因为并发执行而导致的程序执行结果的不确定性。而导致的程序执行结果的不确定性。并发控制并发控制竞争资源竞争资源当并发进程竞争使用同一资源时，它们之间就会当并发进程竞争使用同一资源时，它们之间就会发生冲突。发生冲突。如果操作系统将资源分配给其中的某一个进程使如果操作系统将资源

8、分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。用时，由操作系统分配给它。如果竞争某资源的进程太多，这些进程还必须等如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等。待在一个队列中，如就绪队列，阻塞队列等。一种极端的情况是，被阻塞进程永久得不到申请一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁。的资源，而死锁。并发控制并发控制竞争资源竞争资源进程竞争资源首先必须解决进程竞争资源首先必须解决“互斥互斥”问题，问题，某些资源必须互斥使用，如打印机、共享某些资源必须互斥使用

9、，如打印机、共享变量、表格、文件等。变量、表格、文件等。这类资源又称为临界资源，访问临界资源这类资源又称为临界资源，访问临界资源的那段代码称为临界区。的那段代码称为临界区。任何时刻，只允许一个进程进入临界区，任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。以此实现进程对临界资源的互斥访问。进程互斥进入临界区阻塞队列进程进入区临界区退出区唤醒互斥使用临界资源互斥使用临界资源当进程需要使用临界资源时，通过获得临界区的当进程需要使用临界资源时，通过获得临界区的使用权实现的。使用权实现的。首先，在首先，在“进入区进入区”判断是否可以进入临界区，判断是否可以进入临界区，如果可以进入

10、，则必须设置临界区使用标志，阻如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区，后来的进程通过止其它后来的进程进入临界区，后来的进程通过查看临界区使用标志，知道自己不能进入临界区，查看临界区使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。就进入阻塞队列，将自己阻塞。当临界区内的进程使用完毕，退出临界区时，即当临界区内的进程使用完毕，退出临界区时，即在在“退出区退出区”修改临界区使用标志，并负责唤醒修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。阻塞队列中的一个进程，让其进入临界区。互斥使用临界资源互斥使用临界资源由于同一个临界资源在多个共享

11、它的进程由于同一个临界资源在多个共享它的进程中将对应多个临界区，那么怎样才能保证中将对应多个临界区，那么怎样才能保证诸进程间互斥地执行临界区呢？诸进程间互斥地执行临界区呢？这就必须保证这就必须保证“临界区使用标志临界区使用标志”是可被是可被系统中所有进程共享的全局变量，而且诸系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。进程对该标志的修改操作必须互斥进行。临界区使用原则（也称互斥条件）临界区使用原则（也称互斥条件）每次只允许一个进程处于临界区（每次只允许一个进程处于临界区（忙则等待忙则等待）；）；进程只能在临界区内逗留有限时间，不得使其它进程只能在临界区内逗留有限时间

12、，不得使其它进程在临界外无限期等待（进程在临界外无限期等待（有限等待有限等待）；）；如果临界区空闲，则只要有进程申请就立即让其如果临界区空闲，则只要有进程申请就立即让其进入（进入（空闲让进空闲让进）；）；进入临界区的进程，不能在临界区内长时间阻塞进入临界区的进程，不能在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（等待某事件，必须在一定期限内退出临界区（让让权等待权等待）不能限制进程的执行进度及处理机的数量。不能限制进程的执行进度及处理机的数量。竞争资源可能引起死锁竞争资源可能引起死锁例如：两个进程例如：两个进程P1、P2，竞争资源竞争资源R1、R2.假设，现在假设，现在P1已经占

13、用已经占用了了R1，且，且P2占用占用了了R2，如果此时如果此时P1申请申请R2，且，且P2申请申请R1。会怎么样？会怎么样？结果是结果是P1、P2双方都占用对方申请的资源双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是而阻塞，谁也不让步地永久等待，这就是死锁。死锁。进程因竞争资源而死锁竞争资源竞争资源饥饿饥饿假设假设有有3个进程个进程P1、P2、P3，每个进程都需要周每个进程都需要周期性的使用资源期性的使用资源R。如果当前如果当前P1正在使用临界资源正在使用临界资源R，P2和和P3因为等因为等待待R而阻塞。而阻塞。当当P1退出临界区时退出临界区时，P2立即进入临界区执行立即进入临

14、界区执行，若，若P2还未退出临界区时，还未退出临界区时，P1又申请使用临界资源又申请使用临界资源R。假设假设P2退出临界区后，系统退出临界区后，系统将将R分给分给了了P1，然后然后，当当R空闲时，又将其分给空闲时，又将其分给P2，如此反复。如此反复。竞争资源竞争资源饥饿饥饿使使P1、P2都能正常执行都能正常执行，而，而P3被长时间饥被长时间饥饿。饿。这种情况不是死锁，但是这种情况不是死锁，但是对对P3不公平，也不公平，也是系统应该避免的。是系统应该避免的。并发控制并发控制共同协作共同协作多个进程常常需要共同修改某些共享变量、多个进程常常需要共同修改某些共享变量、表格、文件数据库等，协作完成一些

15、功能。表格、文件数据库等，协作完成一些功能。必须确保它们对共享变量的修改是正确的，必须确保它们对共享变量的修改是正确的，保证数据的完整性。保证数据的完整性。共享协作同样涉及到互斥、死锁和饥饿问共享协作同样涉及到互斥、死锁和饥饿问题，但更强调对数据的写操作必须互斥地题，但更强调对数据的写操作必须互斥地进行。进行。必须保证数据一致性。必须保证数据一致性。前面列举了银行联网储蓄的例子，除了必须保前面列举了银行联网储蓄的例子，除了必须保证储户余额的正确性以外，还必须使银行储蓄证储户余额的正确性以外，还必须使银行储蓄总余额、当日发生额、流水账等数据得到一致总余额、当日发生额、流水账等数据得到一致的修改。

16、的修改。一般通过事务处理来保证数据的一致性，可以一般通过事务处理来保证数据的一致性，可以将对储户余额、储蓄总余额、当日发生额、流将对储户余额、储蓄总余额、当日发生额、流水账等数据的修改放到一个临界区中，进入临水账等数据的修改放到一个临界区中，进入临界区的进程必须一次性完成对这一系列数据的界区的进程必须一次性完成对这一系列数据的修改操作。修改操作。只有该进程退出临界区以后，才允许别的进程只有该进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致进入临界区进行数据修改，以保证数据的一致性。性。并发控制并发控制通信协作通信协作当进程进行通信合作时，各个进程之间需当进程进行通信合

17、作时，各个进程之间需要建立连接，进程通信需要同步和协调，要建立连接，进程通信需要同步和协调，进程通信的方式很多，包括消息传递、管进程通信的方式很多，包括消息传递、管道、共享存储区等。道、共享存储区等。通过消息传递实现进程通信时，由于没有通过消息传递实现进程通信时，由于没有共享资源，故无须互斥，但仍可能出现死共享资源，故无须互斥，但仍可能出现死锁和饥饿。锁和饥饿。并发控制并发控制通信协作通信协作例如，两个进程相互等待对方发来的数据例如，两个进程相互等待对方发来的数据而永久阻塞，即死锁。而永久阻塞，即死锁。又又如，如，3个进程个进程P1、P2、P3，其中其中P1不断不断尝试尝试与与P2或或P3通信

18、通信，P2和和P3又不断尝试又不断尝试与与P1通信，如果通信，如果P1与与P2总能成功建立连接进总能成功建立连接进行通信行通信，而，而P3一直阻塞等待一直阻塞等待P1，这样这样P3被被长时间饥饿。长时间饥饿。互斥与同步的解决策略互斥与同步的解决策略软件方法软件方法硬件方法硬件方法信号量方法信号量方法管程方法管程方法消息传递方法消息传递方法软件方法软件方法软件方法是指由进程自己，通过执行相应软件方法是指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互的程序指令，实现与别的进程的同步与互斥，无须专门的程序设计语言或操作系统斥，无须专门的程序设计语言或操作系统的支持。的支持。实践证明，该

19、方法很难正确控制进程间的实践证明，该方法很难正确控制进程间的同步与互斥，而且可能会大大地增加系统同步与互斥，而且可能会大大地增加系统的额外开销。的额外开销。硬件方法硬件方法为了解决软件方法存在的不足，有人提出为了解决软件方法存在的不足，有人提出了硬件解决方法，通过屏蔽中断或采用专了硬件解决方法，通过屏蔽中断或采用专门的机器指令控制同步与互斥。门的机器指令控制同步与互斥。与软件解决方法比较，这种方法减少了系与软件解决方法比较，这种方法减少了系统额外开销，但由于需要太强的硬件约束统额外开销，但由于需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，条件，以及可能导致进程饥饿与死锁现象，一直没有

20、成为通用的解决方法。一直没有成为通用的解决方法。另一类解决方法是由操作系统，或专门的另一类解决方法是由操作系统，或专门的程序设计语言提供的特别支持，包括信号程序设计语言提供的特别支持，包括信号量方法、管程方法和消息传递方法。量方法、管程方法和消息传递方法。其中，信号量方法已经成为控制进程同步其中，信号量方法已经成为控制进程同步与互斥的通用方法。与互斥的通用方法。互斥与同步解决方法之一互斥与同步解决方法之一软件方法软件方法软件解决方法有很多种，比较有代表性的软件解决方法有很多种，比较有代表性的软件方法有荷兰数学家软件方法有荷兰数学家Dekker提出提出的的Dekker算法和科学家算法和科学家G.

21、L.Peterson提出提出的的Perterson算法。算法。为了说明设计并发程序时可能出现的典型为了说明设计并发程序时可能出现的典型错误，下面错误，下面以以Dekker算法为例，分析如何算法为例，分析如何设计并改进一个互斥算法的过程。设计并改进一个互斥算法的过程。互斥与同步解决方法之一：软件方互斥与同步解决方法之一：软件方法法初步设想初步设想为了控制两个进程互斥进入临界区，可以为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区。让两个进程轮流进入临界区。当一个进程正在临界区执行时，另一个进当一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。程就不能进入临界区，

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

23、想分析：初步设想例如，例如，P0需要需要每每10分钟使用一次临界区，分钟使用一次临界区，P1需要每需要每1分分钟使用一次临界区。钟使用一次临界区。假设假设turn的初值为的初值为0，进程，进程P0正好先请求进入临正好先请求进入临界区，并成功进入临界区执行，这时，如果界区，并成功进入临界区执行，这时，如果P1申申请进入临界区，循环检测请进入临界区，循环检测turn=0，不可以进入，不可以进入，只能只能“空空”循环，等待。循环，等待。当当P0退出临界区时，修改退出临界区时，修改turn的值为的值为1，P1循环循环检测检测到到turn=1时，就可以进入临界区执行，退出时，就可以进入临界区执行，退出临

24、界区时，修改临界区时，修改turn=0.分析：初步设想分析：初步设想根据假设根据假设，P1很快又需要进入临界区，但很快又需要进入临界区，但是是P0却只能却只能在在10分钟之后，按照分钟之后，按照turn规定规定的顺序，进入临界区执行，退出时修改的顺序，进入临界区执行，退出时修改turn=1.即，即，P1必须在临界区空闲的情况下，等待必须在临界区空闲的情况下，等待10分钟，才能使用临界区。这不符和互斥分钟，才能使用临界区。这不符和互斥原则，降低了系统性能。原则，降低了系统性能。分析：初步设想分析：初步设想问题问题3：任何进程在临界区内或外失败，其：任何进程在临界区内或外失败，其他进程将可能因为等

25、待使用临界区，而无他进程将可能因为等待使用临界区，而无法向前推进。法向前推进。因为两个进程相互依赖对方将临界区的使因为两个进程相互依赖对方将临界区的使用权（顺序）进行修改，一旦这种修改不用权（顺序）进行修改，一旦这种修改不能进行，对方都将因为等待临界区而无法能进行，对方都将因为等待临界区而无法推进。推进。互斥与同步解决方法之一：软件方互斥与同步解决方法之一：软件方法法第一次改进第一次改进可以为临界区设置一个状态标志，标明临可以为临界区设置一个状态标志，标明临界区是否可用。当临界区空闲时，任何一界区是否可用。当临界区空闲时，任何一个进程都能进入，但此时必须修改临界区个进程都能进入，但此时必须修改

26、临界区标志为标志为“被占用被占用”，别的进程就不能进入，别的进程就不能进入临界区，当临界区使用完毕，必须修改该临界区，当临界区使用完毕，必须修改该标志为标志为“空闲空闲”。这样就不再使诸进程严格交替使用临界区，这样就不再使诸进程严格交替使用临界区，而且，如果某进程在临界区外失败，也不而且，如果某进程在临界区外失败，也不会影响其它进程。会影响其它进程。Var flag:array0.1of boolean:false;/*共享的全局变量共享的全局变量*/ P0 P1 While flag1 do nothing; while flag0 do nothing;Flag0:=true; flag1

27、:=true; Flag0:=false; flag1:=false; 互斥算法：第一次改进问题：问题：假若你是软件测试人员，请问第一假若你是软件测试人员，请问第一次改进有没有问题？次改进有没有问题？分析：第一次改进分析：第一次改进如果进程在临界区外失败，其他进程不会如果进程在临界区外失败，其他进程不会阻塞。阻塞。问题问题1：“忙等忙等”问题问题2：若进程在临界区内失败且相应：若进程在临界区内失败且相应的的Flag为为true，则其他进程永久阻塞。则其他进程永久阻塞。问题问题3：不能保证进程互斥进入临界区。：不能保证进程互斥进入临界区。互斥与同步解决方法之一：软件方互斥与同步解决方法之一：软件

28、方法法第二次改进第二次改进互斥算法的第一次改进不能实现互斥算法的第一次改进不能实现“互斥互斥”。因为，进程首先检测到临界区状态，若因为，进程首先检测到临界区状态，若“被占用被占用”则则“忙等忙等”，否则就直接进入临，否则就直接进入临界区。从而，可能出现同时进入临界区的界区。从而，可能出现同时进入临界区的现象。现象。能否让进程预先表明能否让进程预先表明“希望进入临界区的希望进入临界区的态度态度”，然后，再检测临界区状态。，然后，再检测临界区状态。Var flag:array0.1of boolean:false;/*共享的全局变量共享的全局变量*/ P0 P1 Flag0:=true; flag

29、1:=trueWhile flag1 do nothing; while flag0 do nothing; Flag0:=false; flag1:=false; 互斥算法：第二次改进分析：第二次改进假设P0需要进入临界区，首先执行flag0:=true，再执行while flag1,若P1正在占用临界区，则P0忙等；否则，P0进入临界区。但是，如果此时P1未占用临界区，而与P0几乎同时需要使用临界区。互斥与同步解决方法之一：软件方互斥与同步解决方法之一：软件方法第三次改进法第三次改进互斥算法的第二次改进可能导致死锁，因互斥算法的第二次改进可能导致死锁，因为为0、都、都“坚持自己的权利，执意

30、进坚持自己的权利，执意进入临界区，且互不谦让入临界区，且互不谦让”可以考虑，允许进程既表明需要进入临界可以考虑，允许进程既表明需要进入临界区的区的“态度态度”，又能相互，又能相互“谦让谦让”，即首，即首先表示自己需要使用临界区，再检测临界先表示自己需要使用临界区，再检测临界区的状态，若临界区区的状态，若临界区“被占用被占用”，可以等，可以等一小段时间再申请。一小段时间再申请。Var flag:array0.1of boolean:false;/*共享的全局变量共享的全局变量*/ P0 Flag0:=true;While flag1 doBegin flag0:=false; ; flag0:=

31、true;End;Flag0:=false; P1 Flag1:=true;While flag0 doBegin flag1:=false; ; flag1:=true;End;Flag1:=false;分析：第三次改进分析：第三次改进P0、P1的的“谦让谦让”可能使它们都不能进入可能使它们都不能进入临界区。临界区。这种现象不是死锁，因为这种僵局不会是这种现象不是死锁，因为这种僵局不会是永久行为，某一时刻可能会自动解除。永久行为，某一时刻可能会自动解除。但是，这种现象也是不希望出现的。但是，这种现象也是不希望出现的。互斥与同步解决方法之一互斥与同步解决方法之一:软件方法软件方法-Dekker

32、互斥算法互斥算法该算法既允许进程该算法既允许进程“谦让谦让”地申请进入临地申请进入临界区界区,又通过给定序号又通过给定序号避免避免“过分谦让过分谦让”。Procedure P0;Begin 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;Var flag:array0.1 of boolean:false;/*共享的全局变量，表示临界区状态共享的全局变量，

33、表示临界区状态*/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; foreverEnd;begin /*主程序主程序 */ flag0:=false; flag1:=false;turn:=1;parbeginP0;P1;parendendb

34、egin /*主程序主程序 */ 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 if turn=1 then begin flag0:=false; while turn=1 d

35、o 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;Begin Repeat flag0:=true; while flag1 do if turn=1 the

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

37、赖中断来实现，如果屏蔽中由于进程切换需要依赖中断来实现，如果屏蔽中断，则不会出现进程切换。断，则不会出现进程切换。因此，为了实现对临界资源的互斥使用，可以在因此，为了实现对临界资源的互斥使用，可以在进程进入临界区之前，屏蔽中断，当进程退出临进程进入临界区之前，屏蔽中断，当进程退出临界区时，打开系统中断。界区时，打开系统中断。中断被屏蔽以后，系统时钟中断也被屏蔽，处理中断被屏蔽以后，系统时钟中断也被屏蔽，处理机将不会被切换到其他进程。机将不会被切换到其他进程。于是，一旦屏蔽中断，进程就可以检查和修改共于是，一旦屏蔽中断，进程就可以检查和修改共享内存区中的数据，而不必担心其他进程介入。享内存区中的

38、数据，而不必担心其他进程介入。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-屏蔽中断屏蔽中断Repeat ; ; ; Forever.互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-屏蔽中断屏蔽中断这种方法的约束条件太强，付出的代价太大。这种方法的约束条件太强，付出的代价太大。因为中断被屏蔽以后，系统将无法响应任何外部因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应当前执行进程的任何异常及系请求，也不会响应当前执行进程的任何异常及系统故障，严重地降低了处理机性能。统故障，严重地降低了处理机性能。这种方法仅对单处理机系统有效，如果系统有两这种方法仅

39、对单处理机系统有效，如果系统有两个或多个共享内存的处理机，屏蔽中断仅仅对执个或多个共享内存的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其它处理机仍将能继续行本指令的处理机有效，其它处理机仍将能继续运行，并可以访问共享内存空间。运行，并可以访问共享内存空间。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-专用机器指令专用机器指令利用一些专用机器指令也能实现互斥，机利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到器指令在一个指令周期内执行，不会受到其它指令的干扰，也不会被中断。其它指令的干扰，也不会被中断。互斥与同步解决方法之二：硬件方互斥与同步解决方

40、法之二：硬件方法法-testset指令指令function testset(var i:integer):boolean; begin if i=0 then begin i:=1; testset:=true; end else testset:=false; end program mutualexclusion;const n=; /*进程数进程数*/var bolt:integer;begin repeatrepeat nothing until testset (bolt); ; bolt:=0; foreverend;begin /*主程序主程序*/bolt:=0;parbegin

41、 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;end.program mutualexclusion;const n=;/*进程数进程数*/var bolt:integer;proceduce P(I:integer);var key:integer;begin repeat key:=1; repeat exchange(ke

42、y,bolt)until key=0; ; exchange(key,bolt); foreverend;begin /*主程序主程序*/bolt:=0;parbegin P(1); P(2); P(n);parendEnd.互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-机器指令的优点机器指令的优点非常简单，易于证明；同时适合于单处理机系统和共享内存的多处理机系统中多个进程的互斥;可以分别为临界区设置属于它自己的变量，以实现对多个临界区的互斥访问。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-机器指令的缺点机器指令的缺点“忙等忙等”现象仍然存在。现象仍然

43、存在。进程都需要循环进程都需要循环检测，等待时机进入临界区。但是，由于检测，等待时机进入临界区。但是，由于采用了机器指令，这种采用了机器指令，这种“忙等忙等”消耗的机消耗的机器时间比软件方法小，属于器时间比软件方法小，属于“可接受的忙可接受的忙等等”。可能出现饥饿现象。可能出现饥饿现象。当临界区空闲时，执当临界区空闲时，执行循环检测的若干等待进程能进入临界区行循环检测的若干等待进程能进入临界区的机率是相等的，有的进程可能的机率是相等的，有的进程可能“运气运气”非常不好，很难有机会进入临界区，而饥非常不好，很难有机会进入临界区，而饥饿。饿。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬

44、件方法法-机器指令的缺点机器指令的缺点还还可能导致死锁。可能导致死锁。例如：进程例如：进程P1的优先级低于的优先级低于P2的优先级的优先级，若，若P1通通过执行专用的机器指令，进入临界区，且在临界过执行专用的机器指令，进入临界区，且在临界区内被中断区内被中断，P2被调度执行。若被调度执行。若P2也需要进入该也需要进入该临界区，由于临界区被临界区，由于临界区被P1占用，占用，P2“忙等忙等”。由。由于于P1的优先级低于的优先级低于P2，调度程序不可能强行剥夺调度程序不可能强行剥夺P2的执行而调度的执行而调度P1。这样这样，P1将一直占用临界区将一直占用临界区被中断被中断，P2一直一直“忙等忙等”

45、，如果没有外力的作用，如果没有外力的作用，这种这种“僵持僵持”状态将一直保持下去，即系统出现状态将一直保持下去，即系统出现死锁。死锁。信号信号量量(semaphore)方法方法软件方法和硬件方法都存在软件方法和硬件方法都存在“忙等忙等”问题，问题，浪费了处理机时间。浪费了处理机时间。信号量方法能实现进程互斥与同步，而不信号量方法能实现进程互斥与同步，而不必必“忙等忙等”。实例实例交通信号灯：红灯停，绿灯行。交通信号灯：红灯停，绿灯行。信号量实现互斥的基本原理信号量实现互斥的基本原理两个或多个进程可以通过传递信号进行合两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执作，可

46、以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以行（阻塞等待），直到它收到一个可以“向前推进向前推进”的信号（被唤醒）。的信号（被唤醒）。相应地，将实现信号灯作用的变量称为信相应地，将实现信号灯作用的变量称为信号量，常定义为记录型变量号量，常定义为记录型变量s，其中一个域其中一个域为整型、另一个域为队列，其元素为等待为整型、另一个域为队列，其元素为等待该信号量的阻塞进程该信号量的阻塞进程（FIFO）。）。信号量定义信号量定义Type semaphore=recordCount:integerQueue:list of processEnd;Var s:semaphore;定义对

47、信号量的两个原子操作定义对信号量的两个原子操作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.count+1;if s.count = 0 Thenbegin 唤醒队首进程；唤醒队首进程； 将进程将进程从从s.queue阻塞队列中移出；阻塞队列中移出；End;Wait、singal的应用的应用进程进入临界区之前，首先执行进程进入临界

48、区之前，首先执行wait(s)原语，若原语，若s.count0,则进程调用阻塞原语，将自己阻塞，则进程调用阻塞原语，将自己阻塞，并插入并插入到到s.queue队列排列。队列排列。注意，阻塞进程不会占用处理机时间，不是注意，阻塞进程不会占用处理机时间，不是“忙忙等等”，直到某个从临界区退出的进程执行，直到某个从临界区退出的进程执行signal(s)原语，唤醒它。原语，唤醒它。一旦其它某个进程执行一旦其它某个进程执行了了sigal(s)原语中的原语中的s.count+1操作后，发现操作后，发现s.count=0，即阻塞队即阻塞队列中还有被阻塞进程，则调用唤醒原列中还有被阻塞进程，则调用唤醒原语，把

49、语，把s.queue中第一个进程修改为就绪状态，送就绪中第一个进程修改为就绪状态，送就绪队列，准备执行临界区代码。队列，准备执行临界区代码。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信号

50、量的类型信号量的类型信号量分为：互斥信号量和资源信号量。信号量分为：互斥信号量和资源信号量。互斥信号量用于申请或释放资源的使用权，常初始化互斥信号量用于申请或释放资源的使用权，常初始化为为1。资源信号量用于申请或归还资源，可以初始化为大于资源信号量用于申请或归还资源，可以初始化为大于1的的正整数，表示系统中某类资源的可用个数。正整数，表示系统中某类资源的可用个数。Wait操作用于申请资源（或使用权），进程执行操作用于申请资源（或使用权），进程执行wait原语原语时，可能会阻塞自己；时，可能会阻塞自己；Signal操作用于释放资源（或归还资源使用权），进程执操作用于释放资源（或归还资源使用权），

51、进程执行行signal原语时，有责任唤醒一个阻塞进程。原语时，有责任唤醒一个阻塞进程。信号量的物理意义信号量的物理意义s.count = 0表示还可执行表示还可执行wait(s)而不会阻塞的而不会阻塞的进程数（可用资源数），每执行一次进程数（可用资源数），每执行一次wait(s)操作，操作，就意味着请求分配一个单位的资源。就意味着请求分配一个单位的资源。当当s.count 0时，表示已无资源可用，因此请求时，表示已无资源可用，因此请求该资源的进程被阻塞，此时该资源的进程被阻塞，此时，s.count的绝对值等的绝对值等于该信号量阻塞队列中的等待进程数于该信号量阻塞队列中的等待进程数。执行一次。执

52、行一次signal操作，就意味着释放一个单位的资源操作，就意味着释放一个单位的资源，若，若s.count0,表示表示s.queue队列中还有被阻塞的进队列中还有被阻塞的进程，需要唤醒该队列中的第一个进程，将它转移程，需要唤醒该队列中的第一个进程，将它转移到就绪队列中。到就绪队列中。s.Count的取值范围的取值范围当仅有两个并发进程共享临界资源时，互当仅有两个并发进程共享临界资源时，互斥信号量仅能斥信号量仅能取值取值0、1、-1，其中，其中，s.count=1,表示无进程进入临界区表示无进程进入临界区s.count=0,表示已有一个进程进入临界区表示已有一个进程进入临界区s.count=-1,

53、则表示已有一进程正在等待进则表示已有一进程正在等待进入临界区入临界区当当用用s来实现来实现n个进程的互斥个进程的互斥时，时，s.count 的取值范围的取值范围为为1 -(n-1)操作系统内核以系统调用形式提供操作系统内核以系统调用形式提供wait和和signal原语，应用程序通过该系统调原语，应用程序通过该系统调用实现进程间的互斥。用实现进程间的互斥。工程实践证明，利用信号量方法实现进工程实践证明，利用信号量方法实现进程互斥是高效的，一直被广泛采用。程互斥是高效的，一直被广泛采用。 进程间的相互作用利用信号量实现进程互斥的过程描述 为使多个进程互斥地访问某个临界资源，只需为该资源设置一个信号

54、量，并设其初始值为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(); 进程间的相互作用 利用信号量来描述程序或语句之间的前趋关系 可以利用信号量，按照语句

55、的前驱趋关系（如图所示如图所示），可写出一个可并发执行的程序，其描述如下例：有例：有6 6个语句的前驱图个语句的前驱图main()main() semaphore a=b=c=d=e=f=g=0;semaphore a=b=c=d=e=f=g=0;cobegincobegin T1;signal(a);signal(b); T1;signal(a);signal(b); wait(a);T2;signal(c);signal(d); wait(a);T2;signal(c);signal(d); wait(b);T3;signal(e); wait(b);T3;signal(e); wait(

56、d);T4;signal(f); wait(d);T4;signal(f); wait(c);T5;signal(g); wait(c);T5;signal(g); wait(e);wait(f);wait(g);T6; wait(e);wait(f);wait(g);T6; 经典进程互斥与同步问题经典进程互斥与同步问题生产者生产者/消费者问题消费者问题读者读者/写者问题写者问题哲学家进餐问题哲学家进餐问题生产者与消费者问题生产者与消费者问题生产者与消费者问题生产者与消费者问题生产者与消费者是一个广义的概念，可以生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程。代表一类具有相同属

57、性的进程。生产者和消费者进程共享一个大小固定的生产者和消费者进程共享一个大小固定的缓冲区，其中，一个或多个生产者生产数缓冲区，其中，一个或多个生产者生产数据，并将生产的数据存入缓冲区，并有一据，并将生产的数据存入缓冲区，并有一个消费者从缓冲区中取数据。个消费者从缓冲区中取数据。假设缓冲区的大小假设缓冲区的大小为为n（存储单元的个数）存储单元的个数），它可以被生产者和消费者循环使用。，它可以被生产者和消费者循环使用。分别设置两个指针分别设置两个指针in和和out ,指向生产者指向生产者将存放数据的存储单元和消费者将取数将存放数据的存储单元和消费者将取数据的存储单元。据的存储单元。生产者与消费者循

58、环使用缓冲区?不控制生产者不控制生产者/消费者消费者指针指针in和和out初始化指向缓冲区的第一个存储单元。初始化指向缓冲区的第一个存储单元。生产者通过生产者通过In指针向存储单元存放数据，一次存指针向存储单元存放数据，一次存放一条数据放一条数据，且，且In指针向后移一个位置。指针向后移一个位置。消费者从缓冲区中逐条取走数据，一次取一条数消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为据，相应的存储单元变为“空空”，每取走一条数，每取走一条数据据，out指针向后移一个存储单元位置。指针向后移一个存储单元位置。试想，如果不控制生产者与消费者，会产生什么试想，如果不控制生产者与消费

59、者，会产生什么结果？结果？生产者生产者/消费者必须互斥消费者必须互斥生产者和消费者可能同进进入缓冲区，甚生产者和消费者可能同进进入缓冲区，甚至可能同时至可能同时读读/写一个存储单元，将导致执写一个存储单元，将导致执行结果不确定。行结果不确定。这显然是不允许的，必须使生产者和消费这显然是不允许的，必须使生产者和消费者互斥进入缓冲区，即，某时刻只允许一者互斥进入缓冲区，即，某时刻只允许一个实体（生产者或消费者）访问缓冲区，个实体（生产者或消费者）访问缓冲区，生产者互斥消费者和其它任何生产者。生产者互斥消费者和其它任何生产者。生产者生产者/消费者必须同步消费者必须同步生产者不能向满缓冲区写数据，消费

60、者也生产者不能向满缓冲区写数据，消费者也不能在空缓冲区中取数据，即生产者与消不能在空缓冲区中取数据，即生产者与消费者必须同步。费者必须同步。生产一条数据是否可用是否有空存储单元存入一条数据归还使用权数据单元加1，唤醒一个消费者有是阻塞等待资源被唤醒阻塞等待使用权被唤醒否无生产者是否可用是否有数据单元取一条数据归还使用权空单元加1，唤醒一个生产者有是阻塞等待资源被唤醒阻塞等待使用权被唤醒否无消费数据消费者Program producer_consumer;Const sizeofbuffer=; /*缓冲区的大小*/Var s:semaphore(:=1); /*互斥信号量s,初始化为1 */

61、n:semaphore(:=0); /*资源信号量n，数据单元，初始化为0 */ e:semaphore(:=sizeofbuffer); /*资源信号量e，空存储单元*/Procedure producer:Begin repeat 生产一条数据； wait(e); wait(s); 存入一条数据; signal(s); signal(n); foreverEnd;Procedure consumer:Begin repeat wait(n); wait(s); 取一条数据； signal(s); signal(e); 消费数据； foreverEnd;Begin /*主程序*/ parbe

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

63、; foreverEnd;Program producer_consumer;Const sizeofbuffer=; /*缓冲区的大小*/Var s:semaphore(:=1); /*互斥信号量s,初始化为1 */ n:semaphore(:=0); /*资源信号量n，数据单元，初始化为0 */ e:semaphore(:=sizeofbuffer); /*资源信号量e，空存储单元*/Procedure consumer:Begin repeat wait(n); wait(s); 取一条数据； signal(s); signal(e); 消费数据；foreverEnd;注意注意进程应该先

64、申请资源信号量，再申请互斥进程应该先申请资源信号量，再申请互斥信号量，顺序不能颠倒。信号量，顺序不能颠倒。对同一个信号时对同一个信号时的的wait与与signal可以不在同可以不在同一个进程中。一个进程中。对任何信号对任何信号量的量的wait与与signal操作必须配对，操作必须配对，同一进程中的多对同一进程中的多对wait与与signal语句只能嵌语句只能嵌套，不能交叉。套，不能交叉。Wait与与signal语句不能颠倒顺序语句不能颠倒顺序，wait语句语句一定一定先于先于signal语句。语句。2009下半年软件设计师考试上午试题进程P1、P2、P3和P4的前趋图如下：P1P4P3P2p1

65、aP1执行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) B.P(S2)P(S3)和P(S4) C.V(S1)V(S2)和P(S4) D.V(S2)V(S3)和V(S4)P1P4P3P2答案(25): C(

66、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(S4)(25) A.P(S3)P(S4)和V(S5)V(S6) B.V(S5)V(S6)和P(S5)P(S6) C.P(

67、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操作写出

68、能够正确操作写出能够正确的执行的程序。的执行的程序。分析分析进程进程A读入一个数读入一个数如果这个数如果这个数MOD 3得到得到0，那么通知进程，那么通知进程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

69、 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(Sempty);END;Process PDBegin P(SD); V(Sempty);END Parend;End;例题例题假设假设有有3个并发进程个并发进程P、Q、R。其中其中P负责负责从输入设备上读入信息并传递从输入设备上读入信息并传递给给Q；Q将信将信息加工后传送息加工后传送给给R；R则负责将信息打印输则负责

70、将信息打印输出。进程出。进程P、Q共享一个共享一个由由m个缓冲区组成个缓冲区组成的缓冲池；进程的缓冲池；进程Q、R共享一个共享一个由由n个缓冲个缓冲区组成的缓冲池（假设缓冲区足够大，进区组成的缓冲池（假设缓冲区足够大，进程间每次传输信息的单位均小于等于缓冲程间每次传输信息的单位均小于等于缓冲区长度）。写出满足上述条件的并发进程。区长度）。写出满足上述条件的并发进程。分析分析这是一个典型的生产者与消费者问题，本题中这是一个典型的生产者与消费者问题，本题中Q既作消费者又作为生产者。既作消费者又作为生产者。3个进程个进程P、Q和和R之间的关系：之间的关系：PQR进程P和Q之间存在着同步关系，进程Q和

71、R之间也存在着同步关系，且进程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,

72、m,0,n,0;Process PBeginLoop: ; P(Sip); P(mutex_1); ; V(Siq); V(mutex_1); Goto loop;End;Process 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; 例：在公共汽车上,司机和售票员各行其职,司机负责开

73、车和到站停车;售票员负责售票和开、关门，当售票员关好车门后，驾驶员才能开车行驶。试用P、V操作实现司机与售票员间的同步。司机和售票员间的同步关系如下图所示：司机正常行车到站停车开车售票关车门开车门售票员解析：设置两个信号量S1、S2，分别表示司机和售票员的私用信号量，其初值均为0。两者之间的同步关系描述如下所示： S1,S2:Semaphore S1:=0;S2:=0; /司机进程Process DriverBeginLoop: ; ; V(S2); P(S1); Goto Loop;End;/售票员进程Process BookingClerk;BeginLoop: ; P(S2); ; ;

74、V(S1); Goto Loop;End;读者读者/写者问题写者问题问题描述问题描述该问题为多个进程访问一个共享数据区，如数据该问题为多个进程访问一个共享数据区，如数据库、文件，内存区及一组寄存器等的数据问题建库、文件，内存区及一组寄存器等的数据问题建立了一个通用模型，其中若干读进程只能读数据，立了一个通用模型，其中若干读进程只能读数据，若干写进程只能写数据。若干写进程只能写数据。例如，一个联网售票系统，数据的查询和更新非例如，一个联网售票系统，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修常频繁，不可避免会出现多个进程试图查询或修改改（读（读/写）其中某一条数据的情形，多个进程

75、同写）其中某一条数据的情形，多个进程同时读一条记录是可以的，但如果一个进程正在更时读一条记录是可以的，但如果一个进程正在更新数据库中的某条记录，则所有其他进程都不能新数据库中的某条记录，则所有其他进程都不能访问（读或写）的记录，否则可能会将同一个座访问（读或写）的记录，否则可能会将同一个座位销售多次。位销售多次。读者读者/写者进程满足的条件写者进程满足的条件允许多个读者进程可以同时读数据；允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据，即只能不允许多个写者进程同时写数据，即只能互斥写数据；互斥写数据；若有写者进程正在写数据，则不允许读进若有写者进程正在写数据，则不允许读进程读数据

76、。程读数据。如何控制读者和写者如何控制读者和写者如果采用生产者如果采用生产者/消费者问题解决方法，严消费者问题解决方法，严格互斥任何读者和写者进程，可以保证数格互斥任何读者和写者进程，可以保证数据更新操作的正确性。据更新操作的正确性。但是，对于若干读者进程，只不过希望查但是，对于若干读者进程，只不过希望查询售票情况，却被严格互斥，严重影响了询售票情况，却被严格互斥，严重影响了系统效率，显然应该让多个读者同时读数系统效率，显然应该让多个读者同时读数据。据。如果一个写者进程正在修改数据，别的写如果一个写者进程正在修改数据，别的写者以及任何读者都不能访问该数据。者以及任何读者都不能访问该数据。读者优

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

78、入读数据，只有当读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。全部读者退出，才允许写者进入写数据。Program readers_writers;Const readcount:integer; /*统计读者的个数*/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); readcoun

79、t:=readcount-1; if readcount=0 then signal(wsem); signal(x);ForeverEnd;Procedure write:Begin repeat wait(wsem); 写数据： signal(wsem); foreverEnd;Begin /*主程序 */ readcount:=0; parbegin reader;writer; parendEnd.写者优先写者优先为了防止为了防止“读者优先读者优先”可能导致写者饥饿，可以考虑写者可能导致写者饥饿，可以考虑写者优先。优先。即，当共享数据区被读者占用时，后续紧邻到达的读者可即，当共享数据区

80、被读者占用时，后续紧邻到达的读者可以继续进入，若这时有一个写者到来且阻塞等待，则写者以继续进入，若这时有一个写者到来且阻塞等待，则写者后面到来的若干读者全部阻塞等待。后面到来的若干读者全部阻塞等待。换句话说，只要有一个写者申请写数据，则不再允许新的换句话说，只要有一个写者申请写数据，则不再允许新的读者进入读数据。这样，写者只需等待先于它到来的读者读者进入读数据。这样，写者只需等待先于它到来的读者完成其读数据任务，而不用等待其后到来的读者。完成其读数据任务，而不用等待其后到来的读者。这种方案解决了写者饥饿问题，但降低了并发程序，使系这种方案解决了写者饥饿问题，但降低了并发程序，使系统的性能较差。

81、统的性能较差。Program readers_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 the

82、n signal(wsem);Signal(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;

83、parbegin reader:writer; parendend.管程管程管程是一种在管程是一种在程序设计级程序设计级控制进程互斥控制进程互斥与同步的机制，具有信号量的功能，且与同步的机制，具有信号量的功能，且更容易使用和控制。更容易使用和控制。目前已有很多程序设计语言支持管程机目前已有很多程序设计语言支持管程机制，如并发制，如并发Pascal、Pascal_Plus、Modula-2、Modula-3、Java等，并且等，并且还作为程序库提供服务。还作为程序库提供服务。利用管程可以锁定任何对象，尤其是链利用管程可以锁定任何对象，尤其是链表型数据结构，可以锁定整个链表，或表型数据结构，可以锁

84、定整个链表，或链表中的某个元素。链表中的某个元素。管程的结构管程的结构管程是由过程、变量及数据结构等组成的集合。管程是由过程、变量及数据结构等组成的集合。典型的管程包括三个部分：典型的管程包括三个部分： (1)对局部于管程的共享数据结构的说明；对局部于管程的共享数据结构的说明； (2)对该数据结构进行操作的一组过程；对该数据结构进行操作的一组过程； (3)对该数据结构初始化的语句。对该数据结构初始化的语句。管程有自己的名字，管程中的各个过程可以带有管程有自己的名字，管程中的各个过程可以带有自己的形式参数，与过程调用一样进行参数替换自己的形式参数，与过程调用一样进行参数替换执行。执行。管程的使用

85、管程的使用管程本身被作为一种临界区，因此，实现管程本身被作为一种临界区，因此，实现管程时，需要考虑互斥、同步和控制变量管程时，需要考虑互斥、同步和控制变量等问题。等问题。进程可在任何需要的地方调用管程中的过进程可在任何需要的地方调用管程中的过程，但不能在管程外直接访问管程内的数程，但不能在管程外直接访问管程内的数据结构。据结构。Type name=monitor /*管程命名 */Var i:integer; /*变最说明 */ c:condition;Procedure P1(x);BeginEnd;Procedure P2(x);BeginEnd;Procedure Pn(x);Begin

86、End;Begin/*初始化语句 */End;用管程实现互斥用管程实现互斥当几个进程调用某个管程时，仅允许一个进程进当几个进程调用某个管程时，仅允许一个进程进入管程，其他进程必须等待，即任何时刻，管程入管程，其他进程必须等待，即任何时刻，管程中只能有一个活跃进程。中只能有一个活跃进程。典型地，当一个进程调用管程中的过程时，若先典型地，当一个进程调用管程中的过程时，若先检查管程中是否有其他的活跃进程，如果有，则检查管程中是否有其他的活跃进程，如果有，则阻塞调用进程、直到管程内的进程离开管程。阻塞调用进程、直到管程内的进程离开管程。管程的互斥操作通常由编译程序支持，编译时自管程的互斥操作通常由编译

87、程序支持，编译时自动为每个管程建立一个初值动为每个管程建立一个初值为为1的互斥信号量。的互斥信号量。用管程实现同步用管程实现同步用管程实现进程同步，是指在管程中要设置一对用管程实现进程同步，是指在管程中要设置一对同步操作原语，例如同步操作原语，例如，wait(或或block)和和signal(或或wakeup）。）。注意，这里注意，这里的的wait和和signal与作用于信号量与作用于信号量的的wait和和signal不同，后者作用于信号量。信号量不同，后者作用于信号量。信号量具有累加功能，当信号量为负数时，其绝对值表具有累加功能，当信号量为负数时，其绝对值表示等待在该信号量上的阻塞进程数。这

88、里示等待在该信号量上的阻塞进程数。这里的的wait和和signal作用于条件变量，条件变量不具有累加作用于条件变量，条件变量不具有累加功能，如果管程中的进程发出了一个信号量，却功能，如果管程中的进程发出了一个信号量，却没有在对应的条件变量上阻塞等待，则该信号量没有在对应的条件变量上阻塞等待，则该信号量没有作用，会被丢失。没有作用，会被丢失。由于进程阻塞等待的原因有多种，为了由于进程阻塞等待的原因有多种，为了区别阻塞等待进程和不同的阻塞队列，区别阻塞等待进程和不同的阻塞队列，管程中设置了不同的条件变量，将因为管程中设置了不同的条件变量，将因为不同事件阻塞的进程组织在不同的队列不同事件阻塞的进程组

89、织在不同的队列中。中。当一个进程利用管程申请资源而未能满当一个进程利用管程申请资源而未能满足时，将调用足时，将调用wait原语阻塞自己，并进原语阻塞自己，并进入相应阻塞队列。当某进程释放出一个入相应阻塞队列。当某进程释放出一个临界资源以后临界资源以后，将用，将用signal原语唤醒等原语唤醒等待在该临界资源上的一个阻塞过进程。待在该临界资源上的一个阻塞过进程。消息传递消息传递进程通信的方式进程通信的方式进程之间的通信内容包含两种类型：进程之间的通信内容包含两种类型：控制控制信息信息与与大批量数据大批量数据。低级通信低级通信：进程之间交换控制信息的过程。：进程之间交换控制信息的过程。高级通信高级

90、通信：进程之间交换批量数据的过程。：进程之间交换批量数据的过程。进程之间同步与互斥是一种低级通信，用进程之间同步与互斥是一种低级通信，用来控制进程执行速度。来控制进程执行速度。发送进程 接收进程邮件邮件邮件接收进程发送进程终端用户发送进程接收进程终端用户发送进程接收进程邮件服件服务器器邮件服件服务器器电子子邮件的件的发送与接收送与接收过程程常用的进程通信机制常用的进程通信机制基于共享存储区方式基于共享存储区方式消息传递方式消息传递方式邮箱机制邮箱机制基于共享存储区方式基于共享存储区方式生产者生产者/消费者问题：生产者与消费者通过消费者问题：生产者与消费者通过共享缓冲区，实现数据传递，属于基于共

91、共享缓冲区，实现数据传递，属于基于共享存储区通信。享存储区通信。这里的共享数据区属于每个互相通信进程这里的共享数据区属于每个互相通信进程的组成部分，这种通信方式不要求数据移的组成部分，这种通信方式不要求数据移动，一般用于本地通信。动，一般用于本地通信。对于远程通信来说，每台计算机拥有各自对于远程通信来说，每台计算机拥有各自的私有内存区，不易实现共享存储区的访的私有内存区，不易实现共享存储区的访问。问。？如何通过共享存储区通信？如何通过共享存储区通信通过程序设计来实现通过程序设计来实现。程序员设计程序时，利用。程序员设计程序时，利用程序指令设置共享存储区，并处理通信进程之间程序指令设置共享存储区

92、，并处理通信进程之间的同步等问题，操作系统只需提供共享存储区。的同步等问题，操作系统只需提供共享存储区。由操作系统在内存中划分出一块区域作为共享存由操作系统在内存中划分出一块区域作为共享存储区储区。进程在通信前向系统申请共享存储区中的。进程在通信前向系统申请共享存储区中的一个分区。然后，申请进程把获得的共享存储分一个分区。然后，申请进程把获得的共享存储分区连接到本进程上，此后便区连接到本进程上，此后便可象读可象读/写普通存储器写普通存储器一样地读一样地读/写共享存储分区，该方式下，通信进程写共享存储分区，该方式下，通信进程之间的同步与互斥访问共享存储区可以由操作系之间的同步与互斥访问共享存储区

93、可以由操作系统实现。统实现。消息传递的机制消息传递的机制消息的一般格式消息传递的同步消息传递的同步进程之间的通信的两条原语：进程之间的通信的两条原语：Send(destination,message)Receive (source, message)消息传递的同步消息传递的同步只有当一个发送进程发送出消息以后，接只有当一个发送进程发送出消息以后，接收进程才能接收消息。收进程才能接收消息。即，当发送进程调用即，当发送进程调用Send原语发送消息时，原语发送消息时，若没有空闲的消息缓冲区，则发送进程阻若没有空闲的消息缓冲区，则发送进程阻塞；当接收进程调用塞；当接收进程调用Receive原语接收消息

94、原语接收消息时，如果没有消息可接收，由接收进程阻时，如果没有消息可接收，由接收进程阻塞，直到一条消息到达。塞，直到一条消息到达。三种同步方式三种同步方式阻塞发送，阻塞接收；进程间的紧密同步。阻塞发送，阻塞接收；进程间的紧密同步。不阻塞发送，阻塞接收；常用于服务进程不阻塞发送，阻塞接收；常用于服务进程为其它进程提供服务。为其它进程提供服务。不阻塞发送，不阻塞接收。不阻塞发送，不阻塞接收。“不阻塞发送不阻塞发送”例如，当进程执行过程中需要打印输出，通常让打印任务例如，当进程执行过程中需要打印输出，通常让打印任务排队等待，而请求打印的进程无须阻塞等待打印完成，即，排队等待，而请求打印的进程无须阻塞等

95、待打印完成，即，每当进程需要打印时，都可以以消息形式发出请求，然后每当进程需要打印时，都可以以消息形式发出请求，然后继续执行。继续执行。“不阻塞发送不阻塞发送”方式容易导致消息的无限发送，无限发送方式容易导致消息的无限发送，无限发送消息会消耗处理机时间，且由于消息需要占用内存的缓冲消息会消耗处理机时间，且由于消息需要占用内存的缓冲区，无限发送消息也会消耗其它系统资源。区，无限发送消息也会消耗其它系统资源。设计并发程序时，若采用设计并发程序时，若采用“不阻塞发送不阻塞发送”方式，就必须在方式，就必须在程序中考虑让接收进程发回应答消息，证实其是否收到消程序中考虑让接收进程发回应答消息，证实其是否收

96、到消息，这将增加程序设计的难度。息，这将增加程序设计的难度。阻塞接收阻塞接收并发程序设计中常采用该方式；并发程序设计中常采用该方式；当接收消息的进程未收到期望的消息时，当接收消息的进程未收到期望的消息时，常需要阻塞等待，直到消息到来，但是，常需要阻塞等待，直到消息到来，但是，如果消息丢失，或发送进程发送消息之前如果消息丢失，或发送进程发送消息之前失败，则接收进程将永久阻塞。失败，则接收进程将永久阻塞。如果采用如果采用“不阻塞接收不阻塞接收”方式，则可能因方式，则可能因为接收方的缘故，丢失消息。为接收方的缘故，丢失消息。消息传递中的寻址消息传递中的寻址寻址方式：直接寻址和间接寻址。寻址方式：直接

97、寻址和间接寻址。若采用直接寻址若采用直接寻址，send原语中必须指定目标进程原语中必须指定目标进程的具体标识号。的具体标识号。Receive原语中的原语中的source地址有两种处理方法：地址有两种处理方法：接收进程显式地指定发送方进程标识号，这就要接收进程显式地指定发送方进程标识号，这就要求接收进程必须事先清楚将接收哪个进程发来的求接收进程必须事先清楚将接收哪个进程发来的消息。消息。接收进程可以不必指定接收哪个进程的消息。接收进程可以不必指定接收哪个进程的消息。间接寻址间接寻址采用间接寻址传递消息时，消息不再从发采用间接寻址传递消息时，消息不再从发送方直接发送到接收方，而是通过发送进送方直接

98、发送到接收方，而是通过发送进程与接收进程共享的一个数据结构进程中程与接收进程共享的一个数据结构进程中转，该数据结构通常称为邮箱。转，该数据结构通常称为邮箱。发送进程将消息发送到指定的邮箱中，接发送进程将消息发送到指定的邮箱中，接收进程从邮箱中接收消息。收进程从邮箱中接收消息。邮箱邮箱邮箱不限制进程数，允许多个发送进程向邮箱不限制进程数，允许多个发送进程向邮箱发送消息，同时，也允许多个接收进邮箱发送消息，同时，也允许多个接收进程从邮箱接收消息。程从邮箱接收消息。利用消息传递实现互斥利用消息传递实现互斥采用采用“不阻塞发送，阻塞接收不阻塞发送，阻塞接收”方式。方式。多个并发执行的发送进程和接收进程

99、共享一个邮多个并发执行的发送进程和接收进程共享一个邮箱箱mutex,它被初始化为一个无内容的它被初始化为一个无内容的“空空”消息。消息。如果一个进程希望进入临界区，首先必须申请从如果一个进程希望进入临界区，首先必须申请从mutex邮箱中接收一条消息若邮箱为邮箱中接收一条消息若邮箱为“空空”，则该进程阻塞（接收）；若进程收到邮箱中的一则该进程阻塞（接收）；若进程收到邮箱中的一条消息，则进入临界区，执行完毕以后，退出临条消息，则进入临界区，执行完毕以后，退出临界区，并将该消息发送回邮箱界区，并将该消息发送回邮箱mutex中。中。Const n=; /*进程数*/Procedure P(I:inte

100、ger);Var msg:message;Begin repeat receive(mutex,msg); /*从邮箱接收一条消息*/ ; send(mutex,msg); /*将消息发回到邮箱 */ foreverEnd.Begin /*主程序*/Create_mailbox(mutex); /*创建邮箱*/Send(mutex_null); /*初始化，向邮箱发送一条空消息*/Parbegin P(1): P(2); P(n)parend注意注意“空空”消息：代表一条消息体为消息：代表一条消息体为“空空”，但具有消息头的但具有消息头的“真正真正”的一条消息，不的一条消息，不是没有消息。是没

101、有消息。当第一个希望进入临界区的进程执行当第一个希望进入临界区的进程执行receive(mutex,msg)语句时，从邮箱语句时，从邮箱mutex中接收了这条中接收了这条“空空”消息，进入临界消息，进入临界区执行。这时，邮箱区执行。这时，邮箱mutex变为变为“空空”，即，即没有消息其后执行没有消息其后执行receive(mutex,msg)语句希望进入临界区的进程被阻塞。语句希望进入临界区的进程被阻塞。注意注意当进入临界区的进程执行完临界区的代码，退出当进入临界区的进程执行完临界区的代码，退出临界区时，执行临界区时，执行send(mutex,msg)语句，将这条语句，将这条“空空”消息归还给

102、邮箱消息归还给邮箱mutex,并唤醒一个阻塞进并唤醒一个阻塞进程，使其取走这条消息，进入临界区执行。程，使其取走这条消息，进入临界区执行。可见，控制进程互斥进入临界区的这条消息本身可见，控制进程互斥进入临界区的这条消息本身可以不含任何有用的内容，它仅被当作进程能否可以不含任何有用的内容，它仅被当作进程能否进入临界区的一种凭证，或令牌。进入临界区的一种凭证，或令牌。只要保证邮箱中最多只有一条消息，就能保证只只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使允许一个进程进入临界区，从而实现进程互斥使用临界资源。用临界资源。利用消息传递解决生产者消费者利用消息传递解

103、决生产者消费者问题问题共使用共使用了了capacity条消息，类似于共享内条消息，类似于共享内存缓冲区中的存缓冲区中的capacity个存储单元。个存储单元。消费者首先将消费者首先将capacity条条“空空”消息发送消息发送给生产者，当生产者向消费者传递一个数给生产者，当生产者向消费者传递一个数据项时，它取走一条据项时，它取走一条“空空”消息，并发送消息，并发送回一条填充了内容的消息。回一条填充了内容的消息。通过这种方式进行数据传递，系统中的总通过这种方式进行数据传递，系统中的总消息数保持不变，所以，消息可以存入在消息数保持不变，所以，消息可以存入在预知数量的内存中。预知数量的内存中。生产者

104、生产者/消费者同步消费者同步如果生产者生产数据的速度比消费者消费如果生产者生产数据的速度比消费者消费数据的速度快，则所有的数据的速度快，则所有的“空空”消息最终消息最终都将被填满，于是生产者将因为接收不到都将被填满，于是生产者将因为接收不到“空空”消息而被阻塞，等待消费者取走带消息而被阻塞，等待消费者取走带有数据的消息，然后返回一条有数据的消息，然后返回一条“空空”消息。消息。如果消费者消费数据的速度更快，则消费如果消费者消费数据的速度更快，则消费者将因为接收不到者将因为接收不到“数据数据”消息而阻塞，消息而阻塞，直到生产者生产并发送来一条直到生产者生产并发送来一条“数据数据”消消息。息。死锁

105、死锁进程的并发控制不仅要控制若干进程的进程的并发控制不仅要控制若干进程的同步与互斥同步与互斥,确保进程之间正常通信确保进程之间正常通信,还还需要解决进程死锁问题。需要解决进程死锁问题。一旦出现进程死锁，相应的进程将无法一旦出现进程死锁，相应的进程将无法向前推进。如果系统内的绝大多数进程向前推进。如果系统内的绝大多数进程或全部进程死锁，那么，整个系统将处或全部进程死锁，那么，整个系统将处于瘫痪状态，造成系统于瘫痪状态，造成系统“死机死机”。交通中的死锁现象进程竞争资源可能引起死锁进程竞争资源可能引起死锁Process P Get A , Get B , Release A , Release B

106、 ,Process Q Get B Get A Release B Release A 进程竞争资源且推进顺序不当可能产生死锁修改进程修改进程P,Q代码代码Process P Get A , Release A , Get B , Release B ,Process Q Get B Release B Get A Release A 死锁的定义死锁的定义死锁死锁(deadlock)概念可以描述为，多个进概念可以描述为，多个进程因为竞争资源，或执行时推进的顺序不程因为竞争资源，或执行时推进的顺序不当，或相互通信而永久阻塞现象，如果没当，或相互通信而永久阻塞现象，如果没有外力作用，这种现象将永远

107、保持下去。有外力作用，这种现象将永远保持下去。若系统出现死锁，必须有相应的措施进行若系统出现死锁，必须有相应的措施进行解除。当然，如果能提前预防和避免死锁解除。当然，如果能提前预防和避免死锁的出现，将能提高系统的运行效率。的出现，将能提高系统的运行效率。引起死锁的原因引起死锁的原因引起进程死锁的一个主要因素是由于进程引起进程死锁的一个主要因素是由于进程竞争系统中的资源竞争系统中的资源，而进程对资源的总需，而进程对资源的总需求量超过系统能提供的最大资源量。求量超过系统能提供的最大资源量。系统中的资源大体可以分为两类：可重用系统中的资源大体可以分为两类：可重用资源和可消耗资源。资源和可消耗资源。可

108、重用资源可重用资源可重用资源，指某一时刻仅允许一个进程可重用资源，指某一时刻仅允许一个进程使用的、不能被进程消耗的，释放以后还使用的、不能被进程消耗的，释放以后还可被其他进程使用的资源。可被其他进程使用的资源。如处理机如处理机、I/O通道和设备通道和设备、内、内/外存储器、外存储器、诸如文件、数据库和信号量之类的数据结诸如文件、数据库和信号量之类的数据结构等。构等。竞争可重用资源可能会死锁竞争可重用资源可能会死锁例如：两个进程例如：两个进程P1、P2互斥修改两张数据库互斥修改两张数据库表表T1、T2、若进程若进程P1打开并锁定表格打开并锁定表格T1、完成修改操作完成修改操作以后，未解锁，又申请

109、修改表格以后，未解锁，又申请修改表格T2。假设这时，表格假设这时，表格T2被进程被进程P2占用且锁定，则进程占用且锁定，则进程P1阻塞等待。阻塞等待。如果进程如果进程P2在修改表格在修改表格T2的过程中，也需要对表的过程中，也需要对表格格T1进行操作，而表格进行操作，而表格T1被进程被进程P1（阻塞阻塞 ）占）占用，不会释放出来。用，不会释放出来。这样进程这样进程P1、P2都会因为等待对方占用的资源而都会因为等待对方占用的资源而阻塞，出现死锁。阻塞，出现死锁。可消耗资源可消耗资源可消耗资源，指可以创造（生产）和撤消可消耗资源，指可以创造（生产）和撤消（消耗）的资源，其数量不限。（消耗）的资源，

110、其数量不限。如中断、信号如中断、信号（signals)、消息消息、buffer中中的数据等。的数据等。进程竞争可消耗的资源也可能产生死锁。进程竞争可消耗的资源也可能产生死锁。Process PReceive(Q,msg1)Send(Q, msg3)Process QReceive(p, msg2)Send(P,msg4)产生死锁的条件产生死锁的条件互斥：竞争的资源一次只能被一个进程使互斥：竞争的资源一次只能被一个进程使用。用。占有且等待：当一个进程占有一些资源，占有且等待：当一个进程占有一些资源，同时又申请新的资源。如果新资源申请失同时又申请新的资源。如果新资源申请失败，进程将占有资源且阻塞等

111、待。败，进程将占有资源且阻塞等待。非剥夺：进程已占有的资源不能被其它进非剥夺：进程已占有的资源不能被其它进程强行剥夺。程强行剥夺。产生死锁的条件产生死锁的条件循环等待：在系统中存在一个由若干进程循环等待：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均形成的环形请求链，其中的每一个进程均占有一些资源，同时又申请环行请求链中占有一些资源，同时又申请环行请求链中下一个进程所占有的资源。下一个进程所占有的资源。进程循环等待：死锁前三个条件是死锁产生的必要条件，但不是充前三个条件是死锁产生的必要条件，但不是充分条件。分条件。互斥条件是临界资源固有的属性，保证进程互互斥条件是临界资源固有的

112、属性，保证进程互斥访问临界资源是必要的，不能因为互斥会导斥访问临界资源是必要的，不能因为互斥会导致死锁而禁止互斥。致死锁而禁止互斥。“占有且等待占有且等待”条件很多时候都存在，也是合条件很多时候都存在，也是合理的，不可能要求进程每次申请新资源时，必理的，不可能要求进程每次申请新资源时，必须释放已占有资源。须释放已占有资源。“非剥夺非剥夺”条件也是应该保留的。允许剥夺的条件也是应该保留的。允许剥夺的资源是指那些，一旦剥夺中断进程的执行以后，资源是指那些，一旦剥夺中断进程的执行以后，可以从断点恢复执行的资源。否则，属于非剥可以从断点恢复执行的资源。否则，属于非剥夺资源。夺资源。第四个条件实际上是前

113、三个条件的可能第四个条件实际上是前三个条件的可能导致的结果，即只有存在互斥、占有且导致的结果，即只有存在互斥、占有且等待与非剥夺条件，就可能出现循环等等待与非剥夺条件，就可能出现循环等待。待。只要系统出现循环等待，则一定出现死只要系统出现循环等待，则一定出现死锁。锁。这四个条件即构成了死锁产生的充分必这四个条件即构成了死锁产生的充分必要条件。要条件。解决死锁的方法解决死锁的方法按照解决死锁的时机不同，可以分为三大按照解决死锁的时机不同，可以分为三大类：类：预防死锁，指进程申请资源必须遵循某些预防死锁，指进程申请资源必须遵循某些预先制定的限制条件，以破坏产生死锁的预先制定的限制条件，以破坏产生死

114、锁的四个必要条件中一个或几个，防止死锁发四个必要条件中一个或几个，防止死锁发生。生。该方法严格限制了系统资源的分配和使用，该方法严格限制了系统资源的分配和使用，会降低系统资源的利用率。会降低系统资源的利用率。解决死锁的方法解决死锁的方法避免死锁：当进程申请资源时，需要首先避免死锁：当进程申请资源时，需要首先判断（预测），如果满足这次资源的请求判断（预测），如果满足这次资源的请求是否会导致死锁，可能导致死锁的资源请是否会导致死锁，可能导致死锁的资源请求将会被拒绝，让请求资源的进程阻塞等求将会被拒绝，让请求资源的进程阻塞等待，直到其所需的资源可分配为止。待，直到其所需的资源可分配为止。该方法并不严

115、格限制产生死锁的四个必要该方法并不严格限制产生死锁的四个必要条件，以提高系统资源的利用率。条件，以提高系统资源的利用率。解决死锁的方法解决死锁的方法检测并解除死锁：当进程申请资源时，不检测并解除死锁：当进程申请资源时，不进行任何限制，即允许死锁发生。但要求进行任何限制，即允许死锁发生。但要求系统定期或不定期检测是否有死锁发生。系统定期或不定期检测是否有死锁发生。当检测到死锁时，再力求解除死锁。当检测到死锁时，再力求解除死锁。实践证明，该方法可进一步提高资源利用实践证明，该方法可进一步提高资源利用率。率。预防死锁：禁止预防死锁：禁止“互斥互斥”产生死锁的第一个条件是产生死锁的第一个条件是“互斥互

116、斥”，而，而“互斥使用互斥使用”是临界资源固有的属性，保证是临界资源固有的属性，保证进程互斥访问临界资源是必要的。不能因进程互斥访问临界资源是必要的。不能因为互斥会导致死锁而禁止互斥。为互斥会导致死锁而禁止互斥。预防死锁：禁止预防死锁：禁止“占有且等待占有且等待”为了禁止为了禁止“占有且等待占有且等待”条件，系统将要条件，系统将要求所有进程一次性地申请其所需要的全部求所有进程一次性地申请其所需要的全部资源。资源。不合理。不合理。第一，降低了系统吞吐量和资源利用率。第一，降低了系统吞吐量和资源利用率。第二，浪费资源。例如，大家都熟悉的条第二，浪费资源。例如，大家都熟悉的条件判断语句，程序中往往少

117、不了它，在程件判断语句，程序中往往少不了它，在程序未执行之前，无法判断条件为真，还是序未执行之前，无法判断条件为真，还是为假。为假。预防死锁：禁止预防死锁：禁止“不剥夺不剥夺”指当一个已经获得了某些资源的进程，再指当一个已经获得了某些资源的进程，再申请的新资源不能立即得到满足时，必须申请的新资源不能立即得到满足时，必须释放其已获得的所有资源，不论是何种资释放其已获得的所有资源，不论是何种资源。源。这种预防死锁的策略实现起来比较复杂，这种预防死锁的策略实现起来比较复杂，而且要付出很大代价。而且要付出很大代价。预防死锁：禁止预防死锁：禁止”环路环路”为了避免进程申请资源形成环路，首先将系统中为了避

118、免进程申请资源形成环路，首先将系统中的所有资源按类型进行线性排序，并赋予不同的的所有资源按类型进行线性排序，并赋予不同的序号。序号。所有进程对资源的请求，必须严格按资源序号递所有进程对资源的请求，必须严格按资源序号递增的次序提出，这样在所形成的资源分配中不可增的次序提出，这样在所形成的资源分配中不可能出现环路。能出现环路。事实上，采用这种策略时，总有一个进程占据了事实上，采用这种策略时，总有一个进程占据了较高序号的资源，它继续请求的资源必须是空闲较高序号的资源，它继续请求的资源必须是空闲的，因此进程可一直向前推进。的，因此进程可一直向前推进。预防死锁：禁止预防死锁：禁止”环路环路”较之前两种策

119、略，不论是资源利用率，还较之前两种策略，不论是资源利用率，还是系统吞吐量，都有显著的改善。是系统吞吐量，都有显著的改善。但也存在严重问题。但也存在严重问题。第一，为系统中各类资源分配序号必须相第一，为系统中各类资源分配序号必须相对稳定，这就限制了新设备类型的增加。对稳定，这就限制了新设备类型的增加。第二，会经常发生作业使用的顺序与系统第二，会经常发生作业使用的顺序与系统规定顺序不同的情况，造成资源浪费。规定顺序不同的情况，造成资源浪费。第三，增加了程序设计难度。第三，增加了程序设计难度。避免死锁避免死锁预防死锁限制条件太强，不利于提高系统吞吐量预防死锁限制条件太强，不利于提高系统吞吐量和资源利

120、用率，而且增加了程序设计难度，因此，和资源利用率，而且增加了程序设计难度，因此，该方法在死锁解决中不常用。该方法在死锁解决中不常用。避免死锁方法通过资源分配之前预防是否会导致避免死锁方法通过资源分配之前预防是否会导致死锁、决定是否进行此次资源分配。只有不会导死锁、决定是否进行此次资源分配。只有不会导致死锁的资源请求才实施分配，否则，让请求进致死锁的资源请求才实施分配，否则，让请求进程阻塞等待。程阻塞等待。首先介绍系统的两个状态：安全状态和不安全状首先介绍系统的两个状态：安全状态和不安全状态。态。安全状态安全状态VS.不安全状态不安全状态安全状态是指系统能按某种进程顺序安全状态是指系统能按某种进

121、程顺序，如，如,分别分别为这为这n个进程分配其所个进程分配其所需资源，直至最大需求，使每个进程都能需资源，直至最大需求，使每个进程都能顺利完成。顺利完成。称称序列为安全序列。序列为安全序列。若系统不存在这样的一个安全序列，则称若系统不存在这样的一个安全序列，则称系统处于不安全状态。系统处于不安全状态。安全状态安全状态vs.不安全状态不安全状态若系统处于安全状态，且按照某个安全序若系统处于安全状态，且按照某个安全序列分配资源，可以保证系统不会出现死锁。列分配资源，可以保证系统不会出现死锁。并非所有不安全状态都是死锁状态。并非所有不安全状态都是死锁状态。当系统进入不安全状态以后，便可能进入当系统进

122、入不安全状态以后，便可能进入死锁状态。死锁状态。因此，避免死锁的实质在于：因此，避免死锁的实质在于：如何避免系如何避免系统进入不安全状态。统进入不安全状态。假定假定系统有三个进程系统有三个进程P1,P2和和P3 ，共有共有14台打台打印机。印机。进程进程P1总共要求总共要求12台打印机台打印机，P2和和P3分别分别要求要求4台和台和9台。台。假设假设T0时刻，进程时刻，进程P1、P2和和P3已分别获得已分别获得5台、台、2台和台和4台，台，尚有尚有3台空闲未分台空闲未分。进程 最大需求 已分配 还需要可用P112573P2422P3945T0时刻系统是安全的，存在一个安全序列安全状态向不安全状

123、态转换安全状态向不安全状态转换如果不按照安全顺序分配资源如果不按照安全顺序分配资源,则系统将由则系统将由安全状态进入不安全状态。安全状态进入不安全状态。例如例如，在，在T0时刻，时刻，P1又请求又请求1台打印机，若台打印机，若系统此时把剩余系统此时把剩余3台中的台中的1台分配给台分配给P1，则，则系统进入不安全状态。系统进入不安全状态。例：银行家算法例：银行家算法银行发放一笔贷款前，预测该笔贷款是否银行发放一笔贷款前，预测该笔贷款是否会引起银行资金周转问题。会引起银行资金周转问题。这里，银行的资金就类似于计算机系统的这里，银行的资金就类似于计算机系统的资源，贷款业务类似于计算机的资源分配。资源

124、，贷款业务类似于计算机的资源分配。银行家算法能预测一笔货款业务对银行是银行家算法能预测一笔货款业务对银行是否是安全的，该算法也能预测一次资源分否是安全的，该算法也能预测一次资源分配对计算机系统是否是安全的。配对计算机系统是否是安全的。为了实现银行家算法，系统中必须设置若为了实现银行家算法，系统中必须设置若干数据结构。干数据结构。数据结构数据结构1.可利用资源向量可利用资源向量Available是一个具有是一个具有m个元素个元素的数组，其中的每一个元素代表一类可利用资源的数组，其中的每一个元素代表一类可利用资源的数目，其初始值为系统中该类资源的最大可用的数目，其初始值为系统中该类资源的最大可用数

125、目。其值将随着该类资源的分配与回收而动态数目。其值将随着该类资源的分配与回收而动态改变改变。Availablej=k，表示系统中现有表示系统中现有Rj类资源类资源k个个.2.最大需求矩阵最大需求矩阵Max是一个是一个n*m的矩阵，定义了系的矩阵，定义了系统统中中n个进程中的每一个进程对个进程中的每一个进程对m类资源的最大需类资源的最大需求求。Max(i,j)=k,表示进程表示进程i当前已分得当前已分得Rj类类资源的资源的数目数目为为k个。个。数据结构数据结构分配矩阵分配矩阵Allocation是一个是一个n*m的矩阵，定的矩阵，定义了系统中每一类资源的数量。例如义了系统中每一类资源的数量。例如

126、，Allocation(i,j)=k,表示进程表示进程i当前已分得当前已分得Rj类资源的数目为类资源的数目为k 个。个。需求矩阵需求矩阵Need是一个是一个n*m矩阵，用以表示矩阵，用以表示每一个进程尚需的各类资源数。例如每一个进程尚需的各类资源数。例如，Needi,j=k,表示进程表示进程i还需要还需要Rj资源资源k个，个，方能完成其任务。方能完成其任务。数据结构数据结构上述三类矩阵存在下述关系：上述三类矩阵存在下述关系：Needi,j=Maxi,j-Allocationi,j设Requesti是进程Pi的请求向量。Requestij=k,表示进程Pi需要k个Rj类资源。当进程Pi发出资源请

127、求后，系统按下述步骤进行检查：1.如果，Requestj= Needi,则转向步骤2；否则，出错。2.如果，Requestj=Available,则转向步骤3；否则，表示尚无足够资源可供分配，进程Pi必须阻塞等待。3.系统试探性地将Pi申请的资源分配给它，并修改下列数据结构的值：Available:= Availale-Requesti;Allocation:= Allocation+Requesti;Needi= Needi- Requesti;4.系统利用安全性算法，检查此次资源分配以后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi ，完成本次资源分配；否则，试探分配失效，让进

128、程Pi阻塞等待。安全性算法安全性算法（1）设置两个工作向量a.设置一个数组Finishn。当Finishi=True(0=i=n,n为系统统中的进程数）时，表示进程Pi可以获得其所需的全部资源，而顺利执行完成。b.设置一个临时向量Work，表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行时，Work:=Available(2)从进程集合中找到一个满足下列条件的进程：Finishi=false; 并且 Need = Work;若找到满足该条件的进程，则执行步骤(3)，否则执行步骤（4）；（3）当进程Pi获得资源后，将顺利执行直至完成，并释放其所拥有的全部资源，故应执行以下操作：Wo

129、rk:=Work+Allocationi;以及Finishi:=True;转向步骤（2）；(4)如果所有进程的Finishi=True，则表示系统处于安全状态，否则系统处于不安全状态。例题设系统中有种类型的资源(A、B、C)和个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5,C资源的数量为20。在T0时刻系统的状态如下表所示。系统采用银行家算法实施死锁避免策略。进程最大资源需求量已分配资源数量 A B C A B CP1P2P3P4P5 5 5 9 5 3 6 4 0 11 4 2 5 4 2 4 2 1 2 4 0 2 4 0 5 2 0 4 3 1 4例题 T0时刻

130、是否为安全状态？若是，请给出安全序列。解答由题目所给出的最大资源需求量和已分配资源数量，可以计算出T0时刻各进程的资源需求量Need，Need=最大资源需求量-分配资源数量。如下表所示。进程资源需求量 A B CP1P2P3P4P5 3 4 7 1 3 4 0 0 6 2 2 1 1 1 0进程最大资源需求量已分配资源数量 A B C A B CP1P2P3P4P5 5 5 9 5 3 6 4 0 11 4 2 5 4 2 4 2 1 2 4 0 2 4 0 5 2 0 4 3 1 4解答利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全序列，分析情况如下表所示。进程WorkA B

131、 CNeedA B CAllocationA B CWork+AllocationA B CFinishP5P4P3P2P12 3 35 4 77 4 1111 4 1615 4 18 1 1 0 2 2 1 0 0 6 1 3 4 3 4 7 3 1 4 2 0 4 4 0 5 4 0 2 2 1 2 5 4 7 7 4 11 11 4 16 15 4 18 17 5 20TrueTrueTrueTrue True 从上述情况分析中可以看出，此时存在一个安全序列P5,P4,P3,P2,P1,故该状态是安全的。死锁避免的资源分配策略设系统中有3种类型的资源R1,R2,R3和5个进程P1、P2、

132、P3、P4、P5，R1资源数量为10，R2资源数量为5，R3资源数量为7，在某个时刻系统的状态如：MaxAllocationNeedAvailableR1R2 R3R1R2R3R1R2R3R1R2R3P1753010743332P2322200122P3902302600P4222211011P5433002431（1）利用银行家算法对此时的资源分配情况进行分析，可得此时的安全性分析情况如下表：WorkNeedAllocationWork+AllocationR1 R2 R3 R1 R2 R3R1R2 R3R1R2R3P2332122200532P4532011211743P574343100

133、2745P37456003021047P110477430101057（1）若此时P2请求资源Request(1,0,2),系统按银行家算法进行检测： Request(1,0,2) = Need(1,2,2) Request(1,0,2) = Available(3,3,2) 资源变化情况如下：MaxAllocationNeedAvailableR1R2 R3R1R2R3R1R2R3R1R2R3P1753010743230P2322302020P3902302600P4222211011P5433002431 再利用安全性算法检查此时系统是否安全，分析如表： 安全性分析情况WorkNeedAl

134、locationWork+AllocationR1 R2 R3 R1 R2 R3R1R2 R3R1R2R3P2230020302532P4532011211743P5743431002745P1745743010755P37556003021057 (3)在（2）的基础上P5发出资源请求Request(3,3,0)，系统按照银行家算法进行检查： Request(3,3,0) = Need(4,3,1) Request(3,3,0) = Available(2,3,0) 所以让P5等待。 (3)在（3）的基础上P1发出资源请求Request(0,2,0)，系统按照银行家算法进行检查： Reque

135、st(0,2,0) = Need(7,4,3) Request(0,2,0) = Available(2,3,0) 系统试探性分配，修改相应向量，形成的资源变化情况如下表：AllocationNeedAvailableR1R2R3R1R2R3R1R2R3P1030723210P2302020P3302600P4211011P5002431系统进入不安全状态避免死锁不象预防死锁那样需要剥夺进避免死锁不象预防死锁那样需要剥夺进程已获得的资源，或重新执行进程。而程已获得的资源，或重新执行进程。而且，避免死锁比预防死锁施加的限制条且，避免死锁比预防死锁施加的限制条件要弱得多。件要弱得多。但它仍然有限制

136、条件：但它仍然有限制条件：（1）预先必须申明每个进程需要的资源总）预先必须申明每个进程需要的资源总量；量；（2）进程之间相互独立，其执行顺序取决）进程之间相互独立，其执行顺序取决于系统安全，而非进程间的同步要求。于系统安全，而非进程间的同步要求。（3）系统必须提供固定数量的资源供进程）系统必须提供固定数量的资源供进程使用。使用。（4）若进程占有系统资源，则不能让其退）若进程占有系统资源，则不能让其退出系统。出系统。检测并解除死锁检测并解除死锁如果系统不愿意附加太多约束条件预防死如果系统不愿意附加太多约束条件预防死锁，也不希望系统额外开销预测并避免死锁，也不希望系统额外开销预测并避免死锁，那么，

137、只能允许死锁出现，然后再解锁，那么，只能允许死锁出现，然后再解除它。除它。因此，系统需要利用某种方法来检测死锁。因此，系统需要利用某种方法来检测死锁。检测死锁资源分配图的简化死锁定理死锁定理若能消去资源分配图中所有结点的连接边，若能消去资源分配图中所有结点的连接边，使用全部结点都成为使用全部结点都成为孤立点孤立点，则称该图可，则称该图可完全简化图；若不能使该图完全简化，则完全简化图；若不能使该图完全简化，则称该图是不可完全化简图。称该图是不可完全化简图。可以证明：当且仅当系统某状态可以证明：当且仅当系统某状态S所对应的所对应的资源分配图是不可完全化简的资源分配图是不可完全化简的，则，则S是死锁

138、是死锁状态，该充分条件称为状态，该充分条件称为死锁定理死锁定理。解除死锁解除死锁撤消死锁进程。该方法是目前操作系统中撤消死锁进程。该方法是目前操作系统中解除死锁的常用方法。解除死锁的常用方法。把死锁进程恢复到前一个检查点，重新执把死锁进程恢复到前一个检查点，重新执行每个进程。行每个进程。按照某种原则逐个选择死锁进程进行撤消，按照某种原则逐个选择死锁进程进行撤消，直到解除系统死锁。直到解除系统死锁。按照某种原则逐个剥夺进程资源，直到解按照某种原则逐个剥夺进程资源，直到解除死锁。除死锁。最小代价原则最小代价原则到目前为止，花费处理机的时间最少的进到目前为止，花费处理机的时间最少的进程；程；到目前为

139、止，产生输出最少的进程；到目前为止，产生输出最少的进程；估计未执行部分最多的进程；估计未执行部分最多的进程；到目前为止，已获得资源量最少的进程；到目前为止，已获得资源量最少的进程；优先级最低的进程。优先级最低的进程。哲学家就餐问题哲学家就餐问题问题描述问题描述五个哲学家围坐在一张五个哲学家围坐在一张圆桌周围，每个哲学家圆桌周围，每个哲学家面前都有一碗面，相邻面前都有一碗面，相邻两碗面条之间有一只筷两碗面条之间有一只筷子，只有同时获得两只子，只有同时获得两只筷子，才能开始吃面条。筷子，才能开始吃面条。Program diningphilosophers;var fork:array04 of s

140、emaphore(:=1);i:integer;Procedure philosopher(i:integer);Begin repeat think; wait(forki); wait(fork(i+1) mod 5); eat; signal(fork(i+1)mod 5); signal(forki); foreverend;begin parbegin philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4); parendend.改进改进能否规定：当哲学家获得了其左边的筷子以后，能否

141、规定：当哲学家获得了其左边的筷子以后，查看其右边的筷子是否可用，如果不可用，则查看其右边的筷子是否可用，如果不可用，则“谦让谦让”，放下其已获得的左边的筷子，等一段时，放下其已获得的左边的筷子，等一段时间再重复整个过程。间再重复整个过程。但是，存在问题，可能反复但是，存在问题，可能反复“谦让谦让”下去。下去。这种情况下，所有的哲学家都在这种情况下，所有的哲学家都在“忙碌忙碌”，但却，但却无法取得进展，称为无法取得进展，称为“饥饿饥饿”现象。现象。改进改进可以可以在新买在新买5只筷子（对于计算机系统来说，只筷子（对于计算机系统来说，需要增加资源，似乎不可能的），或教会需要增加资源，似乎不可能的）

142、，或教会哲学家用一只筷子吃面条。哲学家用一只筷子吃面条。另一种有效方法是，增加一位服务员，让另一种有效方法是，增加一位服务员，让他安排其中的四位哲学家入座，四位哲学他安排其中的四位哲学家入座，四位哲学家竞争五只筷子，必然有一位哲学家能同家竞争五只筷子，必然有一位哲学家能同时获得两只筷子，当他进餐完毕，再安排时获得两只筷子，当他进餐完毕，再安排剩下的那位哲学家入座，参与五只筷子的剩下的那位哲学家入座，参与五只筷子的竞争。这样，五位哲学家都能顺利进餐。竞争。这样，五位哲学家都能顺利进餐。Program diningphilosophers;var fork:array04 of semaphore

143、(:=1); room:semaphore(:=4); i:integer;Procedure philosopher(i:integer);Begin repeat think; wait(room); wait(forki); wait(fork(i+1) mod 5); eat; signal(fork(i+1)mod 5); signal(forki); signal(room); foreverend;begin parbegin philosopher(0); philosopher(1); philosopher(2); philosopher(3); philosopher(4

144、); parendend.多线程多线程操作系统中引入进程的目的是，为了描述和实现操作系统中引入进程的目的是，为了描述和实现多个程序的并发执行，以改善资源利用率及提高多个程序的并发执行，以改善资源利用率及提高系统的吞吐量。系统的吞吐量。为什么还需要引入线程？这是为了减少程序并发为什么还需要引入线程？这是为了减少程序并发执行时系统所付出的额外开销，使操作系统具有执行时系统所付出的额外开销，使操作系统具有更好的并发性。更好的并发性。进程的两个基本属性：进程的两个基本属性：进程是一个拥有资源的独立单位；进程是一个拥有资源的独立单位；进程同时又是一个可以独立调度的基本单位。进程同时又是一个可以独立调度的

145、基本单位。系统为进程进行的操作系统为进程进行的操作创建进程、撤消进程、进程切换。创建进程、撤消进程、进程切换。进程作为资源的拥有者和系统的调度对象，进程作为资源的拥有者和系统的调度对象，需要花费系统较大的额外开销。故，系统需要花费系统较大的额外开销。故，系统中同时存在的进程数目不宜过多，进程切中同时存在的进程数目不宜过多，进程切换的频率也不宜过高，而这也就限制了并换的频率也不宜过高，而这也就限制了并发度的进一步提高发度的进一步提高。由进程到线程由进程到线程目标：既能提高进程并发度，又能降低系统的额目标：既能提高进程并发度，又能降低系统的额外开销。外开销。实现：实现：将进程的资源申请和调度属性分

146、开，即进将进程的资源申请和调度属性分开，即进程作为资源的申请和拥有者，但不作为调度的基程作为资源的申请和拥有者，但不作为调度的基本单位本单位。这样，就产生了线程的概念。这样，就产生了线程的概念。线程是进程中的一个实体，是独立调度和分派的线程是进程中的一个实体，是独立调度和分派的基本单位基本单位。线程自身基本上不拥有系统资源，只拥有少许运线程自身基本上不拥有系统资源，只拥有少许运行中必不可少的私有资源。线程可与同属一个进行中必不可少的私有资源。线程可与同属一个进程的其它线程共享进程的全部资源。程的其它线程共享进程的全部资源。线程的状态线程的状态进程的所有线程共享该进程的状态。进程的所有线程共享该

147、进程的状态。线程具有三种基本状态：就绪、执行和阻线程具有三种基本状态：就绪、执行和阻塞。塞。一般不具有挂起状态，因为线程共享进程一般不具有挂起状态，因为线程共享进程的资源，包括存储空间，如果挂起一个进的资源，包括存储空间，如果挂起一个进程，其所属的全部进程必将被挂起，而单程，其所属的全部进程必将被挂起，而单独挂起某进程中的一个线程，必然会影响独挂起某进程中的一个线程，必然会影响同一进程中的其它线程的执行，这是没有同一进程中的其它线程的执行，这是没有任何意义的。任何意义的。对线程的操作对线程的操作一个进程可以创建和撤销一个或多个线程。一个进程可以创建和撤销一个或多个线程。同一进程中的多个线程可以

148、并发执行。同一进程中的多个线程可以并发执行。对线程的操作包括：对线程的操作包括：派生派生（Spawn），），当系统创建一个进程时，当系统创建一个进程时，同时也为该进程派生一个线程，同一进程同时也为该进程派生一个线程，同一进程中的线程可以再派生其它线程。中的线程可以再派生其它线程。阻塞阻塞（Block），），当线程需要等待某事件时，当线程需要等待某事件时，它将被阻塞，释放处理机执行其它线程。它将被阻塞，释放处理机执行其它线程。对线程的操作对线程的操作解除阻塞解除阻塞（Unblock），），当线程的阻塞事件当线程的阻塞事件发生，其状态转换为就绪，并插入到就绪发生，其状态转换为就绪，并插入到就绪队列

149、，等待调度执行。队列，等待调度执行。结束结束（Finish），），当线程执行完毕，释放其当线程执行完毕，释放其私有资源。私有资源。注意：线程阻塞不一定会引起整个进程的注意：线程阻塞不一定会引起整个进程的阻塞，否则，引入线程带来的并发性就不阻塞，否则，引入线程带来的并发性就不会提高。会提高。进程与线程进程与线程传统操作系统中，一个进程可以创建一个传统操作系统中，一个进程可以创建一个线程、如线程、如MS DOS就是一个单用户、单进程、就是一个单用户、单进程、单线程的操作系统单线程的操作系统，UNIX是一个多用户、是一个多用户、多进程、单线程的操作系统。多进程、单线程的操作系统。现代操作系统和软件设

150、计大多支持多线程现代操作系统和软件设计大多支持多线程运行。例如运行。例如：Java虚拟机是一个单进程、虚拟机是一个单进程、多线程的运行环境多线程的运行环境，Windows系列操作系系列操作系统和统和Linux操作系统都采用了多进程、多线操作系统都采用了多进程、多线程技术。程技术。进程进程与线程与线程调度调度传统操作系统中，进程既是拥有资源的基传统操作系统中，进程既是拥有资源的基本单位，又是独立调度的基本单位。本单位，又是独立调度的基本单位。引入线程的操作系统中，引入线程的操作系统中，线程是独立调度线程是独立调度的基本单位，进程是资源拥有的基本单位的基本单位，进程是资源拥有的基本单位，从而可以显

151、著地提高系统的并发程度。从而可以显著地提高系统的并发程度。同一进程中的线程间切换不会引起进程切同一进程中的线程间切换不会引起进程切换，但当一个进程中的线程切换到别一进换，但当一个进程中的线程切换到别一进程中的线程时，将会引起进程切换。程中的线程时，将会引起进程切换。进程进程与线程与线程并发并发进程之间可以并发执行。进程之间可以并发执行。同属于一个进程的多个线程之间，亦可并同属于一个进程的多个线程之间，亦可并发执行。发执行。因而使操作系统具有更好的并发性，从而因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统的吞能更有效地使用系统资源和提高系统的吞吐量。吐量。进程与进程与线程线

152、程并发并发例：例：在一个未引入线程的单处理机操作系统中，若仅在一个未引入线程的单处理机操作系统中，若仅设置一个文件服务进程，当它由于某种原因而被设置一个文件服务进程，当它由于某种原因而被阻塞时，便没有其它的文件服务进程来提供服务。阻塞时，便没有其它的文件服务进程来提供服务。引入线程以后，可以在一个文件服务进程中设置引入线程以后，可以在一个文件服务进程中设置多个服务线程，当第一个线程阻塞时，文件服务多个服务线程，当第一个线程阻塞时，文件服务进程中的第二个线程可以继续运行；当第二个线进程中的第二个线程可以继续运行；当第二个线程阻塞时，第三个线程可以继续执行，从而显著程阻塞时，第三个线程可以继续执行

153、，从而显著地提高了文件服务的质量和系统的吞吐量。地提高了文件服务的质量和系统的吞吐量。进程与进程与线程线程拥有资源拥有资源进程是拥有资源的独立单位，它有权申请进程是拥有资源的独立单位，它有权申请系统的各类资源。系统的各类资源。线程除了拥有很少的私有资源以外，不能线程除了拥有很少的私有资源以外，不能申请系统资源，可以共享其所属进程的资申请系统资源，可以共享其所属进程的资源，即，进程的代码段、数据段以及系统源，即，进程的代码段、数据段以及系统资源，如已打开的文件资源，如已打开的文件、I/O设备等，都可设备等，都可被其内的所有线程共享。被其内的所有线程共享。进程进程与线程与线程系统开销系统开销操作系

154、统管理进程的开销显著地大于管理操作系统管理进程的开销显著地大于管理线程所需的开销。线程所需的开销。进程切换的开销也远大于线程切换的开销。进程切换的开销也远大于线程切换的开销。由于同一进程中的多个线程具有相同的地由于同一进程中的多个线程具有相同的地址空间，使它们之间的同步和通信也比较址空间，使它们之间的同步和通信也比较容易。容易。有些类型的线程切换抽象、同步和通信都有些类型的线程切换抽象、同步和通信都无需操作系统内核的干预。无需操作系统内核的干预。线程的类型线程的类型用户级线程和内核级线程。用户级线程和内核级线程。用户级线程的创建、撤消及切换等操作全部由支用户级线程的创建、撤消及切换等操作全部由

155、支持线程的应用程序完成，内核并不知道线程的存持线程的应用程序完成，内核并不知道线程的存在。在。一些数据库管理系统一些数据库管理系统，如，如Infomix即支持用户级线即支持用户级线程，应用程序可以利用线程库来设计多线程程序，程，应用程序可以利用线程库来设计多线程程序，该线程包含各种用于管理用户级线程的例程，如该线程包含各种用于管理用户级线程的例程，如用于创建和撤消线程的例程，用于线程间传递消用于创建和撤消线程的例程，用于线程间传递消息和数据的例程、线程调度例程，以及保护和恢息和数据的例程、线程调度例程，以及保护和恢复线程上下文的例程等。复线程上下文的例程等。用户级线程用户级线程用户级线程阻塞是

156、否会引起整个进程阻塞呢？用户级线程阻塞是否会引起整个进程阻塞呢？这要视具体情况而定。当某进程中的一个线程需这要视具体情况而定。当某进程中的一个线程需要等待另一线程的输出数据而阻塞时，整个进程要等待另一线程的输出数据而阻塞时，整个进程并不会阻塞。即进程保持执行状态，其内的某个并不会阻塞。即进程保持执行状态，其内的某个线程也是执行状态。线程也是执行状态。当某线程因为当某线程因为I/O阻塞时，内核需要启动系统阻塞时，内核需要启动系统I/O，控制从用户级转到系统内核级，这经常会引起整控制从用户级转到系统内核级，这经常会引起整个进程阻塞，随即将发生进程切换，进程调度程个进程阻塞，随即将发生进程切换，进程

157、调度程序重新调度另一个就绪进程执行。序重新调度另一个就绪进程执行。用户级线程用户级线程用户级线程能节省大量的系统额外开销用户级线程能节省大量的系统额外开销,并提高程并提高程序并发序并发性性,这是因为这是因为:线程的管理和控制仅在用户级进行线程的管理和控制仅在用户级进行,线程切换无须线程切换无须内核干预内核干预,没有模式切换没有模式切换,减少了模式切换的开销。减少了模式切换的开销。调度更灵活。应用程序可以根据需要选用线程库调度更灵活。应用程序可以根据需要选用线程库中不同的线程调度算法。而不受系统内核进程调中不同的线程调度算法。而不受系统内核进程调度程序的约束。度程序的约束。由于线程库独立于系统内

158、核，可以运行在不同的由于线程库独立于系统内核，可以运行在不同的操作系统之上，使用户级线程可以得到不同操作操作系统之上，使用户级线程可以得到不同操作系统的支持，而无须修改操作系统内核。系统的支持，而无须修改操作系统内核。用户级线程用户级线程用户级线程也存在一些问题：用户级线程也存在一些问题：由于很多操作系统的系统调用都会引起阻由于很多操作系统的系统调用都会引起阻塞，用户级线程中的系统调用常常会引起塞，用户级线程中的系统调用常常会引起线程及整个进程阻塞，削弱了线程的并发线程及整个进程阻塞，削弱了线程的并发性。性。由于系统内核不知用户级线程的存在，可由于系统内核不知用户级线程的存在，可能出现进程切换

159、时，强行中断其内某个执能出现进程切换时，强行中断其内某个执行线程的情况。行线程的情况。很难实现不同进程的线程并发。很难实现不同进程的线程并发。内核级线程内核级线程内核级线程的管理全由系统内核完成，应内核级线程的管理全由系统内核完成，应用程序无权进行线程切换等操作，系统为用程序无权进行线程切换等操作，系统为用户程序提供了相应的应用程序编程接口用户程序提供了相应的应用程序编程接口API。W2K、Linux和和OS/2等操作系统即采用内等操作系统即采用内核级线程技术。核级线程技术。内核级线程内核级线程系统内核负责内核级线程的创建、撤消、切换等系统内核负责内核级线程的创建、撤消、切换等操作，应用程序可

160、以设计成多线程程序，多个线操作，应用程序可以设计成多线程程序，多个线程同属于一个进程，系统以线程为调度单位。程同属于一个进程，系统以线程为调度单位。进行线程切换时，需要同时保存整个进程的上下进行线程切换时，需要同时保存整个进程的上下文以及线程的上下文信息。这样，当进程中的某文以及线程的上下文信息。这样，当进程中的某个线程阻塞时，内核可以调度另一个就绪线程执个线程阻塞时，内核可以调度另一个就绪线程执行（同一进程或不同进程）。行（同一进程或不同进程）。线程切换时需要进行模式切换。线程切换时需要进行模式切换。混合模式混合模式由于用户级线程和内核级线程各有自己的由于用户级线程和内核级线程各有自己的优缺

161、点，实际工作设计中可以进行折衷，优缺点，实际工作设计中可以进行折衷，将二者结合起来，成一种混合模式。将二者结合起来，成一种混合模式。混合模式混合模式Solaris操作系统即采用这种技术。操作系统即采用这种技术。在混合模式中，线程的创建、撤消、调度、在混合模式中，线程的创建、撤消、调度、同步等都在用户级应用程序中完成。同步等都在用户级应用程序中完成。应用程序中的多个用户级线程被映射到一应用程序中的多个用户级线程被映射到一个或较少的某些内核级线程。个或较少的某些内核级线程。这样，可以使同一应用程序中的多个线程这样，可以使同一应用程序中的多个线程能分散到不同处理机上并行运行。而且，能分散到不同处理机

162、上并行运行。而且，可以避免因为某些用户级线程的阻塞而引可以避免因为某些用户级线程的阻塞而引起整个进程阻塞的现象。起整个进程阻塞的现象。例题例题（西安理工大学）设有（西安理工大学）设有6个进程个进程P1、P2、P3、P4、P5、P6，它们有如图所示的并发它们有如图所示的并发关系。试用关系。试用P、V操作实现这些进程的同步。操作实现这些进程的同步。P1P3P2P6P5P4题解题解设计四个信号量分别用于进程之间的同步，设计四个信号量分别用于进程之间的同步，它们的初值它们的初值为为0。当进程。当进程P1尚未得到运行，尚未得到运行，则其他进程只能被阻塞等待。算法可描述则其他进程只能被阻塞等待。算法可描述

163、如下：如下： BEGIN Semaphore:s1,s2,s3,s4; s1:=s2:=s3:=s4:=0 COBEGINProcess P1( ) /进程P1 Begin Do all work; V(s1); /唤醒P2 V(s1); /唤醒P3 EndProcess P2( ) /进程P2 Begin p(s1); /等待P1 Do all work; V(s2); /唤醒P4 EndProcess P3( ) /进程P3 Begin p(s1); /等待P1 Do all work; V(s3); /唤醒P5 EndProcess P4( ) /进程P4 Begin p(s2); /等

164、待P2 Do all work; V(s4); /唤醒P6 EndProcess P5( ) /进程P5 Begin p(s3); /等待P3 Do all work; V(s4); /唤醒P6 EndProcess P6( ) /进程P6 Begin p(s4); p(s5); Do all work; End例题例题假设系统中有假设系统中有m个同类的互斥资源个同类的互斥资源,当当n个个进程共享这进程共享这m个互斥资源时个互斥资源时,每个进程的最每个进程的最大需求数是大需求数是w。在下列情况中，系统可能会在下列情况中，系统可能会产生死锁的是产生死锁的是: A.m=4,n=3,w=2 B.m=

165、4,n=2,w=3 C.m=5,n=2,w=3 D.m=5,n=3,w=2题解题解选项选项B，首先给首先给2个进程分别分配个进程分别分配1个资源个资源（这时系统还剩下（这时系统还剩下2个资源），接着再分别个资源），接着再分别为每个进程分配为每个进程分配1个资源（这时系统无资源）个资源（这时系统无资源），但这两个进程的资源都没有完全满足，但这两个进程的资源都没有完全满足，不能运行，即发生死锁。不能运行，即发生死锁。基础题基础题(中科院考研题中科院考研题)若有若有5台绘图仪台绘图仪,有多个进有多个进程均需要使用程均需要使用2台台,规定每个进程一次仅允规定每个进程一次仅允许申请许申请1台台,则至多允

166、许（）个进程参则至多允许（）个进程参与竞争，而不发生死锁。与竞争，而不发生死锁。 A.5 B.2 C.3 D.4基础题基础题解析：判断一个系统是否发生了死锁，方法有很解析：判断一个系统是否发生了死锁，方法有很多种，可以用资源分配图，也可以用下面的公多种，可以用资源分配图，也可以用下面的公式。式。其中，是进程最大需求量，是系统中某资源的个数，是进程个数。当进程的最大需求量不超过时，系统不会发生死锁。解析解析选选D.将将M=5,X=2代入公式代入公式,可得可得N=4例题例题某系统中有某系统中有3个并发进程个并发进程,都需要同类资源都需要同类资源4个个,试问该系统不会发生死锁的最少资源数试问该系统不会发生死锁的最少资源数是是( ) A.9 B.10 C.11 D.12解答解答因为因为:4=1+(M-1)/3所以所以:M=10作业P149 20