Skip to content
Notes
GitHub

习题

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

解：

作业名开始时刻结束时刻周转时间
Job10aa
Job2aa+ba+b
Job3a+ba+b+ca+b+c

平均周转时间

T0=13(a+a+b+a+b+c)=a+23b+13cT_0={1\over 3}(a+a+b+a+b+c)=a+{2\over 3}b+{1\over 3}c

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

T1=a+23c+13bT2=b+23a+13cT3=b+23c+13aT4=c+23a+13bT5=c+23b+13a\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}

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

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

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

首先对这组作业按照执行时间从小到大进行排序，得到 J1′,J2′,⋯ ,Jn′J_1^\prime,J_2^\prime,\cdots,J_n^\prime，且满足 S1′⩽S2′⩽⋯⩽Sn′S_1^\prime\leqslant S_2^\prime\leqslant\cdots\leqslant S_n^\prime.

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

T=1n[S1′+(S1′+S2′)+(S1′+S2′+S3′)+⋯+(S1′+S2′+⋯+Sn′)]=S1′+n−1nS2′+⋯+1nSn′\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}

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

T′=S1′+⋯+n−inSj′+⋯+n−jnSi′+⋯+1nSn′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′−T=j−inSj′−j−inSi′=j−in(Sj′−Si′)>0T^\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优先权
Job1103
Job211
Job323
Job414
Job552
完成下列计算：（1）分别采用先来先服务调度算法 FCFS、时间片轮转算法 RR、短作业优先算法 SJF 及非抢占优先权调度算法计算出各作业的执行次序（注意优先权越高其数值越小）；（2）计算每种情况下作业的平均周转时间和平均带权周转时间。

解：

FCFS 算法
作业名执行时间/ms开始时刻结束时刻周转时间/ms带权周转时间/ms
Job110010101
Job2110111111
Job321113136.5
Job4113141414
Job551419193.8

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

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

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

RR 算法

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

作业名执行时间/ms周转时间/ms带权周转时间/ms
Job110191.9
Job2122
Job3273.5
Job4144
Job55142.8

执行次序：1→2→3→4→5→1→3→5→1→5→1→5→1→5→1→1→1→1→11\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

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

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

SJF 算法
作业名执行时间/ms开始时刻结束时刻周转时间/ms带权周转时间/ms
Job110919191.9
Job210111
Job322442
Job411222
Job554991.8

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

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

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

非抢占优先权调度算法
作业名执行时间/ms优先权开始时刻结束时刻周转时间/ms带权周转时间/ms
Job1103616161.6
Job2110111
Job3231618189
Job41418191919
Job5521661.2

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

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

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

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

作业名进入后备队列的时刻执行时间/min优先数
Job18:00601
Job28:30502
Job38:40304
Job48:50103
作业调度和进程调度均采用高优先级算法（规定数值越大则优先级越高）。试填充下表。
作业名进入后备队
列的时刻		执行时间/min开始执行时刻结束执行时刻周转时间/min带权周转时间
Job18:00608:009:00601
Job28:30509:009:50801.6
Job38:403010:0010:301103.67
Job48:50109:5010:00707

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

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

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

解：

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

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

作业提交时刻估计运行时间/min
18:00120
28:5050
39:0010
49:5020

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

HRRF
结束的作业名J2 响应比J3 响应比J4 响应比
J170+5050=2.4\displaystyle{ \frac{ 70 + 50 }{ 50 } = 2.4 }60+1010=7\displaystyle{ \frac{ 60 + 10 }{ 10 } = 7 }10+2020=1.5\displaystyle{ \frac{ 10 + 20 }{ 20 } = 1.5 }
J380+5050=2.6\displaystyle{ \frac{ 80 + 50 }{ 50 } = 2.6 }-20+2020=2\displaystyle{ \frac{ 20 + 20 }{ 20 } = 2 }
J2--70+2020=4.5\displaystyle{ \frac{ 70 + 20 }{ 20 } = 4.5 }
J4---
作业名提交时刻执行时间/min开始时刻结束时刻周转时间/min带权周转时间
Job18:001208：0010：001201
Job28:505010：1011：001302.6
Job39:001010：0010：10707
Job49:502011：0011：20904.5

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

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

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

作业进入系统时刻估计运行时间/min开始运行时刻结束运行时刻周转时间
Job110:003010:0011:0565
Job210:052010:0510:2520
Job310:10510:2510:3020
Job410:201010:3010:4020
系统采用 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
// "=" 表示执行，"-" 表示被抢占，"." 表示在就绪队列
  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
18:0060
28:2035
38:2520
48:3025
58:355
68:4010
系统采用剩余 SJF 调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占
（1）分别给出 6 个作业的执行时间序列，即开始执行时间、作业完成时间、作业周转时间。
（2）计算平均作业周转时间。
作业进入系统时刻估计运行时间/min开始运行时刻结束运行时刻周转时间
Job18:00608:0010:35155
Job28:20358:209:5595
Job38:25208:258:4520
Job48:30259:009:2555
Job58:3558:458:5015
Job68:40108:509:0020
  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
  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优先数
A10:00405
B10:20303
C10:30604
D10:50206
E11:00204
F11:10104
试填充下表
作业进入内存时刻运行结束时刻作业周转时间/min
A10:0012:40160
B10:2010:5030
C10:3011:5080
D10:5013:00130
E12:0012:2080
F11:5012:0050

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

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

作业号进入输入井时刻运行时间/min内存需求量/KB磁带机需求/台打印机需求/台
18:00251511
28:20103001
38:20206010
48:30202010
58:35151011
作业调度采用 FCFS 策略，优先分配内存低地址区且不准移动已在内存中的作业，内存中的各作业平分 CPU 时间。现求：（1）作业调度的先后次序；（2）全部作业运行结束的时刻；（3）作业平均周转时间；（4）最大作业周转时间。
作业号进入输入井时刻运行时间/min开始时刻结束时刻周转时间
18:00258:008:3030
28:20109:009:1555
38:20208:209:0040
48:30208:309:1040
58:35159:159:3055

订正：

// "#" 表示 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
// "#" 表示 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. 作业调度次序：1→3→4→2→51\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow 5
  2. 全部作业完成时间：9:30
  3. 周转时间
作业12345
周转时间3055404055
  • 平均周转时间为 44 min
  • 最大作业周转时间为 55 min