操作系统课程设计-先进先出页面置换算法(28页).doc

《操作系统课程设计-先进先出页面置换算法(28页).doc》由会员分享，可在线阅读，更多相关《操作系统课程设计-先进先出页面置换算法(28页).doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-操作系统课程设计-先进先出页面置换算法-第 20 页沈 阳 工 程 学 院操作系统课程设计设计题目：先进先出页面置换算法系 别 计算机科学与技术 班级 学生姓名 学号 指导教师 曲乐声、崔妍 职称 讲师 起止日期：2016年6月6日起至2016年6月10日止沈 阳 工 程 学 院操作系统课程设计任务书设计题目：请求调页存储管理方式的模拟1系 别 计算机科学与技术 班级 学生姓名 学号 指导教师 曲乐声 职称 讲师 课程设计进行地点： 信息学院实验室 任 务 下 达 时 间：2016年6月 3日起止日期：2016年6月6日起至2016年6月10日止 系部主任 张欣 2016年 6月2日批准一、

2、设计目的操作系统课程设计是在完成操作系统理论课程学习之后进行的实践性教学。通过课程设计，综合运用操作系统课程的理论，结合实际，加深对操作系统知识全面、深入地理解，进一步掌握操作系统的基本概念、原理和实现方法，能够模拟操作系统对计算机系统的管理和控制功能，培养学生分析和解决实际问题的能力，并使所学知识得到进一步巩固、深化和扩展。该页面置换先进先出算法的设计的主要目的是，通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。二、设计的主要内容及要求1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用c语言模拟一个作业的执行过程，该作业共有320

3、条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：采用先进先出（FIFO）置换算法。三、对设计说明书撰写内容、格式、字数的要求 1.课程设计说明书（论文）是体现和总结课程设计成果的载体，一般不应少于3000字。2.学生应撰写的内容为：目录、正文、参考文献等。课程

4、设计说明书（论文）的结构及各部分内容要求可参照沈阳工程学院毕业设计（论文）撰写规范执行。应做到文理通顺，内容正确完整，书写工整，装订整齐。3.说明书（论文）手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时按沈阳工程学院毕业设计（论文）撰写规范的要求进行打印。4. 课程设计说明书（论文）装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、 设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排序 号主 要 内 容学 时备 注1进行设计准备，阅读资料，分析设计任务书，明确设计要求、内

5、容和步骤0.5天2绘制程序流程图，编写相应的程序代码2天3上机调试1.5天4整理实验数据，撰写课程设计报告0.5天5成绩评定0.5天合 计5天六、主要参考文献1.操作系统基础，清华大学出版社，屠立德、屠祁编著。 2.计算机操作系统，西安电子科技大学出版社，汤子瀛等编。3.计算机操作系统教程，清华大学出版社，张学尧编。4.计算机操作系统，华中理工大学出版社，庞丽萍等编。5.操作系统教程，高等教育出版社，孙钟秀主编。6.Linux操作系统实验教程，高等教育出版社，费翔林主编。7.操作系统原理与Linux，人民邮电出版社，马季兰，冯秀芳等。 8.操作系统习题与解析，清华大学出版社，曾平，李春葆。 沈

6、 阳 工 程 学 院 操作系统 课程设计成绩评定表系（部）： 计算机科学与技术 班级： 学生姓名： 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以12） 分加权分合计指 导

7、 教 师 签 名： 年 月 日答 辩 小 组 意 见评价内容具 体 要 求权重评 分加权分报告内容思路清晰，语言表达准确，概念清楚，论点正确；分析归纳合理；结论严谨；设计具有应用价值。0.25432答辩回答问题有理论根据，基本概念清楚。主要问题回答准确、深入。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432答辩小组评审成绩（加权分合计乘以8）分加权分合计评 阅 教 师 签 名： 年 月 日课 程 设 计 总 评 成 绩分沈 阳 工 程 学 院 操作系统 课程设计成绩评定表系（部）： 计算机科学与

8、技术 班级： 学生姓名： 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以12） 分加权分合计指 导 教 师 签 名： 年 月 日答 辩 小 组 意 见评价内容具 体 要 求

9、权重评 分加权分报告内容思路清晰，语言表达准确，概念清楚，论点正确；分析归纳合理；结论严谨；设计具有应用价值。0.25432答辩回答问题有理论根据，基本概念清楚。主要问题回答准确、深入。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432答辩小组评审成绩（加权分合计乘以8）分加权分合计评 阅 教 师 签 名： 年 月 日课 程 设 计 总 评 成 绩分目录第一章 绪论11.1课题前景11.2 先进先出算法的实现过程21.3 先进先出算法的缺点3第二章 原理及运行环境42.1系统原理42.1.1系统设

10、计原理42.1.2调页策略52.1.3从何处调入页面52.2运行环境（VC+6.0简介）6第三章 需求分析103.1 问题描述103.2 基本功能需求103.3 提示要求10第四章 概念设计124.1 数据结构124.2 系统包含的函数134.3 函数间的关系144.4 系统功能模块图14第五章 详细设计155.1 系统的详细定义和介绍155.2 随机数产生办法155.3 系统功能模块介绍165.4 具体模块设计165.5 程序源代码18第六章 调试分析226.1 测试数据226.2 程序截图226.3 思考题26设计总结27致谢28主要参考文献29第一章 绪论1.1课题前景在信息高速发展的当

11、今社会，各个领域的突飞猛进，计算机也有它卓越的进步，学习都是由浅入深，我们学习计算机也是一样，都是要从简单学起。“操作系统”是计算机专业的核心专业课，“操作系统课程设计”是理解和巩固操作系统基本理论、原理和方法的重要的实践环节，因此，我们必须将之学好。操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统基本理论与管理方式。在算法基础上，解决实际的管理功能的问题，提高学生实际应用、编程的能力。

12、FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。本题目的设计要达到目的：通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统

13、必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。最简单的页面置换算法是先入先出(FIFO)法。优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。关键字：visual c +，页面置换，先进先出页面置换算法，缺页次数，缺页率1.2 先进先出算法的实现过程 假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串:7, 0, 1, 2, 0, 3, 0,4,2,3,

14、 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。采用FIFO算法进行页面置换，进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由图1.2.1可以看出，利用FIFO算法时进行了12次页面置换。访问页面70120304323021201701物理块1777222444000777物理块200033322211100物理块31110003332221缺页否图1.2.1 12次页面置换1.3 先进先出算法的缺点 FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由Belady于1969年发现，故称为Bela

15、dy异常，如下图1.3.1所示。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。访问页面123412512345物3理块1111444555物理块222211133物理块33332224缺页否111555544物理块2*222211115物理块3*33332222物理块4*4444333缺页否图1.3.1 页面置换第二章 原理及运行环境2.1系统原理2.1.1系统设计原理 为了解释它是怎样工作的，我们设想有一个超级市场，它有足够的货架能展示k种不同的商品。有一天，某家公司介绍了一种新的方便食品即食的、冷冻干燥的、可以用微波炉加热的酸乳酪，这个产品非常

16、成功，所以容量有限的超市必须撤掉一种旧的商品以便能够展示该新产品。一种可能的解决方法就是找到该超级市场中库存时间最长的商品并将其替换掉（比如某种120年以前就开始卖的商品），理由是现在已经没有人喜欢它了。这实际上相当于超级市场有一个按照引进时间排列的所有商品的链表。新的商品被加到链表的尾部，链表头上的商品则被撤掉。 同样的思想也可以应用在页面置换算法中。由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。当FIFO用在超级市场时，可能会淘汰剃须膏，但也可能淘汰面粉、盐或黄油这一类常用商品。因此

17、，当它应用在计算机上时也会引起同样的问题，由于这一原因，很少使用纯粹的FIFO算法。由于分区式管理尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。 再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小或内存可用空间的限制。而且分区式管理也不利于程序段和数据段的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分，动态页式管理是在静态页式管理的基础上发展起来的。请求页式管理属

18、于动态页式管理中的一种，它的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号，由页面号与页内相对地址相加而得到实际物理地址。有关的地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此，请求页式管理是一个十分复杂的过程，内存利用率的提高是以牺牲系统开销的代价换来的。 这里用到了置换算法。它是在内存中没有空闲页面时被调用。目的是选出一个被淘汰的页面。如果内存中

19、有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率低的页，将它们移出内存。2.1.2调页策略 何时调入页面 如果进程的许多页面时存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高一些。但如果调入的一批页面中大多数都未被访问，则又是低效的。可采用一种以预测为基础的预测页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功几率仅为50%请求调页策略 当进程在运行中需要访问某部分程序和数据

20、时，若发现其所在的页面不在内存，即便提出要求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，时一定会被访问的，再加之请求调页策略比较容易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。2.1.3从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件区和用于存放兑换页面的对换区。通常，由于对换区时采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存

21、中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_ReplacementAlgorithms)。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。则有以下页面置换方法：先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面

22、就可以实现。2.2运行环境（VC+6.0简介）在数据结构程序的运行环境为Visual C+ 6.0其工作环境如图2.2.1所示图2.2.1 Visual C+ 6.0 的工作环境 C与C+程序Visual C+6.0的材料如下：Visual C+6.0由Microsoft开发, 它不仅是一个C+ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境.Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。 这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境。Visual C+是一

23、个功能强大的可视化软件开发工具。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。总体来讲，运行环境方便快捷。建立C语言源程序文件。建立方法：选择菜单命令“文件” “新建”或直接点击对话框中的“新建”，选择Win32Console，并在右上方“工程名”称下键入工程

24、名如图3.2.2所示。在工程建立完成后选择C+Source，并在“文件名”下键入文件名如图2.2.3所示。图2.2.2 建立C语言源程序建立工程程序的编辑与编译。编辑完成后，选择菜单栏中的“运行”“调试程序”即可对程序进行编译。当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，当然有时提示位置不一定很准确。图2.2.3 建立C语言源程序建立文件程序的执行。单击工具栏上的“红色感叹号”按钮或Ctrl+F5，即可执行刚编写程序，如图2.2.4所示。图2.2.4 对源程序进行编写使用C

25、与C+程序设计VC+6.0开发环境，对源程序执行编译。如图2.2.5所示。图2.2.5执行编写的程序第三章 需求分析3.1 问题描述 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运

26、行过程中发生的缺页率。 3）置换算法：采用先进先出（FIFO）置换算法。3.2 基本功能需求1） 存放页面数M(M=32)，分配给作业的内存块数为N(Ncount; cout*按照要求产生的320个随机数：*endl; for(int i=0;i320;i+) tempi=count; if(flag%2=0)count=+count%320;/产生50%的顺序执行指令（flag=0或2时顺序执行） if(flag=1) count=rand( )% (count-1); /产生25%的均匀分布在前地址部分指令 if(flag=3) count=count+1+(rand( )%(320-(c

27、ount+1); /产生25%的均匀分布在后 地址部分指令 flag=+flag%4; printf( %03d,tempi); if(i+1)%10=0) coutendl; 5.3 系统功能模块介绍该先进先出（FIFO）页面置换算法设计各模块主要完成的功能有：1) 存放页面数M(M=32)。2) 分配给作业的内存块数为N(N=4)。3) 输入指令数（1-320）。4) 计算并显示作业运行过程中发生的缺页率。5) 置换算法：采用先进先出（FIFO）置换算法。6) 结束5.4 具体模块设计1) 输入任意指令数（1-320），产生320个随机数，显示其调用页面队列，选择1：FIFO算法，进行先进

28、先出页面置换算法，显示320条随机数的指令是否存在，若存在显示其物理块地址之后，计算出缺页次数与缺页率，如图所示：开 始初始化页面是输入指令数1=i=320否重新输入指令数1=i=320是 随机生成320个随机数 生成对应调用页面列队图5.4.1 输入模块流程图 输出是否缺页、输出系统分配的物理块数、输出需要进入内存的页面总数、输出缺页中断的次数、根据输出的页面总数和缺页中断的次数计算缺页中断率 假如输入内存的页面总数是10，系统分配的物理块数是4，页面号是7 1 4 5 7 2 3 0 5 6 则输出结果如图所示：开 始输入任意系统指令数随机产生10条指令数例如：7 1 4 5 7 2 3

29、0 5 6输出： 7 页面进入内存,产生第1次缺页 1 页面进入内存,产生第2次缺页. 4 页面进入内存,产生第3次缺页. 5 页面进入内存,产生第4次缺页. 7 内存中有这个页面,直接访问. 2 7被置换出去,产生第5次缺页. 3 1被置换出去,产生第6次缺页. 0 4被置换出去,产生第7次缺页 5 内存中有这个页面,直接访问. 6 5被置换出去,产生第8次缺页.缺页中断次数为8次缺页率=缺页次数/存入的页面总数（%）=80%结 束图5.4.2 输出模块流程图5.5 程序源代码#include #include#include #include#define size 4 typedef s

30、truct BLOCK/声明一种新类型物理块类型 int pagenum;/页号 int accessed;/访问字段，其值表示多久未被访问 BLOCK; int count;/程序计数器，用来记录指令的序号 int n;/缺页计数器，用来记录缺页的次数 static int temp320;/用来存储320条随机数 BLOCK blocksize; /定义一大小为4的物理块数组 void init( ); /程序初始化函数 int findExist(int curpage);/查找物理块中是否有该页面 int findSpace( );/查找是否有空闲物理块 int findReplace

31、( );/查找应予置换的页面 void display ( );/显示 void Random( );/产生320条随机数,显示并存储到temp320 void pagestring( );/显示调用的页面队列 void FIFO( );/FIFO算法 void init( ) for(int i=0;isize;i+) blocki.pagenum=-1; blocki.accessed=0; count=n=0; int findExist(int curpage) /查找物理块中是否有该页面 for(int i=0; isize; i+) if(blocki.pagenum = curpage ) return i; /检测到内存中有该页面，返回block中的位置 return -1; int findSpace( ) /查找是否有空闲物理块