RR q = 1 Tf 6.00 11.00 8.00 18.00 20.00
1.60 8.00 1.60 8.00 1.60 8.00 1.60 20.00 8.00 1.60 8.00 1.60 8.00 1.60
6.20 1.74 7.40 1.85 7.00 1.81 1.98 7.20 1.88 5.60 1.32 5.60 1.32
Tr 6.00 10.00 5.00 9.00 8.00 7.60 Tr/Ts
RR q = 4 Tf
Tr Tr/Ts
SPN
Tf
Tr Tr/Ts
SRT
Tf
Tr Tr/Ts
HRRN
Tf Tr Tr/Ts
FB q = 1 Tf
Tr Tr/Ts
FB q = 2i
9.16 5个批作业，从A到E，同时到达计算机中心。它们的估计运行时间分别为15，9，3，6和12分钟，它们的优先级（外部定义）分别为6，3，7，9和4（值越小，表示的优先级越高）。对下面的每种调度算法，确定每个进程的周转时间和所有作业的平均周转时间（忽略进程切换的开销），并解释是如何得到这个结果的。对于最后三种情况，假设一次只有一个作业运行直到它结束，并且所有作业都完全是受处理器限制的。
a．时间片为1分钟的轮转法。 b．优先级调度
c．FCFS（按15，9，3，6和12顺序运行）。 d．最短作业优先
a: 时间片为1分钟的轮转法： 1
2
3 E E D D D E
4 5 10 E E E 27 E E E E E
30 33 36 38 40 15 19 23 5
Elapsed time
A B C D A B C D A A
B B
C D Tf
Tr Tr/Ts
2.00 3.00 1.00 3.00 1.00 3.00 1.00 3.00 3.00 1.00 7.00 2.33 4.00 1.33
2.00 9.00 1.80 9.00 1.80 9.00 1.80 8.00 7.00 1.40 10.00 2.00 9.00 1.80
2.50 6.00 3.00 2.00 1.00 2.00 1.00 10.00 7.00 3.50 3.00 1.50 5.00 2.50
1.80 10.00 2.00 6.00 1.20 6.00 1.20 15.00 6.00 1.20 9.00 1.80 9.00 1.80
3.00
10.00
9.00
19.00
20.00
3.00 10.00 5.00 15.00 20.00
3.00 10.00 5.00 15.00 20.00
7.00 11.00 6.00 18.00 20.00
4.00 10.00 8.00 18.00 20.00
A B A B A B A B A B A A
A A A
E
42 43 45
每个进程的周转时间
A=45 min , B=35 min , C=13 min , D=26 min , E=42 min 平均周转时间是 (45+35+14+26+42)/5=32.2 min b.
Priority Job Turnaround Time 3 4 6 7 9 c.
Job Turnaround Time A B C D E d.
Running Job Turnaround Time Time 3 6 9
C D B E A
3
3 + 6 = 9 9 + 9 = 18 18 + 12 = 30 30 + 15 = 45
15
15 + 9 = 24 24 + 3 = 27 27 + 6 = 33 33 + 12 = 45
B E A C D
9
9 + 12 = 21 21 + 15 = 36 36 + 3 = 39 39 + 6 = 45
平均周转时间是(9+21+36+39+45)/5=30 min
平均周转时间是(15+24+27+33+45) / 5 = 28.8 min
12 15
平均周转时间是: (3+9+18+30+45) / 5 = 21 min
10.1考虑一组周期任务（3个），表10.5给了它们的执行简表。按照类似与图10.5的形式，给出关于这组任务的调度图。
表10.5 习题10.1的执行简表
进程 到达时间 执行时间 完成最后期限 A(1) 0 10 20 A(2) 20 10 40 . . . . . . . . . . . . B(1) 0 10 50 B(2) 50 10 100 . . . . . . . . . . . . C(1) 0 15 50 C(2) 50 15 100 . . . .
答：对于固定的优先级来说，我们以优先级是ABC来考虑这道题。每一方格代表五个时钟单元，方格里的字母是指现在正在运行的进程。第一行是固定的优先级；第二行表示的是使用完成最后期限的最早最后期限调度。表格如下： A A
对于固定优先级调度来说，进程C总是错过它的最后期限。
10.2 考虑一组非周期性任务（5个），表10.6给出了它们的执行简表。按照类似于图10.6的形式给出关于这组任务的调度图。
表10.6 习题10.2的执行简表
进程 到达时间 执行时间 启动最后期限 A 10 20 100 B 20 20 30 C 40 20 60 D 50 20 80 E 60 20 70
答：每一方格代表10个时间单元。 最早期限 有自愿空闲时间的最早期限 先来先服
10.3 这个习题用于说明对于速率单调调度，式（10.2）是成功调度的充分条件，但它并不是必要条件[也就是说，有些时候，尽管不满足式（10.2）也可能成功调度]。
A A A B A B C C C C C C E E D E E D D D D D A A A A B B B B A A A C C C C A A C A A B A B B A B A A C A C C A C A C A A a.考虑一个任务集，它包括以下独立的周期任务： 任务P1：C1=20; T1=100 任务P2: C2=30; T2=145
使用速率单调调度，这些任务可以成功地调度吗？
b.现在再往集合里增加以下任务： 任务P3: C3=68; T3=150 式（10.2）可以满足吗？
C．假设前述的三个任务的第一个实例在t=0是到达，并假设每个任务的第一个最后期限如下： D1=100; D2=145; D3=150
如果使用速率单调调度，请问这三个最后期限都能得到满足吗？每个任务循环的最后想、期限是多少？ 答：a. P1, P2的总使用率是0.41，小于由方程10.2给出的对于两个任务的界限0.828，因此这两个任务
是可以成功调度的。
b. 所有任务的使用率是0.86，已经超过界限0.779。
c. 可以观察到在P3执行前P1，P2必须至少执行一次。因此P3的第一次瞬间完成时间不低于20＋30
＋68＝118。但是P1在一附加的时间区间（0，118）内初始化。因此P3直到118＋20＝138才完成他的第一次执行。在P3的期限内。继续这个过程，我们可以知道，这三个任务的所有期限都能实现。