否立即满足进程的要求？

2、若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。 （1）先来先服务算法；

（2）最短寻找时间优先算法。 答：（1）((40-20)+(44-20)+(44-40)+(40-4)+(80-4)+(80-12)+(76-12))*3=876 （2）((44-40)+(44-20)+(20-12)+(12-4)+(76-4)+(80-76))*3=360

3、设某作业占有7个页面，如果在主存中只允许装入4个工作页面(即工作集为4)，作业运行时，实际访问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。试用FIFO与LRU页面调度算法，列出各自的页面淘汰顺序和缺页中断次数 FIFO的缺页次数为：10次 1 1 1 1 4 4 4 4 4 4 4 5 5 5 5 5 2 2 2 2 7 7 7 7 7 7 7 6 6 6 6 3 3 3 3 3 2 2 2 2 2 2 2 2 2 6 6 6 6 6 1 1 1 1 1 1 1 1 LRU的缺页次数为14次 1 1 1 1 4 4 4 4 1 1 1 1 6 6 6 2 2 2 2 7 7 7 7 4 4 4 4 4 2 2 3 3 3 3 3 3 3 3 7 7 7 7 7 1 6 6 6 6 2 2 2 2 5 5 5 5 5

4、下表给出作业1、2、3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少？ 作业号 到达时间 运行时间 先来先1 服务： 0.0 8.0 2 0.4 开始时间 完成时间4.0 作业号 到达时间 运行时间 周转时间 3 1.0 1 0.0 8.0 1.0 0.0 8.0 8.0 2 0.4 4.0 8.0 3 1.0 1.0 12.0 平均周转时间T=（8+11.6+12）/3=10.53 短作业优先调度：

12.0 13.0 11.6 12.0 作业号 到达时间 运行时间 开始时间 完成时间 周转时间 1 0.0 8.0 0.0 8.0 8.0 3 1.0 1.0 8.0 9.0 8.0 2 0.4 4.0 9.0 13.0 12.6 平均周转时间：T=（8+8+12.6）/3=9.53

5、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。进程read负责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的

第 29 页 共 37 页

记录取出打印输出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样。请用PV操作，写出它们的并发程序。 B1=1 B2=1 D1=0 D2=0

进程read: 进程 move: 进程 print

P(B1); P(B2) P(D2) READ P(D1) PRINT V(D1) MOVE V(B2)

V(D2) V(B1)

2、设某计算机系统有一台输入机、一台打印机。现有两道程序同时投入运行，且程序A先开始运行，程序B后运行。程序A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。程序B的运行的轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试说明： （1） 两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？

为什么会空闲等待？

（2） 程序A、B运行时有无等待现象？若有，在什么时候会发生等待

现象？

答：CPU存在空闲等待。时间段为程序A开始运行后100ms到150ms之间。此期间，程序A正在打印信息，而程序B正在输入数据。程序A启动运行后无等待现象 ，而程序B启动运行后存在等待现象。程序B的等待时间段为A开始运行后180ms到200ms之间.

3、如磁盘的每个磁道分成9个块，现有一文件共有A、B、?I 9个记录，每个记录的大小与块的大小相等，设磁盘转速为27ms/转，每读出一块后需要2ms的处理时间。若忽略其他辅助时间，试问：⑴如果顺序存放这些记录并顺序读取，处理该文件要多少时间？⑵如果要顺序读公元前该文件，记录如何存放处理时间最短？

(1) 8*（27+3）+（3+2）=245ms (2) 记录顺序：A F B G C H D I E 6*8+5=53ms

4、有一矩阵：VAR A:ARRAY[1..100,1..10] OF integer; 按先行后列次序存储。在一虚存系统中，采用LRU淘汰算法，一个进程有3页内存空间，每页可以存放200个整数，其中第1页存放程序，且假定程序已在内存。 程序A： 程序B：

FOR I:=1 TO 100 DO FOR J:=1 TO 100 DO

FOR J:=1 TO 100 DO FOR I:=1 TO 100 DO A[I,J]:=0; A[I,J]=0;

分别就程序A和程序B的执行过程计算缺页次数。

第 30 页 共 37 页

答：对于程序A由于程序A访问矩阵是按行进行，即按照存储顺序进行，因此每次缺页中断调进一页后，位于该页内的数组元素全部设置为0，然后调入下一页，所以缺页次数为50次。 对于程序B：由于程序B对矩阵的访问是按列进行，而矩阵每行有100个数据，每页可以存储200个数据，因此每页中有2个数据属于同一列，每次缺页中断调进一页时，只有其中的2个数据被赋0值，即程序对矩阵每两次访问会遇到一次缺页，所以缺页次数为5000次。

5、设公共汽车上，司机和售票员的活动分别是：

司机的活动：启动车辆； 售票员的活动：关车门；

正常行车； 售票； 到站停车； 开车门；

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现它们的同步。 Int s1=0,s2=0;

Driver: P(s1); 启动车辆 正常行车 到站停车 v(s2)

busman() 关车门 v(s1) 售票 P(s2) 开车门 上下乘客

1、 假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请

求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：36、40、23、97、120、22、110、76、49。试用：(1)电梯调度算法 (2)最短寻找时间优先算法 分别列出实际处理上述请求的次序。

(80) 97 110 120 (180) 76 49 40 36 23 22 17 13 10 60 104

1.(1)电梯调度算法的处理次序为：

第 31 页 共 37 页

5 8 1 4 3 6 2 7 (得4分) 若写出5 8 (得1分)

若写出5 8 1 4 3 (得2分)

(2)最短寻找时间优先算法的处理次序为： 5 8 6 2 7 1 4 3 (得4分) 若写出5 8 (得1分)

若写出5 8 6 2 7 (得2分) 亦即：前2个对 (得1分) 前5个对 (得2分)

2、有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答： (1)若对资源分配不加限制，会发生什么情况?为什么? (2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 2.(1)可能会发生死锁 (2分)

例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待(2分)，这是循环等待。

(或进程在等待新源时均不释放已占资源) (2)可有几种答案：

A.采用静态分配 (2分)

由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。 (2分) 或B.采用按序分配 (2分)

不会出现循环等待资源现象。(2分) 或C.采用银行家算法 (2分)

因为在分配时，保证了系统处于安全状态。 (2分) 3、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

(2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。

COBEGIN PROCESS PI(I=1，2，……) begin ； P(S)

进入售票厅；

购票； 退出；

V(S)

end；

COEND 20 20-n

(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。 (1)定义一信号量S，初始值为20。 (1分) 意义：

S>0 S的值表示可继续进入售票厅的人数 (1分)

第 32 页 共 37 页