操作系统原理实验三：页面调度算法程序

实验三：页面调度算法程序

课程名称：操作系统原理
项目名称：页面调度算法程序
实验（实训）类型：验证性实验
实验（实训）课时：2

[目的和要求]

目的：

加深对请求页式存储管理实现原理的理解，掌握页面置换算法。

1. 进一步理解页面调度算法的相关内容
2. 明白页面调度的主要内容
3. 通过编程掌握页面调度的主要算法

要求：

页式虚拟存储器实现的一个难点是设计页面调度(置换)算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度(置换)算法，加深对页面思想的理解。

具体要求为：
1、假设分给一作业的内存块数为4,每个页面中可存放10条指令
2、用C语言设计一个程序，模拟一作业的执行过程。设该作业共有320条指令，即它的地址空间为32页，目前它的所有页面都还未调入内存。

[内容与步骤]

在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。

内容：

1先入先出法(FIFO)

最简单的页面置换算法是先入先出(FIFO)法。这种算法的实质是，总是选择在主存中停留时间最长(即最老)的一页置换，即先进入内存的页，先退出内存。理由是:最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

2最优置换算法(OPT)

最优置换(Optimal Replacement)是在理论上提出的一种算法。 其实质是:当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。
但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量(如通过模拟实验分析或理论分析)其他算法的优劣。

3最久未使用算法(LRU)

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换–页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法(Least Recently Used, LRU)。
LRU算法是与每个页面最后使用的时间有关的。当必须置换–个页面时，选择过去–段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在的问题。LRU算法需要实际硬件的支持。

步骤：

(1)计数器。

最简单的情况是使每个页表项对应一-个使用时间字段，并加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小样做，不仅要查页表，而且当页表改变时(因CPU调度)要维护这个页表还要考虑到时钟值溢出的问题。

(2)栈。

用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放这样–来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，哪个页面却可直接得到，用不着查找，因为尾指针指向栈底。

[主要器材与工具]

Windows xp、VMware、 I inux系统