操作系统课设08554

《操作系统课设08554》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、西安工业大学信息与计算科学0级《操作系统实验》课程设计报告题目:页面置换方法班级：101002学号：091002107姓名：时间：2013/01ZL0【课设题目】:设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率【课设任务】：要求设计主界面以灵活选择某算法，但以下算法都要实现1）先进先出算法（FIFO）2）最近最久未使用算法（LRU）3）最佳置换算法（OPT）【课设目的】：1、用C语言编写OPT、FIFO、LRU三种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案是算法得以模拟实

2、现。【主要思想儿先进先出算法（FIFO）最简单的页而置换算法是先进先出（FIFO）法。这种算法的实质杲，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停附得最久，结果它们因变“老”而不得不被置换出去。FIFO的另-•个缺点是，它有一种异常现象，即在增

3、加存储块的情况下，反而使缺页中断率增加To当然，导致这种异常现象的页而走向实际上是很少见的。最近最久未使用算法（LRU）FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的吋间长短作为置换依据，而OPT算法的依据是将来使用页面的吋间。如果以最近的过去作为不久将来的近似,那么就可以把过去戢长一段吋间里不曾被使川的页面置换掉。它的实质是，当需要置换一页时,选择在最近一段时间里最久没有使用过的页血予以置换。这种算法就称为最久未使用算法（LeastRecentlyUsed,LRU）。LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，L

4、RU算法选择过去一段时间里最久未被使用的页而。LRU算法是经常釆用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硕件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页而时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页血最后访问的"时间”。在置换贞面时，选择该时间值最小的贞面。这样做，不仅要杳页表，而且当页表改变时（因CPU调度）要维护这个

5、页表中的时间，还要考虑到时钟值溢出的问题。（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一-來，栈顶总是放有冃前使用最多的页，而栈底放着冃前最少使用的页。由于要从栈的中间移走一项，所以要丿TJ具有头尾指针的双向链连起来。在最坏的悄况下，移走-•页并把它放在栈顶上需要改动6个指针。每次修改那要有开销，但需要置换哪个页而却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。因实现LRU算法必须有大量硬件支持，述需耍一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。—•种LRU近似算法是最近未使川算法（NotRec

6、entlyUsed,NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问吋，由破件将该位置1。过一段时间后，通过检杳这些位对以确定哪些页使用过，哪些页自上次置0后还未使用过。就町把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。最佳置换算法（OPT）最佳置换（OptimalReplacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将來不再被使用，或者是在最远的将來才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页而置换算法的实现是困难的，因为它需

7、要人们预先就知道一个进程整个运行过程屮页血走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。【设计方案】：根据算法的思想：程序开始时，输入所冇的页面号，选择算法，OPT算法用一个一维的数组来实现，LRU与OPT基本一样，前者是向前看的而后者则是向后看的。FIFO则用队列来实现，很显然，先进先出是队列的主要特征。按照所选的算法能得到相应的结果。输出时要有命中率，同时输出发生置换的物理块。可以用switch语句来实现大体框架，分别用三种算法作为函数来调用。【算法流程图】：1.FIFO（先进先出）算法▼选择物理块中距离该页农Z询最远

8、的一页表与