操作系统实验指导书

中断”信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

(3) 设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“*该页页号”，表示产生了一次缺页中断。该模拟程序的算法如图4-1。

(4) 假定主存的每块长度为128个字节；现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存；该作业的页表为： 页号 标志 主存块号 在磁盘上的位置 0 1 5 011 1 1 8 012 2 1 9 013 3 1 1 021 4 0 022 5 0 023 6 0 121 图4-1 地址转换模拟算法

如果作业依次执行的指令序列为： 操作 页号 单元号 + 0 070 + 1 050 2 015 ? 3 021 存 0 056 取 - 6 040

24

操作 移位 + 存 取 + 存 页号 4 5 1 2 4 6 单元号 053 023 037 078 001 084 运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。

第二题：用先进先出（FIFO）页面调度算法处理缺页中断。 [提示]：

(1) 在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。

(2) FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。例如：

P[0]，P[1]?，P[m-1]

其中每一个P[i] (i=0, 1, ?, m-1) 表示一个在主存中的页面号。它们的初值为：

P[0]： =0, P[1]： =1, ?, P[m-1]： =m-1

用一指针K指示当要装入新页时，应淘汰的页在数组中的位置，K的初值为“0”。

当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行： P[k]： =要装入页的页号 k： = (k+1) mod m

再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。

(3) 编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：

页号 标志 主存块号 修改标志 在磁盘上的位置

由于是模拟调度算法，所以，不实际地启动调出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。

把第一题中程序稍作改动，与本题结合起来，FIFO页面调度模拟算法如图5-2。

(4) 如果一个作业的副本已在磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。于是增加了“修改标志”后的初始页表为：

页号 标志 主存块号 修改标志 在磁盘上的位置 0 1 5 0 011 1 1 8 0 012 2 1 9 0 013 3 1 1 0 021 4 0 0 022 5 0 0 023 6 0 0 121

按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执

25

行了最后一条指令后的数组P的值。

(5) 为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

图5-2 FIFO页面调度模拟算法

第三题：用最近最少用（LRU）页面调度算法处理缺页中断。 [提示]：

(1) 在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用LRU页面调度算法把该作业中距现在最久没有被访问过的一页调出，存放到磁盘上。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。

(2) LRU页面调度算法总是淘汰该作业中距现在最久没被访问过的那页，因此可以用一个数组来表示该作业已在主存的页面。数组中的第一个元素总是指出当前刚访问的页号，因此最久没被访问过的页总是由最后一个元素指出。如果主存只有四块空闲块且执行第一题中

26

提示（4）假设的指令序列，采用LRU页面调度算法，那么在主存中的页面变化情况如下：

3 0 6 4 5 1 2 4 6 2 3 0 6 4 5 1 2 4 1 2 3 0 6 4 5 1 2 0 1 2 3 0 6 4 5 1 当产生缺页中断后，操作系统总是淘汰由最后一个元素所指示的页，再把要访问的页装入淘汰页所占的主存块中，页号登记到数组的第一个元素中，重新启动刚才那条指令执行。

(3) 编制一个LRU页面调度程序，为了提高系统效率，如果淘汰的页在执行中没有修改过，则可不必把该页调出。参看第二题中提示（3）。模拟调度算法不实际地启动调出一页和装入一页的程序而用输出调出的页号和装入的页号来代替。把第一题中程序稍作改动，与本题结合起来，LRU页面调度模拟算法如图5-3。

图5-3 LRU页面调度模拟算法

27

(4) 按第一题中提示（4）的要求，建立一张初始页表，页表中为每一页增加“修改标志”位（参考第二题中提示（4））。然后按依次执行的指令序列，运行设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后数组中的值。

(5) 为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

五、思考题

(1) (2) (3) (4)

先进先出页面调度算法的思想？

最近最少用（LRU）页面调度算法思想？

比较两种调度算法的效率（哪种调度算法使产生缺页中断的次数少）？ 分析在什么情况下采用哪种调度算法更有利？

六、实验报告

(1) 实验题目（第二题或第三题）。

(2) 程序中使用的数据结构及符号说明。 (3) 打印一份源程序并附上注释。

(4) 打印初始页表、每次调出（要调出一页时）和装入的页号、执行最后一条指令后在主存中的页面号（即数组的值）。

参考资料

(1)《计算机操作系统》（修订版），汤子瀛等编，西安电子科技大学出版社，2001-8。 (2)《<计算机操作系统>学习指导与题解》,汤子瀛等编, 西安电子科技大学出版社,2003-3。

28