操作系统chapter7.ppt

操作系统概念 第七章 进程同步 2 本章主要内容 背景临界区域问题同步硬件信号量经典同步问题管程 3 7 1背景 共享数据的并发访问可能导致数据的不一致维护数据的一致性需要能够保证协作进程顺序执行的机制 4 Shareddata defineBUFFER SIZE10Typedefstruct item itembuffer BUFFER SIZE intin 0 intout 0 共享缓冲是通过循环数组和两个逻辑指针来实现的 in指向缓冲区中下一个空位 out指向缓冲区中的第一个非空位 5 ProducerProcesswhi1e 1 produceaniteminnextProduced while in 1 BUFFER SIZE out donothing buffer in nextProduced in in 1 BUFFER SIZE 6 ConsumerProcesswhile 1 while in out donothingnextConsumed buffer out out out 1 BUFFER SIZE consumetheiteminnextConsimed 实现方法的缺点 7 asolutiontotheconsumer producerproblemthatfillsallthebuffers Count aninteger keepstrackofthenumberoffullbuffers Initially 0Incremented producesanewbufferDecremented consumesabuffer 8 Bounded Buffer Shareddata defineBUFFER SIZE10typedefstruct item itembuffer BUFFER SIZE intin 0 intout 0 intcounter 0 9 ProducerprocessitemnextProduced while 1 produceaniteminnextProduced while counter BUFFER SIZE donothing buffer in nextProduced in in 1 BUFFER SIZE counter ConsumerprocessitemnextConsumed while 1 while counter 0 donothing nextConsumed buffer out out out 1 BUFFER SIZE counter consumetheiteminextConsumed 10 虽然生产者和消费者程序都各自正确 但是当并发执行时他们可能不能正确执行假设counter的当前值为5 且生产者和消费者并发执行语句 counter 和 counter 那么counter的值应该是多少呢 11 Thestatement count maybeimplementedinmachinelanguageas register1 counterregister1 register1 1counter register1Thestatement count maybeimplementedas register2 counterregister2 register2 1counter register2 12 如果生产者和消费者都试图并发地更新缓冲区 汇编语句可能交叉交叉依赖于生产者和消费者如何被调度 13 Assumecounterisinitially5 Oneinterleavingofstatementsis producer register1 counter register1 5 producer register1 register1 1 register1 6 consumer register2 counter register2 5 consumer register2 register2 1 register2 4 producer counter register1 counter 6 consumer counter register2 counter 4 CPU 5 counter 5 5 R1 R2 4 6 6 4 14 RaceCondition 竞争条件 像这样的情况 即多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关 称为竞争条件生产者 往银行存款的丈夫 消费者 从银行提款的夫人为了防止竞争条件 需要确保一段时间内只有一个进程能操作变量counter 为了实现这种保证 要求一定形式的进程间同步 15 7 2临界区问题的解决 代码块 进入区 entrysection 临界区 criticalsection 退出区 exitsection 剩余区 remaindersection 互斥 MutualExclusion 如果进程Pi在其临界区执行 那么其他进程都不能在其临界区内执行 有空让进 Progress 如果没有进程在其临界区内执行且有进程希望进入临界区 那么只有那些不在剩余区内执行的进程能参加决策 以选择谁能下一个进入临界区 且这种选择不能无限推迟 有限等待 BoundedWaiting 在一个进程做出进入其临界区的请求到该请求被允许期间 其他进程被允许进入期临界区的次数存在一个上限 16 实现互斥的方法 实现互斥的方法软件方法硬件方式 利用专门机器指令信号量 17 软件的方法 特点无需硬件 OS和程序设计语言的支持处理开销大 容易出错代表方法Dekker算法Peterson算法 18 两进程解法 两个进程标为P0和P1 为了方便 当使用Pi时 用Pj来表示另一个进程 即j 1 i 19 Dekker算法 算法1 进程共享一普通整数变量turn 其初值为0 或1 如果turn i Pi允许在其临界区内执行 确保了每个时刻只有一个进程处于临界区域 但不满足 有空让进 需要 为什么 P0能否连续两次进入临界区 do while turn i 进入区临界区turn j 退出区剩余区 while 1 20 优点 保持了互斥的特性缺点 严格轮流使用临界区 限制推进速度 由执行较慢的进程决定容易造成资源利用不充分 在Pi出让临界区之后 Pj使用临界区之前 Pi不可能再次使用临界区 如果一个进程失败了 另一个进程将被永久阻塞忙等待 busywaiting 为了等待一事件的发生 重复执行一段循环代码 白白消耗CPU时间 21 Dekker算法 算法2 Sharedvariablesbooleanflag 2 用数组来替换变量turn initiallyflag 0 flag 1 false flag i true PireadytoenteritscriticalsectionProcessPido criticalsectionremaindersection while 1 flag i true while flag j flag i false while flag j flag i true 违反了互斥条件 Satisfiesmutualexclusion butnotprogress notboundedwaiting 22 算法3 Peterson算法 结合算法1与算法2的思想是否满足临界区的要求 do flag i true turn j while flag j 23 7 3同步硬件 许多系统提供了临界区代码的硬件支持单处理器系统 可以禁用中断当前正在执行的代码可以顺利执行而不会被抢占在多处理器环境下 这种解决方案是不可行的 现代机器提供了特殊的原子硬件指令原子 不可中断的TestAndSet指令Swap指令 交换内存中两个字的内容 24 TestAndSet指令 TestAndSet指令的定义booleanTestAndSet boolean 25 Swap指令 定义voidSwap boolean 26 使用TestAndSet的有限等待互斥 do waiting i true key true while waiting i 27 7 4信号量 信号量机制OS可从进程管理者的角度来处理互斥的问题信号量就是OS提供的管理公有资源的有效手段是解决并发进程问题的第一个重要进展 28 7 4信号量 信号量S是个整数变量两种标准原子操作用来修改S wait 和signal 原来也称为P 和V wait的伪代码定义wait S whileS 0 no opS signal的伪代码定义signal S S 29 用法 解决n个进程的临界区问题 n个进程共享一个信号量mutex 初始值为1do wait mutex 临界区signal mutex 剩余区 while 1 用来同步 P1和P2共享信号量synch 其初始值为0P1 S1 signal synch P2 wait synch S2 30 实现 忙等待当一个进程位于其临界区内 任何其他试图进入其临界区的进程都必须在其进入代码中连续地循环 这种类型的信号量也称为自旋锁 spinlock 改进办法 将忙等待改成阻塞 记录型信号量如voidwait semaphoreS S value if S value 0 addthisprocesstos L block 31 记录型信号量及其操作的意义 Semaphore 某类资源S value 0 该类可用资源的数量 s value 等待该类资源的进程数S L等待该类资源的进程队列Wait signal Wait s 申请一个s信号量对应的资源成功 继续执行后面的指令失败 阻塞 进入S L队列等待Signal s 释放一个s信号量对应的资源S value 若S L队列非空 则唤醒 wakeup 其中一个进程 就绪 32 死锁与饥饿 死锁 两个或多个进程无限地等待一个事件 而该事件只能由这些等待进程之一来产生 设S和Q为两个信号量 其初值皆为1P0P1wait S wait Q wait Q wait S signal S signal Q signal Q signal S 饥饿 无限阻塞 一个被悬挂的进程可能永远无法从信号量队列中移出 33 二进制信号量 计数信号量其整数值可跨越于一个不受限制的域内 二进制信号量只能为整数值0或1 34 补充例题 信号量的应用 35 用P V原语解决n个进程互斥共享一个临界资源的编程模型 constintn 进程数 Semaphoremutex 1 VoidProcess inti while true P mutex V mutex voidmain parbegin Process 1 Process 2 Process n 请仔细分析信号量的变化过程 它是如何保证互斥的 36 用信号量实现互斥 为每一个临界资源设置一个互斥信号量mutex在互斥问题中 对信号量mutex必须设置一次初值 初值必须为1P V原语操作应该分别紧靠临界区的头部和尾部 从而提高进程的并发度Mutex的取值为 1 0 1 2 n 1 P V操作必须成对出现 而且它们同处于同一个进程中 37 互斥 例1 过河问题 某条河上只有一个独木桥 以便行人过河 现在河的两边都有人要过桥 若把过桥者看做一个进程 规定 每次只有一个人通过 为了保证过桥安全 请用P V操作分别实现正确的管理 constintn 进程数 Semaphoremutex 1 voidProcess EW inti while true P mutex V mutex voidmain parbegin ProcessEW 1 ProcessEW 2 ProcessEW n ProcessWE 1 ProcessWE n 38 互斥 例2 对共享变量的访问 观察者和报告者是两个并发执行的进程 观察者不断观察并对通过的卡车计数 报告者定时地将观察者的计数随时打印 请用P V原语进行正确描述 Processreporter while true P mutex printcount count 0 V mutex Semaphoremutex 1 Count 0 Processobserver while true 观察到一辆车P mutex count count 1 V mutex 39 例3 利用信号量实现进程同步司机P1售票员P2REPEATREPEAT启动关门正常运行售票到站停开门UNTILFALSEUNTILFALSE 司机启动车辆的动作必须于售票员关车门的动作取得同步 售票员开车门的动作也必须与司机停车取得同步 40 设信号量 S1 是否允许司机启动汽车 初值为0S2 是否允许售票员开门 初值为0 Driver While 1 P S1 启动汽车 正常行车 到站停车 V S2 Busman While 1 关车门 V S1 售票P S2 开车门 上下乘客 Ints1 0 Ints2 0 Main CobeginDriver Busman Coend 41 7 5经典同步问题 有限缓冲问题读者 作者问题哲学家进餐问题 42 1 Bounded BufferProblem Shareddata defineBUFFER SIZEntypedefstruct item Itembuffer BUFFER SIZE intin 0 intout 0 Semaphoremutex 1 empty n full 0 Full 是 满 缓冲区数量 初值为0Empty 是 空 缓冲区数量 初值为N full empty NMutex 用于访问缓冲区时的互斥 初值是1 43 Theproducerprocess do produceaniteminnextp wait empty wait mutex addnextptobuffer signa1 mutex signa1 full while 1 Theconsumerprocess do wait full wait mutex removeanitemfrombuffertonextc signal mutex signal empty consumetheiteminnextc while 1 wait mutex wait empty wait mutex wait full 44 几点说明 在每个程序中用于实现互斥的wait mutex 和signal mutex 必须成对地出现对信号量empty和full的wait和singal操作 同样需要成对地出现 但分别处于不同的程序中在每个程序中的多个wait操作顺序不能颠倒 应先执行对资源信号量的wait操作 然后执行对互斥信号量的wait操作 否则可能引起进程死锁 45 读者 作者问题 一个数据对象可以为多个并发进程所共享 其中有的进程可能只需要读共享对象的内容 而其他进程可能要更新共享对象 即读和写 将只对读感兴趣的进程称为读者其他则称为作者任意多的读进程可以同时读这个数据区一次只有一个写进程可以往数据区写如果一个写进程正在往数据区中写 禁止任何读进程读数据区分类第一读者 作者问题 没有读者会因为有一个写者在等待而等待其他读者的完成第二读者 作者问题 如果一个写者等待访问对象 那么不会有新读者开始读操作 46 利用记录型信号量解决第一读者 写者问题的数据结构为实现读者和写者在读或写时的互斥而设置了一个互斥信号量wrt 设置一个整型变量Readcount表示正在读的进程的数目仅当Readcount 0时 读者进程才需要执行wait wrt wait通过后 读者可读 Readcount加1同理 仅当读者执行了Readcount减1操作后其值为0时 才须执行能够Signal wrt Readcount是可被多个读者进程访问的临界资源 因此应该为它设置一个互斥信号量mutex 47 ReaderProcesswait mutex readcount if readcount 1 wait wrt signal m