操作系统概念：第七章进程同步.ppt

操作系统概念 第七章：进程同步 1 本章主要内容 n背景 n临界区域问题 n同步硬件 n信号量 n经典同步问题 n管程 2 7.1 背景 n共享数据的并发访问可能导致数据的不一致 n维护数据的一致性需要能够保证协作进程顺序 执行的机制 3 竞争条件（Race Condition） n生产者 while(1) while (counter = BUFFER_SIZE) ; / do nothing /produce an item and put in nextProduced bufferin = nextProduced; in = (in + 1) % BUFFER_SIZE; counter +; 4 竞争条件 消费者 while (1) while (counter = 0) ; / do nothing nextConsumed = bufferout; out = (out + 1) % BUFFER_SIZE; counter -; 5 竞争条件 ncounter+可按如下方式以机器语言实现 nregister1 = counter nregister1 = register1 + 1 ncounter = register1 ncounter - - 可按如下方式实现 nregister2 = counter nregister2 = register2 1 ncounter = register2 n考虑以下交叉执行顺序 nS0: 生产者执行 register1 = counter register1 = 5 nS1: 生产者执行 register1 = register1 + 1 register1 = 6 nS2: 消费者执行 register2 = counter register2 = 5 nS3: 消费者执行 register2 = register2 1 register2 = 4 nS4: 生产者执行 counter = register1 counter = 6 nS5: 消费者执行 counter = register2 counter = 4 6 n多个进程并发访问和操作同一数据且执行结果 与访问发生的特定顺序有关，称为竞争条件（ race condition） 7 7.2 临界区问题的解决 n代码块： n进入区（entry section） n临界区（critical section） n退出区（exit section） n剩余区（remainder section） n互斥（Mutual Exclusion）：如果进程Pi在其临界区执行，那么其 他进程都不能在其临界区内执行。 n有空让进（Progress）：如果没有进程在其临界区内执行且有进 程希望进入临界区，那么只有那些不在剩余区内执行的进程能参 加决策，以选择谁能下一个进入临界区，且这种选择不能无限推 迟。 n有限等待（Bounded Waiting）：在一个进程做出进入其临界区 的请求到该请求被允许期间，其他进程被允许进入期临界区的次 数存在一个上限。 8 两进程解法 n两个进程标为P0和P1，为了方便，当使用Pi时 ，用Pj来表示另一个进程；即j = 1 i; 9 算法1 n进程共享一普通整数变量turn，其初值为0（或1） n如果turn = i, Pi允许在其临界区内执行。 n确保了每个时刻只有一个进程处于临界区域。 n但不满足“有空让进”需要。 n为什么？ nP0能否连续两次进入临界区？ n do nwhile (turn != i) ; /进入区 n临界区 nturn = j; /退出区 n剩余区 n while (1); 10 算法2 1. do 2. flagi = true; 3. while (flagj) ; /进入区 4. 临界区 5. flagi = false; /退出区 6. 剩余区 7. while (1); n增加了更多的状态信息 n布尔标志用来表示线程它准备进入其临界区 n“有空让进”的要求仍然没有得到满足 n为什么？ n将语句2与语句3的位置互换，又将如何？ 11 算法3 n结合算法1与算法2的思想 n是否满足临界区的要求？ do flagi = true; turn = j; while (flagj /进入区 临界区 flagi = false; /退出区 剩余区 while (1); 12 多进程解法 n面包店算法的思想： n在进入商店时，每个客户接收一个号码。具有最小号码 的客户先得到服务。然而，面包店算法不能保证两个进 程不会收到同样的号码。在出现相同号码时，具有最小 名称的进程先得到服务。即如果Pi和Pj收到同样号码， 且i j，那么Pi 先得到服务。 n实现 nboolean choosingn; nint numbern; n定义： n若a c，若a=c且bd， (a, b) (c, d) nmax(a0, , an-1)是数k, 从而kai, 对 I = 0, , n-1成立 。 n算法见下页 13 do choosingi = true; numberi = max(number0, number1, , numbern-1) + 1; choosingi = false; for (j = 0; j n; j +) while (choosingj) ; while (numberj != 0) 临界区 numberi = 0; 剩余区 while (1); 14 7.3 同步硬件 n许多系统提供了临界区代码的硬件支持 n单处理器系统 可以禁用中断 n当前正在执行的代码可以顺利执行而不会被抢 占 n在多处理器环境下，这种解决方案是不可行的 。 n现代机器提供了特殊的原子硬件指令 n原子 = 不可中断的 nTestAndSet指令 nSwap指令（交换内存中两个字的内容） 15 TestAndSet指令 nTestAndSet指令的定义 boolean TestAndSet(boolean target = true; return rv; n使用TestAndSet的互斥实现 do while (TestAndSet(lock) ; 临界区 lock = false; 剩余区 while (1); n该算法不满足有限等待要求 16 Swap指令 n定义 nvoid Swap(boolean na = b; nb = temp; n n用swap实现互斥 ndo nkey = true; nwhile (key = true) Swap(lock, key); n临界区 nlock = false; n剩余区 n while (1); n该算法也不满足有限等待要求。 17 使用TestAndSet的有限等待互斥 do waitingi = true; key = true; while (waitingi waitingi = false; 临界区 j = (i + 1) %n; while (j != i) if (j = i) lock = false; else waitingj = false; 剩余区 while (1); 18 7.4 信号量 n信号量 S 是个整数变量 n两种标准原子操作用来修改S：wait() 和 signal() n原来也称为P() 和 V() n某些参考书也称为acquire和release nwait的伪代码定义 wait(S) while S = 0 ; / no-op S-; nsignal的伪代码定义 signal (S) S+; 19 用法：解决n个进程的临界区问题 nn个进程共享一个信号量mutex，初始值为1 do wait(mutex); 临界区 signal(mutex); 剩余区 while (1); n用来同步：P1和P2共享信号量synch，其初始值为0 nP1: S1; signal(synch); nP2: wait(synch); S2; 20 实现 n忙等待 n当一个进程位于其临界区内，任何其他试图进入其临界 区的进程都必须在其进入代码中连续地循环。这种类型 的信号量也称为自旋锁（spinlock） n改进办法：将忙等待改成阻塞 n如 void wait (semaphore S) S.value -; if (S.value 0) add this process to s.L; block; 21 死锁与饥饿 n死锁：两个或多个进程无限地等待一个事件，而该事 件只能由这些等待进程之一来产生。 n设S和Q为两个信号量，其初值皆为1 nP0P1 nwait(S);wait(Q); nwait(Q);wait(S); n nsignal(S);signal(Q); nsignal(Q);signal(S); n饥饿：无限阻塞。一个被悬挂的进程可能永远无法从 信号量队列中移出。 22 二进制信号量 n计数信号量 n其整数值可跨越于一个不受限制的域内。 n二进制信号量 n只能为整数值0或1 n如何用二进制信号量实现计数信号量 n设S为计数信号量，可以下列数据结构来实现 nbinary-semaphore S1, S2; nint C; n开始时，S1 = 0, S2 = 0, 整数C的值设置为计数信号量 的初值 nwait与signal的实现见下一页 23 nWait nwait(S1); nC-; nif (C 0) nsignal(S1); nwait(S2); n nsignal(S1); nSignal nwait(S1); nC+; nif (C = 0) nsignal(S2); nelse nsignal(S1); 24 7.5 经典同步问题 n有限缓冲问题 n读者作者问题 n哲学家进餐问题 25 有限缓冲问题 do produce an item in nextp wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); while (1); do wait(full); wait(mutex); remove an item from buffer to nextc signal(mutex); signal(empty); consume the item in nextc while (1); 26 读者作者问题 n一个数据对象可以为多个并发进程所共享。其 中有的进程可能只需要读共享对象的内容，而 其他进程可能要更新共享对象（即读和写）。 n将只对读感兴趣的进程称为读者 n其他则称为作者 n第一读者作者问题 n仅当无读者等待时，才允许写者执行 n第二读者作者问题 n在读者与作者同时申请资源的时候，写者优先 。 27 第一读者作者问题 wait(wrt); writing is performed signal(wrt); wait(mutex); readcount +; if (readcount = 1) wait(wrt); signal(mutex); reading is performed wait(mutex); readcount -; if (readcount = 0) signal(wrt); signal(mutex); 28 哲学家就餐问题 29 n共享数据 nsemaphore chopstick5; n哲学家i结构 do wait(chopsticki); wait(chopstick(I + 1) % 5); eat signal(chopsticki); signal(chopstick(I + 1) % 5); think while (1); 30 7.6 管程(monitor) n为了保证共享变量的数据一致性，管程应互斥使用。 管程通常是用于管理资源的，因此管程中有进程等待 队列和相应的等待和唤醒操作。在管程入口有一个等 待队列，称为入口等待队列。当一个已进入管程的进 程等待时，就释放管程的互斥使用权；当已进入管程 的一个进程唤醒另一个进程时，两者必须有一个退出 或停止使用管程。在管程内部，由于执行唤醒操作， 可能存在多个等待进程（等待使用管程），称为紧急 等待队列，它的优先级高于入口等待队列。 n因此，一个进程进入管程之前要先申请，一般由管程 提供一个enter过程；离开时释放使用权，如果紧急等 待队列不空，则唤醒第一个等待者，一般也由管程提 供外部过程leave。 31 条件变量 n管程内部有自己的等待机制。管程可以说明一 种特殊的条件型变量：var c : condition；实际 上是一个指针，指向一个等待该条件的PCB队 列。对条件型变量可执行wait和signa