FIFOLUR算法JAVA.doc

实现请求分页存储管理页面Optimal、FIFO、LRU调度算法文档1引言1.1编写的目的（1）通过编写程序实现请求分页存储管理页面Optimal、FIFO、LRU调度算法，使学生掌握虚拟存储管理中有关缺页处理方法等内容，巩固有关虚拟存储管理的教学内容。（2）了解Windows2000/XP中内存管理机制，掌握页式虚拟存储技术。（3）理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。1.2背景a. 实现请求分页存储管理页面Optimal、FIFO、LRU调度算法实验;b. 提出者：龙陈锋老师，开发者：孙敏，用户：面向所有学生；1.3定义 请求分页存储管理；Optimal调度算法；FIFO调度算法；LRU调度算法。1.4参考资料1 顾宝根,王立松,顾喜梅.操作系统实验教程核心技术与编程实例.北京:科学出版社.2003,2.2 任爱华,李鹏,刘方毅.操作系统实验指导.北京:清华大学出版社.2004,6. 3 王险峰,刘宝宏.Windows环境下的多线程编程原理与应用.北京:清华大学出版社.2002,7. 4 上课用教材2任务概述2.1目标 在Windows XP、Windows 2000等操作系统下，使用的VC、VB、java或C等编程语言，实现请求分页存储管理页面Optimal、FIFO、LRU调度算法。2.2用户的特点本专业的学生，能够对本专业的语言和运行环境有所了解。2.3问题描述 1）用随机数产生一个指令序列，共320条指令。其地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；2）指令序列变换成页地址流 设：页面大小为1K； 用户虚存容量为32K。 在用户虚存中，按每1K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条第9条指令为第0页（对应虚存地址为0，9）； 第10条第19条指令为第1页（对应虚存地址为10，19）； 310条第319条指令为第31页（对应虚存地址为310，319）； 按以上方式，用户指令可组成32页。3）计算并输出下述各种算法在不同内存容量(用户内存容量为4页到32页)下的缺页率。 A. OPT最佳淘汰算法B. FIFO先进先出的算法 C. LRU最近最少使用算法3.3输入输出要求PV原语的要求。4运行环境规定4.1设备 Windows2000/XP4.2支持软件VC、VB、java或C等编程语言。5. 具体实现及分析1 利用随机数产生一个指令序列，共320条指令。其地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；2.指令序列变换成页地址流 设：页面大小为1K； 用户虚存容量为32K。 在用户虚存中，按每1K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为： 第0条第9条指令为第0页（对应虚存地址为0，9）； 第10条第19条指令为第1页（对应虚存地址为10，19）； 310条第319条指令为第31页（对应虚存地址为310，319）； 按以上方式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量(用户内存容量为4页到32页)下的缺页率。 a) OPT最佳淘汰算法：OPT.java源代码：package instructions.algorithm;import instructions.*; /* * The implementation of Optimal algorithm. * author DigitalSonic */public class OPT extends Algorithm /* * Creates a new instance of OPT */ public OPT(int UserPagesCount,SequenceSeq, VirtualMemory VM) super(UserPagesCount, Seq, VM); = OPT; /* * Replace a page with the new one. * param NewPage The page ready to be inserted. */ public void replacePage(Page NewPage) if (VM.getCurrentEmptyIndex() != VM.UserPagesCount) VM.getUserPages()VM.getCurrentEmptyIndex()=NewPage; VM.setCurrentEmptyIndex(VM.getCurrentEmptyIndex() + 1); else VM.getUserPages()findUnusedPage(VM.getUserPages(), NewPage.getVisitTime() = NewPage; private int findUnusedPage(Page Pages, int CurrentInstruction) int Pos = new intPages.length; Page page; for (int m = 0; m Pages.length; m+) Posm = 0; page = Pagesm; for (int n = CurrentInstruction; n seq.getList().size(); n+) if (page = VM.getPages()Integer.parseInt(seq.getList().get(n).getName() / Page.PAGE_SIZE) Posm=n; break; return findMax(Pos); private int findMax(int Count) int Max = 0; int Index = 0; for (int i = 0; i Max) Max = Counti; Index = i; return Index; b) FIFO先进先出的算法：FIFO.java源代码：package instructions.algorithm;import instructions.*;/* * The implementation of First In First Out algorithm. * author DigitalSonic */public class FIFO extends Algorithm /* * Creates a new instance of FIFO */ public FIFO(int UserPagesCount, Sequence Seq, VirtualMemory VM) super(UserPagesCount, Seq, VM); = FIFO; /* * Replace a page with the new one. * param NewPage The page ready to be inserted. */ public void replacePage(Page NewPage) if(VM.getCurrentEmptyIndex()!=VM.UserPagesCount) VM.getUserPages()VM.getCurrentEmptyIndex()=NewPage; VM.setCurrentEmptyIndex(VM.getCurrentEmptyIndex() + 1); else VM.getUserPages()findFIPage(VM.getUserPages() = NewPage; private int findFIPage(Page Pages) int Index = Page.PAGE_SIZE * VirtualMemory.TOTAL_PAGE_COUNT; for (int i = 0; i Pages.length; i+) if (Pagesi.getVisitTime() Index) Index = i; return Index; c) LRU最近最少使用算法：LRU.java源代码：package instructions.algorithm;import instructions.*;/* * The implementation of Least Recently Used algorithm. * author DigitalSonic */public class LRU extends Algorithm /* * Creates a new instance of LRU */ public LRU(int UserPagesCount, Sequence Seq, VirtualMemory VM) super(UserPagesCount, Seq, VM); = LRU; /* * Replace a page with the new one. * param NewPage The page ready to be inserted.*/ public void replacePage(Page NewPage) if(VM.getCurrentEmptyIndex()!=VM.UserPagesCount) VM.getUserPages()VM.getCurrentEmptyIndex()=NewPage; VM.setCurrentEmptyIndex(VM.getCurrentEmptyIndex() + 1); else VM.getUserPages()findLRUPage(VM.getUserPages(), NewPage.getVisitTime() = NewPage; private int findLRUPage(Page Pages, int CurrentInstruction) Int Count = new intPages.length; Page page; for (int m = 0; m Pages.length; m+) Countm = 0; page = Pagesm; for (int n = 0; n CurrentInstruction & n seq.getList().size(); n+) if (page = VM.getPages()Integer.parseInt(seq.getList().get(n).getName() / Page.PAGE_SIZE) Countm+; return findMin(Count); private int findMin(int Count) int Min = Page.PAGE_SIZE * VirtualMemory.TOTAL_PAGE_COUNT; int Index = 0; for (int i = 0; i Count.length; i+) if (Counti Min)