《操作系统》习题集参考答案：第2章 进程与线程

1、操作系统习题集参考答案 第 2 章 进程与线程 第 1 页 共 12 页 北理珠“操作系统”课题组 2012-10 第第2章章 进程与线程进程与线程-习题集习题集参考参考答案答案 一、一、 选择题选择题 1. A 2. C 3. C 4. A 5. B 6. C 7. B 8. C 9. A 10. C 11. A /已经在就绪队列中的进程不方便改变优先级 12. B 13. C /“作业调度”将作业由“后备”“执行”时创建进程。（另见“选择题 13”） 14. C /“用户登录成功”需要创建进程来解释用户的各种命令；“设备分配”由内核 完成，不需要创建新进程 （对应的设备驱动程序进程一般处于

2、阻塞状态中） ；“启动程 序执行”需创建一个新进程来执行程序。 15. B 16. D /D 可能更有准确。A 也有道理？ 17. B /线程是进程内一个相对独立的执行单元，但并不能单独执行，只能在进程中运 行。线程的引入减少了程序执行的时空开销。一个进程可包含一个或多个线程 18. D 操作系统习题集参考答案 第 2 章 进程与线程 第 2 页 共 12 页 北理珠“操作系统”课题组 2012-10 19. A 20. D 21. B 22. C /系统采用短作业优先算法调度时，执行顺序为J1、J2和J3。J1等待时间为0，执 行时间为 T1；J2 等待时间为 T1，执行时间为 T2；J3

3、等待时间为 T1+T2，执行时间为 T3，则平均周转时间（T1+T1+T2+T1+T2+T3）/3，答案选择为 C。 23. B 24. C /“高响应比优先”即照顾到“短的作业”也关注“等待时间”，当“长作业” 等的时间足够长时也会获得调度机会。 25. B 26. D 27. B 28. C 29. C / 一个正在访问临界资源的进程由于申请 I/O 操作而被阻塞时，可以运行其他进 程抢占处理机继续执行，但不允许其他进程进入临界区。 30. D /算法中利用 flag解决临界资源的互斥访问，利用 turn 解决“饥饿“现象，所以 能保证进程互斥进入临界区，不会出现“饥饿”现象。 31. B

4、 32. A 33. A 34. B 35. B /？。 （引自 AST P74）互斥量是一个处于两态之一的变量：解锁和加锁。0 表示解 锁，而其他所有的值表示加锁。据此，mutex=0 则是解锁， （A）表示没有进程进入临界 区。 36. A 37. C 操作系统习题集参考答案 第 2 章 进程与线程 第 3 页 共 12 页 北理珠“操作系统”课题组 2012-10 38. B 39. D 40. B 41. C /（本注）P1 和 P2 会交替执行。 /-(laod R1，x；inc R1) -(Load R2，x；dec R2) -(store x，R1) -(store x，R2)

5、/总共有 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 二、二、 综合应用题综合应用题 1. 1) 进程的概念是操作系统中最基本的概念。 为了描述系统内部出现的情况、 系统内部 各作业的活动规律而引进的一个新的概念， 由于处于这样一个多道程序系统所带来 的更为复杂的环境中，程序具有了并发、制约、动态的特征，使得原来的程序概念 已难以刻画和反映系统中的情

6、况了。 （本注：程序执行的并发性或多道程序设计的 需要而引入对正在运行的程序的一个抽象。 ） 2) 进程的基本特点：动态性、并发性、独立性和异步性（通常指这 4 个基本特点，也 可以包含进程的结构性） 。 3) 进程与程序 联系：进程是程序的一次执行过程，程序是进程的基础。 区别： 1) 进程是动态的，程序是静态的。 （程序是一组指令的有序集合） 2) 进程有生命期。 （进程有生有死，程序的存在是永久的） 3) 进程包括：程序、数据和记录进程状态信息的 PCB 组成。 4) 进程是竞争计算机系统有限资源的基本单位。 5) 进程是并发的。 6) 二者不是一一对应的。 （一个程序可能对应多个进程，

7、一个进程可以包含 多个程序。 ） 2. 第 1)种情况不可能发生。 3. 1) 先来先服务非抢占式调度算法 平均周转时间=（2+6+13+15）/4=9 操作系统习题集参考答案 第 2 章 进程与线程 第 4 页 共 12 页 北理珠“操作系统”课题组 2012-10 作业号作业号 到达时到达时 刻刻 所需运行时间所需运行时间 优先优先数数 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 1 0 2 4 0 2 2 2 1 5 9 2 7 6 3 2 8 1 7 15 13 4 3 3 8 15 18 15 2) 短作业优先调度算法。 平均周转时间=(2+6+16+7)/4=7.7

8、5 作业号作业号 到达时到达时 刻刻 所需运行时间所需运行时间 优先数优先数 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 1 0 2 4 0 2 2 2 1 5 9 2 7 6 3 2 8 1 10 18 16 4 3 3 8 7 10 7 3) 静态优先级调度算法 平均周转时间=(2+17+8+10)/4=9.25 作业号作业号 到达时到达时 刻刻 所需运行时间所需运行时间 优先数优先数 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 1 0 2 4 0 2 2 2 1 5 9 13 18 17 3 2 8 1 2 10 8 4 3 3 8 10 13 10 4.

9、 1) 先来先服务调度算法 进程进程 就绪时就绪时 刻刻 服务时间服务时间 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 带权周转时间带权周转时间 P1 0 3 0 3 3 3/3=1 P2 2 6 3 9 7 7/6=1.17 P3 4 4 9 13 9 9/4=2.25 P4 6 5 13 18 12 12/5=2.4 P5 8 2 18 20 12 12/2=6 平均 8.6 2.56 2) 短作业优先调度算法 进程进程 就绪时就绪时 刻刻 服务时间服务时间 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 带权周转时间带权周转时间 P1 0 3 0 3 3 3/

10、3=1 P2 2 6 3 9 7 7/6=1.17 P3 4 4 11 15 11 11/4=2.75 P4 6 5 15 20 14 14/5=2.8 P5 8 2 9 11 3 3/2=1.5 操作系统习题集参考答案 第 2 章 进程与线程 第 5 页 共 12 页 北理珠“操作系统”课题组 2012-10 平均 7.6 1.84 3) 高响应比优先 进程进程 就绪时就绪时 刻刻 服务时间服务时间 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 带权周转时间带权周转时间 P1 0 3 0 3 3 3/3=1.0 P2 2 6 3 9 7 7/6=1.17 P3 4 4 9 13

11、 9 9/4=2.25 P4 6 5 15 20 14 14/5=2.8 P5 8 2 13 15 7 7/2=3.5 平均 8.0 2.14 时刻时刻 9:9: P3:响应比 (9-4)/4=5/4 P4:响应比 (9-6)/5=3/5 P5:响应比 (9-8)/2=1/2 选择:P3 时刻时刻 1313： P4:响应比 (13-6)/5=7/5 P5:响应比 (13-8)/2=5/2 选择：P5 4) 时间片轮转（时间片=1）调度算法 0 P1 P2 P3 P4 P5 1234567891011121314151617181920 P1P1 P1 P2 P1 P2 P1 P2 P3 P2

12、P3 P2 P3 P2 P3 P4 P2 P3 P4 P2 P3 P4 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P5 P2 P3 P4 P2 P3 P4 P2 P3 P4 P2 P3 P4 P2 P4 P2 P4 P4 P4 就绪 队列 进程进程 就绪时就绪时 刻刻 服务时间服务时间 开始时开始时 刻刻 结束时结束时 刻刻 周转时周转时 间间 带权周转时间

13、带权周转时间 P1 0 3 0 4 4 4/3=1.33 P2 2 6 2 18 16 16/6=2.67 P3 4 4 5 17 13 13/4=3.25 P4 6 5 7 20 14 14/5=2.8 P5 8 2 10 15 7 7/2=3.5 平均 10.8 2.71 操作系统习题集参考答案 第 2 章 进程与线程 第 6 页 共 12 页 北理珠“操作系统”课题组 2012-10 5. 方法一：图形描述 1 送产品到缓冲区 2 V(S1) 3 P(S2) 1 P(S1) 2 从缓冲区取产品 3 V(S2) 生产者消费者 信号量初值： Vs1=0 Vs2=0 方法二：程序描述 Sema

14、phore Vs1=0; Semaphore Vs2=0; Main() Cobegin producer /生产者进程 while(true) 送产品到缓冲区； V（Vs1）; /允许取产品 P（Vs2） ； /阻止送产品 consumer /消费者进程 while(true) P（Vs1） ； /阻止取产品 从缓冲区取产品； V（Vs2） ； /允许送产品 coend 6. semaphore empty=n; /初始时空的缓冲区单元个数 semaphore full=0; /初始时满的缓冲区个数 semaphore mutex=1; /控制对临界区访问的互斥信号量 main() cobe

15、gin 操作系统习题集参考答案 第 2 章 进程与线程 第 7 页 共 12 页 北理珠“操作系统”课题组 2012-10 procdure /生产者进程 while(true) P(empty); /递减一个空缓冲区单元 P(mutex); /互斥访问缓冲区 送一个产品到缓冲区； V(mutex); /允许访问缓冲区 V(full); /递增一个满缓冲区单元 consumer while(ture) /消费者进程 P(full); /递减一个满缓冲区 P(mutex); /互斥访问临界区 从缓冲区取一个产品； V(mutex); /允许访问缓冲区 V(empty); /递增一个空缓冲区单元

16、coend 7. semaphore Sa=1; semaphore Sb=0; main() cobegin 进程 Ai（i=1,n） while(true) P(Sa); /互斥 A 发消息 向缓冲区发送消息； V(Sb); /允许 B 取消息 进程 B while(true) P(Sb); /互斥 B 取消息 从缓冲区取消息； V(Sa); /允许 A 发消息 coend 8. （本注：假设先拣白子。 ） 操作系统习题集参考答案 第 2 章 进程与线程 第 8 页 共 12 页 北理珠“操作系统”课题组 2012-10 进程进程P1 P（S1） 拣一白子 V（S2） 进程进程P2 P（s

17、2) 拣一黑子 V（S1） S1=1 S2=0 semaphore S1=1; semaphore S2=0; main() cobegin 进程 P1 while(true) P(S1); /互斥拣白子 拣一白子； V(S2); /允许拣黑子 进程 P2 while(true) P(S2); /互斥拣黑子 拣一黑子; V(S1); /允许拣白子 coend 9. semaphore mutex=1; /缓冲区操作互斥信号量 semaphore odd=0,even=0; /奇数、偶数进程的同步信号量 semaphore empty=N; /空缓冲区单元个数信号量 main() 操作系统习题集

18、参考答案 第 2 章 进程与线程 第 9 页 共 12 页 北理珠“操作系统”课题组 2012-10 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(empt

19、y); /递增空缓冲区的单元个数 countodd(); 进程 P3 while(true) P(even); /互斥取偶数 P(mutex); /互斥访问缓冲区 geteven(); V(mutex); /恢复访问缓冲区 V(empty); /递增空缓冲区的单元个数 counteven(); coend 10. semaphore mutex=1; /互斥使用取号机信号量 semaphore empty=10; /空座位的数量信号量 semaphore full=0; /已占座位的数量信号量 semaphore service=0; /等待叫号信号量 cobegin process 顾客 i

20、 操作系统习题集参考答案 第 2 章 进程与线程 第 10 页 共 12 页 北理珠“操作系统”课题组 2012-10 P(empty); P(mutex); 从取号机获得一个号； V(mutex); V(full); P(service); /等待叫号 process 营业员 while(TRUE) P(full); V(empty); V(service); /叫号 为顾客服务； 11. 本题基于读者-写者问题算法（写进程优先） 。设置两个变量：eastn 记录从东端上桥到 西端的车辆数，westn 记录从西端上桥到东端的车辆数，它们的初值均为 0。这两个变 量都是互斥访问的，为此设置两个

21、互斥访问的信号量 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,) /东

22、端车辆过桥进程 while(true) 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) /若东端没车辆车辆过桥，则允许西端车辆过桥 操作系

23、统习题集参考答案 第 2 章 进程与线程 第 11 页 共 12 页 北理珠“操作系统”课题组 2012-10 V(mwest); V(meast); /恢复访问 eastn 变量 进程 westj(j=1,2,) /西端车辆过桥进程 while(true) P(wait); /西端车辆谁先请求，则谁先过桥 P(meast); /互斥访问 eastn 变量（本注：互斥保护下列代 码段） if(eastn=0) /若是西端第一辆车过桥，则禁止东端车辆过桥 P(mwest); westn+; /西端过桥车辆数量增 1 V(mwest); /恢复访问 wastn 变量 V(wait); /恢复车辆过

24、桥 从西端向东端过桥； P（mwest）; /互斥访问 wastn 变量（本注：互斥保护下列代 码段 westn-; /东端过桥车辆数量减 1 if(westn=0) /若东端没车辆车辆过桥，则允许西端车辆过桥 V(meest); V(mwast); /恢复访问 eastn 变量 coend 12. 本题等同于理发师睡觉问题。 其操作员和顾客的工作流程如下图所示 （图中虚框是另设 的） 。 如果等待的人数=6，则离开 等待人数增1（waiting+) 找一个空椅子坐下 顾客站起来（释放空椅子） V(ready) 复印 P(ready) 离开复印室 V(finish) P(finish) 等待人

25、数减(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

26、(ready);/有顾客准备好了 复印； V(finish);/允许其他顾客理发 void customer()/顾客进程 P(mutex);/互斥waiting变量的操作 if(waiting6) 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变量的操作 操作系统习题集参考答案 第 2 章 进程与线程 第 12 页 共 12 页 北理珠“操作系统”课题组 2012-10 13. If each job has 50% I/O wait，then it will take 20 minutes to complete in the absence of compe