《操作系统》习题集参考答案：第2部分 进程管理(2-通信)(知识域编号).pdf

操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 1 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 第第2部分部分 进程进程管理 管理 2 通信 通信 习题集习题集参考参考答案答案 一 一 选择题选择题 1 C 2 C 一个正在访问临界资源的进程由于申请 I O 操作而被阻塞时 可以运行其他进 程抢占处理机继续执行 但不允许其他进程进入临界区 3 D 算法中利用 flag 解决临界资源的互斥访问 利用 turn 解决 饥饿 现象 所以 能保证进程互斥进入临界区 不会出现 饥饿 现象 本注 参考 ASP P69 Peterson 解法 4 B 5 A 6 A 7 B 8 B 引自 AST P74 互斥量是一个处于两态之一的变量 解锁和加锁 0 表示解 锁 而其他所有的值表示加锁 据此 mutex 0 则是解锁 A 表示没有进程进入临界 区 9 A 10 C 11 B 本注 引自 AST P74 互斥量是一个处于两态之一的变量 解锁和加锁 0 表示解锁 而其他所有的值表示加锁 据此 mutex 0 则是解锁 A 表示没有进程进 入临界区 该题中 mutex 相当于 P V 操作中的 信号量 并非是实际上是互斥量 12 D 本注 引自 AST P74 互斥量是一个处于两态之一的变量 解锁和加锁 0 表示解锁 而其他所有的值表示加锁 据此 mutex 0 则是解锁 A 表示没有进程进 入临界区 该题中 mutex 相当于 P V 操作中的 信号量 并非是实际上是互斥量 13 B 14 C 本注 P1 和 P2 会交替执行 laod R1 x inc R1 Load R2 x dec R2 store x R1 store x R2 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 2 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 总共有 6 种执行顺序 第一位有 2 选择 第二位有 2 选择 1 x 结果为 1 2 x 结果为 0 3 x 结果为 2 4 x 结果为 1 5 x 结果为 0 6 x 结果为 2 另外思路 x 只会 减 1 所以不可能 1 x 只会 加 1 所以不可能 3 15 A 二 二 综合应用题综合应用题 1 方法一 图形描述 1 送产品到缓冲区 2 V S1 3 P S2 1 P S1 2 从缓冲区取产品 3 V S2 生产者消费者 信号量初值 Vs1 0 Vs2 0 方法二 程序描述 Semaphore Vs1 0 Semaphore Vs2 0 Main Cobegin producer 生产者进程 while true 送产品到缓冲区 V Vs1 允许取产品 P Vs2 阻止送产品 consumer 消费者进程 while true 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 3 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 P Vs1 阻止取产品 从缓冲区取产品 V Vs2 允许送产品 coend 2 semaphore empty n 初始时空的缓冲区单元个数 semaphore full 0 初始时满的缓冲区个数 semaphore mutex 1 控制对临界区访问的互斥信号量 main cobegin procdure 生产者进程 while true P empty 递减一个空缓冲区单元 P mutex 互斥访问缓冲区 送一个产品到缓冲区 V mutex 允许访问缓冲区 V full 递增一个满缓冲区单元 consumer while ture 消费者进程 P full 递减一个满缓冲区 P mutex 互斥访问临界区 从缓冲区取一个产品 V mutex 允许访问缓冲区 V empty 递增一个空缓冲区单元 coend 3 semaphore Sa 1 semaphore Sb 0 main cobegin 进程 Ai i 1 n while true P Sa 互斥 A 发消息 向缓冲区发送消息 V Sb 允许 B 取消息 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 4 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 进程 B while true P Sb 互斥 B 取消息 从缓冲区取消息 V Sa 允许 A 发消息 coend 4 本注 假设先拣白子 进程进程P1 P S1 拣一白子 V S2 进程进程P2 P s2 拣一黑子 V S1 S1 1 S2 0 semaphore S1 1 semaphore S2 0 main cobegin 进程 P1 while true P S1 互斥拣白子 拣一白子 V S2 允许拣黑子 进程 P2 while true 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 5 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 P S2 互斥拣黑子 拣一黑子 V S1 允许拣白子 coend 5 semaphore mutex 1 缓冲区操作互斥信号量 semaphore odd 0 even 0 奇数 偶数进程的同步信号量 semaphore empty N 空缓冲区单元个数信号量 main cobegin 进程 P1 while true number produce P empty 递减空缓冲区的单元个数 P mutex 互斥访问缓冲区 put V mutex 恢复访问缓冲区 if number 2 0 V even 允许取偶数 else V odd 允许取奇数 进程 P2 while true P odd 互斥奇数 P mutex 互斥访问缓冲区 getodd V mutex 恢复访问缓冲区 V empty 递增空缓冲区的单元个数 countodd 进程 P3 while true P even 互斥取偶数 P mutex 互斥访问缓冲区 geteven V mutex 恢复访问缓冲区 V empty 递增空缓冲区的单元个数 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 6 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 counteven coend 6 semaphore mutex 1 互斥使用取号机信号量 semaphore empty 10 空座位的数量信号量 semaphore full 0 已占座位的数量信号量 semaphore service 0 等待叫号信号量 cobegin process 顾客 i P empty P mutex 从取号机获得一个号 V mutex V full P service 等待叫号 process 营业员 while TRUE P full V empty V service 叫号 为顾客服务 7 本题基于读者 写者问题算法 写进程优先 设置两个变量 eastn 记录从东端上桥到 西端的车辆数 westn 记录从西端上桥到东端的车辆数 它们的初值均为 0 这两个变 量都是互斥访问的 为此设置两个互斥访问的信号量 meast 和 mwest 它们的初值均为 1 对于从东端过桥和从西端过桥的车辆而言 桥上没有车辆时 谁先请求谁先过桥 所以再设置一个互斥访问信号量 wait 其初值为 1 用 P V 操作来实现东西两端车辆 过桥问题的描述如下 int eastn 0 记录从东端上桥到西端的车辆数 int westn 0 记录从西端上桥到东端的车辆数 semaphore meast 1 保护 eastn 变量 的操作 的信号量 semaphore mwest 1 保护 wastn 变量 的操作 的信号量 main cobegin 进程 easti i 1 2 东端车辆过桥进程 while true 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 7 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 P wait 东端车辆谁先请求 则谁先过桥 P meast 互斥访问 eastn 变量 本注 互斥保护下列代 码段 if eastn 0 若是东端第一辆车过桥 则禁止西端车辆过桥 P mwest eastn 东端过桥车辆数量增 1 V meast 恢复访问 eastn 变量 V wait 恢复车辆过桥 从东端向西端过桥 P meast 互斥访问 eastn 变量 本注 互斥保护下列代 码段 eastn 东端过桥车辆数量减 1 if eastn 0 若东端没车辆车辆过桥 则允许西端车辆过桥 V mwest V meast 恢复访问 eastn 变量 进程 westj j 1 2 西端车辆过桥进程 while true P wait 西端车辆谁先请求 则谁先过桥 P meast 互斥访问 eastn 变量 本注 互斥保护下列代 码段 if westn 0 若是西端第一辆车过桥 则禁止东端车辆过桥 P meast westn 西端过桥车辆数量增 1 V mwest 恢复访问 wastn 变量 V wait 恢复车辆过桥 从西端向东端过桥 P mwest 互斥访问 wastn 变量 本注 互斥保护下列代 码段 westn 东端过桥车辆数量减 1 if westn 0 若东端没车辆车辆过桥 则允许西端车辆过桥 V meast V mwest 恢复访问 eastn 变量 coend 8 本题等同于理发师睡觉问题 其操作员和顾客的工作流程如下图所示 图中虚框是另设 的 操作系统 习题集参考答案 第2部分 进程管理 2 通信 第 8 页 共 8 页 北理珠 操作系统 课题组 201210 201507 201510 如果等待的人数 6 则离开 等待人数增1 waiting 找一个空椅子坐下 顾客站起来 释放空椅子 V ready 复印 P ready 离开复印室 V finish P finish 等待人数减 waiting 操作员操作员 顾客顾客int waiting 0 等待的顾客 含正在复印的人数 最多不超过6人 semaphore mutex 1 用于waiting变量的互斥操作 semaphore standup 1 顾客站起来准备复印的人数 semaphore wchair 5 空椅子的个数 semaphore ready 0 是否有顾客准备好 semaphore finish 0 操作员是否完成复印 main cobegin operator customer coend void operator 操作员进程 while true P ready 有顾客准备好了 复印 V finish 允许其他顾客理发 void customer 顾客进程 P mutex 互斥waiting变量的操作 if waiting 6 waiting waiting 1 等待顾客数增1 V mutex 允许waiting变量的操作 else V mutex 允许waiting变量的操作 离开 P wchair 找一个空椅子坐下 P standup 再站起来准备复印 V wchair 允许其它人坐空椅子 V ready 该顾客准备好了 P finish 等待操作员完成 V standup 离开复印室 P mutex 互斥waiting变量的操作 waiting waiting 1 等待顾客数减1 V mutex 允许waiting变量的操作 9 原答案 The employees communicate by passing messages