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

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

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

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

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

5、况可能发生的情况 进程进程P1需要向缓冲区存储数据，并知道需要向缓冲区存储数据，并知道In指针当前指向指针当前指向7号空闲缓冲单元。若这时进号空闲缓冲单元。若这时进程程P1的时间片用完，被中断，调度程序调的时间片用完，被中断，调度程序调度进程度进程P2执行。执行。P2正好也需要向缓冲区存放数据，首先获正好也需要向缓冲区存放数据，首先获取取In指针位置，同样也是指针位置，同样也是7，于是，于是，P2将数将数据送入据送入7号单元，并将号单元，并将In指针移动一格，指指针移动一格，指向向8号单元，然后继续执行其他操作。号单元，然后继续执行其他操作。可能发生的情况可能发生的情况 当进程当进程P1再次被

6、调度执行时，将从上次的再次被调度执行时，将从上次的断点继续执行，即将数据送入断点继续执行，即将数据送入7号单元（覆号单元（覆盖进程盖进程P2的数据），并移动的数据），并移动In指针指向指针指向8号号单元，然后继续执行其他操作。单元，然后继续执行其他操作。进程进程P3不会发现上述错误，继续从缓冲区不会发现上述错误，继续从缓冲区取数据，进行打印，显然，进程取数据，进行打印，显然，进程P2的相应的相应计算结果不会被打印输出。计算结果不会被打印输出。分析分析 该例中，由于进程该例中，由于进程P1和和P2共享缓冲区和位共享缓冲区和位置指针，而未对这种共享进行有效控制，置指针，而未对这种共享进行有效控制，

7、导致打印数据的丢失。导致打印数据的丢失。如果控制进程如果控制进程P1、P2互斥地访问缓冲区和互斥地访问缓冲区和修改位置指针，将避免这种因为并发执行修改位置指针，将避免这种因为并发执行而导致的程序执行结果的不确定性。而导致的程序执行结果的不确定性。并发控制并发控制竞争资源竞争资源 当并发进程竞争使用同一资源时，它们之间就会当并发进程竞争使用同一资源时，它们之间就会发生冲突。发生冲突。如果操作系统将资源分配给其中的某一个进程使如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。用时，由操作系统分配给

8、它。如果竞争某资源的进程太多，这些进程还必须等如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等。待在一个队列中，如就绪队列，阻塞队列等。一种极端的情况是，被阻塞进程永久得不到申请一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁。的资源，而死锁。并发控制并发控制竞争资源竞争资源 进程竞争资源首先必须解决进程竞争资源首先必须解决“互斥互斥”问题，问题，某些资源必须互斥使用，如打印机、共享某些资源必须互斥使用，如打印机、共享变量、表格、文件等。变量、表格、文件等。这类资源又称为临界资源，访问临界资源这类资源又称为临界资源，访问临界资源的那段代码称为临界区。的那

9、段代码称为临界区。任何时刻，只允许一个进程进入临界区，任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。以此实现进程对临界资源的互斥访问。进程互斥进入临界区阻塞队列进程进入区临界区退出区唤醒互斥使用临界资源互斥使用临界资源 当进程需要使用临界资源时，通过获得临界区的当进程需要使用临界资源时，通过获得临界区的使用权实现的。使用权实现的。首先，在首先，在“进入区进入区”判断是否可以进入临界区，判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区，后来的进程通过止其它后来的进程进入临界区，后来的进程

10、通过查看临界区使用标志，知道自己不能进入临界区，查看临界区使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。就进入阻塞队列，将自己阻塞。当临界区内的进程使用完毕，退出临界区时，即当临界区内的进程使用完毕，退出临界区时，即在在“退出区退出区”修改临界区使用标志，并负责唤醒修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。阻塞队列中的一个进程，让其进入临界区。互斥使用临界资源互斥使用临界资源 由于同一个临界资源在多个共享它的进程由于同一个临界资源在多个共享它的进程中将对应多个临界区，那么怎样才能保证中将对应多个临界区，那么怎样才能保证诸进程间互斥地执行临界区呢？诸进程

11、间互斥地执行临界区呢？这就必须保证这就必须保证“临界区使用标志临界区使用标志”是可被是可被系统中所有进程共享的全局变量，而且诸系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。进程对该标志的修改操作必须互斥进行。临界区使用原则（也称互斥条件）临界区使用原则（也称互斥条件）每次只允许一个进程处于临界区（每次只允许一个进程处于临界区（忙则等待忙则等待）；）；进程只能在临界区内逗留有限时间，不得使其它进程只能在临界区内逗留有限时间，不得使其它进程在临界外无限期等待（进程在临界外无限期等待（有限等待有限等待）；）；如果临界区空闲，则只要有进程申请就立即让其如果临界区空闲，则只要有

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

13、P2双方都占用对方申请的资源双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是而阻塞，谁也不让步地永久等待，这就是死锁。死锁。进程因竞争资源而死锁竞争资源竞争资源饥饿饥饿 假设有假设有3个进程个进程P1、P2、P3，每个进程都需要周，每个进程都需要周期性的使用资源期性的使用资源R。如果当前如果当前P1正在使用临界资源正在使用临界资源R，P2和和P3因为等因为等待待R而阻塞。而阻塞。当当P1退出临界区时，退出临界区时，P2立即进入临界区执行，若立即进入临界区执行，若P2还未退出临界区时，还未退出临界区时，P1又申请使用临界资源又申请使用临界资源R。假设假设P2退出临界区后，系统将退出临

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

15、完整性。保证数据的完整性。共享协作同样涉及到互斥、死锁和饥饿问共享协作同样涉及到互斥、死锁和饥饿问题，但更强调对数据的写操作必须互斥地题，但更强调对数据的写操作必须互斥地进行。进行。必须保证数据一致性。必须保证数据一致性。前面列举了银行联网储蓄的例子，除了必须保前面列举了银行联网储蓄的例子，除了必须保证储户余额的正确性以外，还必须使银行储蓄证储户余额的正确性以外，还必须使银行储蓄总余额、当日发生额、流水账等数据得到一致总余额、当日发生额、流水账等数据得到一致的修改。的修改。一般通过事务处理来保证数据的一致性，可以一般通过事务处理来保证数据的一致性，可以将对储户余额、储蓄总余额、当日发生额、流将

16、对储户余额、储蓄总余额、当日发生额、流水账等数据的修改放到一个临界区中，进入临水账等数据的修改放到一个临界区中，进入临界区的进程必须一次性完成对这一系列数据的界区的进程必须一次性完成对这一系列数据的修改操作。修改操作。只有该进程退出临界区以后，才允许别的进程只有该进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致进入临界区进行数据修改，以保证数据的一致性。性。并发控制并发控制通信协作通信协作 当进程进行通信合作时，各个进程之间需当进程进行通信合作时，各个进程之间需要建立连接，进程通信需要同步和协调，要建立连接，进程通信需要同步和协调，进程通信的方式很多，包括消息传递、管

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

18、进行通信，而P3一直阻塞等待一直阻塞等待P1，这样，这样P3被长时间饥饿。被长时间饥饿。互斥与同步的解决策略互斥与同步的解决策略 软件方法软件方法 硬件方法硬件方法 信号量方法信号量方法 管程方法管程方法 消息传递方法消息传递方法软件方法软件方法 软件方法是指由进程自己，通过执行相应软件方法是指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互的程序指令，实现与别的进程的同步与互斥，无须专门的程序设计语言或操作系统斥，无须专门的程序设计语言或操作系统的支持。的支持。实践证明，该方法很难正确控制进程间的实践证明，该方法很难正确控制进程间的同步与互斥，而且可能会大大地增加系统同步与互斥，

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

20、系统，或专门的程序设计语言提供的特别支持，包括信号程序设计语言提供的特别支持，包括信号量方法、管程方法和消息传递方法。量方法、管程方法和消息传递方法。其中，信号量方法已经成为控制进程同步其中，信号量方法已经成为控制进程同步与互斥的通用方法。与互斥的通用方法。互斥与同步解决方法之一互斥与同步解决方法之一软件方法软件方法 软件解决方法有很多种，比较有代表性的软件解决方法有很多种，比较有代表性的软件方法有荷兰数学家软件方法有荷兰数学家Dekker提出的提出的Dekker算法和科学家算法和科学家G.L.Peterson提出提出的的Perterson算法。算法。为了说明设计并发程序时可能出现的典型为了说

21、明设计并发程序时可能出现的典型错误，下面以错误，下面以Dekker算法为例，分析如何算法为例，分析如何设计并改进一个互斥算法的过程。设计并改进一个互斥算法的过程。互斥与同步解决方法之一：软件方互斥与同步解决方法之一：软件方法法初步设想初步设想 为了控制两个进程互斥进入临界区，可以为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区。让两个进程轮流进入临界区。当一个进程正在临界区执行时，另一个进当一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。程就不能进入临界区，而在临界区外等待。Var turn:0.1;/*共享的全局变量共享的全局变量*/P0 P1 While

22、 turn 0 donothing;while turn 1 do nothing;Turn:=1;turn:=0;互斥算法：初步设想分析：初步设想分析：初步设想 保证了互斥保证了互斥 问题问题1：“忙等忙等”现象现象 问题问题2：进程严格交替进入临界区。如果进：进程严格交替进入临界区。如果进程需要多次使用临界区，那么，使用临界程需要多次使用临界区，那么，使用临界区频率低的进程严重制约着使用临界区频区频率低的进程严重制约着使用临界区频率高的进程的执行进度。率高的进程的执行进度。分析：初步设想分析：初步设想 例如，例如，P0需要每需要每10分钟使用一次临界区，分钟使用一次临界区，P1需要每需要每

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

24、进入临界区，但很快又需要进入临界区，但是是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:=true;Flag0:=false;flag1:=false;互斥算法：第一次改进问题：问题：假若

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

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

29、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:=true;End;Flag0:=false;P1 Flag1:=true;While flag0 doBegin fl

31、ag1:=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;/*共享的全局变量，表示临界区状态共享的全局变量，表示临界区状态*/Turn:0.1;/*共享的全局变量，表示进入临界区的顺序共享的全局变量，表示进入临界区的顺序*/Procedur

33、e 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;parendendbegin /*主程序主程序*/flag0:=false;flag1:=false;turn:=1;parbegin P0;P1;parendendVa

34、r 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 do nothing;flag0:=true;end;Turn:=1;flag0:=false;foreverEnd;Procedure P1;Begin Repeat

35、 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 then begin flag0:=false;while turn=1 do nothing;flag0:=true;end;Turn:=1;flag0:=false;foreverEnd

36、;互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法 采用软件方法实现进程互斥使用临界资源是很困难的，它们通常实现两个进程互斥，很难控制多个进程互斥。算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。软件方法始终不能解决“忙等”现象，降低系统效率。硬件方法包括屏蔽中断和专用机器指令。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-屏蔽中断屏蔽中断 由于进程切换需要依赖中断来实现，如果屏蔽中由于进程切换需要依赖中断来实现，如果屏蔽中断，则不会出现进程切换。断，则不会出现进程切换。因此，为了实现对临界资源的互斥使用，可以在因此，为了实现对临界资源的互斥使

37、用，可以在进程进入临界区之前，屏蔽中断，当进程退出临进程进入临界区之前，屏蔽中断，当进程退出临界区时，打开系统中断。界区时，打开系统中断。中断被屏蔽以后，系统时钟中断也被屏蔽，处理中断被屏蔽以后，系统时钟中断也被屏蔽，处理机将不会被切换到其他进程。机将不会被切换到其他进程。于是，一旦屏蔽中断，进程就可以检查和修改共于是，一旦屏蔽中断，进程就可以检查和修改共享内存区中的数据，而不必担心其他进程介入。享内存区中的数据，而不必担心其他进程介入。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-屏蔽中断屏蔽中断Repeat ;Forever.互斥与同步解决方法之二：硬件方互斥与同步解决

38、方法之二：硬件方法法-屏蔽中断屏蔽中断 这种方法的约束条件太强，付出的代价太大。这种方法的约束条件太强，付出的代价太大。因为中断被屏蔽以后，系统将无法响应任何外部因为中断被屏蔽以后，系统将无法响应任何外部请求，也不会响应当前执行进程的任何异常及系请求，也不会响应当前执行进程的任何异常及系统故障，严重地降低了处理机性能。统故障，严重地降低了处理机性能。这种方法仅对单处理机系统有效，如果系统有两这种方法仅对单处理机系统有效，如果系统有两个或多个共享内存的处理机，屏蔽中断仅仅对执个或多个共享内存的处理机，屏蔽中断仅仅对执行本指令的处理机有效，其它处理机仍将能继续行本指令的处理机有效，其它处理机仍将能

39、继续运行，并可以访问共享内存空间。运行，并可以访问共享内存空间。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-专用机器指令专用机器指令 利用一些专用机器指令也能实现互斥，机利用一些专用机器指令也能实现互斥，机器指令在一个指令周期内执行，不会受到器指令在一个指令周期内执行，不会受到其它指令的干扰，也不会被中断。其它指令的干扰，也不会被中断。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-testset指令指令function testset(var i:integer):boolean;begin if i=0 then begin i:=1;testset

40、:=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 P(1);P(2);P(n)parendend.互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-exchange指令指令procedure exchange(var r:register;var

41、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(key,bolt)until key=0;exchange(key,bolt);foreverend;begin/*主程序主程序*/bolt:=0;parbegin P(1);P(2);P(n);parendEnd.互斥与同步解决

42、方法之二：硬件方互斥与同步解决方法之二：硬件方法法-机器指令的优点机器指令的优点 非常简单，易于证明；同时适合于单处理机系统和共享内存的多处理机系统中多个进程的互斥;可以分别为临界区设置属于它自己的变量，以实现对多个临界区的互斥访问。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-机器指令的缺点机器指令的缺点“忙等忙等”现象仍然存在。现象仍然存在。进程都需要循环检进程都需要循环检测，等待时机进入临界区。但是，由于采测，等待时机进入临界区。但是，由于采用了机器指令，这种用了机器指令，这种“忙等忙等”消耗的机器消耗的机器时间比软件方法小，属于时间比软件方法小，属于“可接受的忙可接

43、受的忙等等”。可能出现饥饿现象。可能出现饥饿现象。当临界区空闲时，执当临界区空闲时，执行循环检测的若干等待进程能进入临界区行循环检测的若干等待进程能进入临界区的机率是相等的，有的进程可能的机率是相等的，有的进程可能“运气运气”非常不好，很难有机会进入临界区，而饥非常不好，很难有机会进入临界区，而饥饿。饿。互斥与同步解决方法之二：硬件方互斥与同步解决方法之二：硬件方法法-机器指令的缺点机器指令的缺点 还可能导致死锁。还可能导致死锁。例如：进程例如：进程P1的优先级低于的优先级低于P2的优先级，若的优先级，若P1通过执行专用的机器指令，进入临界区，且在临通过执行专用的机器指令，进入临界区，且在临界

44、区内被中断，界区内被中断，P2被调度执行。若被调度执行。若P2也需要进入也需要进入该临界区，由于临界区被该临界区，由于临界区被P1占用，占用，P2“忙等忙等”。由于由于P1的优先级低于的优先级低于P2，调度程序不可能强行剥，调度程序不可能强行剥夺夺P2的执行而调度的执行而调度P1。这样，。这样，P1将一直占用临将一直占用临界区被中断，界区被中断，P2一直一直“忙等忙等”，如果没有外力的，如果没有外力的作用，这种作用，这种“僵持僵持”状态将一直保持下去，即系状态将一直保持下去，即系统出现死锁。统出现死锁。信号量信号量(semaphore)方法方法 软件方法和硬件方法都存在软件方法和硬件方法都存在

45、“忙等忙等”问题，问题，浪费了处理机时间。浪费了处理机时间。信号量方法能实现进程互斥与同步，而不信号量方法能实现进程互斥与同步，而不必必“忙等忙等”。实例实例 交通信号灯：红灯停，绿灯行。交通信号灯：红灯停，绿灯行。信号量实现互斥的基本原理信号量实现互斥的基本原理 两个或多个进程可以通过传递信号进行合两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以行（阻塞等待），直到它收到一个可以“向前推进向前推进”的信号（被唤醒）。的信号（被唤醒）。相应地，将实现信号灯作用的变量称为信相应地，将实现信号灯作用的变量

46、称为信号量，常定义为记录型变量号量，常定义为记录型变量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

47、0 then begin 进程阻塞；进程阻塞；进程进入进程进入s.queue队列；队列；End;Signal(s)s.count:=s.count+1;if s.count=0 Thenbegin 唤醒队首进程；唤醒队首进程；将进程从将进程从s.queue阻塞队列中移出；阻塞队列中移出；End;Wait、singal的应用的应用 进程进入临界区之前，首先执行进程进入临界区之前，首先执行wait(s)原语，若原语，若s.count0,则进程调用阻塞原语，将自己阻塞，则进程调用阻塞原语，将自己阻塞，并插入到并插入到s.queue队列排列。队列排列。注意，阻塞进程不会占用处理机时间，不是注意，阻塞进

48、程不会占用处理机时间，不是“忙忙等等”，直到某个从临界区退出的进程执行，直到某个从临界区退出的进程执行signal(s)原语，唤醒它。原语，唤醒它。一旦其它某个进程执行一旦其它某个进程执行了了sigal(s)原语中的原语中的s.count+1操作后，发现操作后，发现s.count=0，即阻塞队，即阻塞队列中还有被阻塞进程，则调用唤醒原语，把列中还有被阻塞进程，则调用唤醒原语，把s.queue中第一个进程修改为就绪状态，送就绪中第一个进程修改为就绪状态，送就绪队列，准备执行临界区代码。队列，准备执行临界区代码。program mutualexclusion;const n=;/*进程进程数数*/

49、*定义信号量定义信号量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。资源信号量用于申请或归还资源，可以初始化为大于

50、资源信号量用于申请或归还资源，可以初始化为大于1的的正整数，表示系统中某类资源的可用个数。正整数，表示系统中某类资源的可用个数。Wait操作用于申请资源（或使用权），进程执行操作用于申请资源（或使用权），进程执行wait原语原语时，可能会阻塞自己；时，可能会阻塞自己；Signal操作用于释放资源（或归还资源使用权），进程执操作用于释放资源（或归还资源使用权），进程执行行signal原语时，有责任唤醒一个阻塞进程。原语时，有责任唤醒一个阻塞进程。信号量的物理意义信号量的物理意义 s.count=0表示还可执行表示还可执行wait(s)而不会阻塞的而不会阻塞的进程数（可用资源数），每执行一次进程数