001-操作系统原理

[键入文字]

三、操作系统策略、算法描述与应用题

1、动态页面置换算法应用题

在采用分页管理进程分配存储空间时，假设某程序共有5个虚页内容，而在运行时只分配到了三个页面；初始时页面为空，页面访问顺序为4，3，2，1，4，3，5，4，3，2，1，5。请测算使用OPT和LRU页面置换算法管理页面分配时，分别会出现怎样的缺页状况。给出缺页分配页面的具体描述过程及缺页次数。

★考核知识点:分页管理页面置换算法。P228-232 中关于OPT、LRU置换法的原理。

答：根据教程中页面置换算法一节描述（P228-232），经测算该题目中采用OPT置换法将出现7次缺页中断；采用LRU置换法将出现10次缺页中断。参考相关描述画出置换算法图表。

2、动态页面置换算法应用题

假设某程序在内存中被分配到了三个页面，初始页面为空，页面走向为3，2，1，5，1，4，2，3，4，2，1，5。请完成以下工作：

（1）使用OPT页面置换算法分配时，将出现几次缺页，用图表方式给出置换步骤。 （2）使用 LRU页面置换算法分配时，将出现几次缺页，用图表方式给出置换步骤。

★考核知识点:分页管理页面置换算法。P228-232 中关于OPT、LRU置换法的原理。

答：

（1）采用OPT将出现8次缺页中断；

3 2 1 5 1 4 2 3 4 2 1 5 3 x 2 3 x 1 2 3 x 5 1 2 x 1 5 2 v 4 1 2 x 2 4 1 v 3 2 4 x 4 3 2 v 2 4 3 v 1 2 4 x 5 1 4 x

（2）采用LRU将出现9次缺页中断。

3 2 1 5 1 4 2 3 4 2 1 5 3 x

2 3 x 1 2 3 x 5 1 2 x 1 5 2 v 4 1 5 x 2 4 1 x 3 2 4 x 4 3 2 v 2 4 3 v 1 2 4 x 5 1 2 x 17

[键入文字]

3、目录管理结构应用题

根据以下文字描述构建出该文件系统的目录树形结构

请按照以下的文字描述画出一棵文件目录树形结构，并说明对该树形结构应采取几级目录结构方式进行管理？在管理中是否能实现文件重名控制？描述如下： 系统中有一个根节点，在根节点下有三个顶级节点zhao、qian、sun；在节点zhao下有文件z-file1、zfile2及一个子目录节点z-sub；在节点qian下存在有文件节点q-file1、q-file2、q-file3；在节点sun下包含有子目录节点s-sub1 s-sub2及文件s-file1 s-file2。

★考核知识点:目录树形结构。P248-249。

答：

根据题意描述构建出以下文件目录树形结构：

根目录根目录 zhaozhaoqianqiansun sun Z-sunZ-sunZ-file1Z-file1Z-file2Z-file2s-sub1s-sub1S-sub2S-sub2S-file1S-file1s-file2s-file2Z-file2Z-file2Z-file2Z-file2Z-file2Z-file2

4、操作系统知识阐述题

理解操作系统对多进程做并发管理的原理，回答以下问题： 1. 系统会对什么样的进程做挂起操作？ 2. 系统将进程挂起的意义是什么？

3. 画出单挂起进程模型图，并用文字对该模型图做必要的解释。

★考核知识点:进程挂起意义及模型。P105。

答：

1）在进程管理中，当内存空间变小又要保证多个进程并发执行时，系统会选择一些进程做挂起操作，这些进程通常是那些暂时无法运行的进程，选择时需要使用选择算法来完成。 2）这样做的意义是，将那些暂时不运行的进程换出内存即保存到外存的交换区中，将有限

18

[键入文字]

的内存让给更需要的进程使用，保证并发执行能够进行下去。 3）单挂起进程模型如下：

新建 允许就绪 事件 分派 超时 运行 释放 退出 激活 发生 事件 等待 挂起

挂起起 阻塞 在该单挂起模型中是指，当进程阻塞时间比较长时就会被挂起，而进程挂起后被保存在交换区中，只有当该进程再次被激活时才可以进入就绪态；其它状态转换过程与五状态进程模型相似。

5、进程调度中通常需要计算出进程的优先级，请根据UNIX系统V的进程优先数计算公式（见教程P1987.6.3）分析并描述以下问题： （1） 解释该公式包含项的意义；

（2） 说明在进程调度过程中，该公式对不同进程将如何控制； （3） 说明该调度策略为什么能满足分时系统的调度特性。

★考核知识点:进程调度算法理解。P198。

答案：

1）优先数计算公式：

P-pri= P-cpu/2+PUSER+P-nice+NZERO 其中：

? PUSER，NZERO—是优先数基值；

? P-cpu—是每个进程最近一次使用 CPU的时间； ? P-nice—是用户设置的进程优先数偏置值。

2）利用该公式计算进程优先级时，对于新建进程，由于P-cpu/2项为0，所以优先数最小，则优先级最高，会很快得到调度；而随着进程被调度，P-cpu项增大，它的优先级会减低，

19

[键入文字]

因此它会被其他进程抢占处理器使用权；随着进程的等待P-cpu/2值会减少，进程又有可能占用处理器。

3）由于分时系统强调的是进程的及时交互性，该公式计算结果总是将新进程的优先级置成最高，因此新进程总能被最快地调度，所以该公式满足分时系统调度特性。

6、磁盘管理调度算法应用

在磁盘调度中，假定当前磁头臂处于第10号柱面处，目前有６个进程正在请求访问磁盘，它们的请求顺序如下表所示，现在磁头正从小柱面向大柱面方向移动。请根据磁盘调度管理原理，按照以下调度算法分别计算出磁盘的柱面访问序列。 1）根据短查找时间优先算法，给出柱面访问序列. 2）根据扫描算法，给出柱面访问序列。

请求序号 柱面号 磁头号 扇区号 （１） ９ ６ ３ （２） ７ ５ ６ （３） １５ ２０ ６ （４） ９ ４ ４ （５） ２０ ９ ５ （６） ７ １５ ２

★考核知识点:磁头调度算法应用。P306-307。 答：

1）短查找时间优先的访问序列为：1，2，4，6，3，5

2）扫描法向大磁道方向移动时的访问序列为：3，5，4，1，6，2

7、在设计文件管理的目录结构时，采用二级目录结构与采用一级目录结构相比有何主要优势呢？

★考核知识点:目录树形结构。P248-249。

20