操作系统复习资料全第二章进程管理-经典同步问题.ppt

复习 为什么需要进程同步 哪些进程需要同步 进程同步的两种解决方法什么是临界资源和临界区 信号量的物理意义 信号量有哪些应用 并发进程的同步问题 包括资源共享和进程之间的合作 是多道环境下操作系统必须解决重要问题 否则 将会造成计算错误 资源不能共享 系统混乱等严重错误发生 本节将研究几个典型的进程同步问题 2 4经典进程的同步问题 进程同步机制应遵循的准则 掌握 空闲让进忙则等待有限等待让权等待 几种不同类型的信号量 1 整型信号量 最早期的信号量实现 定义一个整型变量S 当S 0时 表示某类可用资源数目 即表示还有S个资源空闲可供共享使用 当S 0时 其绝对值表示信号量S所代表资源的阻塞队列中的进程数 即系统中因请求该类资源而被阻塞的进程数目 信号量S的值除初始化 为资源数目 外 其值只能通过原语wait和signal 也称P V操作来改变 整型信号量的P V操作描述 wait和signal操作原语为 wait S whileS 0dono op S S 1 signal S S S 1 解释 P或wait操作 当S 0时 说明无资源可用 一直测试直到其他进程释放该类资源 V或signal操作 使用完资源时释放该资源 简单地将资源数目加一即可 并不需要唤醒等待该资源的进程 为什么 2 记录型信号量 整型信号量机制中的wait操作 只要信号量S 0 就会不断地测试 系统处于空转状态 因此 该机制并未遵循 让权等待 的准则 而是使进程处于 忙等 的状态 记录型信号量机制 采用 让权等待 策略 必然出现多个进程等待访问同一临界资源的情况 为此 信号量设置除需要一个用于代表资源数目的整型变量value外 还应增加一个进程链表L 用于链接等待资源的进程队列 2 记录型信号量的定义 typesemaphore record value integer L listofprocess end 相应地 wait S 操作可描述为 procedurewait S varS semaphore begin S value S value 1 ifS value 0thenblock S L end 2 记录型信号量的定义 signal S 操作可描述为proceduresignal S varS semaphore begin S value S value 1 ifS value 0thenwakeup S L end 3 AND型信号量 假若并发进程A和B都要访问两个数据D和E 因共享数据为临界资源 为D和E设置用于互斥的信号量分别为Dmutex和Emutex 且初始值为1 则进程A和B共享临界数据D和E必须进行同步操作 processA processB wait Dmutex wait Emutex wait Emutex wait Dmutex 若进程A和B按下述次序交替执行wait操作 processA wait Dmutex 于是Dmutex 0 processB wait Emutex 于是Emutex 0 processA wait Emutex 于是Emutex 1A阻塞 processB wait Dmutex 于是Dmutex 1B阻塞形成死锁 AND同步机制的基本思想是 将进程在整个运行过程中需要的所有资源 一次性全部分配给进程 待进程使用完后再一起释放 只要尚有一个资源未能分配给进程 其它所有可能为之分配的资源 也不分配给他 为实现这种机制 在wait操作中增加了一个 AND 条件 故称为AND同步 或称为同时wait操作 即Swait Simultaneouswait 定义如下 Swait S1 S2 Sn ifSi 1and andSn 1then fori 1tondo Si Si 1 endfor else placetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi 1 andsettheprogramcountofthisprocesstothebeginningofSwaitoperation endif Ssignal S1 S2 Sn fori 1tondo Si Si 1 RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue endfor 4 信号量集 自学 之前的信号量机制在分配资源时一次只能分配一个单位的资源 当进程对某类资源的需求量不是1个 而是N个时 就需要执行N次P操作 V操作也是一样 效率较低 为此 引入信号量集 信号量集定义如下 Swait S1 t1 d1 Sn tn dn S为信号量 t为下限 d为需求量ifSi t1and andSn tnthen fori 1tondo Si Si di endfor else PlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi tiandsetitsprogramcountertothebeginningoftheSwaitOperation endif signal S1 d1 Sn dn fori 1tondo Si Si di RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue endfor 信号量集的几种特殊情况 1 Swait S d d 此时在信号量集中只有一个信号量S 但允许它每次申请d个资源 当现有资源数少于d时 不予分配 2 Swait S 1 1 此时的信号量集已蜕化为一般的记录型信号量 S 1时 或互斥信号量 S 1时 3 Swait S 1 0 这是一种很特殊且很有用的信号量操作 当S 1时 允许多个进程进入某特定区 当S变为0后 将阻止任何进程进入特定区 换言之 它相当于一个可控开关 2 4 1生产者 消费者问题 一组生产者生产产品 一组消费者取走产品 1 n 3 n 1 2 公用缓冲池 共有n个缓冲区 in out Varmutex empty full semaphore 1 n 0 buffer array 0 n 1 ofitem in out integer 0 0 空 满缓冲区队列起始位置begin parbegin proceducer begin repeat produceranitemnextp nextp为临时缓冲区 buffer in nextp in in 1 modn untilfalse end consumer begin repeat wait full wait mutex nextc buffer out 临时消费缓冲区out out 1 modn signal mutex signal empty consumertheiteminnextc untilfalse end parend end每次都是两个wait和两个signal操作 因此可以改造成AND型信号量 2 利用AND信号量解决生产者 消费者问题 varmutex empty full semaphore 1 n 0 buffer array 0 n 1 ofitem inout integer 0 0 begin parbegin producer begin repeat produceaniteminnextp Swait empty mutex buffer in nextp in in 1 modn Ssignal mutex full untilfalse end consumer begin repeat Swait full mutex nextc buffer out out out 1 modn Ssignal mutex empty consumertheiteminnextc untilfalse end parend end 2 4 2哲学家进餐问题 利用记录型信号量解决哲学家进餐问题 问题 5位哲学家进餐共用一张圆桌 分别坐在周围的5把椅子上 每座位前依次前摆放一个碗一个筷子 即桌上共5个碗和5只筷子 哲学家生活方式是交替思考和进餐 经分析可知 放在桌子上的筷子是临界资源 在一段时间内只允许一位哲学家使用 为了实现对筷子的互斥使用 可以用一个信号量表示一只筷子 由这五个信号量构成信号量数组 其描述如下 第i位哲学家的活动可描述为 Varchopstick array 0 4 ofsemaphore 1 1 1 1 1 repeat wait chopstick i wait chopstick i 1 mod5 eat signal chopstick i signal chopstick i 1 mod5 think untilfalse 问题 上述算法有可能引起死锁 为什么 如何解决 可采取以下几种解决方法 至多只允许有四位哲学家同时去拿左边的筷子 最终能保证至少有一位哲学家能够进餐 增加一个总资源信号量S 4 仅当哲学家的左 右两只筷子均可用时 才允许他拿起筷子进餐 AND型信号量 规定奇数号哲学家先拿他左边的筷子 然后再去拿右边的筷子 而偶数号哲学家则相反 按此规定 将是1 2号哲学家竞争1号筷子 3 4号哲学家竞争3号筷子 即五位哲学家都先竞争奇数号筷子 获得后 再去竞争偶数号筷子 最后总会有一位哲学家能获得两只筷子而进餐 2 利用AND信号量机制解决哲学家进餐问题 在哲学家进餐问题中 要求每个哲学家先获得两个临界资源 筷子 后方能进餐 这在本质上就是前面所介绍的AND同步问题 故用AND信号量机制可获得最简洁的解法 Varchopsiickarray 0 4 ofsemaphore 1 1 1 1 1 processi repeat think Sswait chopstick i 1 mod5 chopstick i eat Ssignat chopstick i 1 mod5 chopstick i untilfalse 另外两种方法 自己试着写代码实现 2 4 3读者 写者问题 自学 学期结束再讲 读者 写者问题 有多个并发执行的进程对一个数据文件或一个记录或一个变量进行共享 要求在同一时间段可由多个读者进程共享文件 而写者进程与读者进程 写者进程与写者进程只能互斥共享文件 这就是读者 写者进程同步问题 如何解决 2 4 3读者 写者问题 1 利用记录型信号量解决读者 写者问题 为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex 设置一个整型变量Readcount表示正在读的进程数目 当Readcount 0时 表示尚无Reader进程在读时 Reader进程才需要执行Wait Wmutex 操作 若wait Wmutex 操作成功 做Readcount 1和读文件操作 当Reader进程在执行了Readcount减1操作后其值为0时 才须执行signal Wmutex 操作 以便让Writer进程写 又因为Readcount是一个可被多个Reader进程访问的临界资源 因此 应该为它设置一个互斥信号量rmutex 读者 写者问题可描述如下 Varrmutex wmutex semaphore 1 1 Readcount integer 0 begin parbegin Reader begin repeat wait rmutex 对Readcount互斥访问 ifreadcount 0thenwait wmutex 第一个进入读访问的进程关闭写进程进入Readcount Readcount 1 signal rmutex performreadoperation wait rmutex 要对readcount资源互斥访问readcount readcount 1 ifreadcount 0thensignal wmutex signal rmutex untilfalse end writer begin repeat wait wmutex performwriteoperation signal wmutex untilfalse end parend end 2 利用信号量集机制解决读者 写者问题 VarRNinteger 最多允许RN读者进程共享文件L mx semaphore RN 1 L读者数控制信号量 mx写互斥信号量begin parbegin reader begin repeat Swait L 1 1 读进程检查L 1 才可进入临界区 Swait mx 1 0 如果无写进程进入临界区 mx 1 performreadoperation Ssignal L 1 untilfalse end writer begin repeat Swait mx 1 1 L RN 0 既无写者进程在写 又无读者进程在读时 才允许写进程进入临界区performwriteoperation Ssignal mx 1 untilfalse end parend end 练习题 三个进程P1 P2 P3互斥使用一个包含N N 0 个单元的缓冲区 P1每次用put 将一个正整数送入缓冲区的一个单元中 P2每次用getodd 从缓冲区中取出一个奇数 P3每次用geteven 从缓冲区中取出一个偶数 试用信号量机制实现这三个进程的互斥与同步活动 用伪代码实现 Semaphoreempty N mutex 1 s1 s2 0 p1 p empty p mutex put if 是奇数 thenv s1 elsev s2 v mutex p2 p s1 p mutex getodd v mutex v empty p3 p s2 p mutex geteven v mutex v empty