湖南大学操作系统实验报告-(3)

1、实验三 内存页面置换算法的设计一、实习内容实现最近最久未使用（LRU）置换算法二、实习目的LINUX 中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分 （段或页） 调入内存便可运行，还支持请求调页的存储管理方式。当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向 CPU 发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。当 CPU 接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容

2、纳新页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的技术特点，掌握请求页式存储管理的页面置换算法。三、实习题目实现最近最久未使用（LRU）置换算法提示：(1) 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。例

3、如 :分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，则缺页次数和缺页率按表 3-1 给出: 缺页次数: 15缺页率: 15/20=0.75(2) 假定分配给该进程的页块数为 3，页面访问序列长度为 20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用 LRU算法，将当前一段时间内最久未使用过的页替换出去。模拟程序的算法如图 3-2。四、源程序及程序中使用的数据结构、符号说明#include<iostream>#include<cstring>#include<ve

4、ctor>#include<cmath>#include<ctime>#include<cstdlib>#include<iomanip>using namespace std;void showState(int page20,int visit2,int t);int pick(int page20,int visit2,int time,int useTime);int min(int a,int b,int c);int main()srand(time(NULL);int visit202;memset(visit,-1,size

5、of(visit);for(int i=0;i<20;i+)visiti0=rand()%8;cout<<"20位长的随机访问序列为:"<<endl;for(int i=0;i<20;i+)cout<<setw(2)<<visiti0<<" "cout<<endl;int page320;memset(page,-1,sizeof(page);int useTime3;memset(useTime,0,sizeof(useTime);for(int t=0;t<20

6、;t+)int p=pick(page,visit,t,useTime);/选中的页 if(p<0)/命中第p+3页，设置此页命中，帧内容不变 visitt1=1;for(int x=0;x<3;x+)pagext=pagext-1; useTimep+3=t;else/ 此页不命中，帧内容替换 visitt1=0;if(t=0)pagept=visitt0;elsefor(int y=0;y<3;y+)pageyt=pageyt-1;pagept=visitt0;useTimep=t;showState(page,visit,t);int miss=0;for(int i=

7、0;i<20;i+)if (visiti1=0) miss+; double per=1-(double)miss/20;int peri=per*100;cout<<"共miss"<<miss<<"/20次,"<<"命中率为" <<peri<<"%"return 0;int pick(int page20,int visit2,int time,int useTime)/如果命中了，就返回下标-3，比如如果0帧命中，返回-3/如果不命中

8、，选择一个最久没有访问到的帧，返回帧下标cout<<"输出usetime: "cout<<useTime0<<" " <<useTime1<<" " <<useTime2<<" "<<endl; for(int i=0;i<3;i+) /先遍历一遍，看有没有命中的if(pageitime-1=visittime0)cout<<"time"<<time<<&qu

9、ot;此次要调度的页号"<<visittime0<<"命中当前第"<<i<<"帧"<<endl; return i-3; for(int i=0;i<3;i+)/不存在命中，则从头开始选，先选帧空的情况 if(pageitime-1=-1)cout<<"time"<<time<<"选中第"<<i<<"个空页" <<endl;return i;/都没有

10、，就选最久没用过的 int m=min(useTime0,useTime1,useTime2);cout<<"time"<<time<<"此次要调度的页号"<<visittime0<<"选中第"<<m<<"个最久没有使用的页" <<endl;return m;void showState(int page20,int visit2,int t)cout<<t<<"时刻访问状态"

11、<<endl;cout<<"时间"for(int i=0;i<20;i+)cout<<setw(3)<<i<<" "cout<<endl;cout<<"序列"for(int i=0;i<20;i+)cout<<setw(3)<<visiti0<<" "cout<<endl;cout<<"零帧"for(int i=0;i<=t;i+)co

12、ut<<setw(3)<<page0i<<" "cout<<endl;cout<<"一帧"for(int i=0;i<=t;i+)cout<<setw(3)<<page1i<<" "cout<<endl;cout<<"二帧"for(int i=0;i<=t;i+)cout<<setw(3)<<page2i<<" "cout<

13、<endl;cout<<"命中"string str1=""string str2="×" for(int i=0;i<=t;i+)string x=(visiti1=1)? str1:str2;cout<<setw(3)<<x<<" " cout<<endl<<endl;int min(int a,int b,int c)if(a<=b&a<=c) return 0;if(b<a&b&l

14、t;=c) return 1;if(c<a&c<b) return 2;代码详细说明：在本例中，我设定了页面调度页块数为3，要访问的页面序列长度为20.从随机数获取20个访问的页面后进行页面调度算法，并将每次调度完的结果打印到控制台面板上，页面调度的具体算法为：维护一个useTime数组，其中存储着三个页块的上次使用时间，在每次向页块中调度内容/页块或页面访问命中页块时，更新被访问的页块的使用时间，如果页面访问不命中页块时，则选择useTime数组中最小的那一块，即最久没使用的页块，置换其中的内容。下面是针对代码的说明：srand(time(NULL);int visit2

15、02;memset(visit,-1,sizeof(visit);for(int i=0;i<20;i+)visiti0=rand()%8;int page320;memset(page,-1,sizeof(page);int useTime3;memset(useTime,0,sizeof(useTime);以上几行代码的作用为生成一个随机的20位的页面访问序列，由于对8作了取余操作，所以生成的访问序列下标为0-7，并存储在visit数组的第0位中，且在visit数组的第1位中赋值-1。同时生成page数组以实现对3个页块的随时间变化的追踪，维护useTime数组以保存3个页块的上次使

16、用时间。下面介绍代码的调度实现部分int pick(int page20,int visit2,int time,int useTime)/如果命中了，就返回下标-3，比如如果0帧命中，返回-3/如果不命中，选择一个最久没有访问到的帧，返回帧下标cout<<"输出usetime: "cout<<useTime0<<" " <<useTime1<<" " <<useTime2<<" "<<endl; for(int i=0

17、;i<3;i+) /先遍历一遍，看有没有命中的if(pageitime-1=visittime0)cout<<"time"<<time<<"此次要调度的页号"<<visittime0<<"命中当前第"<<i<<"帧"<<endl; return i-3; for(int i=0;i<3;i+)/不存在命中，则从头开始选，先选帧空的情况 if(pageitime-1=-1)cout<<"t

18、ime"<<time<<"选中第"<<i<<"个空页" <<endl;return i;/都没有，就选最久没用过的 int m=min(useTime0,useTime1,useTime2);cout<<"time"<<time<<"此次要调度的页号"<<visittime0<<"选中第"<<m<<"个最久没有使用的页" &

19、lt;<endl;return m;Pick函数传入的参数为page数组，visit数组，当前时间t和useTime数组，它会首先检查下一时刻的访问内容visitt0是否出现在上一时刻的三个页块中，如果出现，则返回值为 【块数-3】，以区别于调度的返回值。如果下一时刻的访问没有出现在上一时刻的页块中，则对于下一时刻的访问，要首先判断是否有空块，即页块内容为-1的情况，如果有页块为空，则选择页号最小的页块，将要访问的内容置入该块。如果以上情况均没有出现，则选择useTime中最小的那一块，替换该块中的内容。该函数在main函数中的调用为：for(int t=0;t<20;t+)int

20、 p=pick(page,visit,t,useTime);/选中的页 if(p<0)/命中第p+3页，设置此页命中，帧内容不变 visitt1=1;for(int x=0;x<3;x+)pagext=pagext-1; useTimep+3=t;else/ 此页不命中，帧内容替换 visitt1=0;if(t=0)pagept=visitt0;elsefor(int y=0;y<3;y+)pageyt=pageyt-1;pagept=visitt0;useTimep=t;showState(page,visit,t);分别对于页面命中的情况和不命中的情况设置对应的输出，并更

21、新页面的useTime数组，并在最后调用showState(page,visit,t);函数来展示实时的页面内容showState(page,visit,t);函数的定义如下：void showState(int page20,int visit2,int t)cout<<t<<"时刻访问状态"<<endl;cout<<"时间"for(int i=0;i<20;i+)cout<<setw(3)<<i<<" "cout<<endl;co

22、ut<<"序列"for(int i=0;i<20;i+)cout<<setw(3)<<visiti0<<" "cout<<endl;cout<<"零帧"for(int i=0;i<=t;i+)cout<<setw(3)<<page0i<<" "cout<<endl;cout<<"一帧"for(int i=0;i<=t;i+)cout<<

23、setw(3)<<page1i<<" "cout<<endl;cout<<"二帧"for(int i=0;i<=t;i+)cout<<setw(3)<<page2i<<" "cout<<endl;cout<<"命中"string str1=""string str2="×" for(int i=0;i<=t;i+)string x=(visiti1=1)? str1:str2;cout<<setw(3)<<x<<" " cout<<endl<<endl;由于展示部分的代码较为简单，只是对于数组的输入输出，就不做赘述了。最后，遍历一次page数组，求出总的缺页次数和缺页率。i