复习题_问答题部分New (2).doc

1、第二章1、已知一个求值公式(3A+2B)/(A+5B 2+C)，若 A、B、C 已赋值，试画出该公式求值过程的前趋图。 解：令 S1： X1 = 3A;S2： X2 = 2B;S3： X3 = X1+X2;S4： X4 = 5B2;S5： X5 = A+X4+C;S6： X6 = X3/X5则求值过程的前趋图为： S 1 S 2S 3S 4S 5S 62、已知一个求值公式(B 2+AB)/(5B+A)，若 A、B 已赋值，试画出该公式求值过程的前趋图。解：令 S1：X1 = B 2；S2：X2 = AB；S3：X3 = X1 + X2；S4：X4 = 5B；S5：X5 = X4 + A；S6：

2、X6 = X3 / X5。则求值过程的前趋图为： (自己画出)3、写出实现两个进程单向同步问题的伪码。 （参考讲义）3、写出通过信号量实现生产进程和消费进程（单缓冲区）双向同步的伪码。 （参考讲义）解：定义信号量：var s1,s2: semaphore :=1,0;生产进程伪码：Process P:beginwhile(true) dobegin生产一个产品；wait(s1); /P 操作，等待可以生产的信号量将产品放入缓冲区。 。 。 。 。 。/其他操作singal(s2); /V 操作，发送可以消费的信号量endend消费进程伪码：Process C:beginwhile(true)

3、dobeginwait(s2); /P 操作，等待可以消费的信号量从缓冲区中取出产品进行消费。 。 。 。 。 。/其他操作singal(s1); /V 操作，发送可以生产的信号量endend4、写出通过信号量实现进程 1 和进程 2 互斥访问共享资源（临界资源）的伪码。 （参考讲义）解：定义信号量：var s: semaphore :=1;访问资源进程 1 伪码：Process P1:beginwhile(true) dobeginwait(s); /P 操作，申请访问资源权限的的信号量临界区代码; /其他访问资源操作singal(s); /V 操作，释放访问资源权限的信号量endend访问

4、资源进程 2 伪码：（同 P1 类似）Process P2:beginwhile(true) dobeginwait(s); /P 操作，申请访问资源权限的的信号量临界区代码; /其他访问资源操作singal(s); /V 操作，释放访问资源权限的信号量endend5、写出具有缓冲池（n 个缓冲区）的生产者-消费者问题的伪码。（参考讲义、教材）6、写出公共汽车司机和售票员同步问题的伪码。 （参考讲义）解：信号量定义var s1,s2:semaphore:=0,0;/s1 为控制能否行车的信号量/s2 为控制能否开门的信号量司机进程：Process Driver:beginwhile(true)

5、 dobeginwait(s1); 加油行车；到站停车；singal(s2); endend售票员进程：Process Conductor:beginwhile(true) dobegin关车门;singal(s1);售票；wait(s2); 开车门；endend7、读者-写者同步问题（参考讲义和教材）第三章1、系统有 5 个进程，其就绪时刻(指在该时刻已经在就绪队列中就绪) 、服务时间如下表所示。当分别采用先来先服务(FCFS) 和短进程优先(SPF)算法时，画出调度过程，并计算平均周转时间和平均带权周转时间。(参考 P91-92)进程 就绪时刻 服务时间P1 0 2P2 2 5P3 4 3

6、P4 6 6P5 8 1解：（1） 采用 FCFS 算法时，调度过程如下表所示：进程 就绪时刻 服务时间开始执行时间完成时间 周转时间带权周转时间P1 0 2 0 2 2 1P2 2 5 2 7 5 1P3 4 3 7 10 6 2P4 6 6 10 16 10 5/3P5 8 1 16 17 9 9平均周转时间=平均带权周转时间=（2）采用最短进程优先算法时，调度过程如下表所示：进程 就绪时刻 服务时间开始执行时间完成时间 周转时间带权周转时间P1 0 2 0 2 2 1P2 2 5 2 7 5 1P3 4 3 7 10 6 2P4 6 6 11 17 11 11/6P5 8 1 10 11

7、 3 3平均周转时间=平均带权周转时间=2、系统中有 5 个进程，每个进程的运行时间和到达时刻如下表所示。若采用时间片轮转调度算法(时间片为 1)，画出进程执行过程，并计算平均周转时间和平均带权周转时间。( 参考 P95)进程 到达时刻 运行时间P1 0 5P2 1 1P3 2 2P4 3 1P5 4 3解：进程执行过程如下：0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2时间 :P 1P 2P 3P 4P 5平均周转时间：(11+1+6+2+8)/5 = 5.6 平均带权周转时间：(11/5+1/1+6/2+2/1+8/3)/52.17 3、系统中有 5 个进程，每个进程的运行

8、时间、优先级和到达时刻如下表所示。若采用抢占式优先级调度算法(优先级越大越优先执行)，画出进程执行过程，并计算平均周转时间和平均带权周转时间。进程 到达时刻 运行时间 优先级P1 0 5 4P2 1 1 6P3 2 2 2P4 3 1 3P5 4 3 54、假定系统中有三个进程 P1、 P2 和 P3，共有 12 台磁带机。进程 P1 总共要求 10 台磁带机， P2 和 P3 分别要求 4 台和 9 台。假设在 T0 时刻，进程 P1、P2 和 P3 已分别获得 5 台、2 台和 2 台磁带机，如下表所示：进 程 最 大 需 求 已 分 配P1P2P31049522(1) 该状态是否是安全状

9、态？请说明理由。解：T0 时刻，系统是处于安全状态，因为此时的空闲磁带机资源为 3，存在一个安全序列，即只要系统按此进程序列分配磁带机资源，就能够使三个进程都顺利完成。 （为什么？）(2) 若到达一新进程 P4，请求 1 台磁带机，其最大需求为 4 台，是否可以分配？请说明理由。(参考 P108)解：可以进行资源分配。因为将 1 台磁带机分配给 P4 后，尚有2 台空闲磁带机，存在一个安全序列，即只有系统按此进程序列分配磁带机资源，就能够使四个进程都顺利完成。（为什么？）5、 设系统中有 3 种类型的资源(A，B ，C)和 5 个进程P1、 P2、P3 、P4 、P5 ，A 资源的数量为 17

10、，B 资源的数量为 5，C资源的数量为 20，在 T0 时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。 （参考 P110）最大资源需求量 已分配资源数量进程A B C A B CP1 5 5 9 2 1 2P2 5 3 6 4 0 2P3 4 0 11 4 0 5P4 4 2 5 2 0 4P5 4 2 4 3 1 4A B C剩余资源数 2 3 3(1) T0 时刻是否为安全状态？若是，请给出安全序列；解： 最大资源需求量 已分配资源数量 Need 资源需求量进程A B C A B C A B CP1 5 5 9 2 1 2 3 4 8P2 5 3 6 4 0 2 1 3 4P

11、3 4 0 11 4 0 5 0 0 6P4 4 2 5 2 0 4 2 2 1P5 4 2 4 3 1 4 1 1 0A B C剩余资源数 2 3 3T0 时刻是安全状态。存在安全序列( 为什么？能否找出其他安全序列？)(2) 若在 T0 时刻进程 P2 请求资源(0, 3, 4) ，是否能实施资源分配？为什么？解：若在 T0 时刻进程 P2 请求资源(0, 3, 4)，不能实施资源分配。因为请求资源数(0, 3, 4)可用资源数(2, 3, 3)不成立，没有足够资源。 (3) 在 (1)的基础上，若进程 P4 请求资源(2, 0, 1)，是否能实施资源分配？为什么？最大资源需求量 已分配资

12、源数量 Need 资源需求量进程A B C A B C A B CP1 5 5 9 2 1 2 3 4 8P2 5 3 6 4 0 2 1 3 4P3 4 0 11 4 0 5 0 0 6P4 4 2 5 4 0 5 0 2 0P5 4 2 4 3 1 4 1 1 0A B C剩余资源数 0 3 2解：可以实施分配，因为分配后有安全序列：(为什么？能否找出其他安全序列？),即分配后的状态是安全的。 6、假定系统中有三个进程 P1、 P2 和 P3，共有 12 台磁带机。进程 P1 总共要求 10 台磁带机， P2 和 P3 分别要求 4 台和 9 台。假设在 T0 时刻，进程 P1、P2 和

13、P3 已分别获得 5 台、2 台和 2 台磁带机，尚有 3 台空闲未分配，如下表所示： (参考教材 P108)进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223(1) T0 时刻是否为安全状态？若是，请给出安全序列；(2) 在 T0 时刻 P3 申请一台磁带机，请问能否实施资源分配，为什么？解：参考教材7、理解 FCFS 和 SJF 作业调度算法思想。8、理解时间片轮转算法思想9、通过上课所讲示例理解 EDF（最早截止时间优先）算法和 LLF(最低松弛度优先) 算法思想。进 程 名 A B C D E 平 均 到 达 时 间 0 1 2 3 4 作 业 情 况 调 度 算

14、 法 服 务 时 间 4 3 5 2 4 完 成 时 间 4 7 12 14 18 周 转 时 间 6 0 4 9 FCS (a) 带 权 周 转 时 间 1 2 2 5. 3.5 2.8 完 成 时 间 4 9 18 6 1 周 转 时 间 8 6 3 9 8 SJF (b) 带 权 周 转 时 间 1 2.67 3.1 1.5 2.5 2.1 进 程 名 A B C D E 平 均 到 达 时 间 0 1 2 3 4 作 业 情 况 时 间 片 服 务 时 间 4 3 5 2 4 完 成 时 间 12 10 18 1 17 周 转 时 间 9 6 8 3 1.6 R q=1 带 权 周 转

15、 时 间 3 3 3.2 4 .25 3.29 完 成 时 间 4 7 18 13 17 周 转 时 间 6 6 0 3 9.8 R q=4 带 权 周 转 时 间 1 2 3.2 5 .25 2. 第四章1、某系统采用动态分区分配方式管理内存，内存空间为640KB，高端 40KB 用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业 1 申请 130KB，作业 2 申请 60KB，作业 3 申请 100KB，作业 2 释放 60KB，作业 4申请 200KB，作业 3 释放 100KB，作业 1 释放 130KB，作业 5 申请140KB，作业 6 申请 60

16、KB，作业 7 申请 50KB，作业 6 释放60KB，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实际使用情况。( 参考教材和讲义)解：参考教材、讲义和下题方法2. 某操作系统采用分区存储管理技术。操作系统在低地址占用了 100KB 的空间，用户区主存从 100KB 处开始占用 512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为已分配区。在执行以下申请、释放操作序列后：请求 300KB；请求100KB；释放 300KB；请求 150KB；请求 50KB；请求 90KB，进行以下回答：(1) 分别采用首次适应算法和最佳适应算法时，主存的实际使用情况如何？分别画出主存分布图，并指出空闲分区的首地址和大小；(2) 若随后又要请求 80KB，针对上述两种情况产生什么后果？说明了什么问题？（参考教材和讲义）(1) 采用首次适应算法时，主存分布图如下图 O S 占用 1 0 0 K B1 5 0 K B ( 已分配 )5 0 K B ( 已分配 )9 0 K B ( 已分配 )1 0 K B ( 空闲 )1 0 0 K B ( 已分配 )1 1 2 K B ( 空闲 )空闲区 1：首地址 390KB，大小 10KB； 空闲区 2：首地址 500KB，大小 112KB；