《操作系统教程》（第三版）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