《第4章 进程同步与通信 (2)讲义教材》由会员分享，可在线阅读，更多相关《第4章 进程同步与通信 (2)讲义教材（241页珍藏版）》请在金锄头文库上搜索。
1、进程的同步与互斥,？,采用多道程序设计技术的操作系统，允许多个进程同时驻留内存并发执行。 ？如何协调多个进程对系统资源，如内存空间、外部设备等的竞争和共享？ ？如何解决多个进程因为竞争资源而出现执行结果异常，甚至导致系统不稳定、失败等问题。 ？例如，多个进程同时申请文件打印，如何有效分配打印机？,例,银行的联网储蓄业务允许储户同时用储蓄卡和存折对同一帐户进行存取款操作，如果某储户同时（在ATM机和营业柜台）办理两笔存款业务（假设分别为1000和2000元） 从系统的角度看，有两个进程将同时对储户余额等数据进行修改。如果两个进程同时读出原余额（假设为5000元），两个进程分别将最新余额修改为60
2、00(5000+1000)和7000(5000+2000).,例,假设系统中有3个进程P1、P2、P3，其中P1和P2是计算进程，P3是打印进程，每当P1或P2计算出一个结果以后，将计算结果送到缓存区中，以便P3进程从中取出数据打印。 假设缓冲区被划分为0、1、2n-1共n个单元。 有两个指针：In指针用于计算进程存放数据，指向缓冲区中下一个空闲的单元，Out指针用于打印进程取数据，指向缓冲区中下一个将取走数据的单元。,例,假设某时刻，0到3号单元空闲，4到6号单元被占用，这时候P1、P2进程都准备将数据送入缓冲区。如下,多个进程同时访问共享区,可能发生的情况,进程P1需要向缓冲区存储数据，并
3、知道In指针当前指向7号空闲缓冲单元。若这时进程P1的时间片用完，被中断，调度程序调度进程P2执行。 P2正好也需要向缓冲区存放数据，首先获取In指针位置，同样也是7，于是，P2将数据送入7号单元，并将In指针移动一格，指向8号单元，然后继续执行其他操作。,可能发生的情况,当进程P1再次被调度执行时，将从上次的断点继续执行，即将数据送入7号单元（覆盖进程P2的数据），并移动In指针指向8号单元，然后继续执行其他操作。 进程P3不会发现上述错误，继续从缓冲区取数据，进行打印，显然，进程P2的相应计算结果不会被打印输出。,分析,该例中，由于进程P1和P2共享缓冲区和位置指针，而未对这种共享进行有效
4、控制，导致打印数据的丢失。 如果控制进程P1、P2互斥地访问缓冲区和修改位置指针，将避免这种因为并发执行而导致的程序执行结果的不确定性。,并发控制竞争资源,当并发进程竞争使用同一资源时，它们之间就会发生冲突。 如果操作系统将资源分配给其中的某一个进程使用，另一个进程就必须等待，直到申请的资源可用时，由操作系统分配给它。 如果竞争某资源的进程太多，这些进程还必须等待在一个队列中，如就绪队列，阻塞队列等。 一种极端的情况是，被阻塞进程永久得不到申请的资源，而死锁。,并发控制竞争资源,进程竞争资源首先必须解决“互斥”问题，某些资源必须互斥使用，如打印机、共享变量、表格、文件等。 这类资源又称为临界资
5、源，访问临界资源的那段代码称为临界区。 任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。,进程互斥进入临界区,互斥使用临界资源,当进程需要使用临界资源时，通过获得临界区的使用权实现的。 首先，在“进入区”判断是否可以进入临界区，如果可以进入，则必须设置临界区使用标志，阻止其它后来的进程进入临界区，后来的进程通过查看临界区使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。 当临界区内的进程使用完毕，退出临界区时，即在“退出区”修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。,互斥使用临界资源,由于同一个临界资源在多个共享它的进程中将对应多个临
6、界区，那么怎样才能保证诸进程间互斥地执行临界区呢？ 这就必须保证“临界区使用标志”是可被系统中所有进程共享的全局变量，而且诸进程对该标志的修改操作必须互斥进行。,临界区使用原则（也称互斥条件）,每次只允许一个进程处于临界区（忙则等待）； 进程只能在临界区内逗留有限时间，不得使其它进程在临界外无限期等待（有限等待）； 如果临界区空闲，则只要有进程申请就立即让其进入（空闲让进）； 进入临界区的进程，不能在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区（让权等待） 不能限制进程的执行进度及处理机的数量。,竞争资源可能引起死锁,例如：两个进程P1、P2，竞争资源R1、R2. 假设，现在P1已
7、经占用了R1，且P2占用了R2，如果此时P1申请R2，且P2申请R1。会怎么样？ 结果是P1、P2双方都占用对方申请的资源而阻塞，谁也不让步地永久等待，这就是死锁。,进程因竞争资源而死锁,竞争资源饥饿,假设有3个进程P1、P2、P3，每个进程都需要周期性的使用资源R。 如果当前P1正在使用临界资源R，P2和P3因为等待R而阻塞。 当P1退出临界区时，P2立即进入临界区执行，若P2还未退出临界区时，P1又申请使用临界资源R。 假设P2退出临界区后，系统将R分给了P1，然后，当R空闲时，又将其分给P2，如此反复。,竞争资源饥饿,使P1、P2都能正常执行，而P3被长时间饥饿。 这种情况不是死锁，但是
8、对P3不公平，也是系统应该避免的。,并发控制共同协作,多个进程常常需要共同修改某些共享变量、表格、文件数据库等，协作完成一些功能。 必须确保它们对共享变量的修改是正确的，保证数据的完整性。 共享协作同样涉及到互斥、死锁和饥饿问题，但更强调对数据的写操作必须互斥地进行。,必须保证数据一致性。 前面列举了银行联网储蓄的例子，除了必须保证储户余额的正确性以外，还必须使银行储蓄总余额、当日发生额、流水账等数据得到一致的修改。 一般通过事务处理来保证数据的一致性，可以将对储户余额、储蓄总余额、当日发生额、流水账等数据的修改放到一个临界区中，进入临界区的进程必须一次性完成对这一系列数据的修改操作。 只有该
9、进程退出临界区以后，才允许别的进程进入临界区进行数据修改，以保证数据的一致性。,并发控制通信协作,当进程进行通信合作时，各个进程之间需要建立连接，进程通信需要同步和协调，进程通信的方式很多，包括消息传递、管道、共享存储区等。 通过消息传递实现进程通信时，由于没有共享资源，故无须互斥，但仍可能出现死锁和饥饿。,并发控制通信协作,例如，两个进程相互等待对方发来的数据而永久阻塞，即死锁。 又如，3个进程P1、P2、P3，其中P1不断尝试与P2或P3通信，P2和P3又不断尝试与P1通信，如果P1与P2总能成功建立连接进行通信，而P3一直阻塞等待P1，这样P3被长时间饥饿。,互斥与同步的解决策略,软件方
10、法 硬件方法 信号量方法 管程方法 消息传递方法,软件方法,软件方法是指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互斥，无须专门的程序设计语言或操作系统的支持。 实践证明，该方法很难正确控制进程间的同步与互斥，而且可能会大大地增加系统的额外开销。,硬件方法,为了解决软件方法存在的不足，有人提出了硬件解决方法，通过屏蔽中断或采用专门的机器指令控制同步与互斥。 与软件解决方法比较，这种方法减少了系统额外开销，但由于需要太强的硬件约束条件，以及可能导致进程饥饿与死锁现象，一直没有成为通用的解决方法。,另一类解决方法是由操作系统，或专门的程序设计语言提供的特别支持，包括信号量方法、管程
11、方法和消息传递方法。 其中，信号量方法已经成为控制进程同步与互斥的通用方法。,互斥与同步解决方法之一软件方法,软件解决方法有很多种，比较有代表性的软件方法有荷兰数学家Dekker提出的Dekker算法和科学家G.L.Peterson提出的Perterson算法。 为了说明设计并发程序时可能出现的典型错误，下面以Dekker算法为例，分析如何设计并改进一个互斥算法的过程。,互斥与同步解决方法之一：软件方法初步设想,为了控制两个进程互斥进入临界区，可以让两个进程轮流进入临界区。 当一个进程正在临界区执行时，另一个进程就不能进入临界区，而在临界区外等待。,Var turn:0.1;/*共享的全局变量
12、*/ P0 P1 While turn 0 donothing; while turn 1 do nothing ; Turn:=1; turn:=0; ,互斥算法：初步设想,分析：初步设想,保证了互斥 问题1：“忙等”现象 问题2：进程严格交替进入临界区。如果进程需要多次使用临界区，那么，使用临界区频率低的进程严重制约着使用临界区频率高的进程的执行进度。,分析：初步设想,例如， P0需要每10分钟使用一次临界区，P1需要每1分钟使用一次临界区。 假设turn的初值为0，进程P0正好先请求进入临界区，并成功进入临界区执行，这时，如果P1申请进入临界区，循环检测turn=0，不可以进入，只能“空
13、”循环，等待。 当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 nothing; Flag0:=true; flag1:=true ;
15、Flag0:=false; flag1:=false; ,互斥算法：第一次改进,问题：假若你是软件测试人员，请问第一次改进有没有问题？,分析：第一次改进,如果进程在临界区外失败，其他进程不会阻塞。 问题1：“忙等” 问题2：若进程在临界区内失败且相应的Flag为true，则其他进程永久阻塞。 问题3：不能保证进程互斥进入临界区。,互斥与同步解决方法之一：软件方法第二次改进,互斥算法的第一次改进不能实现“互斥”。 因为，进程首先检测到临界区状态，若“被占用”则“忙等”，否则就直接进入临界区。从而，可能出现同时进入临界区的现象。 能否让进程预先表明“希望进入临界区的态度”，然后，再检测临界区状态。,Var flag:array0.1of boolean:false;/*共享的全局变量*/ P0 P1 Flag0:=true; flag1:=true While flag1 do nothing; while flag0 do nothing ; Flag0:=false; flag1:=false; ,互斥算法：第二次改进,分析：第二次改进,假设P0需要进入临界区，首先执行flag0:=true，再执行while flag1,若P1正在占用临界区，则P0忙等；否则
