南邮操作系统ch_03_并发进程

《南邮操作系统ch_03_并发进程》由会员分享，可在线阅读，更多相关《南邮操作系统ch_03_并发进程（102页珍藏版）》请在金锄头文库上搜索。

1、第三章 并发进程,3.1 并发进程 3.2 临界区管理 3.3 信号量与PV操作 3.4 管程 3.5 进程通信 3.6 死锁,学习目标,并发的进程间为何要对话？(协作或竞争) 并发的进程间的对话方式(通信方式)有哪些？ 信号量(重点掌握) 共享文件 共享存储区 消息传递 并发的进程间如果沟通的不好的话会咋样？ 答：会死锁！ 掌握如何解决死锁问题,3.1 并发进程,顺序程序设计 并发进程 与时间有关的错误 进程间的交互,并发的进程(洗衣房的故事),A, B, C, D的任务是收衣服、洗衣服、干衣服和折衣服洗衣服要用 30 分钟干衣服要用 40 分钟折衣服要用 20 分钟,顺序作业,30,40,

2、20,30,40,20,30,40,20,30,40,20,6,7,8,9,10,11,12,Time,流水线作业,? D如何得知C使用完了洗衣机？! C使用完毕应该通知D！,6,7,8,9,10,11,12,Time,?,并发进程间的关系,并发进程执行时分别在各自的变量集合上操作，则称他们是独立或无关的。进程 A 进程 Bx = 1; y = 2; x = x + 1; y = y 2;并发进程执行时共享某些变量，一个进程的执行结果可能会影响其它进程的执行结果，则称他们是交互或相关的。进程 A 进程 Bx = 1; y = 2; x = y + 1; y = y * 2;,两个交互进程可能会

3、产生的问题1,Ti是订票终端，x=2代表剩余票数，为所有终端共享T1 : T2: T=x; T=x; if T=1 then if T=1 then x =T-1; x =T-1; 剩余票数最终结果不确定！可能是1，也可能是0.,两个交互进程可能会产生的问题2,/B表示申请和归还主存的容量，x表示空闲主存容量 procedure borrow (int B) if B x then 申请进程进入等待队列等主存资源 x = x - B;修改主存分配表，申请进程获得主存资源 procedure return (int B) x = x + B; 修改主存分配表 释放等主存资源的进程 可能会导致申请

4、进程永远等待！,交互的并发进程与时间有关的错误,错误的两种表现形式： 结果不惟一（飞机订票） 永远等待（内存管理）无关的并发进程不会产生此类错误，如何判断并发的进程是无关的？Bernstein条件： R(pi)=a1,a2,an，程序pi在执行期间引用的变量集 W(pi)=b1,b2,bm，程序pi在执行期间改变的变量集 若两个程序的变量集交集之和为空集： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 则并发进程的执行与时间无关。,例题 (p211),有如下四条语句：S1: a := x + y S2: b := z + 1S3: c := a b S4: w := c +

5、1于是有：S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。,进程间的交互,竞争 多个进程访问同一共享资源时发生 可能出现两个问题：死锁和饥饿 解决竞争关系的手段 : 进程的互斥 协作 多个进程为完成同一任务需要分工协作 处理协作关系的手段 : 进程的同步 互斥是一特殊的同步，即逐次使用互斥资源,3.2 临界区管理,临界区（互斥区） 临界区管理的尝试 实现临界区管理的软件方法 实现临界区管理的硬件方法,临界区(互斥区),由于相关的并发进程共享变量会引起与时间相关的错误，故引入一种机制来解决这种错误。 互斥：确保一个时刻仅有一个进程在访问共享资源。 共

6、享变量代表的资源叫“临界资源”。 在并发进程中涉及到临界资源的程序段叫“临界区”。 一个时刻仅能让一个进程进入临界区 临界区(critical section)与互斥(mutual exclusion)是同一事物的两种描述方式,使用临界区的原则,有空让进,临界区是否空？,无空等待,临界区,择一而入(互斥),让权等待,有限等待,实现互斥机制的基本手段,锁(lock)：阻止某进程做某事 在进入临界区前应该上锁 在离开临界区时要开锁 进程见到锁必须等待直到锁被打开所有的同步互斥都引入了进程的等待！使用锁是为了实现互斥，必须满足临界区的使用原则，因此对锁的使用必须谨慎。,临界区管理的尝试 ,int t

7、urn = 1 or 2; /*表示谁可以进入临界区*/,process P1 while (turn != 1);turn = 2; ,临界区;,process P2 while (turn != 2);turn = 1; ,临界区;,P1和P2必须交替执行，若时刻无P1在执行，但turn=1，则P2想进空的临界区也没有办法。此法不满足有空让进。,临界区管理的尝试 1,process P1 while (inside2); inside1 = true; inside1 = false; ,process P2 while (inside1); inside2 = true; inside2

8、 = false; ,BOOL inside1,inside2; inside1 = false; /* P1不在其临界区内 */ inside2 = false; /* P2不在其临界区内 */,临界区;,临界区;,临界区管理的尝试 2,process P1 inside1 = true; while (inside2); inside1 = false; ,process P2 inside2 = true; while (inside1); inside2 = false; ,BOOL inside1,inside2; inside1 = false; /* P1不想进其临界区 */ i

9、nside2 = false; /* P2不想进其临界区 */,临界区;,临界区;,两次尝试失败的原因,两进程总是想争先进入临界区，导致： 尝试1：先测试再上锁，两个都进去了（不满足择一而入） 尝试2：先上锁再测试，两个都进不去（不满足有空让进，有限等待） 进入临界区的两个必要步骤： 测试/等待：while(insidei) 上锁：insidei = true 如何改进？ 让双方变得更礼貌点，总是让对方先进！,临界区管理的尝试 3,insidei表示i进程想进入临界区，而不表示它已经在临界区； 加入一个令牌turn，表示该由谁进入； i若想进入临界区先提交申请，并将令牌丢给对方，让对方优先进入

10、： insidei = true ; turn = j ; 然后测试对方j是否能进入： if (turn = j) and (insidej = true),改进后的算法描述(Peterson算法),Process P1 inside1 = true;turn = 2;while (inside2 ,Process P2 inside2 = true;turn = 1;while (inside1 ,临界区;,临界区;,int turn = 1 or 2; /* 令牌归谁所有 */ BOOL inside1 = false; /* P1不想进其临界区 */ BOOL inside2 = fal

11、se; /* P2不想进其临界区 */,实现临界区管理的软件方法,Dekker算法(自学) Peterson算法 软件方法缺点： 忙式等待：空循环在浪费CPU时间片 实现复杂，需要较高的编程技巧，不同的进程实现代码要分别设计 产生问题的根本原因： 测试和上锁没有一气呵成,如果测试与上锁工作不被打断,我们将这两个工作分别封装进两个函数: BOOL Lock = FREE;LockAcquire() while (Lock = BUSY);Lock = BUSY ; LockRelease() Lock = FREE ; ,那么进程i的描述可以简化为Process Pi LockAcquire()

12、;LockRelease();,临界区;,Disable Ints;,Enable Ints;,怎么实现呢？,可能出什么问题？,原语(原子操作),原语是操作系统内核中执行时不可中断的过程，即原子操作。许多系统提供了特殊的硬件指令，指令执行过程是原子地。用硬件指令来管理临界区 测试并建立指令(TestAndSet) 对换指令(Swap) (自学),TS指令(TestAndSet),BOOL TS(BOOL s) BOOL result = s; s = false; return result; TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，s为true表示临界区空闲，可把它看成一把

13、锁。进程进入临界区前要保证TS(s)的返回值为true。,用TS指令实现临界区管理,算法描述如下：BOOL s = true; / freeLockAcquire() while ( !TS(s) ); /loop if busy LockRelease() s = true; 算法解释： 如果临界区空闲则s=true，TS返回true并将s设为false，此时临界区为设为占用状态，同时跳出while循环进入临界区。 如果临界区占用则s=false，TS返回false并且s值不变，所以此时循环将继续。 存在忙式等待！,临界区;,复习：临界区,为了解决并发进程共享变量时可能引起的错误，引入互斥的

14、概念： 互斥：确保一个时刻仅有一个进程在访问共享资源。 共享变量代表的资源叫“临界资源”。 在并发进程中涉及到临界资源的程序段叫“临界区”。 临界区的使用原则 有空让进 择一而入 无空等待 有限等待 让权等待,复习：用软件方法实现锁,锁(lock)是互斥机制的实现手段！ 使用过程： 测试成功并上锁(若测试失败则等待) 进入临界区 开锁 两次用软件方法尝试失败的原因 测试和上锁没有一气呵成，导致两进程交替执行 Peterson和Dekker算法解决了这一问题，但设计的过于复杂,复习：用硬件指令实现锁,硬件指令大都是原子操作，其执行过程不会被打断，可以使用开/关中断来达到这一目的。,BOOL TS

15、(BOOL s) /s表示临界区是否空闲 BOOL result = s; s = false; /上锁 return result; /返回测试结果 ,使用TS指令实现的锁算法： BOOL s = true; /free LockAcquire() while ( !TS(s) ); LockRelease() s = true; ,忙式等待 进程在等待进入临界区时仍占有CPU执行一个空循环，浪费了CPU时间片。 浪费的时间和临界区长度有关 解决方法？,让忙等的进程睡觉去,为了克服忙等，可以让进程阻塞自己。阻塞操作将一个进程插入一个等待队列，同时调度程序可以调度另一个进程运行。 算法描述如下：,LockAcquire() if ( !TS(s) ) sleep(); ,LockRelease() if (有等待进程) wakeup();/释放一个到就绪队列 else s = true; ,这个算法完美了？ 还记得“永远等待”吗？,临 界 区 代 码,BOOL guard = true; int lock = FREE;LockAcquire() / 短暂的忙等while ( !TS(guard) );if (lock = BUSY) sleep() ,