先进先出报告.doc

摘 要 FIFO算法是最简单的的页面置换算法，在实现时，对应的每一个页面需要有一个调入时间，该时间可设置在内存中并用软件记录，但最好设置在寄存器中并使用硬件记录。当内存空间紧张时，调入时间最早的页面将被淘汰。FIFO算法也可以这样实现：由操作系统维护一个所有当前在内存中的页面的链接，必威体育精装版进入的页面放在表尾，最先进入的放在表头，当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。除了链指针外，还可以用表格等方法来实现。 关键词：页面置换缺页率 二、设计内容 三、设计过程 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调度；一个对话框用于显示调度结果。 页面地址流保存在页面队列中。 构造LRU调度器类，该类中包含一个长度为n的堆栈，n表示实页数，该值从1到k（不同的虚页数）循环；可以通过类构造函数传入n。包含一个记数值记录访问时间，记数值初始为0。 构造FIFO调度器类，该类中包含一个长度为n的堆栈，n表示实页数，该值从1到k（不同的虚页数）循环；可以通过类构造函数传入n。包含一个记数值记录访问时间，记数值初始为0。 用定时器模拟页面访问，每个时间片从虚页面队列中取出一个虚页号，通过LRU调度器类和FIFO调度器类的对应接口函数将该虚页作为参数传入。 LRU类的接口函数实现如下功能：用传入的虚页号遍历堆栈，查找与之一致的记录，如果有则表示命中，将对应的虚页号压入堆栈直到覆盖原记录。并将记数值加1。如为查到表示未命中，将对应的虚页号压入堆栈直到堆栈尾，并将记数值加100。 FIFO类的接口函数实现如下功能：用传入的虚页号遍历堆栈，查找与之一致的记录，如果有则表示命中，将记数值加1。如为查到表示未命中，将对应的虚页号压入堆栈直到堆栈尾，并将记数值加100。 程序初始化时创建n个FIFO类对象和n个LRU类对象，其堆栈大小分别从1-n。 虚页队列空表示模拟完成，提前n个FIFO类对象和n个LRU类对象中的记数值和相应参数，在显示对话框中输出并打印。 与（二）中的结果进行比对。 使用多个不同的页地址流多次进行模拟，并保存每次模拟的结果。 对结果进行分析，判断两种调度算法的优劣，判断其中那种算法是堆栈型算法。 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 Page[3]; 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