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