信号量机制PPT课件.ppt

2 3 2信号量 semaphore 机制P53 前面的互斥算法都存在问题 它们是平等进程间的一种协商机制 需要一个地位高于进程的管理者来解决公有资源的使用问题 OS可从进程管理者的角度来处理互斥的问题 信号量就是OS提供的管理公有资源的有效手段1965年 由荷兰学者Dijkstra提出 他把互斥的关键概念抽象到信号量这个概念中 是一种卓有成效的进程同步机制 1 整型信号量机制2 记录型信号量机制3 信号量集机制 信号量是一个被保护的变量 并且只能通过初始化和两个标准的原子操作来访问 1 整型信号量机制 1 整型信号量是一个整数值 表示空闲资源总数 又称为 资源信号量 若为非负值表示当前的空闲资源数 为负值其绝对值表示当前等待临界区的进程数 初值应该大于零 两个原子操作即 P V操作 也常称为wait s singal s P V分别是荷兰语的test proberen 和increment verhogen 即 P s Wait s whiles 0 s s 1 V s Singal s s s 1 process1 beginrepeatP mutex critcialsection V mutex remaindersection untilfalse end 2 利用信号量实现互斥P56 利用信号量实现进程互斥 Varmutex semaphore 说明一个信号量process1 beginrepeatwait mutex criticalsection signal mutex remaindersection untilfalse end process2 beginrepeatwait mutex criticalsection signal mutex remaindersection untilfalse end 为临界资源设置一个互斥信号量mutex MUTualEXclusion 初值为1 在每个进程中将临界区代码置于wait mutex 和signal mutex 原语之间 注意 必须成对使用wait和signal原语wait signal原语不能出现次序错误 重复或遗漏遗漏wait原语则不能保证互斥访问遗漏signal原语则不能在使用临界资源之后将其释放 给其他等待的进程 3 利用信号量来描述前趋 合作 关系 前趋关系 并发执行的进程P1和P2中 分别有代码C1和C2 要求C1在C2开始前完成 C1 C2 为每个前趋关系设置一个互斥信号量S12 其初值为0 例 用信号量来描述如下的前趋图 beginS1 signal a signal b end beginwait a S2 signal c signal d end beginwait b S3 signal e end beginwait c S4 signal f end beginwait d S5 signal g end beginwait e wait f wait g S6 end Vara b c d e f g semaphore 0 0 0 0 0 0 0 0 ParbeginParend 实例1 如下两个并发执行的进程 是否能够正确运行 如果不能请举例说明 并改正之 ParbeginVarx integerProcessP1vary z integer Begin 1 x 1 2 y 0 3 ifx 1theny y 1 4 z y Endparend ProcessP2vart u integer Begin 5 x 0 6 t 0 7 ifx 1thent t 2 8 u t End 分析 顺序执行 y 1 z 1 t 2 u 2 并发执行 如果按照 1 5 2 3 4 6 7 8 的顺序执行 则结果为y 0 z 0 t 2 u 2 改正方法 找到临界区 设置信号量s 初值为1 实例2 假设在某单CPU系统中有两个合作进程P1 P2 他们的主要操作如下 P1 Calculating P2 Input Output 若要求的执行顺序为 Input Calculating Output 请用信号量上的P V操作实现P1和P2进程的协调执行 实例2 P1 Calculating P2 Input Output Calculating Input Output 画出该问题的前趋图 P1P2 引入进程阻塞机制 在信号量里增加对阻塞进程的记录 2 记录型信号量机制 P s s value s value 1 s value 0 本进程获得一个资源 临界区 资源访问区 本进程进入s list队列 进入阻塞状态 N Y V s s value s value 1 s value 0 将s list中第一个进程唤醒 N Y 记录型信号量的P V操作 wait s 和signal s Procedurewait s varS semaphore beginS value s value 1 ifS value 0thenblock S L end Proceduresignal s VarS semaphore BeginS value S value 1 IfS value 0thenwakeup S L End 伪码描述 当s value初值为1时 转化为互斥信号量 3 信号量集 信号量集用于进程需要多个资源时的信号量操作 整型信号量机制和记录型信号量机制都是针对进程间要共享一个临界资源而言的 当一段处理代码需要同时获取两个或多个临界资源时 使用整型或记录型信号量 会产生各进程分别获得部分临界资源 然后等待其余的临界资源 各不相让 的问题 死锁 如 A B进程都要访问共享资源D E 1 AND型信号量集机制 将一段代码同时需要的多个临界资源 采用原子方式 要么全分配给它 要么一个都不分配 称为Swait SimultaneousWait 同样地 使用结束后一起释放 称为Ssignal 基本思想 Swait SimultaneousWait Swait S1 S2 Sn P原语 if S1 1andS2 1 Sn 1 满足资源要求时的处理 for i 1 i n i Si Sj 1 注 与wait的处理不同 这里是在确信可满足 资源要求时 才进行减1操作 else 某些资源不够时的处理 调用进程进入第一个小于1信号量的等待队列Sj queue 阻塞调用进程 Ssignal S1 S2 Sn for i 1 i n i Si 释放占用的资源 for eachprocessPwaitinginSi queue 检查每种资源的等待队列中的所有进程 从等待队列Si queue中取出进程P if 判断P是否通过Swait中的测试 注 与signal不同 需重新判断进程P进入就绪队列 break else 未通过检查 资源不够用 时的处理 进程P进入某等待队列 然后继续循环判断下一个进程 Ssignal SimultaneousSignal 2 一般 信号量集 机制 一次需要N个某类临界资源时 要进行N次wait操作 低效 一般 信号量集 的几种特定情况 Swait S d d 表示每次申请d个资源 当少于d个时 便不分配Swait S 1 1 表示互斥信号量 Swait S 1 0 作为一个可控开关 并不申请资源当S 1时 可以通过测试 允许多个进程进入某特定区 当S 0时 无法通过测试 禁止任何进程进入某特定区 一般信号量集的基本思想 在AND型信号量集的基础上进行扩充 扩充为进程需要申请多个资源 每个资源可能申请多个的情况 每个资源对应一个信号量Si 进程对资源i的需求值为di 每次申请或释放di个 Si Si di和Si Si di资源i的测试值为ti 当资源个数小于ti时 便不再分配 PV原子操作 Swait S1 t1 d1 Sn tn dn Ssignal S1 d1 Sn dn 多个进程共享一个临界资源 And型信号量集机制 同时需要多种资源且每种占用一个时的信号量操作 一般信号量集机制 同时需要多种资源 每种占用的数目不同 且可分配的资源还存在一个临界值时的处理 信号量 整型信号量机制记录型信号量机制信号量集机制 2 3 3经典进程同步问题P60 生产者 消费者问题 producer consumerproblem 问题描述 若干进程通过有限的共享缓冲区交换数据 其中 生产者 进程不断写入 而 消费者 进程不断读出 共享缓冲区共有N个 任何时刻只能有一个进程 可对共享缓冲区进行操作 消费者 生产者 共享缓冲区 放产品 取产品 一次只可放一个产品 生产者 消费者同步的关键问题 需要保证以下同步关系 1 多个进程互斥地访问公共缓冲区 2 不能向满的缓冲区中添加产品 3 不能从空的缓冲区中提取产品 互斥信号量mutex可用的空资源信号量empty可用的满资源信号量full full empty N 涉及两类进程 生产者进程和消费者进程 每个进程中各个wait操作的次序是重要的 先检查资源数目 再检查是否互斥 思考 否则会怎样 采用AND信号量集 Swait empty mutex Swait full mutex Ssignal mutex full Ssignal mutex empty Producer Consumer varmutex full empty semaphore 1 n 0 采用记录型信号量机制解决该同步问题 类C伪代码描述 semaphorefull 0 满缓冲区单元个数semaphoreempty n 空缓冲区单元个数semaphoremutex 1 互斥信号量 控制对临界资源的访问charbuffer n 说明其他类型变量intin 0 intout 0 charnextc nextp voidmain cobegin 进程并发执行producer consumer coend 类C伪代码描述 voidproducer 生产者进程 while 1 produceanitemnextp 生产一个数据wait empty 空缓冲区数量减1wait mutex 进入临界区buffer in nextp 将一个数据送入缓冲池in in 1 modn 修改in指针signal mutex 退出临界区signal full 满缓冲区数量增1 voidconsumer 消费者进程 while 1 wait full 满缓冲区数量减1wait mutex 进入临界区nextc buffer out 从缓冲区读出一个数据out out 1 modn 修改out指针signal mutex 退出临界区signal empty 空缓冲区数量增1consumetheiteminnextc 消费一个数据 2 读者 写者问题 readers writersproblem 问题描述 一个数据对象 数据文件或记录 可以被多个进程共享 其中有些进程要读 有些要写或修改 允许多个读者进程同时读一个共享对象 但不允许一个写者进程和其它读者或写者进程同时访问共享对象 该同步问题涉及两类进程 读者 reader 进程和写者 writer 进程 并且 这两个进程的同步问题就是指 保证 读 写 互斥 写 写 互斥 读 读 允许的问题 Wmutex 互斥信号量 表示 允许写 初值是1 A 采用记录型信号量机制 if Readcount 0 wait wmutex Readcount Readcount 1 Readcount Readcount 1 ifReadcount 0thensignal Wmutex Rmutex 互斥信号量 表示对Readcount的互斥操作 初值是1 公共变量Readcount表示 正在读 的进程数 初值是0 WriterSwait mx 1 1 L RN 0 Write Ssignal mx 1 ReaderSwait L 1 1 mx 1 0 Read Ssignal L 1 采用一般 信号量集 机制 增加一个限制条件 同时读的 读者 最多R个mx表示 允许写 初值是1L表示当前 允许读者数目 初值为RN B 采用一般信号量集机制 保证多个读 有人写时不能读 进入读的开关 有人读时不能写 进入写的开关 并与写互斥 3 哲学家进餐问题 thediningphilosophersproblem 由Dijkstra首先提出并解决 问题描述 5个哲学家围绕一张圆桌而坐 桌子上放着5支筷子 每两个哲学家之间放一支 哲学家的动作包括思考和进餐 进餐时需要同时拿起他左边和右边的两支筷子 思考时则同时将两支筷子放回原处 如何保证哲学家们的动作有序进行 如 不出现相邻者同时进餐的冲突情况 进餐 不能进餐 进餐 问题分析 临界资源 筷子为临界资源设置信号量 varchopstick array 0 4 ofsemaphore 初值均为1 则第i个哲学家的动作可描述为 wait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 think 死锁 不能进餐 不能进餐 不能进餐 不能进餐 不能进餐 可以保证不会有两个相邻的哲学家同时进餐 但会引起死锁 死锁问题的几种解决方法P62 1 最多只允许四个哲学家同时进餐 以保证至少一个哲学家能够进餐 最终释放出他所使用过的筷子 从而使得更多的哲学家进餐 2 仅当哲学家的左 右两只筷子均可用时 才允许他拿起筷子进餐 3 规定奇数号哲学家先拿他左边的筷子 然后再去拿他右边的筷子 而偶数号哲学家则相反 方法一 加一个资源信号量 Varchopstick array 0 4 ofsemaphore 1 1 1 1 1 Varcount semaphore 4 第i个哲学家的活动 repeatwa