操作系统课程设计实验报告.doc

操作系统原理课程设计报告姓 名： 班 级： BX1204 学 号： 指导老师： 范光宇 2015年 1月16日 目录一、操作系统原理课程设计的目的与要求11目的12要求1二、简述课程设计内容、主要功能21课程设计内容22主要功能23实现环境2三、任务的分析、设计、实现和讨论31任务的分析32任务的设计与实现42.1 main( )函数流程图：42.2 主菜单流程图：52.3 LRU函数流程图：62.4 FIFO函数流程图：73操作过程73.1进入主页面73.2选择a，83.3选择b94结果分析10两种算法的比较：115思考题的解答和讨论11四、 操作系统课程设计小结15五、参考文献15一、操作系统原理课程设计的目的与要求1目的近年来，由于大规模集成电路（LSI）和超大规模集成电路（VLSI）技术的发展，使存储器的容量不断扩大，价格大幅度下降。但从使用角度看，存储器的容量和成本总受到一定的限制。所以，提高存储器的效率始终是操作系统研究的重要课题之一。虚拟存储技术是用来扩大内存容量的一种重要方法。学生应独立地用高级语言编写几个常用的存储分配算法，并设计一个存储管理的模拟程序，对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。2要求任务四采用最近最少使用页淘汰算法(LRU)实现。为了比较真实地模拟存储管理，可预先生成一个大致符合实际情况的指令地址流。然后模拟这样一种指令序列的执行来计算和分析各种算法的访问命中率.15二、简述课程设计内容、主要功能1课程设计内容 先进先出算法（FIFO）最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。最近最少使用页淘汰算法(LRU)这是一种经常使用的方法。有各种不同的实施方案，这里采用的是在固定的物理块中，每进来一个页面，有一个记录时间的值，当物理块没有空闲时，有新的页面进来，首先先判断物理块里有没有该页面存在，如果有，那更新该页面的时间，调整为0，如果没有，那查看记录时间的值，看哪个时间最久，即置换该页面，放在物理块里。并把最新进来的页面的时间也调整为0，即是最新的时间。 2主要功能（1） YZ_replace(); /构造函数 （2） YZ_replace(); /析构函数 （3） int findSpace(); /查找是否有空闲内存 （4） int findExist(int curpage); /查找内存中是否有该页面 （5） int findReplace(); /查找应予置换的页面 （6） void FIFO(); /FIFO算法 （7） void LRU(); /LRU算法 （8） void BlockClear(); /BLOCK恢复 （9） void initia1(int string);/初始化 （10） pageInfor *block; /物理块 （11） pageInfor *page; /页面号串 （12） int memory_stateBsizePsize; /内存块 页面数（13） int s; /记录命中数三、任务的分析、设计、实现和讨论1任务的分析本示例是采用页式分配存储管理方案，并通过分析计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣。另外也考虑到改变页面大小和实际存储器容量对计算结果的影响，从而可为算则好的算法、合适的页面尺寸和实存容量提供依据。本程序是按下述原则生成指令序列的：（1） 50%的指令是顺序执行的。（2） 25%的指令均匀散布在前地址部分。（3） 25%的指令均匀散布在后地址部分。示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。公式为假定虚存容量为32K，页面尺寸从1K至8K，实存容量从4页至32页。调页策略 1)何时调入页面 如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 2)请求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。 2任务的设计与实现2.1 main( )函数流程图：2.2 主菜单流程图：2.3 LRU函数流程图：2.4 FIFO函数流程图：3操作过程3.1进入主页面3.2选择a，按1实现FIFO算法，输出命中率按2实现LRU算法，输出命中率返回主菜单3.3选择b按1实现FIFO算法，输出命中率按2实现LRU算法，输出命中率按c退出程序4结果分析两种算法的比较：FIFO算法该算法总是淘汰最先进入内存的页面，既选择内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调入内存的页面，按照先后测序链接成一个队列，并设置一个指针，使他总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 这里，我们用下面的例子，采用FIFO算法进行页面置换。当进程第一次访问页面2时，将把第七页换出，因为它是最先被调入内存的；在第一次范文页面3时，又将把第零页换出，因为他在现有的2，0，1三个页面中是最老的页。由下图可以看出，利用FIFO算法时进行了十二次页面置换，比最佳置换算法正好多一倍。 先进先出(FIFO)算法较易实现，比较适用于具有线性顺序特性的程序，而对其他特性的程序则效率不高。缺页中断率为最佳算法的23倍；增加可用主存块的数量会导致更多的缺页，此算法还可能出现抖动现象异常。LRU算法最近最久未被使用(LRU)算法的实现需要硬件支持，基于程序的局部性原理，所以适用用大多数程序，此算实现必须维护一个特殊的队列页面淘汰队列。关键是确定页面最后访问以来所经历的时间。5思考题的解答和讨论（1）设计一个界地址存储管理的模拟系统，模拟界地址方式下存储区的分配和回收过程。提示：必须设置一个内存分配表，按照分配表中有关信息实施存储区的分配，并不断根据存储区的分配和回收修改该表。算法有首次匹配法，循环首次匹配法和最佳匹配法等。可用各种方法的比较来充实实习内容。可使用碎片收集和复盖等技术。答：开始选择菜单0退出程序123分配主存回收主存显示主存NYNN （1）数据结构及说明 本程序为可变分区管理方式主存分配回收模拟程序，采用首次适应策略。 主要数据结构： 空闲区链表FBC，分配区链表ABC： 表中记录块的起始地址和大小，块按照始地址大小从小到大排列。 （2）功能实现 分配时，根据用户提供的作业大小，从第一个空闲块开始查找，将找到的第一个足够大的空闲块块分配给该作业，返回给用户该块始地址。如果该块剩余部分小于特定阈值（本程序为2k),将该块整体分配给此作业，将该块直接加入分配区链表，若剩余块大于或等于阈值，将分配块加入分配区链表，剩余部分作为新的空闲块.另：程序开始时已将0到20k分配给操作系统。 回收时，根据用户提供的作业的始地址，在分配区表查找，若找到该块，将其加入空闲区链表，提示用户释放成功。若新形成的空闲块与其前后的空闲块相连，合并空闲块形成更大的空闲块。 显示，用户可随时选择查看内存分配状态图以及空闲区表与分配区表，在分配或回收成功时，程序自动显示内存分配状态图、空闲区表与分配区表。（2）自行设计或选用一种较为完善的内存管理方法，并加以实现。提示：设计一个段页式管理的模拟程序或通过一个实际系统的消化和分析，编制一个程序来模拟该系统。答: 分配总空间大小为128，若输入的进程大于该数，则显示“占用空间过大，分配失败”若分配的进程大小为0，则显示“进程空间大小错误”选择1分配内存，输入内存名和占用空间大小即可分配内存，显示的项目有进程名、起始地址和长度，已分配的内存分配情况会显示出来，如上图。空间分配满则显示“无空闲区”选择2回收内存，输入已分配的内存名称即可回收该内存，并显示剩余的已分配内存4、 操作系统课程设计小结为期两周的操作系统课设在不断的探索、尝试、成功中结束了。现在，站在成功地峰顶，回顾着走过的一路，真是什么感觉都有，枯燥、失败、劳累、迷茫、喜悦，应该说，我的设计体会相当深刻。首先，谈谈本系统的不足：第一，我设计的页面值换算法里，页面个数和内存个数是一个定数，在这一点上没有实现与操作员的交互，即页面数和内存个数并不能手动输入；第二，我设计的系统在界面上并没有太大的优化，没有实现选择算法后可以重新选择页面产生的算法，重新进行页面置换的选择。总体上来说，这两方面是本系统可以改进的地方，虽然我的课设已经验收，但是我在验收完成后，继续完善了我的整个界面并改进了系统的不足之处，以达到系统的完整性，简洁性，交互性。其次，谈谈本系统特色、新的发明、创造等：第一，在我的系统里，我觉得最大的亮点以及不同于别人的地方就是将三种页面置换算法按照课本上老师讲的方式直观简便的输出，在采用输出算法时，我摒弃了常人所用的一维数组输出法，而别出心裁的采用了二维数组的输出算法，模拟了内存的物理块，清晰直观的表达了页面是如何在外存中被调入内存中的，以及各页面在调入过程中是否命中或在置换时又置换了内存中哪个页面。第二，在软件工程的角度来看，我的系统具有高内聚低耦合的优点，即各种算法之间，并不影响彼此的函数调用，而在各算法的内部，内聚度很高。最后，在整体上自我评价一下我的系统：第一，在功能上，它完全实现了各种页面置换算法的模拟；第二，在界面设计上，新颖独特，独树一帜，采用了二