操作系统复习（三）

复习题

一、 假定在单CPU条件下有下列要执行的作业：

作业	到达时间	运行时间	优先级
1	0	10	2
2	1	4	3
3	2	3	5（高）

（1）用一个执行时间图描述在采用非抢占优先级算法时执行这些作业的情况；
（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？
（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少

二、 有两个程序，A程序按顺序使用CPU 10S，使用设备甲5S，使用CPU 5S，使用设备乙10S，最后使用CPU 10S。B程序按顺序使用设备甲10S，使用CPU 10S，使用设备乙5S，使用CPU 5S，使用设备乙10S。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少？提示：CPU利用率=CPU运行时间/程序运行时间。

三、 在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级如下表所示。假设进程的调度时间忽略不计。请分别给出采用下面不同的进程调度算法时各个进程的调度次序，画出执行时间图，并计算平均周转时间、平均带权周转时间。

进程	到达就绪队列的时刻	执行时间（ms）	优先级
P1	0	3	3
P2	2	6	5
P3	4	4	1（高）
P4	6	5	2
P5	8	2	4

（1）先来先服务调度算法；

（2）时间片轮换调度算法（时间片为1ms）；

（3）抢占式短进程优先调度算法；

（4）抢占式优先级调度算法；

（5）非抢占式优先级调度算法。

四、 假设在单CPU条件下有下列要执行的作业：

作业	到达时间	运行时间	优先级
A	0	10	3
B	1	1	1
C	2	2	3
D	3	1	4（高）
E	4	5	2

（1）用一个执行时间图描述在非抢占优先级算法时，执行这些作业的情况。

（2）用一个执行时间图描述在RR算法时（不考虑优先级），执行这些作业的情况（时间片为1单位）。

五、 设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P、V操作写出这些进程使用打印机的算法。

六、 有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：

(1)若对资源分配不加限制，会发生什么情况?为什么?

(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么?

七、 用信号灯及P、V操作来描述右图

1、说明进程的同步关系：

2、设置信号灯，说明含义、初值。

3、写出程序描述（ 用P、V操作描述 P1、P2、P3）。

主函数如下：

main()

{int s13=0,s23=0;

cobegin

p1;

p2;

p3;

coend}

八、 假定系统中有4个进程P1、P2、P3、P4和3种类型的资源R1、R2、R3，数量分别为9、3、6，在t0时刻的资源分配情况如表所示。

表  t0时刻的资源分配表

	Max	Allocation	Need	Available
R1	R2	R3	R1	R2	R3	R1	R2	R3	R1	R2	R3
P1	3	2	2	1	0	0	2	2	2	1	1	2
P2	6	1	3	5	1	1	1	0	2
P3	3	1	4	2	1	1	1	0	3
P4	4	2	2	0	0	2	4	2	0

试问：（1）t0时刻是否安全？

（2）P2发出请求向量Request2（1，0，1），系统能否将资源分配给它？

（3）在P2申请资源后，若P1发出请求向量Request1（1，0，1），系统能否将资源分配给它？

（4）在P1申请资源后，若P3发出请求向量Request3（0，0，1），系统能否将资源分配给它？

九、 试化简图1中的进程——资源图，并利用死锁定理给出相应的理论。

十、 试化简图2中的进程——资源图，并利用死锁定理给出相应的理论。

十一、      在银行家算法中，若出现下述资源分配情况：（5个进程，4类资源）

Process	Allocation	Need	Available
A	0032	0012	1622
B	1000	1750
C	1354	2356
D	0032	0652
E	0114	0656

试问： ⑴ 该状态是否安全，说明理由？

⑵ 若某进程提出请求Request(1，2，2，2)后，系统能否将资源分配给它，为什么？

十二、      考虑某一系统，它有四类资源R1，R2，R3，R4，有五个并发进程P0，P1，P2，P3，P4。请按照银行家算法解答下列问题：

（1）      各进程的最大资源请求和已分配的资源矩阵如表所示，计算各进程仍需要请求的资源向量组成的矩阵。

（2）      系统当前是处于安全状态吗？

（3）      当进程P2申请的资源分别为（0，1，0，0）时，系统能立即满足吗？

进程	Allocation	Max	Available
R1	R2	R3	R4	R1	R2	R3	R4	R1	R2	R3	R4
P0	0	0	1	2	0	0	1	2	2	1	0	0
P1	2	0	0	0	2	7	5	0
P2	0	0	3	4	6	6	5	6
P3	2	3	5	4	4	3	5	6
P4	0	3	3	2	0	6	5	2

十三、      某虚拟存储器的用户编程空间有若干个页面，每页为1KB，内存为16MB。假定某时刻已将一页面调入内存，该页逻辑地址为4062B,已知页表寄存器中页表始址为2004B，页表长度为8，此时刻内存部分数据如下表，求该页的物理地址，并指出该物理地址中的数据。

内存地址	数据		内存地址	数据
2000B	1535		2011B	78
2001B	652		2012B	599
2003B	71		2013B	111
2004B	211		2014B	3478
2005B	45		2015B	24
2006B	3		2016B	78
2007B	1		2017B	962
2008B	57		2018B	7758
2009B	5		2019B	75
2010B	486		2020B	85

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

（1）先来先服务（FCFS）      （2）最短寻找时间优先调度（SSTF）

（3）电梯调度法（SCAN） （4）单向扫描（循环扫描C－SCAN）

十五、      考虑下述页面走向：

1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3时，试问FIFO、LRU这两种置换算法的缺页次数各是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

十六、      某移动臂磁盘的柱面由外向里顺序编号，假定当前磁头停在100号柱面且移动臂方向是向里的，现有如下表所示的请求序列在等待访问磁盘：

表 访问磁盘请求序列

请求次序	1	2	3	4	5	6	7	8	9	10
柱面号	190	10	160	80	90	125	30	20	140	25

回答下面的问题：

① 写出分别采用“最短查找时间优先算法”和“电梯调度算法”时，实际处理上述请求的次序。

② 针对本题比较上述两种算法，就移动臂所花的时间（忽略移动臂改向时间）而言，哪种算法更合适？简要说明之。

十七、      有一个系统其内存容量为1024KB，有8个作业同时到达，各作业需要的内存量和运行时间如表所示。

作业编号	A	B	C	D	E	F	G	H
需要内存量（KB）	140	80	100	60	50	30	15	20
运行时间（S）	3	1	3	2	1	3	2	3

假定系统初启时，将内存1024KB按作业的编号顺序分给各道作业，并假定是多CPU下，分配到内存的作业都可以立即运行。试问：

（1）      1S后，内存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？

（2）      2S后，其内存空白区按上述两种算法如何链接？

（3）      在（2）后，此时有一个作业I要求进入内存，它需要内存量为12KB，按上述两种算法，将把哪一块空白区分给它？

十八、      某计算机系统的内存容量为128KB，对存储器采用可变分区的存储管理办法，现有3个作业(J1，J2，J3)在内存，其存储器的分配如图所示。

操作系统	J1	空闲区	J2	空闲区	J3	空闲区
0K	5K	20K	40K	50K	90K	100K	128K

(1)现有一个需要25KB存储空间的作业J4请求装入内存，若采用最先适应分配算法来给J4分配空间。请给出装入J4后的内存分配表。

(2)若采用最优适应算法来给J4分配空间，给出装入J4后的内存分配表。

(3)在只有J1，J2，J3三个作业的情况下，J2运行结束撤离后，请给出J2撤离后的内存分配表。

十九、      某程序在逻辑地址100处有一条取数指令LOAD l，500，而500单元内存放数据51888。假设程序被分配到内存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。

(1)静态重定位。

(2)采用重定位寄存器实现动态重定位。

(3)采用页表映像(映射)方式，假定页面大小为100单元，其负表各页映射到50，51、52，53，54，55，，59物理页上。

二十、      对于如下的页面访问序列： 1，2，3，4，1，2，5，1，2，3，4，5。当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少（画出详细过程）？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

二十一、 给定下面的段表，已知下面的逻辑地址(其中方括号中的第一个元素为段号，第二个元素为段内地址)求其对应的物理地址：

(1)[0,430]；(2)[3,400]；(3) [l,10]； (4) [2,2500]； (5) [4,42]；(6) [1,11]。

段号	段长	段首地址
0	600	219
1	14	2300
2	100	90
3	580	1327
4	96	1954

二十二、 某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号	物理块号		页号	物理块号
0	3		2	11
1	7		3	8

则逻辑地址0A5C（H）所对应的物理地址是什么？要求：写出主要计算过程。

二十三、 某磁盘组有6片盘片，每片有两个记录面，存储区域内径为22cm，外径为33cm，道存储密度为40道/cm，内层位存储密度为400b/cm，转速为3000r/min（转/分），问共有多少柱面？盘组总存储量为多少？平均等待时间为多少？

二十四、 假设有一个磁盘组共有100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。现有一个含有6400逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从“0”开始，逻辑记录的编号也从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放，试问：

（1）      该文件的3680个逻辑记录应该存放在什么位置？

（2）      78柱面的6磁道的6扇区中存放了该文件的第几号逻辑记录？

二十五、 假设一个可移动磁头的磁盘具有200个磁道，其编号为0～199，当它刚刚结束了125道的存取后，现正在处理143道的服务请求，假设系统当前I/O请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘I/O请求调度算法而言，满足以上请求序列，磁头将分别如何移动，请列出磁道访问次序，并计算出移动距离？

（1）先来先服务（FCFS） （2）最短寻找时间优先调度（SSTF）

（3）电梯调度法（SCAN） （4）单向扫描（循环扫描C－SCAN）

二十六、 有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s（转/秒），磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道第3扇区，并立即被系统响应，假设磁头当时处于15道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多长时间？

二十七、 假定磁盘转速为6000r/min（转/分），磁盘格式化时每个盘面被分为9个扇区，现有一个文件共有       A，B，C，D，E，F，G，H，I九个逻辑记录要存放在同一磁道上供处理程序使用，假设每个记录的大小与扇区的大小相同，处理程序每次从磁盘读出一个记录后要花2.5ms处理时间。若忽略其他辅助时间，请回答下列问题：

（3）      现在假设已经顺序存放好这9个记录，那么读出该文件需要多少时间？

（4）      为了使读出文件需要的时间最短，请重新调整各个记录的存放位置，画出各个记录的存放位置，计算该文件的读出时间，并与（1）进行比较说明。

二十八、 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

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

（2 ）在下列横线中填入所定义的信号量，并把应执行的PV操作填入横线中，以保证进程能够正确地并发执行。

main()

{ int           ；

；

进入售票厅；

购票；

退出；

；

｝

（3 ）若欲购票者最多为n 个人，写出信号量可能的变化范围（最大值和最小值）。

二十九、 设有三个人，M，Q，R，其中M负责采购原材料并放到房间A中，Q从房间A中取出原材料并加工成产品后，放到房间B中，R从房间B中取出产品并销售（房间A和B都恰好能放一件原材料）。试用P、V操作描述 M，Q，R三人实现上述工作的控制流程。

(1)在下列横线中写出该定义的信号量及其初值。

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

main（ ）

{

int         ，        ，         ，         ；

cobegin    /下列进程将并发执行/

M（ ）；

Q（ ）；

R（ ）；

coend

Q（ ）{            ；从房间A中取原材料；            ；加工成产品；            ；将产品放到房间B中；            ；}

}
R（ ）{            ；从房间B中取原材料；            ；销售；}

三十、      四个进程A、B、C、D都要读一个共享文件F，系统允许多个进程同时读文件F，但限制是进程A和进程C不能同时读文件F，进程B和进程D也不能同时读文件F，为了使这四个进程并发执行时能按系统要求使用文件，现用PV操作进行管理，请回答下面的问题：

（1）在下列程序中填入应定义的信号量及初值。

（2）在下列程序中填上适当的P、V操作，以保证它们能正确并发工作：

main（ ）

{

int                                          ；

cobegin   /下列进程将并发执行/

A（ ）；

B（ ）；

C（ ）；

D（ ）；

coend

A（ ）{            ；read F；            ；}

}

	C（ ）{            ；read F；             ；}		D（ ）{            ；read F；            ；}

三十一、 桌上有一只盘子，每次只能放一只水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用P—V操作实现他们这间的同步机制。

三十二、 有5批处理作业（A,B,C,D,E）几乎同时到达，估计运行的时间分别为2，4，6，8，10分钟，它们的优先级数分别为1，2，3，4，5（1为最低优先数）。对下面的每种调度算法，分别计算作业的平均周转时间：

1、优先级算法；2、时间片轮转法（时间片为2分钟）；3、FCFS（作业到达顺序为C,D,B,E,A）;4、短作业优先

答案：

复习题答案

一、（1）


（2） 平均周转时间 ：（10+11+16）/3＝12.33

（3） 平均带权周转时间 ：（10/10+11/3+16/4）/3＝2.89

二、10+5+10+10+5/10+5+5+10+10+10+10+5+5+10＝50％

三、(1)先来先服务：平均周转时间为(3+7+9+12+12）/5＝8.6

(2)时间片轮转：平均周转时间为(4+16+13+14+7）/5＝10.8

(3)剥夺式短进程优先,有两种情况:

A：P1→ P2→P3→ P5→P4→ P2   (3+18+4+9+2)/5=5.2

B：P1→ P2→P3→ P5→P2→ P4   (3+13+4+14+2)/5=7.2

(4)剥夺式优先级： P1→ P2→P3→ P4→P5→ P2     （3+18+4+7+7）/5＝7.8

(5)非剥夺式优先级： P1→ P2→P3→ P4→P5    结果与先来先服务相同。

四、1、非抢占式优先级：因为作业到来的时间是按作业编号顺序进行的（即后面的作业依此比前一个作业迟到一个时间单位）。T=1时，只有作业一到达，不必分析优先级，作业一先进入运行态运行10个时间单位。T=10时，作业二、三、四、五陆续到达，其优先级分别为1、3、4、2，按优先级高低陆续进入运行态的是：作业四、作业三、作业五、作业二。


2、时间片轮转：清注意：到达时间差一个单位。

（1）在第一秒内（T=0~1S），A进入运行态，

①运行态：A

就绪队列：    无，  因到达时间差一个单位，其它作业均未到达。

在第一秒末（T=1S），B到达进入就绪队列，A进入就绪队列，B由就绪转入运行；

②运行态：B

就绪队列：A    ，  因到达时间差一个单位，其它作业均未到达。

（2）在第二秒内（T=1~2S），B运行；A就绪。

第二秒末（T=2S）C才到达，进入就绪队列；此时就绪队列中顺序为：A、C；因为队首A由就绪转入运行，B运行时间为1，所以时间片结束时，作业完成，退出系统；此时各队列如下：

③运行态：A

就绪队列：C

（3）在第三秒内（T=2~3S），A运行，此时就绪队列中仅为：C；

在第三秒末（T=3S）D才到达，进入就绪队列；同时A由运行转入就绪；C进入运行；此时就绪队列中顺序为：D、A。

④运行态：C

就绪队列：D、A

（4）在第四秒内（T=3~4S），C运行，此时就绪队列中顺序为：D、A；

第四秒末（T=3S）同时E到达，进入就绪队列，同时C由运行转入就绪；D进入运行；此时就绪队列中顺序为：A、E、C。此时各个作业已经分别陆续到达。

⑤运行态：D

就绪队列：A、E、C

（5）在第五秒内（T=4~5S），D运行，此时就绪队列中顺序为：A、E、C；

第五秒末（T=5S）D运行时间仅为1，所以时间片结束时，作业完成，退出系统同时A转入运行；此时就绪队列中顺序为：E、C。

⑥运行态：A

就绪队列：E、C

（6）在第六秒内（T=5~6S），A运行，此时就绪队列中顺序为：E、C；

第六秒末（T=6S）A时间片结束时，转入就绪队列尾，同时E转入运行；此时就绪队列中顺序为：C、A。

⑦运行态：E

就绪队列：C、A

以后E、C、A循环转入运行态、就绪态。并且根据所需运行时间陆续退出。按照进入运行态的顺序，如下图所示。

五、因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完成之后，另一个用户才能打印。

设：三个进程分别表示为：A，B，和C。又设：一个互斥信号量mutex，其初值为1。

六、(1)可能会发生死锁

例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待，这是循环等待。(或进程在等待新源时均不释放已占资源)

(2)可有几种答案：

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

B.采用按序分配：不会出现循环等待资源现象。

C.采用银行家算法：因为在分配时，保证了系统处于安全状态。

七、1、进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。

2、s13= 0 表示进程P1尚未执行完成；s23 = 0 表示进程P2尚未执行完成；

3、

八、（1）安全序列：P2、P1、P3、P4

（2）可以分配，因为分配资源后可找到一安全序列：P2、P1、P3、P4

（3）不能分配，因为request1(1,0,1)＞available(0,1,1)

（4）不能分配，因为分配资源后找不到一安全序列。

九、十：略

十一、（1）安全，因为能找到一个安全序列：A→D→E→B→C。

（2）不能，因为只有进程C提出请求Request(1，2，2，2)，才能满足条件Request（1,2,2,2）<NeedC（2,3,5,6）,假定将资源分配给进程C后，却找不到一个安全序列。

十二、（1）

进程	Allocation	Need	Available
R1	R2	R3	R4	R1	R2	R3	R4	R1	R2	R3	R4
P0	0	0	1	2	0	0	0	0	2	1	0	0
P1	2	0	0	0	0	7	5	0
P2	0	0	3	4	6	6	2	2
P3	2	3	5	4	2	0	5	2
P4	0	3	3	2	0	3	2	0

（2）不存在安全序列

（3）不能满足

十三、（1）页号=INT[4062/1024]=3，页内地址＝4062 MOD 1024=990

（2）因为页表始址为2004B，页表项大小为1个字节，所以，3号页对应的页表地址为2007B，
物理块号为1

（3）可得：物理地址 1*1024+990＝2014B  所存数据为3478

十四、（1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76

20+24+4+36+76+68+64＝292，共移动292柱面，292*3＝876ms

（2）40 → 40 → 44 → 20 → 12 → 4 → 76 → 80

0+4+24+8+8+72+4=120, 共移动120柱面，120*3＝360ms

（3）40 → 40 → 44 → 76 → 80 → 20 → 12 → 4

0+4+32+4+60+8+8＝116，共移动116柱面，116*3＝348ms

or 40 → 40 → 20 → 12 → 4 →44 → 76 → 80

0+20+8+8+40+32+4=112,共移动112柱面，112*3＝336ms

(4) 40 → 40 → 44 → 76 → 80 →4 → 12 → 20

**         ** 0+4+32+4+76+8+8=132, 共移动132柱面，132*3＝396ms

(C-SCAN算法总是从0号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到0号柱面。

约定：按教材的解释，C-SCAN算法磁头只移到每个方向上最远的道上，一旦在当前方向上没有请求了，磁头的移动方向就反过来。****)

十五、所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。

当内存块数量为3时：

  FIFO    1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

1 1  1  4    4  4  6 6  6     3 3  3     2 2     2  6

2 2  2     1 1  1  2 2     2  7 7     7  1    1  1

3 3     3  5 5  5  1    1  1  6    6  6     3  3

发生缺页中断的次数为16。

  LRU    1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

1  1  1 4     4  5 5  5  1    1  7  7    2  2        2

2  2  2    2  2  6 6  6     3 3  3     3 3        3

3  3    1  1  1 2  2     2 2  6     6 1        6

发生缺页中断的次数为15。

十六、（1）SSTF：100→90→80→125→140→160→190→30→25→20→10

SCAN：100→125→140→160→190→90→80→30→25→20→10

（2）SSTF：10+10+45+15+20+30+160+5+5+10＝310

SCAN：25+15+20+30+100+10+50+5+5+10＝270

SCAN更合适。

十七、令内存剩余空闲分区为K，容量为：

1024－（140+80+100+60+50+30+15+20）＝529（KB）

（1）首次适应算法：B → E → K

最佳适应算法：E → B → K

（2）首次适应算法：B → D+E → G → K

最佳适应算法：G → B → D+E → K

（3）首次适应算法：B

最佳适应算法：G

十八、（1）

操作系统	J1	空闲区	J2	J4	空闲区	J3	空闲区
0K	5K	20K	40K	50K	75K	90K	100K	128K

（2）

操作系统	J1	空闲区	J2	空闲区	J3	J4	碎片
0K	5K	20K	40K	50K	90K	100K	125K	128K

（3）

操作系统	J1	空闲区	J3	空闲区
0K	5K	20K			90K	100K	128K

十九、略

二十、FIFO，3块空间

1	2	3	4	1	2	5	1	2	3	4	5
	1		1		1		4		4		4		5		5		5		5		5		5
	2	2	2	1	1	1	1	1	3	3	3
		3	3	3	2	2	2	2	2	4	4
缺3页	4次	5次	6次	7次	8次	9次

FIFO，4块空间

1	2	3	4	1	2	5	1	2	3	4	5
	1		1		1		1		1		1		5		5		5		5		4		4
	2	2	2	2	2	2	1	1	1	1	5
		3	3	3	3	3	3	2	2	2	2
			4	4	4	4	4	4	3	3	3
缺4页	5次	6次	7次	8次	9次	10次

LRU，3块空间

1	2	3	4	1	2	5	1	2	3	4	5
	1		1		1		4		4		4		5		5		5		3		3		3
	2	2	2	1	1	1	1	1	1	4	4
		3	3	3	2	2	2	2	2	2	5
缺3页	4次	5次	6次	7次	8次	9次	10次

LRU，4块空间

1	2	3	4	1	2	5	1	2	3	4	5
	1		1		1		1		1		1		1		1		1		1		1		5
	2	2	2	2	2	2	2	2	2	2	2
		3	3	3	3	5	5	5	5	4	4
				4	4	4	4	4	4	3	3	3
缺4页	5次	6次	7次	8次

二十一、（1）219+430＝649          （2）1327+400＝1727

（3）2300+10＝2310         （4）段内地址500大于段长100，系统给出错误信息

（5）1954+42＝1996         （6）2300+11＝2311

二十二、（1）逻辑地址为 0A5C（H）的页表编址是：

0A5C（H）=0×163+A×162+5×161+C×160=0×163+10×162+5×161+12×160=2652（D）

（2）页号＝INT(2652/1024)=2， 页内地址＝2652 MOD 1024=604

逻辑页地址表为第2#页，页内偏移量为604

（3）对应的物理块号由表中知是第11块，则其物理地址计算为：

11×1024+604=11868（D）=425C（H）

二十三、（1）有效存储区域:(33-22)/2=5.5(CM)，柱面数:40*5.5=220(道)

（2）内层磁道周长：2πR=23.1411＝69.08（CM），

每道信息量：40069.08=27632（位），每面信息量：27632220＝6079040（位），

盘组总容量：6079040*（12-2）＝60790400（位）

（3）平均等待时间：1/（2*50）＝10（MS）

二十四、（1）该文件的第3680个逻辑记录应该存放的位置为：
柱面号：INT （3680/64）＝57
磁道号：INT （（3680
MOD 64）/8）＝4
扇区号：（3680 MOD 64）MOD 8＝0

（2）第78柱面的第6磁道的第6扇区中存放的文件的逻辑记录号为：
7864+68+6＝5046

二十五、1、FCFS：143→86→147→91→177→94→150→102→175→130

总移动距离：57+61+56+86+83+56+48+73+45+＝565

2、SSTF：143→147→150→130→102→94→91→86→175→177

总移动距离：4+3+20+28+8+3+5+89+2＝162

3、SCAN：143→147→150→175→177→130→102→94→91→86

总移动距离：4+3+25+2+47+28+8+3+5＝125

4、C-SCAN:143→147→150→175→177→86→91→94→102→130

总移动距离：4+3+25+2+91+5+3+8+28＝169

二十六、（25－15）×10＝100ms，1/500r/s=2ms，3×（2/8）＝0.75ms，t＝100.75ms

二十七、（1）磁盘转速为6000r/min，即100r/s，则磁盘旋转一周用时：1/100＝10（ms）;

磁头经过每个扇区用时：10/9（ms）,而读出第一条记录后还需2.5ms的时间进行处理后，此时读/写磁头已经在记录D位置，为了顺序处理B记录，必须等待磁盘把B记录旋转到读/写磁头位置下，即要有**（10-2.5）ms=7.5ms**  的延迟时间。

所以处理这9条记录所要花费的时间为：9×（10/9＋2.5）＋8×7.5＝92.5ms

（2）将9条逻辑记录在磁道上的位置重新安排，如下图所示：

左图所示为这9条逻辑记录的最优分布。当读出一条记录后，读/写磁头只需经过5/6ms 的时间便可读出下一条记录，无需花（1）中那么多的延迟时间。根据上图的安排，处理这9条记录所花的时间为：9×（10/9+2.5）+8×5/6=39.2ms。与（1）中所需的处理时间相比，显然经过优化分布后读/写记录所需的时间要来得少，大大缩短了输入/输出操作时间，提高了系统的效率。

二十八、（1）定义一信号量S，初始值为20。
意义：S>0　S的值表示可继续进入售票厅的人数　
　　          S=0　表示售票厅中已有20名顾客(购票者)
　　          S<0　|S|的值为等待进入售票厅的人数　
（2） S=20       P(S)　      V(S)　
（3） S的最大值为20　        S的最小值为20－n

二十九、（1）主函数中填入：F1=0,E1=1,F2=0,E2=1;

（2）M（）函数中填入： P(E1)   V(F1)
R（）函数中填入： P(F2)   V(E2)
Q（）函数中填入： P(F1)   V(E1) 
P(E2)   V(F2)

三十、（1）主函数中填入： S1=1，S2=1；
（2）A（）函数中填入： P(S1)   V(S1)
     B（）函数中填入： P(S2)   V(S2)
     C（）函数中填入： P(S1)   V(S1) 
     D（）函数中填入： P(S2)   V(S2)

三十一、main ( )

{int mutex=1,apple=orange=0;

cobegin{    father ( );

mother ( );

daughter ( );

son ( );  }

}


三十二、（1）执行顺序为：EDCBA；平均周转时间为：（10+18+24+28+30）/5＝22分

（2）

平均周转时间为：（2+12+20+26+30）/5＝18分

（3）执行顺序为：CDBEA；平均周转时间为：（6+14+18+28+30）/5＝19.2分

（4）执行顺序为：ABCDE；平均周转时间为：（2+6+12+20+30）/5＝14分