虚拟存储器管理设计

摘要虚拟存储技术是随着计算机技术的发展而发展起来的。早在20世纪70年代，为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了虚拟内存技术。本文采用模块化系统设计方法，对磁盘调度进行模拟实现，主要完成了FIFO（先进先出算法）、LRU（最近最久未使用算法）以及OPT（最佳置换算法）的调度实现。系统采用从文件读取进程信息的方式，并提供用户自行选择调度算法，并提供算法对比，以便用户明显看出算法的优劣。本文包含采用了结构体等数据结构，编写了寻找时间最长页面功能模块、页面读入功能模块、FIFO功能模块、LRU功能模块等。基本实现虚拟存储器调度的模拟实现，达到本系统设计要求。关键字：虚拟存储器、页面调度、管理系统目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要I一、设计任务分析11.1虚拟存储技术分析：1\o"CurrentDocument"1.1.1虚拟存储技术概述11.1.2虚拟存储技术的概念11.2使用算法分析：2FIFO算法（先进先出淘汰算法）2\o"CurrentDocument"LRU算法（最久未使用淘汰算法）3\o"CurrentDocument"OPT算法（最佳淘汰算法）3二、总设计方案42.1、置换算法思想4\o"CurrentDocument"2.2、LRU置换算法的硬件支持5三、程序设计结构图63.1虚拟存储管理器系统设计总框图63.2各模块功能N-S图73.2.1寻找时间最长的页面功能模块：73.2.2内存页面输入功能模块：7\o"CurrentDocument"四、项目截图10五、设计程序源代码115.1源代码11\o"CurrentDocument"五、设计心得18\o"CurrentDocument"六、参考文献19虚拟存储器管理系统设计—、设计任务分析本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备管理子模块。1.1虚拟存储技术分析：1.1.1虚拟存储技术概述虚拟存储技术是随着计算机技术的发展而发展起来的。早在20世纪70年代，为了克服内存容量小成本高而不适应大型程序应用需要的矛盾，人们开发了虚拟内存技术。随着计算机技术及相关信息处理技术的不断发展，人们对存储的需求越来越大，单个大容量磁盘已不能适应应用的需要，虚拟存储技术又有进一步的发展，如在操作系统下将一组硬盘捆绑成带区集（STRIP）作为单个逻辑存储单元供主机访问；磁盘冗余阵列（RAID）技术将多个物理磁盘通过一定的逻辑关系集合起来，成为一个大容量的虚拟磁盘。从某种意义上讲，SAN本身也是虚拟存储技术的应用。1.1.2虚拟存储技术的概念所谓虚拟存储技术，是指把多个物理上独立存在的存储体通过软件或硬件的手段集中管理起来，形成一个逻辑上的虚拟存储单元供主机访问。这个虚拟逻辑单元的存储容量是它所集中管理的各物理存储体的存储容量之和，而它的访问带宽则在一定程度上接近各个物理存储体的访问带宽之和。虚拟存储实际上是逻辑存储，是一种智能、有效地管理存储数据的方式。虚拟存储克服了物理存储的局限，它可以把物理设备变成完全不同的逻辑镜像，呈现给用户，既充分利用了物理设备的优势，如高性能、高可用，又打破了物理设备本身不可克服的局限性。从用户角度看，使用存储空间而不是使用物理存储硬件，管理存储空间而不是管理物理存储部件，这就是虚拟存储的概念。1.2使用算法分析：FIFO算法（先进先出淘汰算法）1）什么是先进先出淘汰算法？当需要淘汰一页时，总是选择主存中居留时间最长（即最老）的一页淘汰。2）实现方法系统保留一张次序表，该表记录了作业程序的各页面进入主存的先后次序。•用数组作次序表可在主存中建立一个m（m是分配给该作业的存储块数）个•用存储分块表作次序表该次序表以块号为序，依次各块的分配情况。这里假定m=4,且4,5,1,2页以依次装入2,6,7,4各存储块中。此时存储分块表如下图所示：当需要第6页时将替换第4页LRU算法（最久未使用淘汰算法）1）什么是最久未使用淘汰算法？当需要淘汰一页时，总是选择最长时间未被使用的那一页淘汰。2）实现方法•用硬件实现此算法每一页可以设置一个R位的寄存器；每次访问一页时，将该页所对应的寄存器的最左一位置1；每隔时间t将所有的R位寄存器右移一位。这样，在T=Rt时间内，方问过的页多对应的寄存器R内时一个不全为0的整数，而没有访问过的页相对应的R之值为0。当缺页中断时，选择R值最小的那页进行淘汰。OPT算法（最佳淘汰算法）1）什么是最佳淘汰算法?当需要淘汰一页时，将选择以后永不使用的或许是在最长（未来）时间内不再被访问的页面。2）算法优势采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。二、总设计方案2.1、置换算法思想最佳置换算法（Optimal）:它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。先进先出（FIFO）页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。LRU置换算法：LRU（LeastRecentlyUsed）置换算法的描述:FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。2.2、LRU置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持：1）寄存器为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示R=Rn-1Rn-2Rn-3……R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。此时，定时信号将每隔一定时间（例如100ms）将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。这里，把8个内存页面的序号分别定为1~~8。由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。表2.1寄存器使用状况实页R7R6R5R4R3R2R1R01010100102101011003000001004011010115110101106001010117000001112）栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。三、程序设计结构图3.1虚拟存储管理器系统设计总框图虚拟存储器管理系统输入内存页面数'V1rVV1FFL算法三种算法比较退出计算淘汰页和缺页计算淘汰页和缺a计算淘汰页和缺页系统功能描述：通过设计操作系统流程图页面进行比较，选择适合虚拟存储管理系统理想的调度算法。3.2各模块功能N-S图3.2.1寻找时间最长的页面功能模块:算法思想：通过寻找时间最长的页面，为进行FIFO,LRU,ORT三种调度算法运算提供前提条件。主要参数功能：Pro*page用来指向调入内存最长时间的页面intMax(Pro+pagel)Pro+page=newPm[N];page=pagel;inte=page[0].timej=□;while(i<N液出离现在时间最长的页面)if(e<page[i].time)e=page[i].time;i++；ftir(i=0;i<N;i++)3.算读12.2法思入的:3.算读12.2法思入的:内有页面输入功能想：页面流，如文件不符，则显示“错误，文件打不开，请检查文件名”。输入瞄页面，选择调度功能，并输入正确页面流文件名，显示intreadDataQF=0;FILE*fp;charfriame[20];inti;cout«'请输入贝面流文件名:"；cin>>friame;一~~~~~~~if((fp=fopen(fhame/'r"))==NULL)〜then————elseEUtZ错误j文件打不开.请检查文件名匕图3.2输入模块while(!feof(fp))fecanfffpj"%d",Squeue[F]);N-S图+；cout«"i^A的贝面流:七for(i=0;i<F;i++)coLJt«qLjeue[i]«"7cout«"\ri"；returnF;

FIFO功能模块：算法思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。算法思想：最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

图3.4LRUN-S图四、项目截图4.可女乂lusersijDOEs\ueE£top\znao\znao.exe0033444116|缺页置换情况二111114448缺页次数:12缺页率:0.666667('、0033444116】.」虹■Maiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiifc图43、.五、设计程序源代码5.1源代码#include<iostream.h>#include<stdlib.h>#include<stdio.h>#defineM40intN;intqueue[M];intF;floatS[3][2];structPro(intnum,time;};intreadData()(F=0;FILE*fp;charfname[20];inti;cout<<"请输入页面流文件名：〃；cin>>fname;if((fp=fopen(fname,"r"))==NULL)(cout<<"错误，文件打不开，请检查文件名〃;}else(while(!feof(fp))(fscanf(fp,"%d〃,&queue[F]);F++;}}cout<<"读入的页面流：〃；for(i=0;i<F;i++)(cout<<queue[i]<<”";}cout<<"\n";returnF;}voidprint(Pro*page1)//打印当前的页面(Pro*page=newPro[N];page二page1;for(inti=0;i<N;i++)cout<<page[i].num;cout<<endl;}intSearch(inte,Pro*page1)(Pro*page=newPro[N];page=page1;for(inti=0;i<N;i++)if(e==page[i].num)returni;return-1;}intMax(Pro*page1)(Pro*page=newPro[N];page=page1;inte=page[0].time,i=0;while(i<N)//找出离现在时间最长的页面(if(e<page[i].time)e=page[i].time;i++;for(i=0;i<N;i++)if(e==page[i].time)returni;return-1;}intCompfu(Pro*page1,inti,intt,Prop[M])(Pro*page=newPro[N];page二page1;intcount=0;for(intj=i;j<M;j++)(if(page[t].num==p[j].num)break;elsecount++;}returncount;}voidFifo(Prop[M],Pro*page)(F=0;intt=0,i=0;//Y[0]=0;floatn=0;cout<<"FIFO页面调度算法〃<<endl;F=readData();cout<<"页面置换情况："<<endl;while(i<F)(if(Search(queue[i],page)>=0){i++;}//找到相同的页面else(if(t==N)(t=0;}else(n++;page[t].num=queue[i];print(page);t++;}}}cout<<endl<<"缺页次数：〃<<n<<〃缺页率："<<n/F<<endl;S[0][0]=n;S[0][1]=n/F;}voidLru(Prop[M],Pro*page)(F=0;intt=0,i=0;floatn=0;cout<<"LRU页面调度算法"<<endl;F=readData();cout<<"页面置换情况："<<endl;while(i<F)(intk;k=t=Search(queue[i],page);if(t>=0)page[t].time=0;else(n++;t=Max(page);page[t].num=queue[i];page[t].time=0;}if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}if(k==-1)print(page);i++;}cout<<"缺页次数：〃<<n<<〃缺页率："<<n/F<<endl;S[1][0]=n;S[1][1]=n/F;}voidOpt(Prop[M],Pro*page)(F=0;intt=0,i=0;floatn=0;//m=Input(m,p);cout<<"OPT页面调度算法"<<endl;F=readData();for(i=0;i<F;i++)(p[i].num=queue[i];}i=0;while(i<F)(if(Search(queue[i],page)>=0)i++;else(inttemp=0,cn;for(t=0;t<N;t++)(if(temp<Compfu(page,i,t,p))(temp二Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}cout<<"缺页次数：〃<<n<<〃缺页率："<<n/F<<endl;S[2][0]=n;S[2][1]=n/F;voidcompare()(cout<<"FIFO页面置换算法〃<<endl;缺页率：〃<<S[0][1]<<endl;缺页率：〃<<S[1][1]<<endl;缺页率：〃<<S[2][1]<<endl;cout<<〃缺页次数：〃<<S[0][0]<<〃cout<<"LRU页面置换算法〃<<endl;cout<<〃缺页次数：〃<<S[1][0]<<〃cout<<〃OPT页面置换算法〃<<endl;cout<<〃缺页率：〃<<S[0][1]<<endl;缺页率：〃<<S[1][1]<<endl;缺页率：〃<<S[2][1]<<endl;cout<<〃可用内存页面数〃<<endl;cin>>N;}voidquit()(N=0;F=0;inti=0;intt=0;free(S);free(queue);}intmain()(//cout<<〃可用内存页面数〃<<endl;//cin>>N;Prop[M];floatn=0;intc=0;Pro*page二newPro[N];cout<<〃|1"<<endl;cout<<"|虚拟存储管理器的页面调度|"<<endl;cout<<〃11"<<endl;while(1)(for(inti=0;i<N;i++)//初试化页面基本情况(page[i].num=0;page[i].time=2-i;}i=0;cout<<〃*********************1:输入可用页面数"<<endl;cout<<〃*********************2:FIFO页面置换"<<endl;cout<<〃*********************3:LRU页面置换"<<endl;cout<<〃*********************4:OPT页面置换〃<<endl;cout<<〃*********************5:算法比较〃<<endl;cout<<〃*********************0:退出程序〃<<endl;cout<<endl;cout<<〃请输入功能号(0~5):〃；cin>>c;switch(c)(case1:Build();break;case2:Fifo(p,page);break;case3:Lru(p,page);break;case4:Opt(p,page);break;case5:compare();break;case0:quit();return0;}}return0;五、设计心得通过一周的课程设计，加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现，特别是对虚拟存储，页面置换有了深入的了解，并能够用高级语言进行模拟演示。这次的操作系统大作业的工作量比较大，我投入了很多的时间和精力才完成了系统的设计。不过这些付出都是值得的，因为我收获了更多。在本次实验中，我和我的小组分工合作，互相帮助，通过到图书馆找资料，翻阅书本和网上搜索，理解到虚拟页式管理的基本原理是系统自动地将作业的地址空间分页，还有研究了主存页面的分配策略和页面调入时机。这对之后的算法编写有很大的帮助。其后，为了熟悉各算法的思想，我们重新复习了操作系统页面调度中OPT、FIFO、LRU的算法，上网查阅各算法的资料，经过一段时间的研究，我开始编写算法的程序。虽然了解了各算法的思想，但到编写起程序来，还是有一点难度，又需要再复习C++的部分语法，如文件流的输入输出，因为对课堂知识只是了解，但实践中有些不常用的命令很容易会遗忘。在详