操作系统 应用题 例题+参考答案（考研真题）

1.（考研真题）一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下。

P1：计算60ms，I/O 80ms，计算20ms。

P2：计算120ms，I/O 40ms，计算40ms。

不考虑调度和切换时间，请计算完成两个作业需要的最少时间。

【参考答案】作业执行的过程如图所示。由于多道批处理系统中，P1与P2可以部分并行，那么，P1先到达系统，先占用CPU进行计算到60ms，然后执行I/O时间是80ms~140ms；而P1执行I/O的过程中，P2可获得CPU运行120ms，到180ms结束；当P1执行完它的I/O后，执行计算，此时CPU正被P2占用，P1等P2执行完后，获得CPU执行剩余的20ms完成退出系统；此时，P2执行I/O40ms到220ms；最后P2获得CPU运行剩余的40ms到260ms结束。由图可知，完成两个作业需要的最少时间为260ms。

2.设某计算机系统有一个CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。画出它们的运行图，并说明：

（1）开始运行后，CPU有无空闲等待？若有，在哪段时间内等待？计算CPU的利用率；

（2）进程A运行时有无等待现象？若有，在何时发生等待现象？

（3）进程B运行时有无等待现象？若有，在何时发生等待现象？

【参考答案】进程运行情况如下图所示。

（1）CPU在100~150ms时间段内空闲，利用率为250/300=83.3%。

（2）进程A为无等待现象。

（3）进程B为有等待现象，0~50ms，180~200ms。

3.（考研真题）画出下面4条语句所对应的前驱图。

P1：a=x+2y；     P2：b=a+6；    P3：c=4a-9；     P4：d=2b+5c；

3. 【参考答案】P2和P3都必须在a被赋值之后才能执行；但P2、P3可以并发执行，因此它们彼此互不依赖；P4必须在b和c被赋值后才能执行。因此前趋图如图所示。

4.（考研真题）有以下的进程需要调度执行（见表3-1-1），若用非抢占式短进程优先调度算法，问这5个进程的平均周转时间是多少？

表3-1-1 进程运行时间表

进程名

到达时间

运行时间

P1

0.0

9

P2

0.4

4

P3

1.0

1

P4

5.5

4

P5

7

2

4.【参考答案】本题分步解答如下。

（1）采用非抢占式短进程优先调度算法，各进程执行次序如图所示。

在0时刻，进程P1到达，P1获得处理机。由于不可抢占，所以P1会一直运行到9时刻结束；在9时刻，所有进程到达，根据短进程优先调度，P3获得处理机，然后是P5；P2和P4的预计运行时间一样，P2和P4按照先来先服务原则调度，P2优先获得处理机，最后P4运行。

（2）周转时间=完成时间-作业到达时间。因此P1的周转时间是9-0=9，P2的周转时间是16-0.4=15.6，P3的周转时间是10-1=9，P4的周转时间是20-5.5=14.5，P5的周转时间是12-7=5。平均周转时间为(9+15.6+9+14.5+5)/5=10.62。

5.（考研真题）5个进程P1、P2、P3、P4、P5几乎同时到达，预期运行时间分别为10、6、2、4、8个时间单位。各进程的优先级分别为3、5、2、1、4（数值越大，优先级越高）。请按下列调度算法计算任务的平均周转时间（进程切换开销可忽略不计）。

（1）先来先服务（按P1、P2、P3、P4、P5顺序）算法。

（2）时间片轮转算法，假定时间片大小为2个时间单位。

（3）优先权调度算法。

5. 【参考答案】根据算法思想，确定调度先后顺序。

（1）FCFS调度顺序如图所示。

（2）时间片轮转调度顺序如图所示。

（3）优先权调度算法的调度顺序如图所示。

    于是，可以得到如表所示的结果。

算法

时间类型

P1

P2

P3

P4

P5

平均

运行时间

10

6

2

4

8

FCFS

周转时间

10

16

18

22

30

19.2

带权周转时间

1

2.67

9

5.5

3.75

4.384

RR

周转时间

30

22

6

16

28

20.4

带权周转时间

3

3.67

3

4

3.5

3.434

优先权

周转时间

24

6

26

30

14

20

带权周转时间

2.4

1

13

7.5

1.75

5.13

周转时间=结束时间-到达时间

带权周转时间=WT = (Service Time + Waiting Time) / (Service Time)

6.在一个单道批处理系统中,一组作业的提交时刻和运行时间如下表所示:

作业

提交时间

运行时间

1

8：00

1.0

2

8：50

0.50

3

9：00

0.20

4

9：10

0.10

试计算以下3种作业调度算法的平均周转时间T和平均带权周转时间W：

【参考答案】（1）采用先来先服务作业调度算法时，作业的运行情况如下表所示。

作业执行次序

提交时间

运行时间

开始时刻

完成时刻

周转时间

带权周转时间

1

8：00

1.0

8：00

9：00

1.0

1.0

2

8：50

0.05

9：00

9：50

1.0

2.0

3

9：00

0.20

9：50

9：70

0.7

3.5

4

9：10

0.10

9：70

9：80

0.7

7.0

平均周转时间为T=(1.0+1.0+0.7+0.7)/4=0.85。

平均带权周转时间为W=(1.0+2.0+3.5+7.0)/4=3.375。

（2）采用短作业优先调度算法时，作业的运行情况如下表所示。

作业执行次序

提交时间

运行时间

开始时刻

完成时刻

周转时间

带权周转时间

1

8：00

1.0

8：00

9：00

1.0

1.0

3

8：50

0.20

9：00

9：20

0.2

1.0

4

9：10

0.10

9：20

9：30

0.2

2.0

2

8：50

0.50

9：30

9：80

1.3

2.6

平均周转时间为T=(1.0+0.2+0.2+1.3)/4=0.675。

平均带权周转时间为W=(1.0+1.0+2.0+2.6)/4=1.65。

（3）采用响应比高者优先作业调度算法时，作业的运行情况如下表所示。

作业执行次序

提交时间

运行时间

开始时刻

完成时刻

周转时间

带权周转时间

1

8：00

1.0

8：00

9：00

1.0

1.0

3

9：00

0.20

9：00

9：20

0.2

1.0

2

8：50

0.50

9：20

9：70

1.2

2.4

4

9：10

0.10

9：70

9：80

0.7

7.0

平均周转时间为T=(1.0+0.2+1.2+0.7)/4=0.775。

平均带权周转时间为W=(1.0+1.0+2.4+7.0)/4=2.85。

7.单道批处理系统中有4个作业，其有关情况如下表所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。

作业

提交时间/h

运行时间/h

J1

8.0

2

J2

8.6

0.6

J3

8.8

0.2

J4

9.0

0.5

【参考答案】在8.0只有作业J1到达，系统先将作业J1投入运行。作业J1运行2个小时后完成。这时3个作业都已到达，要计算3个作业的响应比，然后使响应比最高的投入运行。3个作业的响应比为：

响应比=作业周转时间/作业处理时间

                =（作业等待时间+作业处理时间）/作业处理时间

                =1+（等待时间/处理时间）

作业J2的响应比=1+(10.0-86)/0.6=3.33

作业J3的响应比=1+(10.0-8.8)/0.2=7

作业J4的响应比=1+(10.0-9.0)/0.5=3

从计算的结果来看，作业J3的响应比最高，所以让作业J3先执行。

作业J3执行0.2小时后完成。此时作业J2和作业J4的响应比为：

作业J2的响应比=1+(10.2-8.6)/0.6=3.67

作业J4的响应比=1+(10.2-9.0)/0.5=3.4

从计算的结果来看，作业J2的响应比最高，所以再让作业J2执行。

可见，4个作业的执行次序为：作业J1，作业J3，作业J2，作业J4。

计算结果如下表：

作业号

到达时间

运行时间

开始时间

完成时间

周转时间

带权周转时间

 1

8.0

2.0

8.0

10.0

2.0

1.0

2

8.6

0.6

10.2

10.8

2.2

3．67

3

8.8

0.2

10.0

10.2

1.4

7

4

9.0

0.5

10.8

11.3

2.3

4.6

平均周转时间为T=(2.0+2.2+1.4+2.3)/4=1.975

平均带权周转时间为W=(1.0+3.67+7+4.6)/4=3.98

8.（考研真题）假设系统中有下述解决死锁的办法：

（1）银行家算法；

（2）检测死锁，终止处于死锁状态的进程，释放该进程占有的资源；

（3）资源预分配。

简述哪种办法允许最大的并发性？请按“并发性”从大到小对上述3种办法排序。

【参考答案】题中给出的3种办法中，

检测死锁能允许更多的进程无等待地向前推进，并发性最大。因为该方法允许进程最大限度地申请并分配资源，直至出现死锁，再由系统解决。

银行家算法允许进程自由申请资源，只是在某个进程申请时检查系统是否处于安全状态，若是，则可立即分配，若不是，才拒绝。并发性大小次于检测死锁的方法。

最后是资源预分配，因为此方法要求进程在运行之前申请所需的全部资源才可以，这会使得许多进程因申请不到资源而无法开始，得到部分资源的进程因得不到全部资源也不释放已占用的资源，因此导致资源的浪费。

因此，3种方法的并发性按从大到小排序为：检测死锁、银行家算法、资源预分配。

9.（考研真题）假定系统中有5个进程P0、P1、P2、P3、P4和4种资源A、B、C、D，若出现如表所示资源分配情况。

进程

已分配到资源

尚需资源需求

当前可用资源数

P0

（1，1，1，0）

（0，3，3，1）

（0，3，2，2）

P1

（0，2，3，1）

（0，3，4，2）

P2

（0，2，1，2）

（1，0，3，4）

P3

（0，3，1，0）

（0，3，2，0）

P4

（1，0，2，1）

（0，4，2，3）

问：（1）该状态是否安全？为什么？

（2）如果进程P0提出资源请求（0，0，0，1），系统能否将资源分配给它？为什么？

 【参考答案】严格按照银行家算法及安全检查子算法进行。

（1）初始状态如表所示。

进程

Work

Need

Allocation

Work + Allocation

Finish

P3

0，3，2，2

0，3，2，0

0，3，1，0

0，6，3，2

True

P0

0，6，3，2

0，3，3，1

1，1，1，0

1，7，4，2

True

P1

1，7，4，2

0，3，4，2

0，2，3，1

1，9，7，3

True

P4

1，9，7，3

0，4，2，3

1，0，2，1

2，9，9，4

True

P2

2，9，9，4

1，0，3，4

0，2，1，2

2，11，10，6

True

存在一个安全序列P3，P0，P1，P4，P2，所以，该状态是安全的。

（2）Request0(0，0，0，1)