练习题及答案复习进程

第三章 练习题及答案

1. 在单道环境下，某批处理有四道作业，已知它们进入系统的时刻、估计运行时间如下：

作业 进入时刻(h) 运行时间(h)

1 8.00 2.00

2 8.50 0.50

3 9.00 0.10

4 9.50 0.20

设系统每次只选择一个作业进入主机，分别给出在FCFS,SJF,HRN算法中这组作业的运行顺序、平均周转时间和平均带权周转时间。

2. 为什么说多级反馈队列能较好地满足各种用户的需要?

3. 有一个多道程序系统，有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业调度和进程调度均采用FCFS算法。现有一批作业，已知条件如下：

作业名 进入输入井时间 需计算时间（分） 需内存量（KB）

A 8:06 42 15

B 8:18 30 60

C 8:30 24 50

D 8:36 24 10

E 8:42 12

20

假定所有作业都是计算型作业并且忽略系统调度所化的时间。计算各作业被选中装入内存的时间、开始执行的时间、结束执行的时间、周转时间和带权周转时间。

4. 上例中，其他假设条件不变，仅把作业的调度算法改为按SF算法，进程仍采用FCFS算法。

5. 作业调度的性能评价标准有哪些？这些性能评价在任何情况下都能反映调度策略的优劣吗？

6. 什么叫无限期封锁（indefinite blocking）?它在什么情况下出现？

7. 作业调度算法选择作业的原则，可以是保证系统的吞吐量大、可以是对用户公平合理、可以是充分发挥系统资源的利用率。请分别指出先来先服务、最短作业优先、I/O量大与CPU量大的作业搭配３种调度算法，体现了那种选择作业的原则？

8. 假定待处理的三个作业的到达时间和运行时间如下，若采用调度算法①、②、③，这些作业的平均周转时间是多少？

作业名 到达时间(时) 执行时间

1 0.0 8

2 0.4 4

3 1.0 1

①FCFS：

②SJF；

③考虑一下如何改善SJF的性能，并计算新方法的平均周转时间？ 9. 假定要在一台处理机上执行下列作业：

作业 执行时间 优先级

１ 10 3

２ 1 1

３ 2 3

４ 1 4

５ 5 2

且假定这些作业达到的次序是1，2，3，4，5。

⑴给出Gantt图来说明分别使用FCFS，RR(时间片=1)，SJF以及非抢占优先调度算法时这些作业的执行情况；（注：Gantt 图是描述进程/作业执行情况的一种直观形式，它展示了作业/进程执行过程中瞬时段或时间片的变化分布情况。）

⑵针对上述每一调度算法，给出每个作业的周转时间；

⑶就上述每一调度算法，求出每个作业相应的等待时间；

10. 设有5个就绪进程，它们的本次CPU周期的长度、初始优先数及进入就绪队列的相对时刻如下所示：

进程 CPU周期(ms) 优先数 进入时刻(ms)

P1 32 5 0

P2 4 3 0

P3 8 5 0

P4 2 6 0

P5 16 4 16

规定：小的优先数表示高的优先级。画出下列两种情况的Gantt图，计算它们的平均等待时间、平均周转时间和平均带权周转时间。

⑴非剥夺的静态设置方式；

⑵剥夺式的动态设置方式，不妨设现行进程每连续执行12ms后，其优先数加1（即优先级降低），而就绪进程每40ms后，其优先数减1。

11. 有3道作业构成如下，它们在一个系统中运行，该系统有输入/输出设备各一台。

A进程：输入32s，计算8s，输出5s

B进程：输入21s，计算14s，输出35s

C进程：输入12s，计算32s，输出15s

问⑴3道程序顺序执行时最短需要多少时间？

⑵为了充分发挥各设备效能，3道程序并发执行最短需要多少时间？（不计系统开销时间）

12. 在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 40 ms执行一次，执行时间为 20 ms；任务B要求每100ms执行一次，执行时间为 50 ms。请参考课堂相关知识画出在200ms时间内，任务A和B调度情况示意图。并标出任务A和B每一次执行的时间。

习题解答：

1. 解：下面我们用一张表帮助理解

作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00

2 8.50 0.50 10.00 10.50 2.00 4.00

3 9.00 0.10 10.50 10.60 1.60 16.00

4 9.50 0.20 10.60 10.80 1.30 6.50

平均周转时间T=1.725(h)

平均带权周转时间T’=6.875(h) 6.90 27.50

FCFS算法的调度顺序为：1→2→3→4。

作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转

1 8.00 2.00 8.00 10.00 2.00 1.00

2 8.50 0.50 10.30 10.80 2.30 4.60

3 9.00 0.10 10.00 10.10 1.10 11.00

4 9.50 0.20 10.10 10.30 0.80 4.00

平均周转时间T=1.55(h)

平均带权周转时间T’=5.15(h) 6.20 20.60

SJF算法的调度顺序为：1→3→4→2。

作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转

1 8.00 2.00 8.00 10.00 2.00 1.00

2 8.50 0.50 10.10 10.60 2.10 4.20

3 9.00 0.10 10.00 10.10 1.10 11.00

4 9.50 0.20 10.60 10.80 1.30 6.50

平均周转时间T=1.625(h)

平均带权周转时间T’=5.675(h) 6.50 22.70

HRN算法的调度顺序为：1→3→2→4。

2. 答：多级反馈队列是综合了FCFS、RR、HPF三种算法的一种剥夺式的调度算法，它根据进程运行情况的反馈信息动态地改变进程的优先级，按优先级级别组织设置各就绪队列，并规定各就绪队列不同的CPU时间片，对同一队列中的各就绪进程按FCFS或RR算法调度，因而能较好地满足各种用户的需要。

3. 解：

作业名 装入内存 开始执行 结束执行 周转(分) 带权周转

A 8:06 8:06 8:48 42 (1)42/42

B 8:18 8:48 9:18 60 (2)60/30

D 8:36 9:18 9:42 66

(2.75)66/24

C 9:18 9:42 10:06 96 (4)96/24

E 9:18 10:06 10:18 96 (8)96/12

5个作业的平均周转时间和带权周转时间为：T=72(分)，T’=3.55

4. 解：

作业名 装入内存 开始执行 结束执行 周转(分) 带权周转

A 8:06 8:06 8:48 42 (1)42/42

B 8:18 8:48 9:18 60 (2)60/30 D 8:36 9:18 9:42 66 (2.75)66/24

E 9:18 9:42 9:54 72 (4)72/24

C 9:18 9:54 10:18 108 (8)108/12

5个作业的平均周转时间和带权周转时间为：T=69.6(分)，T’=3.25

5. 答：对于批处理系统主要以作业的平均周转时间或平均带权周转时间来衡量调度策略的优劣；而对于分时系统，除了要保证系统的吞吐量大、资源利用率高之外，还应保证用户能容忍的响应时间；实时系统的主要标志则是满足用户要求的时限（截止）时间。

6. 答：无限期封锁也叫饥饿（starvation），即一个具有低优先级的进程决无运行的机会。当CPU接连不断地被较高优先级的作业占用时就可能出现这样的情况。

7. 答：系统的吞吐量大是最短作业优先算法，因为SJF使作业的平均周转时间有明显的改善，从而使系统在单位时间内处理的作业数增多。对用户公平合理是先来先服务算法。因为对用户按照作业进入输入井时间的先后调度，先来先服务，对每个用户都是公平的。发挥系统资源的利用率是I/O量大与CPU量大的作业搭配算法。因为这种算法使I/O与CPU设备都忙碌，并行性好，系统的效率高。

8. 答：①FCFS: 10.53 ((8-0)+(12-0.4)+(13-1))/3 注意：应减去达到时间。

②SJF: 9.53

③分析：由于我们事先并不知道两个较短的作业将很快到达，所以在时刻0，我们选择了作业１。如果让CPU在第一个时间单位空闲，然后使用SJF调度策略，该算法称为“未来知识调度算法FKS”。当然在本例中，由于作业１和２在空闲时间处于等待状态，它们的等待时间会增加。

FKS:6.86 ((2-1)+(6-0.4)+(14-0))/3=6.86

9. 解：

①执行情况的Gantt 图如下所示：

FCFS:

1(10) 2(1) 3(2) 4(1) 5(5)

RR:

1 2 3 4 5 1 3 5 1 5 1 5 1 5

1

SJF:

2 4 3 5 1

Priority:

2 5 1 3 4

②与这些作业相对应的周转时间如下：

作业 FCFS RR SJF Priority

1 10 19 19 16

2 11 2 1 1

3 13 7 4

18

4 14 4 2 19

5 19 14 9 1

③与这些作业相对应的等待时间如下：

作业 FCFS RR SJF Priority

1 0 9 9 6

2 10 1 0 0