操作系统课程设计任务书题目：模拟分页系统的实现学生姓名：朱文涛学号： 13480145班级：物联网工程一班题目类型：软件工程（R）指导教师：贾娟娟/杨书鸿一、设计目的学生通过该题目的设计过程，掌握虚拟存储器管理的原理、软件开发方法并提高 解决实际问题的能力。二、设计任务1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并 掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。2、模拟请求分页虚拟存储管理中的硬件地址变化过程，并采用先进现出或 LRU 算法实现分页管理的缺页调度。三、设计要求1、分析设计要求，给出解决方案（要说明设计实现所用的原理、采用的数 据结构）。2、设计合适的测试用例，对得到的运行结果要有分析。3、设计中遇到的问题，设计的心得体会。4、文档：课程设计打印文档每个学生一份，并装在统一的资料袋中。5、光盘：每个学生的文档和程序资料建在一个以自己学号和姓名命名的文件夹 下，刻录一张光盘，装入资料袋中。四、提交的成果1. 设计说明书一份，内容包括：1）中文摘要 100 字；关键词 3-5个2）设计思想；3）各模块的伪码算法；4）函数的调用关系图；5）测试结果；6）源程序（带注释）；7）设计总结；8）参考文献、致谢等。2. 刻制光盘一张。五、主要参考文献1. 汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社.2. 王清，李光明.计算机操作系统.冶金工业出版社.3. 孙钟秀等. 操作系统教程. 高等教育出版社4. 曾明. Linux 操作系统应用教程. 陕西科学技术出版社.5. 张丽芬，刘利雄.操作系统实验教程. 清华大学出版社.6. 孟静， 操作系统教程原理和实例分析. 高等教育出版社7. 周长林，计算机操作系统教程. 高等教育出版社8. 张尧学，计算机操作系统教程，清华大学出版社9. 任满杰，操作系统原理实用教程，电子工业出版社10. 张坤.操作系统实验教程，清华大学出版社六、各阶段时间安排（共 2周）周次日期内容地点第1周星期一二教师讲解设计要求查找参考资料教室图书馆星期三五算法设计，编程实现教室第2周星期一三调试测试，撰写文档教室星期四五检查程序，答辩教室2015 年12月 9 日摘要为配合计算机操作系统课程的教学，加深对整个课程体系的理解，领会 操作系统工作原理和理解操作系统的实现方法，提高学生的实践动手能力，提高学生 科技论文写作能力，特开设此课程设计。本模拟系统是先进先出页面淘汰算法 FIFO， 最近最少使用 LRU 页面淘汰算法.同时系统可以随意设置当前分配给作业的物理块 数。系统运行时任意输入一个页面访问序列可以设置不同的页面置换算法和物理块 数，输出其页面淘汰的的情况，计算其缺页次数和缺页率。系统结束后，比较同一个 页面访问序列，可以都处在不同的页面置换算法和物理块数的情况下，其产生的缺页 次数和缺页率。使用 FIFO 算法，由于测试数据相同的页面比较少，所以采用 FIFO 算法时，需要置换的页面多，比较繁琐，因此说FIFO算法的性能不是很好。使用LRU 的算法，此算法显示LRU算法的使用比较繁琐，总的来说，LRU算法优于FIFO算 法。在实际应用中一般使用LRU算法实现其页面的置换。关键词：FIFO;LRU;页面置换算法；缺页次数；缺页率目录1 绪论 11.2 设计思想 21.2.1 先进先出法21.2.2 最近最久未使用21.3 基础知识 21.3.1 请求分页中的硬件支持 31.3.2 内存分配策略和分配算法31.3.3 请求分页策略41.3.4 硬件地址的变换过程42 相关的各模块的伪码算法 62.1 void changeaddr(struct Page p,int logaddr) 62.2 void chushihua() 72.3 FIFO 算法的实现 82.4 LRU算法的实现113 函数的调用关系图144 调试结果154.1 分页系统主界面154.2 硬件地址变换算法界面154.3 选择输入指令164.4 逻辑地址向物理地址转换164.5 由于缺页而产生的中断174.6 进入页面置换算法界面184.7 页面置换算法(FIFO、LRU)M=3184.8 页面置换算法(FIFO、LRU)M=4195 源程序代码216 总 结33参考文献34致 谢 351 绪 论分页式虚拟存储系统将作业信息的副本存放在磁盘中，不把作业的程序和数据全 部装入主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生 缺页中断，再把它们动态地装入。虚拟存储的基本思想是基于程序的局部性原理，仅把目前需要的部分程序加载到 内存，其余暂时不用的程序及数据还保留在辅存中。在进程运行过程中，如果所要执 行的程序不在内存，系统要将要执行的程序段自动调入内存。 此时如果内存已满， 则要通过置换操作将暂时不用的程序段先调出到辅存，然后将所需的程序段调入内 存，继续执行该进程。虚拟存储器的引入，实际上是利用了存储管理中逻辑地址空间和物理地址空间 的关系，将计算机的内存和辅存结合起来，使得用户感觉具有大容量的内存，虚拟内 存在将逻辑地址转换成物理地址时，必须通过一个内存管理单元 MMU（Memory Management Unit ）来完成。存储管理一直是操作系统中的重要组成部分，因为冯诺依曼体系结构就是建立 在存储程序概念上的，访问存储器的操作占 CPU 时间的 70%左右。计算机系统中的 存储器一般分为主存储器（简称主存、内存）和辅助存储器（简称辅存）。由于2PU 只能直接与内存进行通信，因此计算机系统的程序以及与该程序相关的数据，只有被 装入到内存中才能有效地执行。计算机系统能否高效地管理内存空间，不仅直接反映 存储器的利用率，还会影响整个操作系统的性能。1.1设计任务1 了解 UNIX 的命令及使用格式，熟悉 UNIX/LINUX 的常用基本命令，练习并 掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。 模拟请求分页虚拟存储管理中的硬件地址变化过程，并采用先进现出或LRU算法实 现分页管理的缺页调度。1.2 设计思想1.2.1先进先出法（FIFO）该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以 淘汰。在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容 都依次向底移一位，需要访问的内容存入数组 0 号单元，即最顶部，这时缺页数加 1； 当不需要进行页面置换，即所需访问的内容在内存中时，不需要操作，继续读下一条 指令。这样就实现了总是淘汰最先进入内存的页面，选择了在内存中驻留时间最久的 页面予以淘汰。1.2.2最近最久未使用（LRU）该算法将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当页面需要被置换进入内存时，最先进入内存的内容 们都依次向底移一位，需要访问的内容存入数组 0 号单元，即最顶部，这时缺页数加 1；当不需要进行页面置换，即所需访问的内容在内存中时，将要访问的指令移到内 存顶部，其他指令依次向下移一位，这样就把最久不用的指令沉到了底部，有必要时 淘汰，即实现了总是淘汰最近最久未使用的指令。1.3 基础知识1.3.1 请求分页中的硬件支持1. 页表机制用于地址转换；增加页表项：页号、页架号、状态位、访问字段、修改位、外存地址2. 缺页中断机构所要访问的页不在内存时，便引发一次缺页中断；3. 与常规中断的不同之处：在指令执行期间产生和处理中断信号； 一条指令在执行期间，可能产生多次缺页中断。4. 地址变换机构 首先检索快表，若找到，修改页表项中的访问位，然后利用页表项中给出的页架 号和页内地址，形成物理地址。如果在快表中未找到相应的页表项，检索内存中的页表，察看页表中的状态位， 若该页已经调入内存，填写快表，当快表满时，应淘汰一个页表项；若该页尚未调入 内存，产生缺页中断，请求 OS 把该页调入。1.3.2 内存分配策略和分配算法最小物理块（页架）数的确定 保证进程正常运行所需的最少页架数； 与指令的格式、功能和寻址方式有关。1. 页架的分配策略 固定分配局部置换：进程占据的内存页架数不变；但分配时，难于确定某个进程 的页架数。可变分配全部置换：空闲页架由OS管理。可变分配局部置换：当进程缺页率较高或较低时，能由 OS 对其占据的页架数加 以调整。2. 页架的分配算法平均分配算法 将系统中所有可供分配的页架，平均分配给各个进程。按比例分配算法 根据进程的大小按比例分配页架的算法。考虑优先权的分配算法 优先权高的一次分得的页架数多。1.3.3 请求分页策略何时调入页面的问题预调页策略：首次调入内存时请求调页策略：运行中的发生缺页现象时从何处调入页面的问题“文件区” 与“对换区”：页面的调入过程响应中断、保存CPU环境、查找页表(快表)，得到该页在外存中的块号，启动 磁盘IO读入；如果内存已满，先置换，在调入；最后修改页表(快表)对应项的内 容。1.3.4硬件地址的变换过程(1) 请求分页虚拟存储管理技术是把作业地址空间的全部信息存放在磁盘上。当 作业被选中运行时,先把作业的开始几页装入主存并启动运行。为此在为作业建立页 表时,应说明哪些页已在主存,哪些页不在主存。 “状态位”用于指示该页是否已经调入了内存。该位一般由操作系统软件来管理，每 当操作系统把一页调人物理内存中时，置位。相反，当操作系统把该页从物理内存调 出时，复位。CPU对内存进行引用时，根据该位判断要访问的页是否在内存中，若不 在内存之中，则产生缺页中断。“修改位”表示该页调入内存后是否被修改过。当CPU以写的方式访问页面时，对该 页表项中的修改位置位。该位也可由操作系统软件来修改，例如，当操作系统将修改 过页面保存在磁盘上后，可将该位复位。“外存地址”用于指出该页在外存上的地址，供调人该页时使用。“访问字段”用于记录本页在一定时间内被访问的次数，或最近已经有多长时间未被访问。(2) 作业执行时,指令中的逻辑地址指出参加运算的操作数(或指令)地址中的页号和 页内偏移量.硬件地址转换机构按页号查页表。若该页的标志为1 ,则表示该页已在 主存, 从而找到该页对应的主存块号。根据关系式: 绝对地址=块号*块的长度+页内 偏移量；计算出欲访问的主存地址。由于页号为2的整次幂,所以只要将块号与页内 偏移量相拼接, 放入主存地址寄存器即可。按照该地址取指令或取操作数, 完成指定的 操作.(3) 设计一个”地址变换”程序,模拟硬件地址变化过程。当访问的页在主存时,则形 成绝对地址后,不去模拟指令的执行,而是输出被转换的地址。当访问的页不在主存时, 输出”该页不在主存, 产生缺页中断”,以表示产生一次缺页中断。(4) 进行缺页中断处理.中断返回后,重新执行该指令。假定主存的每块长度为 64个字节,现有一个具有 8 页的作业,系统为其分配了 4 个主 存块(即m=4)，且最多分4块。其中第0页至第3页已经装入主存。运行设计的地址 变换程序, 显示或打印运行结果。(5) 先进先出算法(FIFO)。选择装入最早的页面置换。可以通过链表来表示各页的装 入时间先后。FIFO的性