操作系统课后部分答案

调度顺序：A-> D ->C-> B

平均周转时间：T=(60+130+80+40))/4=77.5

平均带权周转时间： W=(1+13/4+8/3+4))/4=2.73

（3）作业调度和进程调度均采用优先级高者时，计算这批作业的T和W。 优先级高者优先算法 作业名 A C D B 进入输入井时间 8:00 8:20 8:30 8:10 运行时间 60 30 10 40 开始时间 8:00 9:00 9:30 9:40 完成时间 9:00 9:30 9:40 10:20 周转时间 60 70 70 130 带权周转时间 1 7/3 7 13/4 调度顺序：A-> C -> D -> B 平均周转时间：T=(60+130+70+70))/4=82.5(分) 平均带权周转时间： W=(1+13/4+7/3+7))/4=3.40

列: 在一个单道批处理系统中，一组作业的提交时间和运行时间如下表所示：

作业 1 2 3 4 提交时间 8:00 8:50 9:00 9:10 运行时间(小时) 1.0 0.50 0.20 0.10 试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W： (1)先来先服务。 (2)短作业优先。 (3)响应比高者优先。

[答] (1)采用先来先服务作业调度算法时，作业的运行情况如下表所示： 作业执行次序 1 2 3 4 提交时间 8:00 8:50 9:00 9:10 运行时间 1.0 0.5 0.20 0.10 开始时刻 8:00 9:00 9:30 9:42 完成时刻 9:00 9:30 9:42 9:48 周转时间 1.0 0.67 0.7 0.63 带权周转时间 1.0 1.34 3.5 6.3 所以，平均周转时间为： T=(1.0+0.67+0.7+0.63)/4=0.75 平均带权周转时间为：

W=(1.0+1.34+3.5+6.3)/4=3.04

(2)采用短作业优先调度算法时，作业的运行情况如下表所示： 作业执行次序 1 2 3 4 提交时间 8:00 9:00 9:10 8:50 运行时间 1.0 0.2 0.10 0.50 开始时刻 8:00 9:00 9:12 9:18 完成时刻 9:00 9:12 9:18 9:48 周转时间 1.0 0.2 0.133 0.97 带权周转时间 1.0 1.0 1.33 1.94

(在9:00时，作业2和作业3就绪，作业3因为时间短而先执行。同理，9:12时作业4开始执行。)

所以，平均周转时间为： T=(1.0+0.2+0.1+0.97)/4=0.57 平均带权周转时间为：

W=(1.0+1.0+1.33+1.94)/4=1.32

(3)采用响应比高者优先作业调度算法时，作业的运行情况如下表所示： 作业执行次序 1 2 3 4 提交时间 8:00 9:00 8:50 9:10 运行时间 1.0 0.20 0.50 0.10 开始时刻 8:00 9:00 9:12 9:42 完成时刻 9:00 9:12 9:42 9:48 周转时间 1.0 0.2 0.87 0.63 带权周转时间 1.0 1.0 1.74 6.3 所以，平均周转时间为：

T=(1.0+0.2+0.87+0.63)/4=0.675 平均带权周转时间为：

W=(1.0+1.0+1.74+6.3)/4=2.51

12．单道批处理系统中，有四个作业，其有关情况如下表所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。 作业 提交时间/h 运行时间/h J1 8.0 2.0 J2 8.6 0.6 J3 8.8 0.2 J4 9.0 0.5 [答] 分析响应比高者优先调度算法是指在每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高的投入运行。

在第8小时，因为只有作业J1到达，系统先将作业J1投入运行。作业J1运行两个小时后完成。这时三个作业都已到达，要计算三个作业的响应比，然后使响应比最高的投入运行。三个作业的响应比为：

作业J2的响应比=1+(10.0-8.6)/0.6=3.33 作业J3的响应比=1+(10.0-8.8)/0.2=7 作业J4的响应比=l+(10.0-9.0)/0.5=3

从计算的结果来看，作业J3的响应比最高，所以让作业J3先执行。作业J3执行0.2小时后完成，此时作业J2和作业J4的响应比为：

作业J2的响应比=1+(10.2-8.6)/0.6=3.67 作业J4的响应比=1+(10.2-9.0)/0.5=3.4

从计算的结果来看，作业J2的响应比最高，所以再让作业J2执行。 可见，四个作业的执行次序为：作业J1，作业J3，作业2，作业J4。 计算结果如下表：

作业号 1 2 3 4 平均周转时间为： 到达时间 8.0 8.6 8.8 9.0 运行时间 2.0 0.6 0.2 0.5 开始完时间 成时间 8.0 10.2 10.0 10.8 10.0 10.8 10.2 11.3 周转时间 2.0 2.2 1.4 2.3 带权周转时间 1.0 3.67 7 4.6

T=(2.0+2.2+1.4+2.3)/4=1.975 平均带权周转时间为： W=(1.0+3.67+7+4.6)/4=3.98

5-15在单道批处理系统中，有下列三个作业用先来先服务调度算法和最短作业优

先调度算法进行调度，哪一种算法调度性能好些？请完成下表中未填写的各项。

作业 1 2 3 提交时间 执行时间 开始时间 10.00 10.10 10.25 2.00 1.00 0.25 完成时间 周转时间 带权周转时间 平均周转时间t= 平均带权周转时间w= 先来先服务调度算法

最短作业优先调度算法

作业123提交时间10.0010.1010.25执行时间2.001.000.25开始时间10.0012.2512.00完成时间12.0013.2512.25周转时间23.152带权周转时间13.158作业123提交时间10.0010.1010.25执行时间2.001.000.25开始时间10.0012.0013.00完成时间12.0013.0013.25周转时间2.002.903.00带权周转时间12.912平均周转时间t=2.63平均带权周转时间w=5.3平均周转时间t=2.38平均带权周转时间w=4.05最短作业优先调度算法性能好些，因为平均周转时间和平均带权周转时间都要比先来先服务调度算法短。

第六章

1、简述死锁的防止与死锁的避免的区别。

1、答：死锁的防止是系统预先确定一些破坏死锁必要条件资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。 而死锁的避免是当进程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁。

6、怎样考虑死锁的检测和恢复？

死锁检测算法(回溯)：每次资源被申请或释放时,检测系统资源图是否存在环路(此时死锁可能还没有发生)，如果存在环路,则逐一在环路中选择一进程撤消,直至死锁消除.

缺点:效率太低，导致系统总体性能太为下降。

死锁恢复策略(事后恢复)：依次流产所有的死锁进程，直至死锁解除；依次剥夺资源直到死锁解除；预先定义检测点，备份每一个死锁的进程，然后重启这些进程。

缺点：原来的死锁可能再次出现 7、产生死锁的四个必要条件？

1）互斥(Mutual exclusion) 在一段时间内某资源只能由一个进程占有。

2）占有且等待(Hold and wait) 已占有了一些资源的进程可能还要等待申请其他的资源才能继续工作。

3）非剥夺(No preemption) 已分配给某进程的资源不可被其他进程剥夺，除非该进程自己释放该资源。

4) 循环等待(Circular wait)存在一个封闭的进程-资源循环链。

8、系统资源向量(Available)为：(1，5，2，0)，最大需求量 (Max)、已分配资源量 (Allocation)如下表所示： 资源 Max(最大需求量) Allocation(已分配资源量) 进程 R1 R2 R3 R4 R1 R2 R3 R4 0 0 1 2 0 0 1 2 P1 P2 P3 P4 1 2 0 7 3 6 5 5 5 0 6 2 1 1 0 0 3 6 0 5 3 1 0 4 2 4 0 6 5 6 0 0 P5 使用银行家算法回答下列问题： (1) Need的内容是什么？ (2)系统是否处于安全状态？ (3)如果P2请求（0，4，2，0），能否立即得到满足？ 3、答：(1)Need的内容如下：

P1 (0 0 0 0)，P2 (0 7 5 0)，P3 (1 0 0 2)，P4 (0 0 2 0)，P5 (0 6 4 2)。 (2) 系统处于安全状态，因为P1已得到它所需资源，可释放它已分配资源，系统资源向量变为：(1，5，3，2)，根据Need，可满足P3，P4，其他进程也相继能满足，因此系统是处于安全状态，其中一个安全序列为：P1，P3，P4，P5。

(3)因为P1已得到它所需资源，可释放它已分配资源，系统资源向量变为：(1，5，3，2)，如果P2请求（0，4，2，0），系统资源向量变为：(1，1，1，2)，能满足P3进程对资源的要求。其中一个安全序列为：P1，P3，P4，P2，P5。系统仍处于安全状态，能立即满足P2的请求。

6-7假设三个进程共享四个资源，每个进程一次只能预定或释放一个资源，每个进程最多需要两个资源，试证明这样做不会发生死锁。

在最坏情况下，三个进程各占用一个资源，并同时请求第二个资源。由于系统中还有一