进程同步与进程通信

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

1、进程同步与进程通信进程的并发性n每一个进程具有顺序性，但是在多道程序设计系 统中，多个进程要竞争，轮流占用处理器。n有两个进程A和B，它们各自顺序执行时的操作序 列如下：q进程A ： a1，a2，a3，amq进程B ： b1，b2，b3，bmn在多道程序设计系统中，处理器可能执行的操作 序列qa1， b1 ，a2， b2 ，a3， b3 qa1， a2， b1 ，a3 ，b2 ，b3 进程的并发性n在一个进程的工作没有完成之前，另一个进程 就可以开始工作，这些进程就称为可同时执行 的。或者称它们具有并发性，并且把可同时执 行的进程称为并发进程。进程的并发性n如果一个进程的执行不影响另一个进程的

2、执行结 果，也不依赖一个进程的进展情况，即它们是各 自独立的，则称这些进程相互之间是无关的。n如果一个进程的执行要依赖其他进程的进展状况 ，或者可能会影响其他进程的执行结果，则说这 些进程是有交互的。并发进程之间的关系n进程互斥多个进程不能同时使用同一个资源，某个进程使用该资源时，其他进程必须等待。n进程同步多个进程的调用存在时序关系，某些进程的执行必须先于另一些进程。n进程通信多个进程之间传递消息。与时间有关的错误n对于有交互的并发进程来说，并发会破坏“封 闭性”和“可再现性”例1：航班售票系统process Pi (i=1,2,)beginRi:=Ak;if Ri=1 thenbeginR

3、i:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ak代表某天某次航班的 剩余票数；Pi代表售票处理进程；Ri是每个售票进程的私 有变量；各个售票处进程的工作 如右边代码所示：process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri = 5假设某时刻Ak为5，A、B两个人

4、同时在2号3号窗口买票process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri = 5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;p

5、rocess P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri = 5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri = 5假设某时刻Ak

6、为5，A、B两个人同时在2号3号窗口买票process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri = 4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已

7、售完“ end;process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ak = 4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ri =

8、 4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;Ak = 4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票process P3beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;e

9、lse 输出”票已售完“ end;process P2beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;else 输出”票已售完“ end;假设某时刻Ak为1，两个窗口同时卖票，可能出现什么情况？例2R1 count; R1+; count = R1; R2 = count; R2+; count = R2;(1) 假设count的初值为5，先运行P1再运行P2的结果是？ (2) 如果P1和P2并发执行，可能会出现什么运行结果？P1P2与时间有关的错误n由于进程交替修改了共享变量造成结果可能不 正确。n有交互的并发进程执行时出现与

10、时间有关的错 误，其根本原因是对共享资源（变量）的使用 不受限，为了使并发进程能正确地执行，必须 对共享变量的使用加以限制。临界资源和临界区n一次仅允许一个进程访问的资源称为临界资源。n并发进程中访问临界资源的那段代码称为临界区 。n涉及相同共享变量的临界区称为相关临界区。临界资源和临界区R1 count; R1+; count = R1; R2 = count; R2+; count = R2;P1P2临界资源 count临界区临界资源和临界区process Pi(i=1,2)beginRi:=Ak;if Ri=1 thenbeginRi:= Ri -1;Ak = Ri输出一张票；end;e

11、lse 输出”票已售完“ end;如果能保证一个进程在临界 区执行时，不让另一个进程 进入相关的临界区执行，即 各进程对共享变量的访问是 互斥的，就不会造成与时间 有关的错误。临界资源临界区临界区进入准则(1)空闲让进：当无进程在临界区时，若有 进程要进入，则允许一个进程进入临界区(2)忙则等待：当有进程在临界区执行时，其 他试图进入临界区的进程必须等待(3)让权等待：当进程不能进入临界区时，应 立即释放处理机，以免其它进程“忙等”(4)有限等待：保证进程在有效的时间内进入 临界区，避免“死等”信号量机制（Semaphores）n1965年，荷兰的 E.W.Dijkstra (狄克斯特拉) 提

12、出了信号量同步机制。n用于进程同步n广泛应用于存在临界资源和临界区控制的场合信号量的定义信号量是一个数据结构，其定义如下：struct semaphoreint value;struct PCB * queue;/等待队列信号量semaphore包括一个整型值和一 个等待队列。信号量只能通过P原语和V原 语访问。PV操作n对信号量的操作只能由P、V操作来进行，即：信号量数值的改变只能由P、V操作完成nPV操作由P操作和V操作组成，也称P操作原语和V 操作原语。P操作原语void P (semaphore s)s.value = s.value 1;if (s.value =1) Ri = Ri

13、 -1;Ak = Ri输出一张票； else 输出”票已售完“ V(S); (1) P1执行P(S), S= 0 (2) P2执行P(S), S = -1, P2阻塞 (3) P3执行P(S), S = -2, P3阻塞 (4) P4执行P(S), S = -3, P4阻塞 (5) P1执行代码，AK = 2,输出一张票 (6) P1执行V(S)，S = -2,唤醒一个等待S 的进程(P2/P3/P4其中一个)(7) 假设P3被唤醒，P2，P4仍然阻塞 (8) P3执行代码，AK = 1,输出一张票 (9) P3执行V(S)，S = -1,唤醒一个等待S 的进程(P2/P4其中一个)(10)假

14、设P2被唤醒，P4仍然阻塞 (11)P2执行代码，AK = 0,输出一张票 (12)P2执行V(S)，S = 0,唤醒一个等待S 的进程，P4(13)P4执行代码，进入else,输出票已售完 (14)P4执行V(S)，S = 1例4Semaphore S = 1; Pi:P(S);临界区Ci（访问共享资源的代码）V(S);假设有n个进程P1，P2，P3Pn共享某一资源,任意时刻只允许一 个进程访问该资源，它们各自的临界区分别为C1，C2Cn。例5n有4个并发执行的进程A，B，C，D,它们在执 行时都要读共享文件F。限定：不允许进程A 和进程B同时读文件F，不允许进程C和进程D 同时读文件F。写

15、出用PV操作管理时四个进程 的程序。semaphore S1 = 1；/用于AB互斥 semaphore S2 = 1；/用于CD互斥 A：P(S1);read file F;V(S1);B: P(S1);read file F;V(S1);D: P(S2);read file F;V(S2);C: P(S2); read file F;V(S2);例6某系统允许最多10个进程同时读文件F，当同时 读文件F的进程不满10个时，欲读该文件的其他 进程可立即读，当已有10个进程在读文件F时其 他欲读文件F的进程必须等待，直至有进程读完 后退出方可去读, 写出进程并发执行时的程序。Semaphore S = 10; Readeri : P(S);read file F;V(s);例7n设有一个售票大厅，可容纳200人购票。如果 厅内不足200人，则允许进入，超过则在厅外 等候；售票员某时只能给一个购票者