操作系统：虚拟存储管理技术

本文主要是介绍操作系统：虚拟存储管理技术，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

虚拟存储管理技术
- 一、实验目的
- 二、实验要求与内容、过程与结果
系列文章

虚拟存储管理技术

一、实验目的

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

二、实验要求与内容、过程与结果

1.用随机数产生一个指令序列，共320条指令。其地址按下述原则生成：

①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分；

具体的实施方法是：

A.在[0，319]的指令地址之间随机选区一起点M;
B.顺序执行一条指令，即执行地址为M+1的指令；
C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’；
D.顺序执行一条指令，其地址为M’+1；
E.在后地址[M’+2，319]中随机选取一条指令并执行；
F.重复A—E，直到执行320次指令。

2.指令序列变换成页地址流

设：（1）页面大小为1K；用户内存容量为4页到32页；用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）；
第10条—第19条指令为第1页（对应虚存地址为[10，19]）；
……………………………………
第310条—第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。

3.计算并输出下述各种算法在不同内存容量下的命中率。

FIFO先进先出的算法
LRU最近最少使用算法
LFU最少访问页面算法

4.运行实例程序，内存块分别为4和5时，记录运行结果。缺页率有何变化？

内存块为4时 FIFO:

4.1

内存块为4时 LRU:

4.2

内存块为4时 LFU:

4.3

内存块为5时 FIFO:

4.4

内存块为5时 LRU:

4.5

内存块为5时 LFU:

4.6

答：随内存块数量的增加，缺页率降低。

5.参照示例程序，实现OPT算法。

提示：

A.缺页率=页面失效次数/页地址流长度=缺页次数/页面访问次数。
B.为了调试方便，可设置页地址流长度（页面访问次数）为100，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
C.关于随机数产生方法，采用函数RAND()和RANDOMIZE()来产生。
D.OPT算法可修改示例程序，先生成页面访问序列，在需要淘汰页面时，从内存块中选择未来最久才被访问的页淘汰之。

程序代码：

#include <iostream>
#include<stdio.h>
#include <stdlib.h>
#include<time.h>
using namespace std;
#define Options 100  //共100条指令
struct MemBlock
{int page;int count;MemBlock* next;
};
int main()
{time_t t;srand(unsigned(time(&t)));int i,n,j,ii,m,answer,ffalse,count,fangfa,min;double sum;MemBlock *head,*tail,*temp,*table,*first,*ti,*Loadin;cout<<"输入分配的内存块数目【2-6】："<<endl;cin>>m;cout<<endl;cout<<"内存块初始化：\n";table=new(MemBlock);temp=table;table->page=-1;table->count=0;head=table;for(ii=2; ii<=m; ii++){table=new(MemBlock);table->page=-1;table->count=0;temp->next=table;temp=table;if (ii==m)table->next=NULL;}for(ti=head; ti!=NULL; ti=ti->next)cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t";cout<<endl;cout<<"采用页面置换法:\n"<<"1-FIFO\n"<<"2-LRU\n"<<"3-LFU\n"<<"4-OPT"<<endl;cout<<"请选择【1-4】:";cin>>fangfa;tail=table;temp=head;ffalse=0;answer=0;first=head;count=0;i=0;int index=0;int z;int input[Options];for(z=0;z<Options;z++){input[z]=(rand()%Options+1)%Options/10;}for(z=0;z<Options;z++){if(z%5==0)printf("\n");printf("%3d",input[z]);}printf("\n");while(i<Options)  //320条指令，指令访问地址为0-319{table=head;temp=head;answer=0;min=400;//随机生成指令的访问地址n，j为页号if (count==0){n=(rand()%Options+1)%Options;j=n/10;}if(count==1){n=rand()%(n+1);j=n/10;}if(count==2){j=((n+1)%Options)/10;}if(count==3){j=((rand()%(Options-n-2))+n+2)/10;}if (fangfa==2||fangfa==3){while(table!=NULL){if (table->page==j) //访问的页已装入内存{answer=1;++(table->count);break;}table=table->next;}if(answer!=1) //访问的页不在内存{++ffalse; //页面缺页次数加1cout<<j<<"页不在内存，请求装入！\n";table=head;while (table!=NULL) //查找最少访问的页temp{if(table->page==-1)  //如果有空闲页，则不需要置换{temp=table;break;}if (table->count<min){temp=table;min=table->count;}table=table->next;}if (temp->page!=-1)  //淘汰temp页cout<<temp->page<<"页被淘汰！\n";temp->page=j;  //装入j页到temp块中temp->count=1;if(count==3)  //每过4次页面访问进行一次计数{table=head;while(table){if(table->page!=j && table->count>0)table->count-=1;table=table->next;}}}}if (fangfa==1)  //FIFO算法{int flag=0;Loadin=first;while(table!=NULL){if (table->page==j){answer=1;table->count++;break;}if(flag==0&&table->page==-1) //空闲块{Loadin=table;flag=1;}table=table->next;}if(answer!=1){++ffalse;cout<<j<<"页不在内存，请求装入！\n";if (Loadin->page!=-1){cout<<Loadin->page<<"页被淘汰！\n";first=first->next;    //下次被淘汰的页if (first==NULL)first=head;}Loadin->page=j;Loadin->count=1;}}if(fangfa==4)       //opt{while(table!=NULL){if (table->page==input[index]) //访问的页已装入内存{answer=1;table->count++;break;}table=table->next;}if(answer!=1) //访问的页不在内存{++ffalse; //页面缺页次数加1cout<<input[index]<<"页不在内存，请求装入！\n";table=head;int h,max=index;while (table!=NULL) //查找未来最久才被访问的页temp{if(table->page==-1)  //如果有空闲页，则不需要置换{temp=table;break;}/*if (table->count<min)   //在input中{                       //查找最久才被访问的页temp=table;         //min=table->count;   //}*/                     ////查找table->page在input中将要被访问的地址for(h=index;h<Options;h++){if(table->page==input[h]){if(h>max){temp=table;max=h;}break;}}if(h>=20){temp=table;break;}table=table->next;}if (temp->page!=-1)  //淘汰temp页cout<<temp->page<<"页被淘汰！\n";temp->page=input[index];  //装入j页到temp块中temp->count=1;}}++i;index++;count=++count%4;for(ti=head; ti!=NULL; ti=ti->next)cout<<ti->page<<"["<<ti->count<<"]"<<"\t\t";cout<<endl;}cout<<"\n缺页率为：";sum=ffalse/(Options*1.0);cout<<sum<<endl;
}

运行效果：

5.1
5.2

程序分析：

本程序是一个模拟操作系统页面置换算法的程序，通过模拟程序的运行过程，来分析不同的页面置换算法的效率，从而选择最优的算法，以达到提高程序运行效率的目的。

程序中使用了四种页面置换算法，分别是FIFO（先进先出）、LRU（最近最少使用）、LFU（最不经常使用）和OPT（最优置换算法）。其中，FIFO算法是最简单的算法，即按顺序淘汰最先进入内存的页面；LRU算法是按页面最后一次被访问的时间来淘汰页面；LFU算法是按页面被访问的频率来淘汰页面；OPT算法是预测将来会被使用的页面，将最长时间不被使用的页面淘汰。

在程序开始运行时，需要输入分配的内存块数目，以及选择要使用的页面置换算法。程序首先进行内存块的初始化，将内存块中的页都设置为-1，表示还没有被装入页。然后程序通过随机生成指令的访问地址来模拟程序运行。每访问一次页面，程序会首先检查页面是否已经在内存中，如果在，则将其访问次数加1；如果不在，则需要进行页面置换。

在FIFO算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要将最先进入内存的页面淘汰，将新的页面装入内存。在LRU算法和LFU算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要淘汰最近或最不经常被使用的页面，将新的页面装入内存。在OPT算法中，程序会检查页面是否在内存中，如果在，则将其访问次数加1；如果不在，则需要预测将来会被使用的页面，并淘汰最长时间不被使用的页面，将新的页面装入内存。

程序最后输出缺页率，即页面置换的次数除以指令总数。

通过模拟程序运行过程，并比较四种不同的页面置换算法的缺页率，可以得出最优的页面置换算法。当然，不同的程序运行情况下，最优的页面置换算法可能会不同，需要根据实际情况进行选择。

系列文章

实验	目录	直达链接
实验一	Linux初步	https://want595.blog.csdn.net/article/details/133145097
实验二	进程的控制和通信（Windows2000）	https://want595.blog.csdn.net/article/details/133903234
实验三	线程同步和调度	https://want595.blog.csdn.net/article/details/133903419
实验四	单处理机调度	https://want595.blog.csdn.net/article/details/133903537
实验五	银行家算法	https://want595.blog.csdn.net/article/details/133903623
实验六	虚拟存储管理技术	https://want595.blog.csdn.net/article/details/133903701