二、分页式存储器管理
目录
2.1目的
2.2内容
2.3实验提示
2.4数据结构
2.5算法设计及流程图
2.6 运行截图
2.7 小结
2.8代码
2.1目的
- 熟练掌握分页式管理基本原理，并在实验过程中体现内存空间的分配回收、地址转换过程。
- 掌握利用位示图管理内存与置换空间的分配与回收。
- 掌握基本的位运算
- 掌握请求式分页存储管理基本原理，并在试验过程中体会内存与置换空间的分配与回收、地址转换以及缺页处理过程。
2.2内容
在实验一的基础上实现分页式存储管理内存分配和地址转换过程。进一步实现请求分页式存储管理过程，包括内存和置换空间管理、地址转换以及缺页处理，能够体现FIFO和LRU算法思想。
2.3实验提示
1.建立一个位示图数据结构，用来模拟内存的使用情况。位示图是利用若干位的0/1值代表某类空间的占用状态的数据结构。在本实验中，位示图的位数与设定的物理块个数相同。程序启动时可利用一组随机0或1填充位示图，以模拟程序开始执行是内存已被占用状态。
假设内存大小为64K，块大小为1K，则共有64个块，需要创建如下的位示图数据结构：
| #define BLOCK_SIZE 1024 //块大小，定义成宏，便于修改 #define MEM_SIZE 64 //块个数 //定义char型数组，每个char变量占用8位，长度为8，共64位 char bitmap[MEM_SIZE/8]; |
随机填充的代码如下：
| #include "time.h" … srand(time(NULL)); for(i=0;i …bitmap[i]=(char)rand(); |
随机填充后的位示图可能的值如图2-1所示。该位示图表示内存的2（0字节第2位）、3（0字节第3位）、6（0字节第6位）、8（1字节第0位）、9（1字节第1位）、12（1字节第4位）、15（1字节第7位）…等块没有被占用。
图2-1 具有随机值的位示图示例
2. 在实验1基础上扩充PCB，添加进程大小和页表：
| struct PCB｛ … int size; int* page_table; ｝ |
创建进程时输入进程大小，并根据程序中设定的页面大小为进程分配页表空间，并分配物理块。例如，在上图基础上，若要建立一个大小为5000字节的进程，则
- 计算该进程共有“向上取整（5000/1024）=5”个页，需要占用5个内存块；
- 建立空的页表，即长度为5的一维整数数组；
- 从位示图中找出前5个“0”位在整个位示图中的位置号（即内存中的空闲块块号）（若第i字节第j位为0，则该位在位示图中的位置为8*i+j），并将这些位置号依次填入页表中，同时把对应的“0”改为“1”，以示对应内存块已经分配。
| tmp=(struct PCB *)malloc(sizeof(struct PCB));//所创建进程的PCB tmp->size=size;//进程大小 //计算出块个数 block_count=(int)ceil(tmp->size/(double)BLOCK_SIZE); //分配页表 tmp->page_table=(int *)malloc(sizeof(int)*block_count); |
在位示图中判断某字节b的第bit_no位是1还是0代码如下：
| int getbit(char b,int bit_no){ //将00000001左移bit_no位，得到如00010000值 char mask=(char)1< if(b&mask) //进行与操作后结果不为0，则第bit_no位一定是1 return 1; else//进行与操作后结果为0，则第bit_no位一定是0 return 0; } |
设置位示图的某字节b的第bit_no位为1或0代码如下：
| void setbit(char *b,int bit_no,int flag){ char mask=(char)1< if(flag)//flag为真，表示将第bit_no位设置为1 *b=*b|mask;//进行或操作，对应位变成1 else{//flag为假，表示将第bit_no位设置为0 mask=~mask;//取反，得到如11101111值 *b=*b&mask;//进行与操作，对应位变成0 } } |
3. 输入当前执行进程所要访问的逻辑地址，并将其转换成相应的物理地址：
（1）首先编写根据页面大小得到逻辑地址中页号和页内地址分界值（如页面大小为1024，则分界值为log21024=10）
| int mylog2(int size){//size为页面大小 return (int)ceil((log10(size)/log10(2))); } |
（2）根据输入的逻辑地址la，计算其页号和页内地址：
| int la,pageno,offset,mask; printf("逻辑地址：(<0退出)"); scanf("%d",&la); //将逻辑地址右移若干位，得到页号 pageno=la>>mylog2(BLOCK_SIZE); //将1111…111左移若干位，得到11…11000..00 mask=(0xffffffff)< //将11…11000..00取反，得到00…00111..11 mask=~mask; //将逻辑地址与mask进行与操作，得到页内地址 offset=la&mask; |
- 进程退出时，根据其页表内容将位示图对应位置的“1”回填为“0”。
- 扩充页表，将其变成支持请求和置换功能的二维页表（增加存在位等）。创建进程时可装入固定的前三页（或键盘输入初始装入页数，不同进程的装入个数可以不同），其余页装入到置换空间内（置换空间大小应为内存空间大小的1.5-2倍，对其还需建立独立的置换空间位示图）。
- 分别采用FIFO或LRU置换算法对地址转换过程中可能遇到的缺页现象进行页面置换。可将多次地址转换过程中所涉及到的页号视为进程的页面访问序列，从而计算置换次数和缺页率。以下是某次地址变换过程中的交互示例（红色为用户输入，蓝色为程序提示）：
| 逻辑地址:3072 是否为写指令(Y/N):Y 逻辑地址3072对应的页号为:3,页内偏移地址为:0 3号页不在内存,外存块号为12,需置换… 利用FIFO算法选中内存1号页,该页内存块号为6,修改位为1,外存块号为10 将内存6号块内容写入外存10号块,成功 将外存12号块内容调入内存6号块中,置换完毕 逻辑地址3072对应的物理地址为6144 |
2.4数据结构
结构体、链表、一维数组
2.5算法设计及流程图
2.6 运行截图
2.7 小结
功能基本实现，调试成功，没警告，没错误。
通过实验更加了解了页面置换算法的基本流程，能够解决相关问题
2.8代码
#include
#include
#include
#include
#include
#include
#define block_size 1024//块大小
#define mem_size 64//内存大小
#define swapspace_size 128//置换空间大小
#define lode_count 3//进程最多装入页数
#define maxsize 10//最大页表空间
int bitmap[64];
int swapbitmap[128];
using namespace std;
typedef struct Page_table//页表
{
int pageno,blockno,swapspaceno;//页号，块号，置换块号
int exists;//存在位，
}page_table[maxsize];
typedef struct PCB
{
int name;
int sizes; //进程大小
page_table pt;//一个进程的页表
int length;//当前页表个数
int fifo[3],lru[3],opt[3];
int optlist[maxsize];
int fifon,lrun,listn;//fifo,lru中页面的个数
double absent1,absent2,absent3;
double visit1,visit2;
struct PCB *next;
}PCB,*PCBlist;
PCBlist running;
void createbitmap()//创建位视图
{
int i;
srand(time(NULL));
for(i=0;inext;
int i,j;
for(i=0;ipt[i].pageno=-1;
p->pt[i].blockno=-1;
p->pt[i].swapspaceno=-1;
p->pt[i].exists=0;
}
for(j=0;jfifo[j]=-1;
p->lru[j]=-1;
p->opt[j]=-1;
}
}
void createpage(PCBlist &s)//创建页表
{
PCBlist p;
p=s->next;
int m;
int i,j=0,k=0,t=0;
m= (int)ceil((double)p->sizes/(double)block_size);
p->length=m;
p->listn=p->fifon=p->lrun=0;
p->absent1=p->absent2=p->absent3=0;
p->visit1=p->visit2=0;
if(m<=lode_count)
{
for(i=0;ipt[i].pageno=i;
p->pt[i].blockno=j;//j记录位置
p->pt[i].exists=1;
}
cout<<"该进程的页表如下:"<pt[i].pageno<<'t'<<'t';
cout<pt[i].blockno<<'t'<<'t';
cout<pt[i].exists<<'t'<<'t';
cout<pt[i].swapspaceno;
cout<pt[i].pageno=i;
p->pt[i].blockno=k;
p->pt[i].exists=1;
}
cout<<"该进程的页表如下:"<pt[i].pageno<<'t'<<'t';
cout<pt[i].blockno<<'t'<<'t';
cout<pt[i].exists<<'t'<<'t';
cout<pt[i].swapspaceno;
cout<pt[i].swapspaceno=t;
p->pt[i].pageno=i;
}
cout<<"该进程在置换空间的页表如下:"<pt[i].pageno<<'t'<<'t';
cout<pt[i].blockno<<'t'<<'t';
cout<pt[i].exists<<'t'<<'t';
cout<pt[i].swapspaceno;
cout<next;
cout<<"输入逻辑地址"<>a;
b=a/block_size;//计算页号
c=a%block_size;//计算页内偏移
d=p->length;
if(b>d-1)//页号是否大于页表长度
cout<<"本次中断，发生越界错误n";
else
{
if(b>=lode_count)
{
cout<<"不在内存中"<pt[b].swapspaceno)*(block_size)+c<<'t'<<"块号是 "<pt[b].swapspaceno<<"号"<<'t'<<'t'<<"在第"<<(p->pt[b].swapspaceno)/8<<"行"<<'t'<<"第"<<(p->pt[b].swapspaceno)%8<<"列"<<'t'<<"偏移量为"<pt[b].blockno)*(block_size)+c<<'t'<<"块号是"<pt[b].blockno<<"号"<<'t'<<'t'<<"在第"<<(p->pt[b].blockno)/8<<"行"<<'t'<<"第"<<(p->pt[b].blockno)%8<<"列"<<'t'<<"偏移量为"<next;
cout<<"进程结束后的位示图"<pt[i].blockno>=0)
bitmap[p->pt[i].blockno]=0;
}
for(j=3;j<=p->length;j++)
{
if(p->pt[j].swapspaceno>=0)
swapbitmap[p->pt[j].swapspaceno]=0;
}
showbitmap();
}
int findplace(int x,PCBlist p)//查找页面在页表中的位置
{
int i;
for(i=0;i<=p->length;i++)
if(p->pt[i].pageno==x)
return i;
return -1;
}
void FIFO(PCBlist s)
{
PCBlist p;
p=s->next;
int i,j,k,a,b,c,d,x,y,z,temp1,temp2;
p->visit1++;
cout<<"请输入逻辑地址"<>a;
b=a/block_size;//页号
c=findplace(b,p);//查找页号在页表中的位置
p->optlist[p->listn]=b;//将页面存在总的页面序列中，为opt做准备
p->listn++;
if(a>p->sizes)
cout<<"发生越界错误"<fifo[i])
break;
z=i;
if(z!=3)//页面在队列中
{
cout<<"不缺页"<fifo[i]!=-1)
cout<fifo[i]<<" ";
}
cout<absent1++;
if(p->fifon<3)//队列未满
{
if(p->pt[c].exists==1)//所缺页面在内存中
{
p->fifo[p->fifon]=p->pt[c].pageno;
for(k=0;k<3;k++)
{
if(p->fifo[k]!=-1)
cout<fifo[k]<<" ";
}
(p->fifon)++;
cout<pt[j].pageno!=p->fifo[0])&&(p->pt[j].pageno!=p->fifo[1])&&(p->pt[j].pageno!=p->fifo[3]))
break;
d=j;
p->fifo[p->fifon]=p->pt[c].pageno;
temp1=p->pt[d].pageno;//交换页号
p->pt[d].pageno=p->pt[c].pageno;
p->pt[c].pageno=temp1;
for(k=0;k<3;k++)
{
if(p->fifo[k]!=-1)
cout<fifo[k]<<" ";
}
(p->fifon)++;
cout<pt[c].exists==1)
{
p->fifo[0]=p->fifo[1];
p->fifo[1]=p->fifo[2];
p->fifo[2]=p->pt[c].pageno;
for(k=0;k<3;k++)
{
if(p->fifo[k]!=-1)
cout<fifo[k]<<" ";
}
cout<fifo[0];
p->fifo[0]=p->fifo[1];
p->fifo[1]=p->fifo[2];
p->fifo[2]=p->pt[c].pageno;
y=findplace(x,p);
temp2=p->pt[y].pageno;
p->pt[y].pageno=p->pt[c].pageno;
p->pt[c].pageno=temp2;
for(k=0;k<3;k++)
{
if(p->fifo[k]!=-1)
cout<fifo[k]<<" ";
}
cout<absent1<<"次 "<<" 缺页率为："<<(p->absent1/p->visit1)*100<<"%"<next;
int i,j,k,a,b,c,d,x,y,z,m,temp1,temp2,temp3,l;//a输入的地址，l判断队列是否存在元素的下标
p->visit2++;
cout<<"请输入逻辑地址"<>a;
b=a/block_size;//页号
c=findplace(b,p);//查找页号在页表中的位置
p->optlist[p->listn]=b;//将页面存在总的页面序列中，为opt做准备
p->listn++;
if(a>=p->sizes)
cout<<"发生越界错误"<lru[l])
break;
z=l;//cout<lru[z];//temp1为存在的那个元素
if(p->lrun<=2)
{
p->lru[z]=p->lru[p->lrun-1];
p->lru[p->lrun-1]=temp1;
}
else
{
for(m=z;m<3;m++)
p->lru[m]=p->lru[m+1];
p->lru[2]=temp1;
}
for(i=0;i<3;i++)
{
if(p->lru[i]!=-1)
cout<lru[i]<<" ";
}
cout<absent2++;//置换次数+1；
if(p->lrun<3)//队列未满
{
if(p->pt[c].exists==1)//所缺页面在内存中
{
p->lru[p->lrun]=p->pt[c].pageno;
for(k=0;k<3;k++)//显示
{
if(p->lru[k]!=-1)
cout<lru[k]<<" ";
}
(p->lrun)++;
cout<pt[j].pageno!=p->lru[0])&&(p->pt[j].pageno!=p->lru[1])&&(p->pt[j].pageno!=p->lru[2]))
break;
d=j;
p->lru[p->lrun]=p->pt[c].pageno;
temp2=p->pt[d].pageno;//交换页号
p->pt[d].pageno=p->pt[c].pageno;
p->pt[c].pageno=temp2;
for(k=0;k<3;k++)
{
if(p->lru[k]!=-1)
cout<lru[k]<<" ";
}
(p->lrun)++;
cout<pt[c].exists==1)
{
p->lru[0]=p->lru[1];
p->lru[1]=p->lru[2];
p->lru[2]=p->pt[c].pageno;
for(k=0;k<3;k++)
{
if(p->lru[k]!=-1)
cout<lru[k]<<" ";
}
(p->lrun)++;
cout<lru[0];
p->lru[0]=p->lru[1];
p->lru[1]=p->lru[2];
p->lru[2]=p->pt[c].pageno;
y=findplace(x,p);
temp3=p->pt[y].pageno;
p->pt[y].pageno=p->pt[c].pageno;
p->pt[c].pageno=temp3;
for(k=0;k<3;k++)
{
if(p->lru[k]!=-1)
cout<lru[k]<<" ";
}
(p->lrun)++;
cout<absent2<<"次 "<<" 缺页率为："<<(p->absent2/p->visit2)*100<<"%"<next!=NULL)
{
cout<next->name<<" ";
cout<next->sizes<<" ";
p=p->next;
}
cout<<"n";
}
void show(PCBlist p)//就绪状态和堵塞状态展示
{
while(p->next)
{
cout<next->name<<" ";
p=p->next;
}
}
void runshow(int m)//执行状态展示
{
if(m==0)
cout<<"没有正在执行的进程"<name=name;
s->sizes=sizes;
s->next=NULL;
if(p->next==NULL)//进程链为空添加节点
{
p->next=s;
}
else
{
while(p->next!=NULL)//进程链不为空添加节点
{
p=p->next;
}
p->next=s;
}
}
void showall(PCBlist p1,PCBlist p2,int m)//进程状态显示
{
cout<<"就绪状态为:";
show(p1);
cout<next=NULL;
PCBlist blocked=new PCB;
blocked->next=NULL;
running=new PCB;
running->next=NULL;
PCBlist pa=ready,pb=blocked,pc=ready,pd=blocked;
PCBlist p,q;
while(true)
{
cout<<"欢迎来到我的页式存储管理系统"<>n;
switch(n)
{
case 1://创建进程
{
cout<<"请输入进程名字(用0~9表示):";
cin>>number;
cout<<"请输入进程大小:";
cin>>sizes;
add(ready,number,sizes);
if(m==0)//如果还没有正在执行的进程
{
if(ready->next!=NULL)//就绪队列不为空
{
add(running,ready->next->name,ready->next->sizes);
temp=ready->next->name;//获取队头进程（就绪队列第一个元素）
ready->next=ready->next->next;//将就绪状态变为执行状态
m=temp;
}
showall(ready,blocked,m);
}
else
{
showall(ready,blocked,m);
}
break;
}
case 2://时间片到
{
if(m!=0)
{
add(ready,m,running->next->sizes);//将正在执行的进程添加到就绪状态中
m=0;running->next=NULL;
if(ready->next!=NULL)
{
//running->next=ready->next;
add(running,ready->next->name,ready->next->sizes);
temp=ready->next->name;
ready->next=ready->next->next;
m=temp;
}//将此时就绪队列的队头变为执行状态
showall(ready,blocked,m);
}
else
{
cout<<"没有正在进行的进程"<next->sizes);//将阻塞的进程添加到阻塞队列
m=0;running->next=NULL;
if(ready->next!=NULL)
{
add(running,ready->next->name,ready->next->sizes);
temp=ready->next->name;
ready->next=ready->next->next;
m=temp;
}//将此时就绪队列的队头变为执行状态
showall(ready,blocked,m);
}
break;
}
case 4://唤醒进程
{
if(blocked->next==NULL)
cout<<"没有正在阻塞的进程"<>c;
while(pb->next->name!=c)//找到要唤醒的进程
pb=pb->next;
add(ready,pb->next->name,pb->next->sizes);//将要唤醒的进程添加到就绪队列中
if(pb->next->next!=NULL)
pb->next=pb->next->next;
else
pb->next=NULL;
//showall(ready,blocked,m);
}
if(m==0)//如果没有正在执行的进程
{
if(ready->next!=NULL)
{
add(running,ready->next->name,ready->next->sizes);
temp=ready->next->name;
m=temp;
ready->next=ready->next->next;
}
showall(ready,blocked,m);
}
else{
showall(ready,blocked,m);
}
break;
}
case 5://结束进程
{
pcbover(running);
m=0;running->next=NULL;
if(ready->next!=NULL)
{
add(running,ready->next->name,ready->next->sizes);
//out(ready);
temp=ready->next->name;
ready->next=ready->next->next;
m=temp;
}
showall(ready,blocked,m);
break;
}
case 6:createbitmap();showbitmap();break;
case 7:
{
initpagetable(running);
p=running->next;
if(p->pt[0].pageno!=-1)
cout<<"页表已经创建"<
