习题

5. 若后备作业队列中同时等待运行的有三个作业 Job1，Job2，Job3，已知其各自的运行时间为 $\displaystyle{ a , b , c }$ ，且满足 $\displaystyle{ a < b < c }$ ，试证明采用短作业优先调度算法能获得最小的平均作业周转时间。

解：

作业名	开始时刻	结束时刻	周转时间
Job1	0	a	a
Job2	a	a+b	a+b
Job3	a+b	a+b+c	a+b+c

平均周转时间

$T_0={1\over 3}(a+a+b+a+b+c)=a+{2\over 3}b+{1\over 3}c$

其他方法的平均周转时间分别为

\begin{aligned} T_1&=a+{2\over 3}c+{1\over 3}b\\ T_2&=b+{2\over 3}a+{1\over 3}c\\ T_3&=b+{2\over 3}c+{1\over 3}a\\ T_4&=c+{2\over 3}a+{1\over 3}b\\ T_5&=c+{2\over 3}b+{1\over 3}a\\ \end{aligned}

而作差可得到 $T_i-T_0>0,(i=1,2,\cdots,5)$ 总成立，故 SJF 算法能获得最小的平均作业周转时间。

6. 若有一组作业 $J_1,J_2,\cdots ,J_n$ ，其执行时间依次为 $S_1,S_2,\cdots,S_n$ . 这些作业同时到达系统，并在单处理器上按照单道方式执行。试找出一种作业调度算法，使得平均作业周转时间最短。

解：按照 SJF 调度算法进行调度。

首先对这组作业按照执行时间从小到大进行排序，得到 $J_1^\prime,J_2^\prime,\cdots,J_n^\prime$ ，且满足 $S_1^\prime\leqslant S_2^\prime\leqslant\cdots\leqslant S_n^\prime$ .

按 SJF 算法进行调度，得到平均周转时间为

\begin{aligned} T&={1\over n}[S_1^\prime+(S_1^\prime+S_2^\prime)+(S_1^\prime+S_2^\prime+S_3^\prime)+\cdots+(S_1^\prime+S_2^\prime+\cdots+S_n^\prime)]\\ &=S_1^\prime+{n-1\over n}S_2^\prime+\cdots+{1\over n}S_n^\prime \end{aligned}

若有任意两个执行长度不同的作业 $J_i^\prime,J_j^\prime(i<j)$ 相互调换，可得到平均周转时间为

T^\prime=S_1^\prime+\cdots+{n-i\over n}S_j^\prime+\cdots+{n-j\over n}S_i^\prime+\cdots+{1\over n}S_n^\prime

两者作差得

T^\prime-T={j-i\over n}S_j^\prime-{j-i\over n}S_i^\prime={j-i\over n}(S_j^\prime-S_i^\prime)>0

所以按照 SJF 算法进行调度能得到最短的平均周转时间。

7. 假定执行作业 Job1~Job5，作业号即为其到达顺序，依次在时刻 0 按照序号 1、2、3、4、5 进入单处理器系统。作业号及执行时间、优先权为

作业号	执行时间/ms	优先权
Job1	10	3
Job2	1	1
Job3	2	3
Job4	1	4
Job5	5	2

完成下列计算：（1）分别采用先来先服务调度算法 FCFS、时间片轮转算法 RR、短作业优先算法 SJF 及非抢占优先权调度算法计算出各作业的执行次序（注意优先权越高其数值越小）；（2）计算每种情况下作业的平均周转时间和平均带权周转时间。

解：

FCFS 算法

作业名	执行时间/ms	开始时刻	结束时刻	周转时间/ms	带权周转时间/ms
Job1	10	0	10	10	1
Job2	1	10	11	11	11
Job3	2	11	13	13	6.5
Job4	1	13	14	14	14
Job5	5	14	19	19	3.8

执行次序： $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$

平均周转时间 $\displaystyle{ T = 13.4 m s }$

平均带权周转时间 $\displaystyle{ W = 7.26 m s }$

RR 算法

假设时间片长度为 $\displaystyle{ 1 m s }$ .

作业名	执行时间/ms	周转时间/ms	带权周转时间/ms
Job1	10	19	1.9
Job2	1	2	2
Job3	2	7	3.5
Job4	1	4	4
Job5	5	14	2.8

执行次序： $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 1\rightarrow 3\rightarrow 5\rightarrow 1\rightarrow 5\rightarrow 1\rightarrow 5\rightarrow 1\rightarrow 5\rightarrow 1\rightarrow 1\rightarrow 1\rightarrow 1\rightarrow 1$

平均周转时间 $\displaystyle{ T = 9.2 m s }$

平均带权周转时间 $\displaystyle{ W = 2.84 m s }$

SJF 算法

作业名	执行时间/ms	开始时刻	结束时刻	周转时间/ms	带权周转时间/ms
Job1	10	9	19	19	1.9
Job2	1	0	1	1	1
Job3	2	2	4	4	2
Job4	1	1	2	2	2
Job5	5	4	9	9	1.8

执行次序： $2\rightarrow 4\rightarrow 3\rightarrow 5\rightarrow 1$

平均周转时间 $\displaystyle{ T = 7 m s }$

平均带权周转时间 $\displaystyle{ W = 1.74 m s }$

非抢占优先权调度算法

作业名	执行时间/ms	优先权	开始时刻	结束时刻	周转时间/ms	带权周转时间/ms
Job1	10	3	6	16	16	1.6
Job2	1	1	0	1	1	1
Job3	2	3	16	18	18	9
Job4	1	4	18	19	19	19
Job5	5	2	1	6	6	1.2

执行顺序： $2\rightarrow 5\rightarrow 1\rightarrow 3\rightarrow 4$

平均周转时间 $\displaystyle{ T = 12 m s }$

平均带权周转时间 $\displaystyle{ W = 6.36 m s }$

8. 在道数不受限制的多道程序系统中，作业进入系统的后备队列时立即进行作业调度。现有4个作业进入系统，有关信息为

作业名	进入后备队列的时刻	执行时间/min	优先数
Job1	8:00	60	1
Job2	8:30	50	2
Job3	8:40	30	4
Job4	8:50	10	3

作业调度和进程调度均采用高优先级算法（规定数值越大则优先级越高）。试填充下表。

作业名	进入后备队列的时刻	执行时间/min	开始执行时刻	结束执行时刻	周转时间/min	带权周转时间
Job1	8:00	60	8:00	9:00	60	1
Job2	8:30	50	9:00	9:50	80	1.6
Job3	8:40	30	10:00	10:30	110	3.67
Job4	8:50	10	9:50	10:00	70	7

平均周转时间 $\displaystyle{ T = 80 \min }$

平均带权周转时间 $\displaystyle{ W = 3.32 \min }$

9. 对某系统进行监测后表明，每个进程在 I/O 阻塞之前的平均运行时间为 $\displaystyle{ T }$ ，一次进程切换的系统开销时间为 $\displaystyle{ S }$ 。若采用时间片长度为 $\displaystyle{ Q }$ 的时间片轮转法，对下列各种情况计算 CPU 利用率。 $(1)Q=\infty;(2)Q>T;(3)S<Q<T;(4)Q=S;(5)Q$ 接近于 $\displaystyle{ 0 }$ .

解：

$Q=\infty$ 相当于串行处理，CPU 利用率 $\displaystyle{ = \frac{ T }{ T + S } }$
$\displaystyle{ Q > T }$ 相当于串行处理，CPU 利用率 $\displaystyle{ = \frac{ T }{ T + S } }$
$\displaystyle{ S < Q < T }$ 每隔 $\displaystyle{ Q }$ 时间就会进行一次进程切换，每个周期 $\displaystyle{ Q }$ 时间用于处理进程， $\displaystyle{ S }$ 时间用于处理进程切换 CPU 利用率 $\displaystyle{ = \frac{ Q }{ Q + S } }$
$\displaystyle{ Q = S }$ CPU 利用率 $\displaystyle{ = 50 \% }$
$\displaystyle{ Q }$ 接近于 $\displaystyle{ 0 }$ 处理器几乎一直在调度，没有处理进程，CPU 利用率接近于 $\displaystyle{ 0 }$

16. 若有 4 个作业进入系统，其提交时间和估计运行时间为

作业	提交时刻	估计运行时间/min
1	8:00	120
2	8:50	50
3	9:00	10
4	9:50	20

分别计算在 FCFS、SJF 和 HRRF 算法下的平均周转时间和平均带权周转时间

HRRF

结束的作业名	J2 响应比	J3 响应比	J4 响应比
J1	$\displaystyle{ \frac{ 70 + 50 }{ 50 } = 2.4 }$	$\displaystyle{ \frac{ 60 + 10 }{ 10 } = 7 }$	$\displaystyle{ \frac{ 10 + 20 }{ 20 } = 1.5 }$
J3	$\displaystyle{ \frac{ 80 + 50 }{ 50 } = 2.6 }$	-	$\displaystyle{ \frac{ 20 + 20 }{ 20 } = 2 }$
J2	-	-	$\displaystyle{ \frac{ 70 + 20 }{ 20 } = 4.5 }$
J4	-	-	-

作业名	提交时刻	执行时间/min	开始时刻	结束时刻	周转时间/min	带权周转时间
Job1	8:00	120	8：00	10：00	120	1
Job2	8:50	50	10：10	11：00	130	2.6
Job3	9:00	10	10：00	10：10	70	7
Job4	9:50	20	11：00	11：20	90	4.5

平均周转时间 $\displaystyle{ T = 102.5 \min }$

平均带权周转时间 $\displaystyle{ W = 3.775 \min }$

17. 如果在限制为两道的多道程序系统中，有 4 个作业进入系统，其进入系统时刻、估计运行时间为

作业	进入系统时刻	估计运行时间/min	开始运行时刻	结束运行时刻	周转时间
Job1	10:00	30	10:00	11:05	65
Job2	10:05	20	10:05	10:25	20
Job3	10:10	5	10:25	10:30	20
Job4	10:20	10	10:30	10:40	20

系统采用 SJF 作业调度算法，采用 SRTF 进程调度算法，请填充上表。

// "=" 表示执行，"-" 表示被抢占，"." 表示在就绪队列
  10:   05    10    15    20    25    30    35    40    45    50    55    11:   05
 r30   r25                     r25   r25         r25
1 |=====|-----------------------|-----|-----------|=============================X
       r20
2 |     |=====|=====|=====|=====X
             r5          r5    r5
3 |           |.....|.....|.....|=====X
                         r10         r10
4 |                       |.....|.....|=====|=====X

20. 有一个 4 道作业的操作系统，若在一段时间内先后到达 6 个作业

作业	提交时间	估计运行时间/min
1	8:00	60
2	8:20	35
3	8:25	20
4	8:30	25
5	8:35	5
6	8:40	10

系统采用剩余 SJF 调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占

（1）分别给出 6 个作业的执行时间序列，即开始执行时间、作业完成时间、作业周转时间。

（2）计算平均作业周转时间。

作业	进入系统时刻	估计运行时间/min	开始运行时刻	结束运行时刻	周转时间
Job1	8:00	60	8:00	10:35	155
Job2	8:20	35	8:20	9:55	95
Job3	8:25	20	8:25	8:45	20
Job4	8:30	25	9:00	9:25	55
Job5	8:35	5	8:45	8:50	15
Job6	8:40	10	8:50	9:00	20

  8:   20   25   30   35   40   45   50   55   9:    25    55   10:35
 r60  r40                           r40       r40   r40
1 |====|-----------------------------|---------|-----|-----|=====X
      r35  r30                      r30       r30   r30
2      |====|------------------------|---------|-----|=====X
           r20  r15  r10  r5
3           |====|====|====|====X
                r25                 r25        r25
4                |....在作业队列中...|.........|=====X
                     r5        r5
5                     |.........|====X
                          r10  r10  r10
6                          |....|....|=========X

平均作业周转时间 T = 60 min

21. 有一个具有三道作业的多道批处理系统，作业调度采用短作业优先 SJF 调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小则优先级越高。

作业名	到达时刻	估计运行时间/min	优先数
A	10:00	40	5
B	10:20	30	3
C	10:30	60	4
D	10:50	20	6
E	11:00	20	4
F	11:10	10	4

试填充下表

作业	进入内存时刻	运行结束时刻	作业周转时间/min
A	10:00	12:40	160
B	10:20	10:50	30
C	10:30	11:50	80
D	10:50	13:00	130
E	12:00	12:20	80
F	11:50	12:00	50

平均周转时间 $\displaystyle{ T = 88.3 \min }$

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

作业号	进入输入井时刻	运行时间/min	内存需求量/KB	磁带机需求/台	打印机需求/台
1	8:00	25	15	1	1
2	8:20	10	30	0	1
3	8:20	20	60	1	0
4	8:30	20	20	1	0
5	8:35	15	10	1	1

作业调度采用 FCFS 策略，优先分配内存低地址区且不准移动已在内存中的作业，内存中的各作业平分 CPU 时间。现求：（1）作业调度的先后次序；（2）全部作业运行结束的时刻；（3）作业平均周转时间；（4）最大作业周转时间。

作业号	进入输入井时刻	运行时间/min	开始时刻	结束时刻	周转时间
1	8:00	25	8:00	8:30	30
2	8:20	10	9:00	9:15	55
3	8:20	20	8:20	9:00	40
4	8:30	20	8:30	9:10	40
5	8:35	15	9:15	9:30	55

订正：

// "#" 表示 CPU 全占用，"=" 表示平分 CPU 时间，"." 表示等待
   8:00      20       30      35      9:00     10        15        30

re 25        5
1  |#########|=========X
re           10                        10      5
2  |         |.........|.......|.......|=======|#########X
re           20        15     12.5
3  |         |=========|=======|=======X
re                     20     17.5     5
4  |                   |=======|=======|=======X
re                                                       15
5  |                           |.......|.......|.........|#########X

T1 |====1====|====1====X========4======|===4===|         |====5====|
T2 |         |====3====|========3======X
P  |====1====|====1====X               |===2===|====2====X====5====|
mem
[1]15    [1]15        -15     -15   [2]30   [2]30     [5]10       -100
  -85    [3]60      [3]60   [3]60     -45     -70       -90
           -25      [4]20   [4]20   [4]20
                    -5      -5      -5

作业调度次序： $1\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow 5$
全部作业完成时间：9:30
周转时间

作业	1	2	3	4	5
周转时间	30	55	40	40	55

平均周转时间为 44 min
最大作业周转时间为 55 min

习题

5. 若后备作业队列中同时等待运行的有三个作业 Job1，Job2，Job3，已知其各自的运行时间为 a,b,c\displaystyle{ a , b , c }a,b,c，且满足 a<b<c\displaystyle{ a < b < c }a<b<c，试证明采用短作业优先调度算法能获得最小的平均作业周转时间。