操作系统chapter7.ppt

《操作系统chapter7.ppt》由会员分享，可在线阅读，更多相关《操作系统chapter7.ppt（36页珍藏版）》请在第壹文秘上搜索。

1、操作系统概念第七章：进程同步2本章主要内容n背景n临界区域问题n同步硬件n信号量n经典同步问题n管程37.1 背景n共享数据的并发访问可能导致数据的不一致n维护数据的一致性需要能够保证协作进程顺序执行的机制4竞争条件（Race Condition）n生产者while(1) while (counter = BUFFER_SIZE); / do nothing/produce an item and put in nextProducedbufferin = nextProduced;in = (in + 1) % BUFFER_SIZE;counter +;5竞争条件消费者while (1)

2、while (counter = 0); / do nothingnextConsumed = bufferout;out = (out + 1) % BUFFER_SIZE;counter -;6竞争条件ncounter+可按如下方式以机器语言实现nregister1 = counternregister1 = register1 + 1ncounter = register1ncounter - - 可按如下方式实现nregister2 = counternregister2 = register2 1ncounter = register2n考虑以下交叉执行顺序nS0: 生产者执行 re

3、gister1 = counter register1 = 5nS1: 生产者执行 register1 = register1 + 1 register1 = 6nS2: 消费者执行 register2 = counter register2 = 5nS3: 消费者执行 register2 = register2 1 register2 = 4nS4: 生产者执行 counter = register1 counter = 6nS5: 消费者执行 counter = register2 counter = 47 n多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为竞争条件竞

4、争条件（race condition）87.2 临界区问题的解决n代码块：代码块：n进入区（进入区（entry section）n临界区（临界区（critical section）n退出区（退出区（exit section）n剩余区（剩余区（remainder section）n互斥互斥（Mutual Exclusion）：如果进程Pi在其临界区执行，那么其他进程都不能在其临界区内执行。n有空让进有空让进（Progress）：如果没有进程在其临界区内执行且有进程希望进入临界区，那么只有那些不在剩余区内执行的进程能参加决策，以选择谁能下一个进入临界区，且这种选择不能无限推迟。n有限等待有限等待（

5、Bounded Waiting）：在一个进程做出进入其临界区的请求到该请求被允许期间，其他进程被允许进入期临界区的次数存在一个上限。9两进程解法n两个进程标为P0和P1，为了方便，当使用Pi时，用Pj来表示另一个进程；即j = 1 i;10算法1n进程共享一普通整数变量turn，其初值为0（或1）n如果turn = i, Pi允许在其临界区内执行。n确保了每个时刻只有一个进程处于临界区域。n但不满足“有空让进”需要。n为什么？nP0能否连续两次进入临界区？n do nwhile (turn != i) ; /进入区n临界区nturn = j; /退出区n剩余区n while (1);11算法2

6、1. do 2. flagi = true;3. while (flagj) ; /进入区4. 临界区5. flagi = false; /退出区6. 剩余区7. while (1);n增加了更多的状态信息n布尔标志用来表示线程它准备进入其临界区n“有空让进”的要求仍然没有得到满足n为什么？n将语句2与语句3的位置互换，又将如何？12算法3n结合算法1与算法2的思想n是否满足临界区的要求？do flagi = true;turn = j;while (flagj & turn = j) ; /进入区临界区flagi = false; /退出区剩余区 while (1);13多进程解法n面包店算

7、法的思想：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算法见下页14 do choosingi = true;numberi = max(number0, number1, , numbe

8、rn-1) + 1;choosingi = false;for (j = 0; j n; j +) while (choosingj) ;while (numberj != 0) & (numberj, j) numberi, i) ;临界区numberi = 0;剩余区 while (1);157.3 同步硬件n许多系统提供了临界区代码的硬件支持n单处理器系统 可以禁用中断n当前正在执行的代码可以顺利执行而不会被抢占n在多处理器环境下，这种解决方案是不可行的。n现代机器提供了特殊的原子硬件指令n原子 = 不可中断的nTestAndSet指令nSwap指令（交换内存中两个字的内容）16Test

9、AndSet指令nTestAndSet指令的定义boolean TestAndSet(boolean &target) boolean rv = target;target = true;return rv;n使用TestAndSet的互斥实现do while (TestAndSet(lock) ;临界区lock = false;剩余区 while (1);n该算法不满足有限等待要求17Swap指令n定义nvoid Swap(boolean &a, boolean &b) nboolean temp = a;na = b;nb = temp;nn用swap实现互斥ndo nkey = true

10、;nwhile (key = true)Swap(lock, key);n临界区nlock = false;n剩余区n while (1);n该算法也不满足有限等待要求。18使用TestAndSet的有限等待互斥do waitingi = true;key = true;while (waitingi & key)key = TestAndSet(lock);waitingi = false;临界区j = (i + 1) %n;while (j != i) & !waitingj)j = (j + 1) %n;if (j = i)lock = false;elsewaitingj = fals

11、e;剩余区 while (1);197.4 信号量n信号量 S 是个整数变量n两种标准原子操作用来修改S：wait() 和 signal()n原来也称为P() 和 V()n某些参考书也称为acquire和releasenwait的伪代码定义wait(S) while S = 0; / no-opS-;nsignal的伪代码定义signal (S) S+;20用法：解决n个进程的临界区问题nn个进程共享一个信号量mutex，初始值为1do wait(mutex);临界区signal(mutex);剩余区 while (1);n用来同步：P1和P2共享信号量synch，其初始值为0nP1:S1;s

12、ignal(synch);nP2:wait(synch);S2;21实现n忙等待n当一个进程位于其临界区内，任何其他试图进入其临界区的进程都必须在其进入代码中连续地循环。这种类型的信号量也称为自旋锁自旋锁（spinlock）n改进办法：将忙等待改成阻塞n如void wait (semaphore S) S.value -;if (S.value 0) add this process to s.L;block;22死锁与饥饿n死锁：两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。n设S和Q为两个信号量，其初值皆为1nP0P1nwait(S);wait(Q);nwait(

13、Q);wait(S);nnsignal(S);signal(Q);nsignal(Q);signal(S);n饥饿：无限阻塞。一个被悬挂的进程可能永远无法从信号量队列中移出。23二进制信号量n计数信号量n其整数值可跨越于一个不受限制的域内。n二进制信号量n只能为整数值0或1n如何用二进制信号量实现计数信号量n设S为计数信号量，可以下列数据结构来实现nbinary-semaphore S1, S2;nint C;n开始时，S1 = 0, S2 = 0, 整数C的值设置为计数信号量的初值nwait与signal的实现见下一页24 nWaitnwait(S1);nC-;nif (C 0) nsign

14、al(S1);nwait(S2);nnsignal(S1);nSignalnwait(S1);nC+;nif (C = 0)nsignal(S2);nelsensignal(S1);257.5 经典同步问题n有限缓冲问题n读者作者问题n哲学家进餐问题26有限缓冲问题do produce an item in nextpwait(empty);wait(mutex);add nextp to buffersignal(mutex);signal(full); while (1);do wait(full);wait(mutex);remove an item from buffer to nex

15、tcsignal(mutex);signal(empty);consume the item in nextc while (1);27读者作者问题n一个数据对象可以为多个并发进程所共享。其中有的进程可能只需要读共享对象的内容，而其他进程可能要更新共享对象（即读和写）。n将只对读感兴趣的进程称为读者n其他则称为作者n第一读者作者问题n仅当无读者等待时，才允许写者执行n第二读者作者问题n在读者与作者同时申请资源的时候，写者优先。28第一读者作者问题wait(wrt);writing is performedsignal(wrt);wait(mutex);readcount +;if (readc

16、ount = 1)wait(wrt);signal(mutex);reading is performedwait(mutex);readcount -;if (readcount = 0)signal(wrt);signal(mutex);29哲学家就餐问题30 n共享数据nsemaphore chopstick5;n哲学家i结构do wait(chopsticki);wait(chopstick(I + 1) % 5);eatsignal(chopsticki);signal(chopstick(I + 1) % 5);think while (1);317.6 管程(monitor)n为了保证共享变量的数据一致性，管程应互斥使用。 管程通常是用于管理资源的，因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列，称为入口等待队列入口等待队列。当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，由于执行唤醒操作，可能存在多个等待进程（等待使用管程），称为紧急紧急等待队列等待队列