操作系统第二章作业讲解

第二章第二章 习题讲解习题讲解 1 进程之间存在着哪几种制约关系 各是什么原因引起的 下列活动分别属于哪种制约关 进程之间存在着哪几种制约关系 各是什么原因引起的 下列活动分别属于哪种制约关 系 系 1 若干同学去图书馆借书 2 两队举行篮球比赛 3 流水线生产的各道工序 4 商品生产和社会消费 答 进程之间存在着直接制约与间接制约这两种制约关系 其中直接制约 同步 是由于 进程间的相互合作而引起的 而间接制约 互斥 则是由于进程间共享临界资源而引起的 1 若干同学去图书馆借书 是间接制约 其中书是临界资源 2 两队举行篮球比赛 是间接制约 其中蓝球是临界资源 3 流水线生产的各道工序 是直接制约 各道工序 间需要相互合作 每道工序的开始都依赖于前一道工序的完成 4 商品生产和社会消费 是直接制约 两者也需要相互合作 商品生产出来后才可以被消费 商品被消费后才需要 再生产 2 试写出相应的程序来描述下图所示的前趋图 试写出相应的程序来描述下图所示的前趋图 var a b c d e f semaphore 0 0 0 0 0 0 begin S1 signal a signal b signal c end begin wait a S2 end begin wait b S3 signal d end begin wait c S4 end begin wait d S5 signal e signal f end begin wait e S6 end begin wait f S7 end 3 已知一个求值公式 已知一个求值公式 A2 3B B 5A 若 若 A B 已赋值 试画出该公式求值过程的前趋已赋值 试画出该公式求值过程的前趋 图 并使用信号量描述这些前趋关系 图 并使用信号量描述这些前趋关系 答 根据求值公式 假设 S1 X1 A A S2 X2 3 B S3 X3 5 A S4 X4 X1 X2 S5 X5 B X3 S6 X6 X4 X5 var a b c d e semaphore 0 0 0 0 0 begin S1 signal a end begin S2 signal b end begin S3 signal c end begin wait a wait b S4 signal d end begin wait c S5 signal e end begin wait d wait e S6 end 4 桌上有一只能容纳一个水果的盘子 爸爸专向盘子中放苹果 桌上有一只能容纳一个水果的盘子 爸爸专向盘子中放苹果 apple 妈妈专向盘子中放 妈妈专向盘子中放 桔子桔子 orange 一个儿子专等吃盘子中的桔子 一个女儿专等吃盘子里的苹果 一个儿子专等吃盘子中的桔子 一个女儿专等吃盘子里的苹果 1 试用信 试用信 号量实现他们的同步关系 号量实现他们的同步关系 2 如果有两个家庭的爸爸 妈妈 儿子 女儿和二只盘子呢 如果有两个家庭的爸爸 妈妈 儿子 女儿和二只盘子呢 会需要专门的实现吗 会需要专门的实现吗 var empty apple orange semaphore 1 0 0 说明 empty 与 apple 表示盘子为空与盘子中放入了苹果 用于表示爸爸与女儿间的同步关 系 empty 与 orange 表示盘子为空与盘子中放入了桔子 用于表示妈妈与儿子间的同步关 系 答案 1 使用记录型信号量 father begin repeat producer an apple wait empty Put an apple to the dish signal apple Until false end daughter begin repeat wait apple Get an apple from dish signal empty Eat an apple Until false end mother begin repeat producer an orange wait empty Put an orange to the dish signal orange Until false end son begin repeat wait orange Get an orange from dish signal empty Eat an orange Until false end 2 使用记录型信号量 var mutex empty apple orange semaphore 1 2 0 0 dish array 0 1 of fruit in out integer 0 0 father begin repeat producer an apple wait empty wait mutex if dish in apple or dish in orange then in in 1 mod 2 disk in apple in in 1 mod 2 signal mutex signal apple Until false end daughter begin repeat wait apple wait mutex if dish out orange then out out 1 mod 2 get an apple from dish out out out 1 mod 2 signal mutex signal empty Eat an apple Until false End mother beginson begin repeat producer an orange wait empty wait mutex if dish in apple or dish in orange then in in 1 mod 2 disk in orange in in 1 mod 2 signal mutex signal orange Until false end repeat wait orange wait mutex if dish out apple then out out 1 mod 2 get an orange from dish out out out 1 mod 2 signal mutex signal empty Eat an apple Until false end 5 试用信号量实现课件 试用信号量实现课件 92 页 司机与售票员进程的同步关系页 司机与售票员进程的同步关系 var stop door semaphore 0 0 driver begin repeat drive a bus arrive at bus station signal stop rest wait door Until false end conductor begin repeat sell tickets wait stop Open the door Close the door signal door Until false end 6 试用信号量解决读者 试用信号量解决读者 写者问题 使得写者与读者优先级根据到达顺序确定 写者问题 使得写者与读者优先级根据到达顺序确定 1 典型错误代码讲解 不增加任何信号量 Var rmutex wmutex semaphore 1 1 Readcount integer 0 begin parbegin Reader begin repeat wait rmutex if Readcount 0 then wait wmutex Readcount Readcount 1 signal rmutex perform read operation wait rmutex Readcount Readcount 1 if Readcount 0 then signal wmutex signal rmutex until false end writer begin repeat if readcount 0 then wait rumtex wait wmutex perform write operation signal rmutex signal wmutex until false end parend end 到达序列 R1 R2 W1 R3 R4 W2 进程进程行为行为rmutex 1wmutex 1Readcount 0状态状态备注备注 R1到达rmutex 0 rmutex 1 wmutex 0Readcount 1执行 就绪第 1 位读者 R2到达rmutex 0 rmutex 1 Readcount 2执行 就绪 W1到达rmutex 0 阻塞 1 阻塞Readcount 0 R3到达阻塞 1阻塞rmutex 0 R4到达阻塞 2阻塞rmutex 0 W2到达阻塞 3阻塞rmutex 0 R1离开阻塞 4阻塞rmutex 0 R2离开阻塞 5阻塞rmutex 0 产生死锁 2 学习指导与题解上的解题思路 学习指导与题解上的解题思路 答 为使写者优先 可在原来的读优先算法基础上增加一个初值为 1 的信号量 S 使得当 至少有一个写者准备访问共享对象时 它可使后续的读者进程等待写完成 初值为 0 的整型变量 writecount 用来对写者进行计数 初值为 1 的互斥信号量 mutex 用来实现 多个写者对 writecount 的互斥访问 读者与写者进程算法描述如下 var S mutex rmutex wmutex semaphore 1 1 1 1 writecount readcount integer 0 0 reader begin repeat wait S wait rmutex if readcount 0 then wait wmutex readcount readcount 1 signal rmutex signal S perform read operation wait rmutex readcount readcount 1 if readcount 0 then signal wmutex signal rmutex until false end writer begin repeat wait mutex if writecount 0 then wait S writecount writecount 1 signal mutex wait wmutex perform write operation signal wmutex wait mutex writecount writecount 1 if writecount 0 then signal S signal mutex until false end 到达序列 R1 R2 W1 R3 R4 W2 进程进程行为行为S 1mutex 1rmutex 1wmutex 1writecount 0readcount 0 备注备注 R1到达S 0 S 1 rmutex 0 rmutex 1 wmutex 0readcount 1 第一个 读者 执行 就 绪 R2到达S 0 S 1 rmutex 0 rmutex 1 readcount 2 执行 就 绪 W1到达 S 0 mutex 0 mutex 1 阻塞 1 writecount 1 第一个 写者 R3到达阻塞 1 R4到达阻塞 2 W2到达mutex 0 mutex 1 阻塞 2 writecount 2 R1离开rmutex 0 rmutex 1 readcount 1 R2离开rmutex 0 rmutex 1 wmutex 1readcount 0 负责唤 醒 W1 W1被唤醒wmutex 0执行 就 绪 W1离开 mutex 0 mutex 1 wmutex 1 writecount 1 负责唤 醒 W2 3 改写上述代码 真正实现读写平等策略 改写上述代码 真正实现读写平等策略 var S rmutex wmutex semaphore 1 1 1 readcount integer 0 reader begin repeat wait S wait rmutex if readcount 0 then wait wmutex readcount readcount 1 signal rmutex signal S perform read operation wait rmutex readcount readcount 1 if readcount 0 then signal wmutex signal rmutex until false end writer begin repeat wait S wait wmutex perform write operation signal wmutex signal S until false end 到达序列 R1 R2 W1 R3 R4 W2 进程进程行为行为S 1rmutex 1wmutex 1readcount 备注备注 0 R1到达S 0 S 1 rmutex 0 rmutex 1 wmutex 0readcount 1 第一个读者 执行 就绪 R2到达S 0 S 1 rmutex 0 rmutex 1 readcount 2 执行 就绪 W1到达S 0 阻塞 1 第一个写者 R3到达阻塞 1 R4到达阻塞 2 W2到达阻塞 3 R1离开rmutex 0 rmutex 1 readcount 1 R2离开rmutex 0 rmutex 1 wmutex 1readcount 0 负责唤醒 W1 W1被唤醒wmutex 0执行 就绪 W1离开 S 1 wmutex 1负责唤醒 R3 7 试说明 试说明 PCB 的作用 为什么说的作用 为什么说 PCB 是进程存在的唯一标志 课本第是进程存在的唯一标志 课本第 7 题 题 答 进程控制块的作用 是使一个在多道程序环境下不能独立运行的程序 成为一个能独 立运行的基本单位 即一个能与其他进程并发执行的进程 在创建进程时 系统将为它配置一个 PCB 在进行进程调度时 系统将根据 PCB 中的 状态和优先级等信息来选择新进程 然后将老进程的现场信息保存到它的 PCB 中 再 根据新进程 PCB 中所保存的处理机状态信息来恢复运行的现场 执行中的进程 如果 需要访问文件或者需要与合作进程实现同步或通信 也都需要访问 PCB 当进程因某 种原因而暂停执行时 也必须将断点的现场信息保存到它的 PCB 中 当进程结束时 系统将回收它的 PCB 可见 在进程的整个生命周期中 系统总是通过其 PCB 对进程 进行控制和管理 亦即 系统是根据其 PCB 而不是任何别的什么而感知到进程的存在 所以说 PCB 是进程存在的唯一标志 8 同步机构应遵循哪些基本准则 为什么 课本第 同步机构应遵循哪些基本准则 为什么 课本第 18 题 题 答 空闲让进 忙则等待 有限等待 让权等待 这样才能保证多个进程对临界资源的互 斥访问 不会造成系统的混乱 程序执行结果的不确定性或死锁的产生 9 试从物理概念上说明记录型信号量 试从物理概念上说明记录型信号量 wait 和和 signal 课本第 课本第 19 题 题 答 一个信号量通常对应一类临界资源 在使用前 信号量必须经过定义并赋适当的初值 每次对它进行 wait 操作意味着申请一个单位的该资源 signal 操作操作意味着归还一 个单位的该类资源 当 S value 0 时 它的值表示系统中该类资源当前可用的数目 S value 0 时 表示该类资源已经分配完毕 其绝对值表示系统中因申请资源而阻塞 在 S L 队列上的进程数目 10 在生产者 在生产者 消费者问题中 如果缺少了消费者问题中 如果缺少了 signal full 或或 signal empty 对执行结果将会 对执行结果将会 有何影响 课本第有何影响 课本第 23 题 题 答 如果生产者进程中缺少了 signal full 生产者一开始是不断往缓冲池送消息 而消费 者一开始就因为 full 为 0 而处于阻塞状态 当所有缓冲区装满之后 由于 empty 由 n 减为 0 而消费者已经阻塞 生产者也会因为 wait empty 而处于阻塞状态 产生死锁 消费者进程中缺少了 signal empty 缓冲区指针 in 从 0 指向了 n 1 后 生产者就会因 为执行 wait empty 处于阻塞状态 生产者阻塞后 消费者消费掉所有的产品 即缓冲 区指针 out 从 0 指向了 n 1 后 也会因为执行 wait full 处于阻塞状态 产生死锁 11 我们为某临界资源设置一把锁 我们为某临界资源设置一把锁 W 当 当 W 1 时表示关锁 当时表示关锁 当 W 0 时表示锁已经打开 时表示锁已经打开 试写出开锁和关锁原语 并利用它们去实现互斥 试写出开锁和关锁原语 并利用它们去实现互斥 课本第 课本第 25 题 题 答 相应的关锁原语 lock W 和开锁原语 unlock W 可描述如下 lock W while W 1 do no op W 1 unlock W W 0 在利用关锁原语和开锁原语实现进程互斥时 可将临界区 CS 放在其间 即 lock W CS unlock W 12 当前有哪几种高级通信机制 课本第 当前有哪几种高级通信机