南京大学操作系统-2013A

考虑下面的进程集合：

进程 到达时间 处理时间 A 0 1 B 1 9 C 2 1 D 3 9 如果使用先来先服务FCFS调度算法，得到的每个单位时间内的进程执行序列表示为

算法 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

FCFS A B B B B B B B B B C D D D D D D D D D 参照该FCFS调度算法给出的执行序列的写法，写出如果采用时间片轮转RR(时间片单位q=4)、多级反馈队列Feedback (反馈Fback, q=1)等3个调度算法，得到进程执行序列，即在如下表格中填入每个单位时间内执行的进程代号。 答：

算法 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

RR,q=4 Fback,q=1 得分 四、（本题满分 6分）

一个进程在主存中固定分配给3个页框(frame)，发生如下顺序的页访问： 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5

(a) 如果使用LRU 算法，给出相继驻留在这3个页框上的页，并计算缺页次数。假设这些页框最初是空的。（注：在计算缺页次数的时候，请将最初页框为空时也统计在内） (b) 如果使用Clock 算法，重复问题(a) (注:不考虑修改位，只考虑引用位)。 答:

LRU算法 页框0 页框1 页框2 缺页标记 4 3 2 1 4 3 5 4 3 2 1 5 缺页次数为 _____次

Clock算法 页框0 页框1 页框2 缺页标记 4 3 2 1 4 3 5 4 3 2 1 5 缺页次数为 ____次

第 5 页 共 9 页

五、（本题满分 6分）

设系统中有4种类型的资源（A、B、C、D）和5个进程（P0、P1、P2、P3、P4），A资源的总量为3，B资源的总量为12，C资源的总量为14，D资源的总量为14。在T0时刻系统中个资源使用情况的状态如下表所示，系统采用银行家算法实施死锁避免策略。

进程 已经分配资源 (Allocation) 最大需求矩阵 (Claim) A B C D A B C D P0 0 0 3 2 0 0 4 4 得分 P1 P2 P3 P4 1 1 0 0 0 3 3 0 0 5 3 1 0 4 2 4 2 3 0 0 7 6 9 6 5 10 8 6 0 10 4 10

剩余资源 (Available) A B C D 1 6 2 2 试问：T0时刻的各资源剩余数量为多少？T0时刻的是否为安全状态? 若是，请给出其中可能的一种安全序列，并依照该序列，写出各资源的回收步骤。 答：

第 6 页 共 9 页

六、（本题满分 7分）

吸烟者问题(Patil，1971)，三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草(编号为0)、纸(编号为1)和火柴(编号为2)，供应者有丰富货物提供。三位吸烟者中，第一位(编号为1)有自己的烟草，第二位(编号为2)有自己的纸和第三位(编号为3)有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。请信号量和P、V操作写出该问题的程得分 序描述。 答: 第 7 页 共 9 页

得分 答：

七、管程（本题满分 7分）

用Hoare管程方法写出五个哲学就餐问题的程序描述。

第 8 页 共 9 页

得分 八、（本题满分 8分）

有一多道程序设计系统，1）进程调度采用时间片调度算法，不考虑进程的输入输出和操作系统的调度开销；2）存储管理采用可变分区方式，用户空间为100K，采用最先适应算法分配主存且不允许移动；3）系统配有4台磁带机，对磁带机采用静态分配策略。今有如下作业序列： 作业名 J1 J2 J3 J4 进输入井时间 10:00 10:20 10:30 10:40 需执行时间 25分钟 30分钟 10分钟 15分钟 主存量要求 15K 60K 50K 30K 申请磁带机数 2 1 3 2 当作业调度采用“响应比最高优先算法”时，假定操作系统从11:00开始调度, 问： J1装入主存时间: ，结束时间: ； J2装入主存时间: ，结束时间: ； J3装入主存时间: ，结束时间: ； J4装入主存时间: ，结束时间: ； 答：

第 9 页 共 9 页