操作系统练习题答案

get ( )

{ while (采集工作未完成) {采集一个数据；

P（Se）;

将数据送入缓冲区中； V (Sf ); } }

compute ( )

{ while (计算工作未完成) { P (Sf )

从缓冲区中取出数据；

V(Se )

进行数据计算； } }

2. 假定磁盘块的大小为1k，对于540M的硬盘，其文件分配表FAT需要占用多少存储空间？当硬盘容量为1.2G时，FAT需要占用多少空间？

解： 由题目条件可知，硬盘大小为540M，磁盘块大小为1K,所以硬盘共有盘块： 540M / 1K=540 K (个) 又 512K< 540K < 1024K

故 540K 个盘块号要用20位二进制表示，即文件分配表的每一个表目为2.5个自

节。FAT要占用的存储空间总数为： 2.5×540K=1350K 当硬盘大小为1.2G, 硬盘共有盘块 1.2G/ 1K = 1.2M（个） 又 1M< 1.2M <2M

故 1.2M 个盘块号要用31位二进制表示，为方便文件分配表的存取，每一个表目用32位二进制表示，即文件分配表的每个表目大小为4 个字节。

FAT 占用的存储空间总数为：4×1.2M=4.8M

3. 在一个分页存储系统中，页面大小为4kB，系统中的地址寄存器占24位，给定页表如下所示，现给定一逻辑地址，页号为3，页内地址为100，试计算相应的物理地址，并画图说明地址变换过程。 页表

解：相应的物理地址为：4096×7＋100＝28772 地址变换过程如下图：

控制寄存器

页表长度 页表地址 3 100 有效地址

页表 页号 块号 0 3 一—5 页号 0 1 2 3 块号 3 4 9 7 1 2 3 4 9 7 7 100 ···

··· 4. 已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2个物理块，当采用先进先出页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰策略是当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又是多少？

解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下表：

页面走向 物理块1 物理块2 缺页 1 2 1 3 1 2 4 2 1 3 4 1 1 1 3 3 2 2 2 1 1 4 缺 2 缺 2 2 缺 1 缺 1 缺 4 缺 4 4 缺 3 缺 3 缺 从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。

若采用后一种页面淘汰策略，其页面置换情况如下：

页面走向 物理块1 物理块2 缺页 1 2 1 3 1 2 4 2 1 3 4 1 1 1 3 1 1 1 1 1 3 4 缺 2 缺 2 2 缺 2 缺 2 4 缺 2 缺 2 2 缺 2 缺 从上述页面置换图可以看出：页面引用次数为11次，缺页次数为8次，所以缺页率为8/11。

5．请画出分页情况下（含快表）地址变换过程，并指出页面尺寸为什么必须是2的幂？

因为计算机内部的代码是二进制，将页面尺寸设为2的幂，为的是方便计算页号，进行地址变换将逻辑地址转换为物理地址。 地址变换图略

6.在一单道批处理里系统中，一组作业的提交时间和运行时间如下表所示：试计算一下三种作业调度算法的平均周转时间T和平均带权周转时间W。 ①先来先服务 ② 短作业优先 ③ 响应比高优先

作业 1 2 3 4 提交时间 8．0 8．5 9．0 9．1 运行时间 1．0 0．5 0．2 0．1 解：作业I的周转时间Ti ＝ 作业I的提交时间－作业I的完成时间

＝ 作业I的运行时间＋作业I的等待时间

作业I的带权周转时间Wi＝Ti / 作业I的运行时间 作业I的平均周转时间T ＝1 / n * ∑ Ti ， 作业I的平均带权周转时间 W ＝1 / n * ∑Wi

（1） 采用先来先服务（FCFS）调度算法的运行情况如下表所示：

先来先服务算法下的作业运行情况表

作业次序 提交时间 运行时间 等待时间 开始时间 完成时间 周转时间 带权周转时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.2 0.1 0 0.5 0.5 0.6 8.0 9.0 9.5 9.7 9.0 9.5 9.7 9.8 1.0 1.0 0.7 0.7 1.0 2.0 3.5 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）采用短作业优先（SJF）调度算法的作业运行情况如表：

短作业优先算法下的作业运行情况表 作业次序 提交时间 运行时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.2 0.1 0.5 0 0 0.1 0.8 8.0 9.0 9.2 9.3 9.0 9.2 9.3 9.8 1.0 0.2 0.2 1.3 等待时间 开始时间 完成时间 周转时间 带权周转时间 1.0 1.0 2.0 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）采用响应比高者优先(BRN) 调度算法时作业运行情况如下表：

响应比高优先算法下的作业运行情况表 作业次序 提交时间 运行时间 1 2 3 4 8.0 8.5 9.0 9.1 1.0 0.5 0.1 0.2 0 0.5 0.4 0.6 8.0 9.0 9.5 9.6 9.0 9.5 9.6 9.8 1.0 1.0 0.5 0.8 等待时间 开始时间 完成时间 周转时间 带权周转时间 1.0 2.0 5.0 4.0 作业平均周转时间 作业平均带权周转时间

T=( 1.0+1.0+0.5+0.8)/4=0.825 W=(1.0+2.0+5.0+4.0)/4=3 7. 某系统的进程状态转换图如下所示。请说明：

① 引起各种状态转换的典型事例有哪些？

在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？

③ 试说明是否会发生下述因果转换：2—〉1 ， 3—〉2 ，4—〉1。

执行 ② 当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一进 2 1 3 阻塞 4 就绪 程作一次状态转换。解 ：(1)在本题所给的进程状态转换图中，存在四种状态转换。当进程调度程序从就绪队列中选取一个进程投入运行时引起转换1；正在执行的进程如因时间片用完而北暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行（如 进程请求完成I/O）则会引起转换3；当进程等待的事件发生时（I/O完成）则会引起转换4。

（2）如果就绪队列非空，则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的

一—7

进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入运行，因此只要就绪队列非空，一个进程的转换3能立即引起另一个进程的转换1。

（3）所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个称为果，这两个

转换称为因果转换。当然这种因果关系并不是什么时候都能发生的，而是在一定条件下才会发生。

2――1 当某进程发生转换2时，就必然引起另一进程的转换1，因为当发生转换2时，正在执行的进程从执行状态变为就绪状

态，进程调度程序必然会从就绪队列中选取一个进程投入运行，即发生转换1

3――2 某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前执行进程从执行状态变为阻塞状态，不可能又从执

行状态变为就绪状态。

4――1 当处理机空闲且就绪队列为空时，某一进程的转换4就会引起该进程的转换1。因为此时处理机空闲，一旦某个进程发生转换4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。

8. 某页式管理系统的主存容量为64kb，被分成16块，其块号为0、1、……、15，设某作业有4页，其页号是0、1、2、3，被分别装入主存的2、4、1、5块中，试问：该作业的总长度（字节）是多少？请写出该作业每一页主存中的起始地址。 解：（1）64/4=64KB ,即主存一块长度为4kb＝16kb。

（2）该作业每一页在主存中的起始地址分别为：4kb×2＝8kb,4kb×4＝16kb, 4kb×1＝4kb, 4kb×5＝20kb。

4kb×4