《多进程编程教程》PPT课件.ppt

第5章 进程同步与互斥 u并发（concurrency）是多道程序技术、多处理技 术、分布式处理技术的基础，也是OS设计的重点 u资源的共享和争用 u多个进程活动的同步 u分配给进程的处理器时间等。 5.1 并发的原理 单处理器，多 道程序：交错 多处理器，多道程序：交错和重叠 5.1 5.1 并发的原理并发的原理示例示例 共享变量的修改冲突共享变量的修改冲突 例1：一飞机订票系统，两个终端 ，运行T1、T2进程 T1 : T2: . . Read(x); Read(x); if x=1 then if x=1 then x:=x-1; x:=x-1; write(x); write(x); . . 设x的当前值为：100 1. 若执行顺序为： 先T1; 后T2; 则结果：x = 98 2. 若执行顺序为： T1: Read(x); T2: Read(x); T1: if x=1 then x:=x-1; T2: if x=1 then x:=x-1; T1: write(x); T2: write(x); 则结果 x = 99 分析：产生错误的原因是不加控制地访问共享变量x Cobegin get; copy; put; Coend getcopyput fstg 复制一个记录 5.1 5.1 并发的原理并发的原理 示例示例 与进程的执行顺序有关的错误与进程的执行顺序有关的错误 源记录目标记录 cmpm c1 g2 p1 c2 g3 p2 g1 并发环境下进程间的制约关系 上例的正确执行顺序上例的正确执行顺序 5.1 并发的原理控制对共享资源的访问 u不加控制地访问共享资源会出现问题 ，要求控制对共享资源的访问！ 5.2 进程间的制约关系 进程的同步（直接制约）：synchronism u指系统中一些进程需要相互合作，共同完成一 项任务。具体说，一个进程运行到某一点时要 求另一伙伴进程为它提供消息，在未获得消息 之前，该进程处于等待状态，获得消息后被唤 醒进入就绪态 进程的互斥（间接制约）mutual exclusion 由于各进程要求共享资源，而有些资源需要互 斥使用，因此各进程间竞争使用这些资源，进 程的这种关系为进程的互斥 5.2 进程间的制约关系 u相关概念： u 互斥：指多个进程不能同时使用同一个资源； u 死锁：指多个进程互不相让，都得不到足够的 资源； u 饥饿：指一个进程一直得不到资源（其他进程 可能轮流占用资源） u 临界资源：系统中某些资源一次只允许一个进 程使用，称这样的资源为临界资源或互斥资源或 共享变量 u 临界区：进程中访问临界资源的一段代码。 司机司机 P1P1 售票员售票员 P2P2 REPEAT REPEATREPEAT REPEAT 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSEUNTIL FALSE UNTIL FALSE 5.2 5.2 进程间的制约关系进程间的制约关系 5.3 临界区问题 进入区 退出区 临界区 剩余区 u临界区(critical section)：进程中 访问临界资源的一段代码。 u进入区(entry section)：在进入临 界区之前，检查可否进入临界区的 一段代码。如果可以进入临界区， 通常设置相应“正在访问临界区“标 志 u退出区(exit section)：用于将“正 在访问临界区“标志清除。 u剩余区(remainder section)：代 码中的其余部分。 5.3 临界区问题原语 u内核在执行某些基本操作时, 往往利用原语操作实现 u原语 u是一种广义指令, 相当于扩充了机器指令集 u原语是由若干条指令构成、用于完成一定功能的一个 过程. u原语是原子操作(atomic operation) u原子操作: u一个操作中的所有动作, 要么全做, 要么全不做. u原子操作是一个不可分割的操作 5.3 临界区问题互斥的要求 u使用临界区应遵循的准则 u有空让进：当无进程在临界区时，任何有权使用临 界区的进程可进入 无空等待：不允许两个以上的进程同时进入临界区 多中择一：当没有进程在临界区，而同时有多个进 程要求进入临界区，只能让其中之一进入临界区， 其他进程必须等待 有限等待：任何进入临界区的要求应在有限的时间 内得到满足 让权等待：处于等待状态的进程应放弃占用CPU 平等竞争：任何进程无权停止其它进程的运行进程 之间相对运行速度无硬性规定 5.4 实现互斥的方法 u实现互斥的方法 u软件方法 u硬件方式：利用专门机器指令 5.4.1 实现互斥的方法：软件的方法（自学） u特点 u无需硬件、OS和程序设计语言的支持 u处理开销大, 容易出错 u学习的意义 u更好地理解并发处理的复杂性 u适用范围 u单处理器系统 u共享主存的多处理系统 u前提假设: 存储器级的访问是互斥的 5.4.1互斥：软件的方法Dekker算法 uDijkstra报告了Dekker（荷兰数学家）设计的算法 u尝试1：单标志 Dekker算法尝试1 u有两个进程Pi, Pj，设立一个共享全局整型变量 turn：描述允 许进入临界区的进程标识 u在进入区循环检查是否允许本进程进入：turn为 i 时，进 程Pi可进入； u在退出区修改允许进入进程标识：进程Pi退出时，改turn 为进程Pj的标识j； u 优点：保持了互斥的特性 u 缺点： u严格轮流使用临界区，限制推进速度，由执行较慢的进程 决定 u容易造成资源利用不充分：在Pi出让临界区之后，Pj使用 临界区之前，Pi不可能再次使用临界区； u如果一个进程失败了，另一个进程将被永久阻塞 u忙等待 (busy waiting) : 为了等待一事件的发生, 重复执 行一段循环代码 - 白白消耗CPU时间 DekkerDekker算法尝试算法尝试2 2：双标志、先检查 u设立一个标志数组flag：描述进程是否在临界区，初值均为 FALSE，它是进程到达临界区的钥匙 u先检查，后修改：在进入区中，检查另一个进程是否在临 界区，不在临界区时修改本进程在临界区的标志； u在退出区修改本进程在临界区的标志； Dekker算法尝试2：双标志、先检查 u优点：不用交替进入，可连续使用； u缺点： u不能保证互斥！Pi 和 Pj可能同时进入临界区。在Pi 和 Pj都不在临界区时，假设按下面序列执行时，会 同时进入：“Pi; Pj ; Pi; Pj”。即在 检查对方flag之后和切换自己 flag 之前有一段时间 ，结果都检查通过。这里的问题出在检查和修改操 作不能连续进行。 u一个进程在临界区内失败, 另一进程永远被阻塞 Dekker算法尝试3:双标志、后检查 Dekker算法尝试3：双标志、后检查 u优点：类似于算法2，与算法2的区别在于先修改、 后检查。可防止两个进程同时进入临界区，实现互 斥。 u缺点：Pi和Pj可能都进入不了临界区。在Pi和Pj都不 在临界区时，假设按下面序列执行，则都进不了临 界区：“Pi Pj Pi Pj”。即在切换自己 的flag之后和检查对方flag之前有一段时间，结果都 切换flag，都检查不通过。 DekkerDekker算法尝试算法尝试4 4 Dekker算法尝试4 u思路：使每个进程更礼让一些：每 个进程设置自己的flag，表明自己 想进入自己的临界区，但也准备重 置flag，以尊重另一个进程。 u优点：保证互斥 u缺点： u出现活锁：一组进程都想进入它们的临 界区，但没有一个能成功进入（不是死 锁，因为两个进程相对速度的任何改变 都会打破这种情形） u可能成功进入，也可能有使得任何进程 都不能进入临界区的执行顺序。 P0将flag0置为true P1将flag1置为true P0检查flag1 P1检查flag0 P0将flag0置为false P1将flag1置为false P0将flag0置为true P1将flag1置为true 此序列无限延伸， 任何一个进程都不能进入 自己的临界区 一种正确的方案 u避免“无原则”的礼让 u规定在都想进入时的进入顺序 5.4.2 Peterson算法：先修改、后检查、后修改者等待 uFlag表示每个进程关于互斥的位置，turn解决同时进入 时的冲突问题 uturn=j：描述可进入的进程（同时修改标志时） u在进入区先修改后检查，并检查并发修改的先后： u检查对方flag，如果不在临界区则自己进入空闲则入 u否则再检查turn：保存的是较晚的一次赋值，则较晚的进 程等待，较早的进程进入先到先入，后到等待 flagi = TRUE; turn = j; while (flagj critical section flagi = FALSE; remainder section uDekker算法解决了 互斥问题，但比较复 杂，证明起来也比较 困难。 uuPetersonPeterson提出一种提出一种 简单的方案。简单的方案。 5.4.3 互斥的实现硬件方法 u1. 中断禁用 (关中断, Interrupt Disabling) u单处理器系统, 并发进程交替执行而不重叠 u一个进程一直运行，直到调用了一个OS服务或 被中断 u如果进程访问临界资源时(执行临界区代码)不被 中断, 就可以利用它来保证互斥地访问 u途径: 使用关中断原语、开中断原语 1.中断禁用 (关中断） u过程:关中断原语; 临界区 开中断原语 其余部分 u存在问题 u代价高：限制了处理器交替执行各进程的能力 u不能用于多处理器结构：关中断不能保证互斥 5.4.3 互斥的实现硬件方法 u2.专门的机器指令 u设计一些机器指令，用于保证两个动作的原 子性 ，如在一个指令周期中实现测试和修改 uTestandSet(TS)指令 uSwap指令 专门的机器指令Test和Set指令(TS指令) uTS指令定义(逻辑) Boolean TestandSet(int i) if (i=0) i=1; return true; else return false; 使用TestAndSet实现互斥 const int n; int bolt; void P(int i) While(true) While(!TestandSet(bolt);/什么都不做 /临界区; bolt=0; /剩余区 void main() bolt=0; Parbegin(p(1),p(2),p(n) Swap指令定义： void Swap(int a, int b) int temp=a; a = b; b=temp ; 专门的机器指令Swap 使用使用SwapSwap指令指令实现互斥实现互斥 do key=1; while(key!=0) Swap(lock,key); /*临界区*/ lock=0; 剩余区 while(1); 5.4.3 专门的机器指令评价 u优点 u适用于单处理器或共享主存的多处理器系统, 进程数目任意 u简单且易于证明 u可以使用多个变量支持多个临界区，只需为每个临界区设立一个布 尔变量 u缺点 u忙等待：当一个进程正在等待进入一个临界区时，继续消耗处理器 时间。 u可能饿死：任意选择等待的进程，有的可能一直选不上 u可能死锁：高优先级进程等待处于阻塞状态的低优先级进程的资源 （如：进程P1执行TS或Swap指令并进入临界区，然后P1被阻塞，并 把CPU给具有更高优先级的P2, 若P2试图使用与P1相同的资源，由 于互斥机制，它被拒绝访问，因此进入忙等待循环，又因P2优先级 高于P1，所以P1总得不到调度执行,P2也无法执行。） 5.5 信号量 u信号量机制 uOS可从进程管理者的角度来处理互斥的问题 u信号量就是OS提供的管理公有资源的有效手段。 u是解决并发进程问题的第一个重要进展 (Dijkstra, 1965) 信号量定义：semaphore是一个数据结构，定义如下 ： struct semaphore integer count; Pointer_PCB queue; ; 信号量声明： Semaphore s; 5.5 信号量-定义与声明 5.5 信号量信号量的物理意义 u信号量s的count值含义 u初始化指定一个非负整数值，表示空闲资源 总数（又称为“资源信号量”）: u若为非负值：表示当前的空闲资源数（s.count= 0 :可用的资源数) u若为负值：其绝对值表示当前等待临界区的进 程数(|s.count|为等待的进程数) u每个信号量 s 除一个整数值 s.count（计数）外， 还有一个进程等待队列 s.queue，其中是阻塞在该 信号量的各个进程的标识 5.5 信号量wait、signal原语的定义 /表示申请一个资源 /表示没有空闲资源 /调用进程进入等待队列s.queue; / 阻塞调用进程;； /表示释放一个资源； /表示有进程处于阻塞状态； /从等待队列s.queue中取出一个进程P; /进程P进入就绪队列; 5.5 信号量P、V原语的定义 struct semaphore integer count; Pointer_PCB queue; ; void P(semaphore s) s.count-; /申请一个资源 If(s.count V(mutex) void main() parbegin(Process(1), Process(2), ., Process(n); 请仔细分析信号量的变化过程，它是如何保证互斥的？ 用信号量实现互斥 u在互斥问题中，对信号量mutex必须设置一次初值，初值 必须为1 uP、V原语操作应该分别紧靠临界区的头部和尾部，从而提 高进程的并发度 uMutex的取值为：1,0,-1,-2,-(n-1) uP、V操作必须成对出现，而且它们同处于同一个进程中 互斥-例1、过河问题 u某条河上只有一个独木桥，以便行人过河。现在河的两边 都有人要过桥，若把过桥者看做一个进程，规定： 每次只 有一个人通过。为了保证过桥安全，请用P、V操作分别实 现正确的管理。 const int n = 进程数； Semaphore mutex = 1; void Process_EW( int i) while ( true) P(mutex); / wait(s) V(mutex) / signal(s) void main() parbegin(Process EW(1); Process EW(2); . Process EW(n); Process WE(1); Process WE(n); 互斥-例2、对共享变量的访问 u观察者和报告者是两个并发 执行的进程。观察者不断观 察并对通过的卡车计数，报 告者定时地将观察者的计数 随时打印。请用P、V原语进 行正确描述。 Semaphore mutex = 1; Count:=0; Process observer Begin repeat 观察到一辆车； P(mutex); count:=count+1; V(mutex) Until false; End; Process reporter Begin repeat P(mutex); print count; count:=0; V(mutex) Until false; End; 缓冲区buf PcPp 计算 打印 放入 条件=buf空 取出结果 条件=buf 非空 u例1. 进程Pc 和 Pp 合作完成计算和打印任务 利用信号量实现进程同步 Pp: B: P(buffull); 取出buf中的数据 置空标记，打印 V(bufempty); Goto B; 设信号量：bufempty: 表示buf 空，=1 buffull: 表示buf满, =0 Pc: A: P(bufempty); 计算； buf 计算结果 V( buffull); Goto A; 例例2 2： 司机司机 P1P1 售票员售票员 P2P2 REPEAT REPEATREPEAT REPEAT 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门 UNTIL FALSE UNTIL FALSEUNTIL FALSE UNTIL FALSE 司机启动车辆的动作必须于售票员关车门的动作取得同步，售票 员开车门的动作也必须与司机停车取得同步。 u设信号量: uS1：是否允许司机启动汽车，初值为0 uS2：是否允许售票员开门，初值为0 Driver() While (1) P(S1); 启动汽车; 正常行车； 到站停车； V(S2); Busman() While (1) 关车门; V(S1)； 售票 P(S2)； 开车门； 上下乘客； Int s1=0; Int s2=0; Main Cobegin Driver(); Busman(); Coend u 生产者/消费者问题 u 读写者问题 u哲学家问题 5.6 经典同步问题 例例1 1、 生产者生产者/ /消费者问题消费者问题 (the producer/consumer problem) u（1）有一群生产者进程在生产消息, 并将消息提供给消费 者进程去消费。为使生产者进程和消费者进程能并发执行 , 在它们之间设置了一个具有n个缓冲区的缓冲池, 生产者 进程可将它所生产的消息放入一个缓冲区中, 消费者进程 可从一个缓冲区中取得一个消息消费。 u（2）尽管所有的生产者进程和消费者进程都以异步方式 运行, 但它们之间必须保持同步, 即不允许消费进程者到一 个空缓冲区去取消息, 也不允许生产者进程向一个已装有 消息且尚未被取走消息的缓冲区中投放消息。 u （3）任何时刻只能有一个进程可对共享缓冲区进行操作 生产者/消费者问题 (the producer/consumer problem) 共享缓冲区 生产指针消费指针 Producer 1 Producer 2 . Producer M Consumer 1 Consumer 2 . Consumer N 满空指针移动方向 u设信号量： uFull：是“满”缓冲区数量，初值为0 uEmpty：是“空”缓冲区数量，初值为N。full + empty= N uMutex：用于访问缓冲区时的互斥，初值是1 Producer P(empty); P(mutex);/进入区 one unit buffer; V(mutex); V(full);/退出区 Consumer P(full); P(mutex);/进入区 one unit buf; V(mutex); V(full); P(full); P(mutex); /进入区 one unit-buf; V(mutex); V(empty);/退出区 分析：当full=0, mutex = 1时，执行顺序： Consumer.P(mutex) ; Consumer.P(full); / C阻塞，等待Producer 发出的full信号 Producer.P(empty) ; Producer.P(mutex) ; / P 阻塞，等待Consumer发出的empty信号 思考：还有其他的执行序列可以产生死锁吗？ 发生 死锁 生产者/消费者问题的有限循环缓冲区 消费者： while (true) p(full); P(mutex); Get product from buffer(out); out = (out + 1) mod n; V(mutex); V(empty); consume item ; 生产者: while (true) produce item v; P(empty); P(mutex); Send product to buffer(in); in = (in + 1) mod N; V(mutex); V(full); 1 2 3 N-2 0 N-1 in out 使用方向 供应方向 缓冲区被看作一个循环缓冲区 指针值必须表达为按缓冲区的大小取模 empty=n;full0；mutex=1; 生产者生产者/ /消费者问题的消费者问题的有限循环缓冲区有限循环缓冲区 例2：图书馆问题 图书馆有100个座位，有一张登记表，要求： 阅读者进入时登记，取得座位号； 出来时，注销；登记表同时只能由一个人使用 ； 用P、V原语描述一个读者的使用过程。 Reader(int i) Enter()； 阅读; Outer() End Enter() Begin P(SN)； P(mutex) ； 登记； V(mutex) ； End Outer() Begin P(mutex); 注销； V(mutex); V(SN); End 信号量SN：表示可用座位数，初值为100； 信号量mutex：表示登记表是否正在使用，初值为1； 例3-与进程的执行顺序有关的问题 u有3个进程PA，PB和PC合作解决文件打印问题： uPA将文件记录从磁盘读入主存的缓冲区1，每执行 一次读一个记录; uPB将缓冲区1的内容复制到缓冲区2，每执行一次复 制一个记录； uPC将缓冲区2的内容打印出来，每执行一次打印一 个记录。缓冲区的大小等于一个记录大小。 要求：请用P，V操作来保证文件的正确打印。 缓冲区1 缓冲区2 PA 从磁盘读入 PB 复制 PC 打印 设置4个信号量：empty1, empty2,full1,full2. empty1及empty2分别表示缓冲区1及缓冲区2是否 为空，初值为1。 full1，full2分别表示缓冲区1及缓冲区2是否有记 录可供处理，其初值为0。 例题3 PA() While (1) 从磁盘读一个记录； P(empty1); 将记录存入缓冲区1； V(full1); PB() While (1) P(full1) 从缓冲区1中取出记录； v(empty1); P(empty2); 将记录存入缓冲区2； V(full2); PC() While (1) P(full2); 从缓冲区2取一个记录； V(empty2); 打印记录; Int empty1=1; empty2=1;full1=0;full2=0; Main() Cobegin PA(); PB(); PC(); Coend 例4、 读/写问题 u问题描述 u有一个许多进程共享的数据区; 有一些只读取这个数据区 的进程(reader)和一些只往数据区中写数据的进程(writer); 此外还必须满足下列条件: u任意多的读进程可以同时读这个数据区 u一次只有一个写进程可以往数据区写 u如果一个写进程正在往数据区中写, 禁止任何读进程读 数据区 u要求：“读写” 互斥；“写写” 互斥；“读读” 允许 uWsem :用于互斥，只要一个写进程正在访问共享数据区， 其他的写进程和读进程都不能访问它。 uReadcount：用于记录读进程的数目 u信号量X用于确保readcount被正确更新。（互斥） 读/写问题 读进程具有优先权 例5. 哲学家进餐问题(the dining philosophers problem) 问题描述：（由Dijkstra首先提出并解决） u5个哲学家围绕一张圆桌而坐; u桌子上放着5支筷子，每两个哲学家之间放一支； u哲学家的动作包括思考和进餐; u进餐时需要同时拿起他左边和右边的两支筷子; u思考时则同时将两支筷子放回原处; 问题：如何保证哲学家们的动作有序进行？如： u不出现相邻者同时