页式虚拟存储管理缺页中断的模拟系统的设计

页式虚拟存储管理缺页中断的模拟系统的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 武汉理工大学《操作系统》课程设计报告书 目录 目录................................................................................................................................................... 1 一 课程设计目的与功能 ................................................................................................................. 2 1目的........................................................................................................................................ 2 2初始条件................................................................................................................................ 2 3 开发环境............................................................................................................................... 2 4功能........................................................................................................................................ 2 二 需求 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ，整体功能及设计数据结构或模块说明 ................................................................. 3 1 需求分析............................................................................................................................... 3 2 算法分析............................................................................................................................... 4 3 数据结构............................................................................................................................... 6 4 各模块 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 功能说明 ........................................................................................................... 7 三 源程序的主要部分 ..................................................................................................................... 7 1 main函数.............................................................................................................................. 7 2 替换算法实现函数 ............................................................................................................... 8 四 使用说明................................................................................................................................... 11 五 运行结果与运行情况分析 ....................................................................................................... 11 1 FIFO算法............................................................................................................................ 11 3 随机替换算法 ..................................................................................................................... 13 3 OPT替换算法 ...................................................................................................................... 14 结论......................................................................................................................................... 15 六自我评价与总结: ..................................................................................................................... 15 参考文献......................................................................................................................................... 16 附录................................................................................................................................................. 16 - 1 - 武汉理工大学《操作系统》课程设计报告书 页式虚拟存储管理缺页中断的模拟 系统的设计 ——OPT、FIFO、随机淘汰算法 一 课程设计目的与功能 1目的 通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，熟悉和掌握请求分页式存储管理的实现过程，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法，熟悉常见替换算法的原理和实现过程，并利用替换算法的评价指标——缺页次数和缺页率，来对各种替换算法进行评价比较。设计并实现出的结果程序要能够很好地显示页面调入和替换详细信息。 2初始条件 (1)预备内容:阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页 式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。 )实践准备:掌握一种计算机高级语言的使用 (2 3 开发环境 (1)使用系统:Windows XP (2)使用语言:C++ (3)开发工具:Visual C++ 6.0 4功能 设计的结果程序能实现OPT、FIFO、随机淘汰算法模拟页式存储管理缺页中断，主要能够处理以下的情形: (1) 用户能够输入给作业分配的内存块数; (2) 用户能够输入给定的页面，并计算发生缺页的次数以及缺页率; (3) 程序可随机生成页面序列，替代用户输入; (4) 缺页时，如果发生页面置换，输出淘汰的页号。 - 2 - 武汉理工大学《操作系统》课程设计报告书 二 需求分析，整体功能及设计数据结构或模块说明 1 需求分析 在纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，人们提出了能提供虚存的存储管理技术——请求分页存储管理技术和请求分段技术。本设计实现请求分页管理技术。 请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入部分页面的程序和数据，便启动运行。以后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上。置换时以页面为单位，为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。其中硬件支持包括:请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构;缺页中断机构，当要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存;地址变换机构，它同样是在纯分页地址变换机构的基础上形成的。实现请求分页的软件包括用于实现请求调页的软件和实现页面置换的软件。他们在硬件的支持下，将程序正在运行时所需的但尚未在内存的页面调入内存，再将内存中暂时不用的页面从内存置换到外存磁盘上。 为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，和在内存的时间的长短。请求分页中的页表如表1: 表1 虚拟页号 物理块号状态位 辅存地址访问字段 修改位 各字段说明如下: 状态位:用于指示该页是否已调入内存，供程序访问时参考。 访问字段:用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供替换页面时参考。 修改位:表示该页面在调入内存后是否被修改过。由于内存中的每一页都在外存上保留有副本，因此，若未被修改，在替换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数;若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。 外存地址:用于指出该页在外存上的地址，通常是物理块号，供调入页面时参考。 在模拟系统的实现中，只需要用到虚拟页号，物理块号和中断位。页表可用 - 3 - 武汉理工大学《操作系统》课程设计报告书 一个结构体的数组实现。 请求分页的具体实现过程如图1 图1请求分页流程图 开始 请求页面序Y结束列结束, N 选择将要调入页面 页面在内存Y中, N N内存块已满, Y 放入未被占用的利用替换算法，选择内 存块中应该被替换的页内存块中,修改页 面进行替换，修改页表表 2 算法分析 在进程运行过程中，若其所要访问的页面不在内存，这时候会产生一个缺页中断，并需要把它们调入内存，但内存已无空闲已空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区。但应将哪个页面调出，必须根据一定的算法来确定。通常，把选择换出页面的算法称为页面替换算法。虚拟内存性能的好坏很大程度上由替换算法的好坏，替换算法的好坏，也将直接影响系统的性能，一个好的页面置换算法，应具有较低的页面更换频率。 常见置换算法有随机淘汰算法(Random Glongram)、轮转法(Round Robin) - 4 - 武汉理工大学《操作系统》课程设计报告书 和先进先出(FIFO)、最近最久未使用页面置换算法和理想型淘汰算法OPT(Optimal Replacement Algorithm)。本次所设计的模拟系统根据题目要求利用随机淘汰算法，先进先出算法和理想型淘汰算法进行页面替换，详细算法原理如下: 随机淘汰算法:在系统设计人员无法确定哪些页被访问的概率较低时，明智的作法是随机地选择某个用户的页并将其换出。随机淘汰算法实现简单，但是缺页率高。 先进先出算法:总是选择在内存驻留时间最长的一页将其淘汰，因为最早调入内存的页，不再被使用的可能性比近期调入内存的大。该算法实现简单，只需要把一个进程调入内存的页面，按先后次序连结成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如有全局变量、常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。 假定系统为某进程分配了三个可用物理块，并考虑有以下的页面号引用串: 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装入内存，且采用FIFO替换算法。当 ，0，1三个页号可知道7先进入内存，所以替换有请求页面2时，内存中页面7 ;当请求页面0时，可知，0在内存中，不需要替换;当请求页面号3时页面1 内存中0，1，2三个页面0先进入内存，替换0号页。如此进行下去，可得出利用FIFO替换算法，以上请求页面号序列共进行了12次页面替换，比理想型算法要多出一倍。 使用FIFO替换算法效率低的原因是:基于处理器按线性顺序访问地址空间这一假设。事实上，许多时候，处理器不是按线性顺序访问地址空间的。例如，执行循环结构的程序段。 使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象(Belady现象)。 例如针对请求序列:1 2 3 4 1 2 5 1 2 3 4 5，若分配3个可用内存块，使用FIFO算法，一共会缺页9次，缺页率:75%;而如果分配4个可用内存块，则一共会缺页10次，缺页率:83.3%。 理想型淘汰算法基本思想:当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。采用理想型替换算法，通常可保证获得最低的缺页率。但是由于人们目前无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是在模拟设计中，由于是事先给定一个页面序列，即知道各个时刻以前和以后的页面出现情况，所以可实现该算法。在实际系统中，虽无法实现理想型淘汰算法，但是可用它来评价其他替换算法。 用上面的例子，先将7，0，1三个页面装入内存。以后当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳替换算法，将选择页面7予以淘汰，这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面1则要在第18次页面访问时才需要调入。下次访问页面0时，因它已经在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1被淘汰;因为，它在现有的1，2，0三个页面中，将是最后被访问的。如此继续，这个作业序列将会产生6次页面置换。 理想型淘汰算法的具体工作流程如图2: - 5 - 武汉理工大学《操作系统》课程设计报告书 图2 开始 i=0; Page=当前请求页面序列号 选择使得OPT[i]最大i= memorySizeY的i，就是应该被替 ,换占用的内存块 N 选择在内存块i 中的页面j结束 t=page+1 t++; OPT[i]=inputSize;Yt=inputSize,i++; NN j=in[t], Y OPT[i]=t; i++; 3 数据结构 模拟设计时，页表用数组模拟。数组的数据类型为结构体，结构体有三个成员:int pageNum 表示页面号;int memoryNum表示页面所对应的内存块号;int isInmemory是存在状态位标志，表示页面是否在内存，0表示不在内存，1表示在内存。程序中设定虚拟页面号共10个，所以页表大小为10，即10个元素的数组pageTable。在每一个算法函数中都要初始化页表，否则，后面的算法会受前面算法结果的影响。 struct page { int pageNum; int memoryNum; int isInmemory; - 6 - 武汉理工大学《操作系统》课程设计报告书 }; page pageTable[10]; 初始化页表: for(int i=0;i<10;i++) { pageTable[i].pageNum=i; pageTable[i].memoryNum=-1; //初始化时，内存块号为-1，即没在内存块中。 pageTable[i].isInmemory =0; //初始化时，各页面均不在内存 } 页面请求序列:int *in= new int[inputSize]。 模拟内存:int *memory=new int[memorySize]，在程序中模拟内存存放页面号。 4 各模块函数功能说明 int Main()函数提示并接受用户输入等待调入页面数inputSize，可用物理块数memorySize，并随机生成inputSize个请求页面，或提示用户自己输入页面序列。然后调用FIFO()、random()和OPT()函数实现按不同替换算法调入页面进内存。 void FIFO()函数实现先进先出的替换算法调入页面。 void random()函数实现随机替换算法调入页面。 void OPT()函数实现理想型替换算法。 int getOPTPage(int page)用于获取最优替换页面所在的内存块。该函数的算法实现流程图如图2。 三 源程序的主要部分 1 main函数 int main() { for(int i=0;i<10;i++) //初始化页表 { pageTable[i].pageNum=i; pageTable[i].memoryNum=-1; pageTable[i].isInmemory =0; } cout<<"输入待调入页面数"<>inputSize; - 7 - 武汉理工大学《操作系统》课程设计报告书 cout<<"输入可使用的物理块数:"<>memorySize; int temp; srand( (unsigned)time( NULL ) ); cout<<"随机生成页面请求序列(0-9)"<opt[optNum]) - 10 - 武汉理工大学《操作系统》课程设计报告书 optNum=i; } return optNum; } 四 使用说明 运行程序替换算法.exe，根据提示输入等待调入页面数和可使用的物理块数，程序会提示是否随机生成并显示一个页面请求序列，如果是，则随机生成序列，否则，要求自行输入序列。然后显示利用各算法处理请求页面的结果:如果页面在内存则显示“ ‘页面号’is in memory ”，若不在内存则显示 “‘页面号’not in memory～take place of ‘被替换的页面号’”。处理完各页面后，统计并显示缺页次数和缺页率。 五 运行结果与运行情况分析 待调入页面数:25 可用物理块数:3 随机生成页面请求序列，如图3: 0 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 图3 1 FIFO算法 运行结果，如图4: - 11 - 武汉理工大学《操作系统》课程设计报告书 图4 结果分析，如表2(×表示缺页，并在下方填被替换的页面号，?表示不缺页): 表2 0 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 4 4 4 6 6 6 6 6 9 9 9 9 6 6 6 6 6 5 5 5 5 5 3 3 3 0 0 0 0 0 5 5 5 5 2 2 2 8 8 8 8 8 8 8 3 3 9 9 9 1 1 1 1 1 0 0 0 0 7 7 7 7 7 2 2 2 2 2 0 × × × × × × × ? ? × × × ? × × × × ? ? × × ? ? × × 0 3 9 4 0 1 6 5 0 9 2 7 6 8 2 通过表可以看出，利用随机替换算法，请求序列共缺页18次，替换序列依 次是:0 3 9 4 0 1 6 5 0 9 2 7 6 8 2，缺页率72%，运行结果与分析结果一致。 - 12 - 武汉理工大学《操作系统》课程设计报告书 3 随机替换算法 运行结果，如图5: 图5 结果分析，如表3(×表示缺页，并在下方填被替换的页面号，?表示不缺页): 表3 0 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0 6 6 6 6 6 5 5 5 5 5 3 3 3 0 1 6 6 1 1 1 9 9 9 7 7 7 7 7 7 7 7 7 7 0 9 9 9 9 9 9 9 5 5 5 5 2 2 2 8 8 8 2 2 2 2 3 3 × × × × × × × ? ? × × × ? × × × × ? ? × × ? ? × × 0 3 0 1 4 6 9 1 5 9 0 2 8 6 2 7 通过表可以看出，利用随机替换算法，请求序列共缺页19次，替换序列依 次是:0 3 0 1 4 6 9 1 5 9 0 2 8 6 2 7 缺页率为76%，运行结果与分析结果一致。 - 13 - 武汉理工大学《操作系统》课程设计报告书 3 OPT替换算法 运行结果，如图6: 图6 结果分析，如表4(×表示缺页，并在下方填被替换的页面号，?表示不缺页): 表4 3 9 4 0 1 6 0 1 5 0 9 5 2 7 6 8 8 8 2 5 2 5 3 0 0 0 0 0 0 0 0 0 0 0 0 9 9 2 2 2 2 2 2 2 2 2 2 3 2 3 3 4 4 1 1 1 1 5 5 5 5 5 7 7 8 8 8 8 5 5 5 5 5 9 9 9 9 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 × × × × ? × × ? ? × × ? × × ? × ? ? ? × ? ? × × 3 4 9 1 0 9 5 7 8 2 3 通过表可以看出，利用随机替换算法，请求序列共缺页14次，替换序列依 次是:3 4 9 1 0 9 5 7 8 2 3， 缺页率为56%，运行结果与分析结果一致。 - 14 - 武汉理工大学《操作系统》课程设计报告书 结论 通过测试运行，可以看出结果程序能满足设计要求，提示用户对请求序列的大小和可用内存数量进行限制，并提示用户输入请求序列号，或系统随机生成序列，按照不同的替换算法处理并且显示请求页面的调入和替换情况。 通过以上运行，比较各种算法的缺页次数和缺页率，可以看出OPT替换算法具有最小的缺页率。虽理论上最优，但是实际却无法实现该算法。 六自我评价与总结: 通过一周的努力，终于完成了模拟系统的设计和实现，并按照 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 编写了课程设计报告书。在这一周里，为了较好地完成本次设计任务，翻阅了大量的图书资料，既有有关操作系统相关知识的，也有针对编写用语言c++语言知识的。在翻阅查看相关资料的过程中，丰富和巩固了操作系统的理论知识，对课堂上不明 补充学习，同时也增加确和不懂的知识，如请求分页的工作流程，都得到了很好 语言本身的应用能力。 了c++ 本次设计作得比较好的地方有:流程清晰，通过绘制流程图，较好地理解了请求分页的工作流程;算法设计合理，容易理解，实现简单;结果显示清晰明了，能清晰地看出各请求页面的存在和替换信息。 设计中不足的地方:实际上请求分页存储管理中，为了增加内存的利用率，所分配的内存是不连续的，但是在模拟系统中，用的是一个数组来模拟内存空间，即使得所分配的内存是连续的，与实际情况不相符合;另外，虽然几经调试和修改，但是程序中仍然有内存访问相关的问题。 其他可用算法:请求分页内存管理的页面替换还可以用LRU，即最近最久未使用替换算法。LRU的基本思想是:当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。即当需要淘汰一页时，选择最长时间未使用的页。它是基于假设:如果某页被访问，它可能马上还要被访问;相反，如果某页长时间未被访问，它可能最近也不可能被访问。实现时可为每个页设置一个特定的单元，用于记录自上次访问以来所经历的时间t，当需要置换一页时，选择t最大的淘汰。 通过对请求分页替换模拟系统的设计和实现，巩固了理论知识，对一些不明白的概念，有了很好的认识，同时增加了自己的程序算法设计能力和编程动手的能力。 - 15 - 武汉理工大学《操作系统》课程设计报告书 参考文献 ,1, 张尧学，史美林编著(计算机操作系统教程(第二版)(清华大学出版社(2000 ,2,孟静(操作系统原理教程(清华大学出版社(2000 ,3,黄干平，陈洛资等(计算机操作系统(科学出版社(1989 ,4,汤子瀛，哲凤屏，汤小丹编著(计算机操作系统(西安电子科技大学出版 社(1996 附录 #include #include using namespace std; int inputSize; int memorySize; int *in; //请求序列 int *memory; //模拟内存 void FIFO(); void random(); void OPT(); int getOPTPage(int inPage); struct page { int pageNum; int memoryNum; int isInmemory; }; page pageTable[10]; //假设虚拟页面数10个，页表长度10 int main() { for(int i=0;i<10;i++) //初始化页表 { pageTable[i].pageNum=i; pageTable[i].memoryNum=-1; pageTable[i].isInmemory =0; } cout<<"输入待调入页面数"<>inputSize; cout<<"输入可使用的物理块数"<>memorySize; in= new int[inputSize]; memory=new int[memorySize]; int temp; int select; srand( (unsigned)time( NULL ) ); cout<<"随机生成请求序列,(1是)"<>select; if(select==1) { cout<<"随机生成页面请求序列(0-9)"<>temp; in[i]=temp; } } cout<opt[optNum]) optNum=i; } return optNum; } - 24 -