先进先出报告.doc

摘 要FIFO算法是最简单的的页面置换算法，在实现时，对应的每一个页面需要有一个调入时间，该时间可设置在内存中并用软件记录，但最好设置在寄存器中并使用硬件记录。当内存空间紧张时，调入时间最早的页面将被淘汰。FIFO算法也可以这样实现：由操作系统维护一个所有当前在内存中的页面的链接，最新进入的页面放在表尾，最先进入的放在表头，当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。除了链指针外，还可以用表格等方法来实现。关键词：页面置换 FIFO 缺页率 Java目 录一、设计题目二、设计内容三、设计过程3.1需求分析3.2概要设计3.3详细设计3.4代码实现3.5程序运行四、总结五、参考文献一、 设计题目先进先出算法。二、设计内容先进先出算法的实现三、设计过程3.1需求分析拥有页面交换机制的操作系统总是把当前进程中急需处理的部分页面换入到内存当中，而把更多暂时不需要的页面置换算法放置在外存当中。由于进程需要处理的页面顺序不同，因此必须要在内存与外存之间进行交换，交换算法也叫应运而生。本设计并没有进入系统空间对实际进程页面进行控制，而是在用户空间用线性表的连续存储方式对进程页面交换进行的模拟。 3.2实验内容给定页面地址流。使用VC开发模拟程序，模拟在不同实页情况下，FIFO和LRU置换算法对实页的使用情况，假定访问实页的时间为 ，访问辅存的时间为100 计算并在屏幕上输出对应该页地址流在不同实页数和置换算法的情况下的访问时间。多次更改页地址流，重复上述操作，记录时间，观测在FIFO和LRU算法下访问时间和实页数的关系。根据结果理解堆栈型算法。（一） 给定页地址流：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1（二） 用堆栈法画图计算该页地址流在1-5个实页情况下，使用FIFO和LRU算法的页面命中情况并计算所需时间： （三） 程序设计 FIFO算法可以用队列来模拟，对页面的访问可以用定时器来模拟。LRU算法可以用堆栈来模拟。程序应该包括一个虚页面队列，该队列用于保存页地址流；一个LRU调度器类用于模拟LRU调度；一个FIFO调度器类用于模拟FIFO调度；一个对话框用于显示调度结果。1、 页面地址流保存在页面队列中。2、 构造LRU调度器类，该类中包含一个长度为n的堆栈，n表示实页数，该值从1到k（不同的虚页数）循环；可以通过类构造函数传入n。包含一个记数值记录访问时间，记数值初始为0。3、 构造FIFO调度器类，该类中包含一个长度为n的堆栈，n表示实页数，该值从1到k（不同的虚页数）循环；可以通过类构造函数传入n。包含一个记数值记录访问时间，记数值初始为0。4、 用定时器模拟页面访问，每个时间片从虚页面队列中取出一个虚页号，通过LRU调度器类和FIFO调度器类的对应接口函数将该虚页作为参数传入。5、 LRU类的接口函数实现如下功能：用传入的虚页号遍历堆栈，查找与之一致的记录，如果有则表示命中，将对应的虚页号压入堆栈直到覆盖原记录。并将记数值加1。如为查到表示未命中，将对应的虚页号压入堆栈直到堆栈尾，并将记数值加100。6、 FIFO类的接口函数实现如下功能：用传入的虚页号遍历堆栈，查找与之一致的记录，如果有则表示命中，将记数值加1。如为查到表示未命中，将对应的虚页号压入堆栈直到堆栈尾，并将记数值加100。7、 程序初始化时创建n个FIFO类对象和n个LRU类对象，其堆栈大小分别从1-n。8、 虚页队列空表示模拟完成，提前n个FIFO类对象和n个LRU类对象中的记数值和相应参数，在显示对话框中输出并打印。9、 与（二）中的结果进行比对。（四） 使用多个不同的页地址流多次进行模拟，并保存每次模拟的结果。（五） 对结果进行分析，判断两种调度算法的优劣，判断其中那种算法是堆栈型算法。3.3详细设计1.原代码public class Page int history;/记录加入时间 int num;/记录叶号 public Page(int num) history = 0; this.num = num; public String toString() return +this.num; public class FIFO public static void main(String args) FIFO f = new FIFO(); Page p = new Page3; int a = 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1; Page pt = new Pagea.length; for(int i = 0;i pt.length;i+) pti = new Page(ai); for(int i = 0 ;i pt.length;i+) /交换处理 f.changePage(p, pti); private void historyAdd(Page p) /历史记录加一 for(int i = 0;i p.length;i+) if(pi != null) pi.history+; private void print(Page p) for(int i = 0;i p.length;i+) if(pi != null) System.out.print(pi); else System.out.print( ); System.out.println(); private void changePage(Page p,Page pa) /做处理 交换 for(int i = 0;i p.length;i+) /检查是否有空余的，在空挡处加入 if(pp.length-1 != null) break; if(pi = null) pi = pa; this.historyAdd(p); this.print(p); return; for(int i = 0;i p.length;i+) /检查是否出现相同的叶号 ，不作处理 if(pi.num = pa.num) System.out.println(*); return; for(int i = 0;i 159只执行一条指令；(7)重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部160条指令。 3.6 基本原理考虑到如果某一调入内存的页没有被修改过，则不必将它拷回到磁盘。于是在改进的Clock增加了一个M位， M=0 表示该页未被修改过。这样我们选择页面换出时，既要最近未访问过的页面，又要未被修改过的页面。其执行过程分一下三步： 第一步：从开始位置循环扫描队列，寻找A=0、M=O的第一类面，找到立即置换。另外，第一次扫描期间不改变访问位A。第二步：如果第一步失败，则开始第二轮扫描，寻找A=0且M=1的第二类页面，找到后立即置换，并将所有扫描过的A都置0。第三步：如果第二步也失败，则返回指针开始位置，然后重复第一步，必要时再重复第二步，此时必能找到淘汰页。当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果该页面没有被修改过（如一个包含程序正文的页面），那么它在磁盘上的副本已经是最新的，不需要回写。直接用调入的页面覆盖掉被淘汰的页面就可以了。 当发生缺页中断时，虽然可以随机地选择一个页面来置换，但是如果每次都选择不常使用的页面会提升系统的性能。如果一个被频繁使用的页面被置换出内存，很可能它在很短时间内又要被调入内存，这会带来不必要的开销。人们已经从理论和实践两个方面对页面置换算法进行了深入的研究。下面我们将介绍几个最重要的算法。有必要指出，“页面置换”问题在计算机设计的其他领域中也会同样发生。例如，多数计算机把最近使用过的32字节或64字节的存储块保存在一个或多个高速缓存中。当这些高速缓存存满之后就必须选择一些块丢掉。除了花费时间较短外（有关操作必须在若干纳秒中完成，而不是像页面置换那样在微秒级上完成），这个问题同页面置换问题完全一样。之所以花费时间较短，其原因是丢掉的高速缓存块可以从内存中获得，而内存既没有寻道时间也不存在旋转延迟。第二个例子是Web服务器。服务器可以把一定数量的经常访问的Web页面存放在存储器的高速缓存中。但是，当存储器高速缓存已满并且要访问一个不在高速缓存中的页面时，就必须要置换高速缓存中的某个Web页面。由于在高速缓存中的Web页面不会被修改，因此在磁盘中的Web页面的副本总是最新的。而在虚拟存储系统中，内存中的页面既可能是干净页面也可能是脏页面。除此之外，置换Web页面和置换虚拟内存中的页面需要考虑的问题是类似的。在接下来讨论的所有页面置换算法中都存在一个问题：当需要从内存中换出某个页面时，它是否只能是缺页进程本身的页面？这个要换出的页面是否可以属于另外一个进程？在前一种情况下，可以有效地将每一个进程限定在固定的页面数目内；后一种情况则不能。这两种情况都是可能的。在3.5.1节我们会继续讨论这一点。很容易就可以描述出最好的页面置换算法，虽然此算法不可能实现。该算法是这样工作的：在缺页中断发生时，有些页面在内存中，其中有一个页面（包含紧接着的下一条指令的那个页面）将很快被访问，其他页面则可能要到10、100或1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。最优页面置换算法规定应该置换标记最大的页面。如果一个页面在800万条指令内不会被使用，另外一个页面在600万条指令内不会被使用，则置换前一个页面，从而把因需要调入这个页面而发生的缺页中断推迟到将来，越久越好。计算机也像人一样，希望把不愉快的事情尽可能地往后拖延。这个算法惟一的问题就是它是无法实现的。当缺页中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问。（在最短作业优先调度算法中，我们曾遇到同样的情况，即系统如何知道哪个作业是最短的呢？）当然，通过首先在仿真程序上运行程序，跟踪所有页面的访问情况，在第二次运行时利用第一次运行时收集的信息是可以实现最优页面置换算法的。用这种方式，我们可以通过最优页面置换算法对其他可实现算法的性能进行比较。如果操作系统达到的页面置换性能只比最优算法差1%，那么即使花费大量的精力来寻找更好的算法最多也只能换来1%的性能提高。为了避免混淆，读者必须清楚以上页面访问情况的记录只针对刚刚被测试过的程序和它的一个特定的输入，因此从中导出的性能最好的页面置换算法也只是针对这个特定的程序和输入数据的。虽然这个方法对评价页面置换算法很有用，但它在实际系统中却不能使用。下面我们将研究可以在实际系统中使用的算法。3.7先进先出实例列举 页面置换算法是FIFO（First-In First-Out，先进先出）算法。为了解释它是怎样工作的，我们设想有一个超级市场，它有足够的货架能展示k种不同的商品。有一天，某家公司介绍了一种新的方便食品即食的、冷冻干燥的、可以用微波炉加热的酸乳酪，这个产品非常成功，所以容量有限的超市必须撤掉一种旧的商品以便能够展示该新产品。一种可能的解决方法就是找到该超级市场中库存时间最长的商品并将其替换掉（比如某种120年以前就开始卖的商品），理由是现在已经没有人喜欢它了。这实际上相当于超级市场有一个按照引进时间排列的所有商品的链表。新的商品被加到链表的尾部，链表头上的商品则被撤掉。同样的思想也可以应用在页面置换算法中。由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。当FIFO用在超级市场时，可能会淘汰剃须膏，但也可能淘汰面粉、盐或黄油这一类常用商品。因此，当它应用在计算机上时也会引起同样的问题，由于这一原因，很少使用纯粹的FIFO算法。3.8详细解析 为使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置R位；当页面（即修改页面）被写入时设置M位。这些位包含在页表项中，如图3-11所示。每次访问内存时更新这些位，因此由硬件来设置它们是必要的。一旦设置某位为1，它就一直保持1直到操作系统将它复位。如果硬件没有这些位，则可以进行以下的软件模拟：当启动一个进程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置R位（在它的内部表格中），修改页表项使其指向正确的页面，并设为READ ONLY模式，然后重新启动引起缺页中断的指令；如果随后对该页面的修改又引发一次缺页中断，则操作系统设置这个页面的M位并将其改为READ/WRITE模式。可以用R位和M位来构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：第0类：没有被访问，没