操作系统 课后答案(1)(11)

37

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

答：使磁盘的旋转圈数为最少的调度次序为：5、3、2、1、和4。

6 有一具有40个磁道的盘面，编号为0~39，当磁头位于第11磁道时，顺序来到如下

磁道请求：磁道号：1、36、16、34、9、12；试用1）先来先服务算法FCFS、2）最短查找时间优先算法SSTF、3）扫描算法SCAN等三种磁盘驱动调度算法，计算出它们各自要来回穿越多少磁道？ 答：1)FCFS为111。 2)SSTF为61。 3)SCAN为60(先扫地址大的请求)，为45(先扫地址小的请求)。

7 假定磁盘有200个柱面，编号0~199，当前存取臂的位置在143号柱面上，并刚刚

完成了125号柱面的服务请求，如果请求队列的先后顺序是：86，147，91，177，94，150，102，175，130；试问：为完成上述请求，下列算法存取臂移动的总量是多少？并算出存取臂移动的顺序。 (1)先来先服务算法FCFS；

(2)最短查找时间优先算法SSTF； (3)扫描算法SCAN。 (4)电梯调度。 答：(1)先来先服务算法FCFS为565，依次为143-86-147-91-177-94-150-102-175-130。

(2)最短查找时间优先算法SSTF为162，依次为143-147-150-130-102-94-91-86-175-177。

(3)扫描算法SCAN为169，依次为143-147-150-175-177-199-130-102-94-91-86。 (4)电梯调度为125(先向地址大的方向)，依次为143-147-150-175-177-102-94-91-86。为148(先向地址小的方向) 依次为143-130-102-94-91-86-147-150-175-177。

8

除FCFS外，所有磁盘调度算法都不公平，如造成有些请求饥饿，试分析：(1)为什么不公平？(2)提出一种公平性调度算法。(3)为什么公平性在分时系统中是一个很重要的指标？

答：(1)对位于当前柱面的新请求，只要一到达就可得到服务，但对其他柱面的服务则不

然。如SSTF算法，一个离当前柱面远的请求，可能其后不断有离当前柱面近的请求到达而得不到服务(饥饿)。

(2)可划定一个时间界限，把这段时间内尚未得到服务的请求强制移到队列首部，并标记任何新请求不能插到这些请求前。对于SSTF算法来说，可以重新排列这些老请求，以优先处理。

(3)可避免分时进程等待时间过长而拉长响应时间。

9

若磁头的当前位置为100柱面，磁头正向磁道号减小方向移动。现有一磁盘读写请求队列，柱面号依次为：190，10，160，80，90，125，30，20，29，140，25。若采用最短寻道时间优先和电梯调度算法，试计算出各种算法的移臂经过的柱面数？

答：采用SSTF处理次序为：100-90-80-125-140-160-190-30-29-25-20-10，总柱面数为：310。采用电梯调度处理次序为：100-90-80-30-29-25-20-10-125-140-160-190，总柱面数为：270。

38

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

10 若磁头的当前位置为100柱面，磁头正向磁道号增加方向移动。现有一磁盘读写请求队

列，柱面号依次为：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出各种算法的移臂经过的柱面数？

答：采用先来先服务处理次序为：100-23-376-205-132-19-61-190-398-29-4-18-40，总柱

面数为：1596。

采用SSTF处理次序为：100-132-190-205-61-40-29-23-19-18-4-376-398，总柱面数为：700。

采用SCAN处理次序为：100-132-190-205-376-398-61-40-29-23-19-18-4，总柱面数为：692。

CH6 应用题参考答案

1. 磁带卷上记录了若干文件，假定当前磁头停在第j个文件的文件头标前，现要按名

读出文件i，试给出读出文件i的步骤。 答：由于磁带卷上的文件用“带标”隔开，每个文件的文件头标前后都使用了三个带标。

文 文 文 文 件 件 件 件 ? * 头 * 文件体 * 尾 * ? * 头 * 文件体 * 尾 * 标 标 标 标 ?

正常情况磁头应停在文件头标的前面，所以，只要计算带标的个数，就可找到所要文件。

1)当i≧j时，要正走磁带，

步1 组织通道程序正走磁带，走过“带标”个数为3×(i-j)个。 步2 组织通道程序读文件i的文件头标。

步3 根据文件i的文件头标信息，组织读文件信息。

2)当i

步1 组织通道程序反走磁带，走过“带标”个数为3×(j-i)+1个。 步2 组织通道程序读文件i的文件头标。

步3 根据文件i的文件头标信息，组织读文件信息。

2. 假定令B=物理块长、R=逻辑记录长、F=块因子。对定长记录(一个块中有整数个逻

辑记录)，给出计算F的公式。 答：F=[B/R]。

3. 某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，

试问：(1)位示图需多少个字? (2)第i字第j位对应的块号是多少? (3)并给出申请/归还一块的工作流程。 答： (1) 位示图占用字数为500/32=16(向上取整)个字。

39

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

(2) 第i字第j位对应的块号N=32×i+j。

(3)申请时自上至下、自左至有扫描位示图跳过为1的位，找到第一个迁到的0位，根据它是第i字第j位算出对应块号，并分配出去。归还时已知块号，块号/32算出第i字第j位并把位示图相应位清0。

4. 若两个用户共享一个文件系统，用户甲使用文件A、B、C、D、E；用户乙要用到

文件A、D、E、F。己知用户甲的文件A与用户乙的文件A实际上不是同一文件；甲、乙两用户的文件D和E正是同一文件。试设计一种文件系统组织方案，使得甲、乙两用户能共享该文件系统又不致造成混乱。 答：可以采用二级目录或树形目录结构来解决难题。例如，

用户甲文件目录

文件名 物理地址

B C 文件

主文件目录 A

D 用户名 文件目录始址E 甲 文件 用户乙文件目录 …… 乙 …… …?… 文件名 物理地址 文件 D

E

文件 A F

5. 在UNIX 中，如果一个盘块的大小为1KB，每个盘块号占4个字节，即每块可放

256个地址。请转换下列文件的字节偏移量为物理地址：(1)9999；(2)18000；(3)420000。

答： 步1 将逻辑文件的字节偏移量转换为文件的逻辑块号和块内偏移。方法是：将逻辑文件的字节偏移量/盘块大小，商为文件的逻辑块号，余数是块内偏移。

步2将文件的逻辑块号转换为物理块号。使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应物理块号。

(1) 9000 L1=INT(9999，1024)=9 B1=MOD(9999，1024)=783 其逻辑块号为9，故直接索引addr[8]中可找到物理块号。

(2) 18000 L2=INT(18000，1024)=17 B1=MOD(18000，1024)=592 其逻辑块号为17，通过一次间接索引addr[10]中可找到物理块号。

(3) 420000 L1=INT(420000，1024)=410 B1=MOD(9000，1024)=160 其逻辑块号为410，通过二次间接索引addr[11]中可找到物理块号。

40