操作系统练习题答案

《操作系统教程》(第三版)CH1应用题参考答案

CPU

(1) 10:00,作业A到达并投入运行。

(2) 10:20,作业B到达且优先权高于作业A,故作业B投入运行而作业A在就绪队列等待。 (3) 10:30,作业C到达,因内存中已有两道作业,故作业C进入作业后备队列等待。

(4) 10:50,作业B运行结束,作业D到达,按SJF短作业优先算法,作业D被装入内存进入就绪

队列。而由于作业A的优先级高于作业D,故作业A投入运行。

(5) 11:10,作业A运行结束,作业C被调入内存,且作业C的优先级高于作业D,故作业C投入

运行。

(6) 12:00,作业C运行结束,作业D投入运行。 (7) 12:20,作业D运行结束。

作业 进入内存时间 运行结束时间

A 10:00 11:10

B 10:20 A ,作业 10;50 各作业周转时间为:作业 70B 30,作业C 90,作业D 90。平均作业周转时间为 C 11:10 12:00 70分钟。 D 10:50 12:20 100K,磁带机2台,打印机1台。采用可变分区内存19 某多道程序设计系统供用户使用的主存为管理,采用静态方式分配外围设备,忽略用户作业I/O时间。现有作业序列如下:

作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求 1 8:00 25分钟 15K 1 1

2 8:20 10分钟 30K 0 1

3 8:20 20分钟 60K 1 0

4 8:30 20分钟 20K 1 0

5 8:35 15分钟 10K 1 1

作业调度采用FCFS策略,优先分配主存低地址区且不准移动已在主存的作业,在主存中的各作业

平分CPU时间。现求:(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少?

答:(1)作业调度选择的作业次序为:作业1、作业3、作业4、作业2和作业5。 (2)全部作业运行结束的时间9:30。

(3)周转时间:作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4为40分钟和作业

5为55分钟。

(4)平均作业周转时间=44分钟。 (5) )最大作业周转时间为55分钟。

20 某多道程序设计系统采用可变分区内存管理,供用户使用的主存为200K,磁带机5台。采用静

态方式分配外围设备,且不能移动在主存中的作业,忽略用户作业I/O时间。现有作业序列如下: 作业号 进入输入井时间 运行时间 主存需求量 磁带需求 A 8:30 40分钟 30K 3

B 8:50 25分钟 120K 1

C 9:00 35分钟 100K 2

D 9:05 20分钟 20K 3 13 E 9:10 10分钟 60K 1 《操作系统教程》(第三版)CH1应用题参考答案

现求:(1)FIFO算法选中作业执行的次序及作业平均周转时间?(2)SJF算法选中作业执行的次序及作

业平均周转时间? 答:

(1) FIFO算法选中作业执行的次序为:A、B、D、C和E。作业平均周转时间为63分钟。 (2) SJF算法选中作业执行的次序为:A、B、D、E和C。作业平均周转时间为58分钟。

CH3 应用题参考答案

1

有三个并发进程:R负责从输入设备读入信息块,M负责对信息块加工处理;P负责打印输出信息块。今提供;

1) 一个缓冲区,可放置K个信息块; 2) 二个缓冲区,每个可放置K个信息块; 试用信号量和P、V操作写出三个进程正确工作的流程。 答:

1) var B : array[0,k-1] of item ; sread : semaphore := k ;

smanage : semaphore := 0 ; swrite : semaphore := 0; rptr : integer := 0 ; mptr : integer := 0 ; wptr : integer := 0 ; x : item cobegin

process reader ; process manager; process writer ; begin begin begin L1: read a message into x ; L2: P(smanage) ; L3: P(swrite) ; P(sread) ; x := B[mptr] ; x := B[wptr] ; B[rptr]:= x ; mptr :=(mptr+1) mod k; wptr :=(wptr +1) mod k; rptr := ( rptr+1) mod k; manage the message in x ; V(sread) ; V(smanage) ; B[mptr] := x; Print the message in x ; goto L1 ; V(swrite) ; goto L3 ; end ; goto L2; end ; end ; coend

2) var A, B : array [0,k-1] of item ;

sput1 : semaphore := k ; sput2 : semaphore := k ; sget1 : semaphore := 0 ; sget2 : semaphore := 0 ; put1 : integer := 0 ; put2 : integer := 0 ; get1 : integer := 0 ; get2 : integer := 0 ;

14

《操作系统教程》(第三版)CH1应用题参考答案

cobegin

process reader ; begin

L1: read a message into x ; P(sput1) ; A[put1] := x ;

put1 := (put1+1) mod k ; V(sget1) ; Goto L1 ; end ;

process manager ; begin

L2: P(sget1) ; x :=A[get1];

get1 :=(get1+1) mod k; V(sput1) ;

Manage the message into x; P(sput2) ; B[put2] := x ;

put2 := (put2+1) mod k ; V(sget2) ; Goto L2 ; end ;

process writer ; begin

L3 : P(sget2) ; x :=B[get2] ;

get2 :=(get2+1) mod k; V(sput2) ;

Print the message in x ; Goto L3 ; end ;

coend

2

设有n个进程共享一个互斥段,如果: (1)每次只允许一个进程进入互斥段;

(2)每次最多允许m个进程(m≤n)同时进入互斥段。

试问:所采用的信号量初值是否相同?信号量值的变化范围如何?

答:所采用的互斥信号量初值不同。

1) 互斥信号量初值为1,变化范围为 [-n+1 ,1]。

当没有进程进入互斥段时,信号量值为1;当有1个进程进入互斥段但没有进程等待进入互斥段时,信号量值为0;当有1个进程进入互斥段且有一个进程等待进入互斥段时,信号量值为-1;最多可能有n-1个进程等待进入互斥段,故此时信号量的值应为-(n-1)也就是-n+1。 2) 互斥信号量初值为m,变化范围为 [-n+m ,m]。

当没有进程进入互斥段时,信号量值为m;当有1个进程进入互斥段但没有进程等待进入互斥段时,信号量值为m-1;当有m个进程进入互斥段且没有一个进程等待进入互斥段时,信号量值为0;当有m个进程进入互斥段且有一个进程等待进入互斥段时,信号量值为-1;最多可能有n-m个进程等待进入互斥段,故此时信号量的值应为-(n-m)也就是-n+m。

3

有两个优先级相同的进程P1和P2,各自执行的操作如下,信号量S1和S2初值均为0。试问P1、P2并发执行后,x、y、z的值各为多少?

P1: P2: begin begin

y:=1; x:=1; y:=y+3; x:=x+5; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=z+y z:=z+x; end. end.

答:现对进程语句进行编号,以方便描述。

P1: P2: begin begin

y:=1; ① x:=1; ⑤ y:=y+3; ② x:=x+5; ⑥

15

《操作系统教程》(第三版)CH1应用题参考答案

V(S1); P(S1);

z:=y+1; ③ x:=x+y; ⑦ P(S2); V(S2);

y:=z+y ④ z:=z+x; ⑧ end. end.

①、②、⑤和⑥是不相交语句,可以任何次序交错执行,而结果是唯一的。接着无论系统如何调度进程并发执行,当执行到语句⑦时,可以得到x=10,y=4。按Bernstein条件,语句③的执行结果不受语句⑦的影响,故语句③执行后得到z=5。最后,语句④和⑧并发执行,最后结果为:

语句④先执行:x=10,y=9,z=15。 语句⑧先执行:x=10,y=19,z=15。

4

有一阅览室,读者进入时必须先在一张登记表上登记,该表为每一座位列出一个表目,包括座号、姓名,读者离开时要注销登记信息;假如阅览室共有100个座位。试用:1)信号量和P、V操作;2)管程,来实现用户进程的同步算法。

答:1) 使用信号量和P、V操作:

var name: array[1..100] of A;

A=record number:integer; name:string; end

for i:=1 to 100 do {A[i].number:=i; A[i].name:=null;} mutex,seatcount:semaphore; i:integer;mutex:=1;seatcount:=100; cobegin {

process readeri(var readername:string)(i=1,2,?) {

P(seatcount); P(mutex);

for i:=1 to 100 do i++

if A[i].name=null then A[i].name:=readername;

reader get the seat number =i; /*A[i].number V(mutex)

进入阅览室,座位号i,座下读书;

P(mutex);

A[i] name:=null; V(mutex); V(seatcount); 离开阅览室; } } coend. 5

在一个盒子里,混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开,设分拣系统有二个进程P1和P2,其中P1拣白子;P2拣黑子。规定每个进程每次拣一子;当一个进程在拣时,不允许另一个进程去拣;当一个进程拣了一子时,必须让另一个进程去拣。试写出两进程P1和P2能并发正确执行的程序。

16

联系客服:779662525#qq.com(#替换为@)