按次序A B C D E B C D EC D E D E E轮转执行。 (2) 优先级调度算法

(4)FCFS调度算法

调度算法5

(3)SJF

15．在单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪种算法性能较好？请完成下表。

作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 1 2 3 10: 00 10：10 10: 25 2:00 1:00 0:25 作业平均周转时间= 作业平均带权周转时间=

答：（1）FIFO算法

提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 作业 1 2 3 10: 00 10：10 10: 25 2:00 1:00 0:25 10:00 12:00 13:00 12:00 13:00 13:25 2 2:50 3 120/120 170/60 180/25 作业平均周转时间=2.61 作业平均带权周转时间=3.68 （2）HRRF算法

作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 1 2 3 10: 00 10：10 10: 25 2:00 1:00 0:25 10:00 12:25 12:00 12:00 13:25 12:25 2 3:15 2 120/120 195/60 120/25 作业平均周转时间=2.41 作业平均带权周转时间=3.02 可见HRRF比FIFO要好。

27. 某多道程序设计系统供用户使用的主存为100K，磁带机2台，打印机1台。采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业I/O时间。现有作业序列如下：

6

作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机 需求 1 8:00 25分钟 15K 1 1 2 8:20 10分钟 30K 0 1 3 8:20 20分钟 60K 1 0 4 8:30 20分钟 20K 1 0 5 8:35 15分钟 10K 1 1 作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中

的各作业平分CPU时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少?

答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。

(2)全部作业运行结束的时间9:30。

(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) 最大作业周转时间为55分钟。

分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。

8:00 作业1到达，占有资源并调入主存运行。

8:20 作业2和3同时到达，但作业2因分不到打印机，只能在后备队列等待。作业3资源满足，可进主存运行，并与作业1平分CPU时间。

8:30 作业1在8:30结束，释放磁带与打印机。但作业2仍不能执行，因不能移动而没有30KB的空闲区，继续等待。作业4在8:30到达，并进入主存执行，与作业3分享CPU。 8:35 作业5到达，因分不到磁带机/打印机，只能在后备队列等待。

7

9:00 作业3运行结束，释放磁带机。此时作业2的主存及打印机均可满足，投入运行。作业5到达时间晚，只能等待。

9:10 作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。 9:15 作业2运行结束，作业5投入运行。 9:30 作业全部执行结束。

第三章

（思考题）42．某系统有m个同类资源供n个进程共享，若每个进程最多申请x个资源（1≤x

≤m）,推导出系统不发生死锁（n、m和x）的关系式。

答：最坏：每个（x-1）个资源，申请最后一个，剩m-n(x-1)

若还有一个资源可用，则可使所有进程执行结束。 m-n(x-1)≥1，即n(x-1)+1≤m系统不会死锁。

3. 有两个优先级相同的进程P1和P2，各自执行的操作如下，信号量S1和S2初值均为0。

试问P1、P2并发执行后，x、y、z的值各为多少？

P1： P2： begin begin

y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.

答：现对进程语句进行编号，以方便描述。

P1： P2： begin begin

y:=1; ① x:=1; ⑤

8