二、分页式存储器管理

目录

2.1目的

2.2内容

2.3实验提示

2.4数据结构

2.5算法设计及流程图 

2.6 运行截图

2.7 小结

2.8代码

2.1目的

1. 熟练掌握分页式管理基本原理，并在实验过程中体现内存空间的分配回收、地址转换过程。
2. 掌握利用位示图管理内存与置换空间的分配与回收。
3. 掌握基本的位运算
4. 掌握请求式分页存储管理基本原理，并在试验过程中体会内存与置换空间的分配与回收、地址转换以及缺页处理过程。

2.2内容

在实验一的基础上实现分页式存储管理内存分配和地址转换过程。进一步实现请求分页式存储管理过程，包括内存和置换空间管理、地址转换以及缺页处理，能够体现FIFO和LRU算法思想。

2.3实验提示

1.建立一个位示图数据结构，用来模拟内存的使用情况。位示图是利用若干位的0/1值代表某类空间的占用状态的数据结构。在本实验中，位示图的位数与设定的物理块个数相同。程序启动时可利用一组随机0或1填充位示图，以模拟程序开始执行是内存已被占用状态。

假设内存大小为64K，块大小为1K，则共有64个块，需要创建如下的位示图数据结构：

随机填充的代码如下：

随机填充后的位示图可能的值如图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，添加进程大小和页表：

创建进程时输入进程大小，并根据程序中设定的页面大小为进程分配页表空间，并分配物理块。例如，在上图基础上，若要建立一个大小为5000字节的进程，则

1. 计算该进程共有“向上取整（5000/1024）=5”个页，需要占用5个内存块；
2. 建立空的页表，即长度为5的一维整数数组；
3. 从位示图中找出前5个“0”位在整个位示图中的位置号（即内存中的空闲块块号）（若第i字节第j位为0，则该位在位示图中的位置为8*i+j），并将这些位置号依次填入页表中，同时把对应的“0”改为“1”，以示对应内存块已经分配。

在位示图中判断某字节b的第bit_no位是1还是0代码如下：

设置位示图的某字节b的第bit_no位为1或0代码如下：

3. 输入当前执行进程所要访问的逻辑地址，并将其转换成相应的物理地址：

（1）首先编写根据页面大小得到逻辑地址中页号和页内地址分界值（如页面大小为1024，则分界值为log21024=10）

（2）根据输入的逻辑地址la，计算其页号和页内地址：

1. 进程退出时，根据其页表内容将位示图对应位置的“1”回填为“0”。
2. 扩充页表，将其变成支持请求和置换功能的二维页表（增加存在位等）。创建进程时可装入固定的前三页（或键盘输入初始装入页数，不同进程的装入个数可以不同），其余页装入到置换空间内（置换空间大小应为内存空间大小的1.5-2倍，对其还需建立独立的置换空间位示图）。
3. 分别采用FIFO或LRU置换算法对地址转换过程中可能遇到的缺页现象进行页面置换。可将多次地址转换过程中所涉及到的页号视为进程的页面访问序列，从而计算置换次数和缺页率。以下是某次地址变换过程中的交互示例（红色为用户输入，蓝色为程序提示）：

2.4数据结构

结构体、链表、一维数组

2.5算法设计及流程图 

2.6 运行截图

2.7 小结

功能基本实现，调试成功，没警告，没错误。

通过实验更加了解了页面置换算法的基本流程，能够解决相关问题

2.8代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#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;i<mem_size;i++)
		bitmap[i]=(rand()%2);
    for(i=0;i<swapspace_size;i++)
		swapbitmap[i]=(rand()%2);
}
void showbitmap()//显示位视图
{
	cout<<"位示图"<<endl;
	int i;
	for(i=0;i<mem_size;i++)
	{
		cout<<bitmap[i];
		if((i+1)%8==0)
			cout<<endl;
	}
	cout<<"置换空间位示图"<<endl;
	for(i=0;i<swapspace_size;i++)
	{
		cout<<swapbitmap[i];
		if((i+1)%16==0)
			cout<<endl;
	}
}
void initpagetable(PCBlist &s)//初始化页表
{
     PCBlist p;
    p=s->next;
	int i,j;
        for(i=0;i<maxsize;i++)
        {
            p->pt[i].pageno=-1;
            p->pt[i].blockno=-1;
            p->pt[i].swapspaceno=-1;
            p->pt[i].exists=0;
        }
        for(j=0;j<lode_count;j++)
        {
            p->fifo[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;i<m;i++)//内存，页表 赋值
		{
			while((bitmap[j]!=0))//找位示图中的空闲内存
			{
				j++;
			}
			bitmap[j]=1;
			p->pt[i].pageno=i;
			p->pt[i].blockno=j;//j记录位置
			p->pt[i].exists=1;
		}
		cout<<"该进程的页表如下:"<<endl;
		cout<<"页号\t\t块号\t\t存在位\t\t置换块号"<<endl;
		for(i=0;i<m;i++)//页表显示
		{
			cout<<p->pt[i].pageno<<'\t'<<'\t';
			cout<<p->pt[i].blockno<<'\t'<<'\t';
			cout<<p->pt[i].exists<<'\t'<<'\t';
			cout<<p->pt[i].swapspaceno;
			cout<<endl;
		}

	}
	else
	{
		for(i=0;i<lode_count;i++)
		{
			while(bitmap[k]!=0)//找位示图中的空闲内存
			{
				k++;
			}
			bitmap[k]=1;//修改位示图
			p->pt[i].pageno=i;
			p->pt[i].blockno=k;
			p->pt[i].exists=1;
		}
		cout<<"该进程的页表如下:"<<endl;
		cout<<"页号\t\t块号\t\t存在位\t\t置换块号"<<endl;
		for(i=0;i<lode_count;i++)
		{
			cout<<p->pt[i].pageno<<'\t'<<'\t';
			cout<<p->pt[i].blockno<<'\t'<<'\t';
			cout<<p->pt[i].exists<<'\t'<<'\t';
			cout<<p->pt[i].swapspaceno;
			cout<<endl;
		}
		for(i=lode_count;i<m;i++)//将不在内存的页存放在置换空间内
		{
			while(swapbitmap[t]!=0)//t是外存块号，i是页号
			{
				t++;
			}
			swapbitmap[t]=1;
			p->pt[i].swapspaceno=t;
			p->pt[i].pageno=i;
		}
		cout<<"该进程在置换空间的页表如下:"<<endl;
		cout<<"页号\t\t块号\t\t存在位\t\t置换块号"<<endl;
		for(i=lode_count;i<m;i++)
		{
			cout<<p->pt[i].pageno<<'\t'<<'\t';
			cout<<p->pt[i].blockno<<'\t'<<'\t';
			cout<<p->pt[i].exists<<'\t'<<'\t';
			cout<<p->pt[i].swapspaceno;
			cout<<endl;
		}
	}
}
void operateadress(PCBlist s)//计算物理地址
{
    PCBlist p;
    p=s->next;
	cout<<"输入逻辑地址"<<endl;
	int a,b,c,d;
	cin>>a;
	b=a/block_size;//计算页号
	c=a%block_size;//计算页内偏移
	d=p->length;
	if(b>d-1)//页号是否大于页表长度
        cout<<"本次中断，发生越界错误\n";
    else
    {
        if(b>=lode_count)
        {
            cout<<"不在内存中"<<endl;
            cout<<"地址为："<<(p->pt[b].swapspaceno)*(block_size)+c<<'\t'<<"块号是 "<<p->pt[b].swapspaceno<<"号"<<'\t'<<'\t'<<"在第"<<(p->pt[b].swapspaceno)/8<<"行"<<'\t'<<"第"<<(p->pt[b].swapspaceno)%8<<"列"<<'\t'<<"偏移量为"<<c<<endl;
        }
        else
        {
             cout<<"在内存中"<<endl;
             cout<<"地址为："<<(p->pt[b].blockno)*(block_size)+c<<'\t'<<"块号是"<<p->pt[b].blockno<<"号"<<'\t'<<'\t'<<"在第"<<(p->pt[b].blockno)/8<<"行"<<'\t'<<"第"<<(p->pt[b].blockno)%8<<"列"<<'\t'<<"偏移量为"<<c<<endl;
        }
    }

}

void pcbover(PCBlist s)
{
    PCBlist p;
    p=s->next;
	cout<<"进程结束后的位示图"<<endl;
	int i,j;
	for(i=0;i<3;i++)
	{
		if(p->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<<"请输入逻辑地址"<<endl;
	cin>>a;
	b=a/block_size;//页号
    /*for(c=0;c<=p->length;i++)
        if(p->pt[c].pageno==b)
            break;*/
	c=findplace(b,p);//查找页号在页表中的位置
	p->optlist[p->listn]=b;//将页面存在总的页面序列中，为opt做准备
	p->listn++;
	if(a>p->sizes)
        cout<<"发生越界错误"<<endl;
    else
    {
        for(i=0;i<3;i++)
            if(b==p->fifo[i])
                break;
        z=i;
		if(z!=3)//页面在队列中
        {
            cout<<"不缺页"<<endl;
            for(i=0;i<3;i++)
            {
                if(p->fifo[i]!=-1)
                    cout<<p->fifo[i]<<" ";
            }

            cout<<endl;
        }
		else
		{   p->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<<p->fifo[k]<<" ";
                    }
                    (p->fifon)++;
                    cout<<endl;
                }
                else
                {
                    for(j=0;j<lode_count;j++)//寻找不在队列里的的页面作为要交换的页面；
                        if(  (p->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<<p->fifo[k]<<" ";
                    }

                    (p->fifon)++;
                    cout<<endl;
                    cout<<"内存中没有此页面，从外存中调入的 "<<endl;
                }
			}
			else//队列已满
            {
                if(p->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<<p->fifo[k]<<" ";
                    }
                    cout<<endl;
                }
                else
                {
                    x=p->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<<p->fifo[k]<<" ";
                    }
                    cout<<endl;
                    cout<<"内存中没有此页面，从外存中调入的 "<<endl;
                }
            }
		}
    }
    cout<<"置换次数为:"<<p->absent1<<"次   "<<" 缺页率为："<<(p->absent1/p->visit1)*100<<"%"<<endl;
}
void LRU(PCBlist s)
{
    PCBlist p;
    p=s->next;
    int i,j,k,a,b,c,d,x,y,z,m,temp1,temp2,temp3,l;//a输入的地址，l判断队列是否存在元素的下标
	p->visit2++;
	cout<<"请输入逻辑地址"<<endl;
	cin>>a;
	b=a/block_size;//页号
	c=findplace(b,p);//查找页号在页表中的位置
	p->optlist[p->listn]=b;//将页面存在总的页面序列中，为opt做准备
	p->listn++;
	if(a>=p->sizes)
        cout<<"发生越界错误"<<endl;
    else
    {
        for(l=0;l<3;l++)//lru队列是否存在此数
            if(b==p->lru[l])
                break;
        z=l;//cout<<z<<endl;
		if(z!=3)//页面在队列中
        {
            cout<<"不缺页"<<endl;
            temp1=p->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<<p->lru[i]<<" ";
           }

            cout<<endl;
      }
		else//不再队列中
		{   p->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<<p->lru[k]<<" ";
                    }
                    (p->lrun)++;
                    cout<<endl;
                }
                else//外存中
                {
                    for(j=0;j<lode_count;j++)//寻找队列中第一个空的物理快；
                        if((p->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<<p->lru[k]<<" ";
                    }

                    (p->lrun)++;
                    cout<<endl;
                    cout<<"内存中没有此页面，从外存中调入的 "<<endl;
                }
			}
			else//队列满了
            {
                if(p->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<<p->lru[k]<<" ";
                    }
                    (p->lrun)++;
                    cout<<endl;
                }
                else
                {
                    x=p->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<<p->lru[k]<<" ";
                    }
                    (p->lrun)++;
                    cout<<endl;
                    cout<<"内存中没有此页面，从外存中调入的 "<<endl;
                }
            }
		}
    }
     cout<<"置换次数为:"<<p->absent2<<"次   "<<" 缺页率为："<<(p->absent2/p->visit2)*100<<"%"<<endl;
}
void out(PCBlist p)
{
  while(p->next!=NULL)
    {
       cout<<p->next->name<<" ";
       cout<<p->next->sizes<<" ";
       p=p->next;
    }
  cout<<"\n";
}
void show(PCBlist p)//就绪状态和堵塞状态展示
{
    while(p->next)
	{
		cout<<p->next->name<<" ";
		p=p->next;
	}
}
void runshow(int m)//执行状态展示
{
	if(m==0)
		cout<<"没有正在执行的进程"<<endl;
	else
		cout<<m<<endl;
}
void add(PCBlist &l,int name,int sizes)
{
	PCBlist p=l;
	PCBlist s=new PCB;
	s->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<<endl;
	cout<<"执行状态为:";
	runshow(m);
	cout<<"阻塞状态为:";
	show(p2);
	cout<<endl;
}
int main()
{
	int n,number,c,m=0,j=0,sizes,temp;//m为正在执行的进程标号 n菜单选择 number进程名，sizes进程的大小 c唤醒进程
	PCBlist ready=new PCB;
	ready->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<<"欢迎来到我的页式存储管理系统"<<endl;
	    cout<<"1-创建进程"<<endl;
        cout<<"2-时间片到"<<endl;
        cout<<"3-进程阻塞"<<endl;
        cout<<"4-唤醒进程"<<endl;
        cout<<"5-结束进程"<<endl;
        cout<<"6-创建位图"<<endl;
        cout<<"7-创建并显示进程的页表"<<endl;
        cout<<"8-显示位图"<<endl;
        cout<<"9-地址变换"<<endl;
        cout<<"10-LRU算法"<<endl;
        cout<<"11-FIFO算法"<<endl;
        cout<<"13-显示执行进程信息"<<endl;
        cout<<"0-退出"<<endl;
        cout<<"请根据功能输入序号"<<endl;
        cin>>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<<"没有正在进行的进程"<<endl;
				}
				break;
			}
		case 3://进程阻塞
			{
				if(m==0)
					cout<<"没有正在进行的进程"<<endl;
				else
				{
					add(blocked,m,running->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<<"没有正在阻塞的进程"<<endl;
				else
				{
					cout<<"请输入要唤醒的进程"<<endl;
					cin>>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<<"页表已经创建"<<endl;
                 else
                 {
                     initpagetable(running);
                     createpage(running); break;
                 }
                 break;
             }
         case 8:showbitmap();break;

         case 9:operateadress(running);break;

         case 10:LRU(running);break;

         case 11:FIFO(running);break;

         case 13:out(running);
             break;

         case 0:exit(0);
		}
	}
	return 0;
}

操作系统实验四 请求分页式存储管理

题目描述：
一、实验目的
通过编写分页式存储管理的模拟程序，加深对页式存储管理方式的理解，熟悉逻辑地址到物理地址的转换过程，掌握虚拟存储管理中的页面调度算法，认识分页式虚拟存储系统中缺页中断的处理过程。
二、实验内容
1、设计一个分页式虚拟存储系统，用程序模拟实现，假设页面大小为1K，每个进程分配三个块。
2、页面调度分别采用FIFO调度算法和LRU算法(堆栈法)。（选中页面直接交换。）
3、假设当前作业的页表如下：

4、假设逻辑指令格式为：
操作符 页号1 页内地址1 页号2 页内地址2
例如 表示将页面1内地址为011单元的内容和页面2中地址为051的单元的内容相加，
如：（1011H）＋（1200H）。
现有指令序列如下：

5、编写模拟程序，执行上述指令，若当前页面不在内存，则使用页面调度算法，交换相应页。
6、要求每执行上述指令流中的一条逻辑指令，输出相应的物理指令，若页表有修改，则显示修改后的页表。
FIFO结果
队列内容

LRU结果
栈内部内容：第三个为栈顶第一个为栈低

三、实验思路
（1）初始化：
①初始化页表：自定义页表项数据结构，所有页表项构成一个数组。页表项数据结构中包含所提供的页表信息。从文件中读取页表信息并写入该数组。
②初始化指令表：自定义指令数据结构，所有指令构成一个数组，该数组表示指令表。
指令数据结构中包含所提供的单条指令信息。从文件中读取指令表信息并写入该数组。
（2）FIFO算法：
该算法总是换出最先进入内存的页面，就是要选择当前在内存中驻留时间最久的页面换出。因此可以设置一个队列来保存当前进入内存的页面页号，表示当前内存分配情况。并给它们设置驻留时间。
根据题目给的页表信息，可以看出该进程所分配到的内存块已经存满了，存的是0，1，2号页。可以初始化当前内存分配情况队列，我这里按照这些页在页表中的逻辑地址将它们保存到队列中，即初始化队列为：0，1，2。并将它们的驻留时间设置为0。又因为每个进程分配到的内存块为3，所以用一个三行二列的二维数组来表示该队列，每一行的第一个元素保存页号，第二个元素保存对应的驻留时间。
我这里设置的FIFO函数只有一个参数，传入的是待查找的页码。因此该算法要完成以下功能：
①判断该页是否在内存中，由serach_page()实现
②找出在内存中驻留时间最长的页面，由search_max()实现
③如果该页没有在内存中，在页表中查找该页的逻辑地址，在页表中找出驻留时间最长页面的逻辑地址交换两个页面的标志，磁盘地址，内存块号。并在队列中换出的页面位置上写入换入页面的信息，驻留时间设为0，其他的驻留时间+1。输出更新后的页表信息。
④将此时的队列信息写入队列信息总表以便程序运行完之后查看。
（这个总表队对应于上述示例图片的FIFO队列，表总共8行，对应4条指令的8个操作页面。所以说是每找一个页面就要写入一条队列信息。）
代码：

void FIFO(int pnum)
{
	if (!serach_page(pnum))
	{
		int a, b, c;
		int max = serach_max();
		for (int i = 0;i < 3;i++)
		{
			if (in_s[i][1] == max)
			{
				c = in_s[i][0];
				break;
			}
		}
		for (int i = 0;i < 6;i++)
		{
			if (p[i].pnum == c)
			{
				a = i;break;
			}
		}
		for (int i = 0;i < 6;i++)
		{
			if (p[i].pnum == pnum)
			{
				b = i;break;
			}
		}
		p[a].flag = 0;
		p[b].flag = 1;
		p[a].add = p[b].add;
		p[b].add = -1;
		p[b].cnum = p[a].cnum;
		p[a].cnum = -1;
		int e;
		for (int i = 0;i < 3;i++)
		{
			if (in_s[i][0] == c)
			{
				e = i;
				break;
			}
		}
		in_s[e][0] = pnum;
		in_s[e][1] = 0;
		cout << "发生第" << ++cnumber << "次缺页，更新后的页表为：" << endl;
		display_p();
	}
	int p = 0;
	for (int i = 0;i < 3;i++)
		in_FIFO[f][p++] = in_s[i][0];
	f++;
}

（3）LRU算法：
用一个特殊的栈来保存当前内存分配情况。当需要某一页且该页在内存中，就将该页从栈中取出，并压入栈顶。如果此时栈满，且需要的页面不在内存中，应该移出栈底页，将要换入的页面压入栈顶。因为这里涉及到不同于栈的操作，且调用的页要成为栈顶，所以可以用双向链表实现该栈，以便经常行的存取。
初始化栈，根据题意应该是0，1，2，其中0为栈底，2为栈顶。
同样，我这里设置的LRU函数也是只有一个参数，用来传入待查找的页码。因此该算法要完成以下功能：
①判断该页是否在内存中，由serach_page2实现。（与FIFO中不同的是这里从栈中查找）
②如果当前栈满，且发生缺页，将栈底元素移出栈，该元素即为换出页面的页码，并在页表中找到该换出和换入页面的逻辑位置，交换两页面的部分信息。输出更新后的页表信息。
③如果没有发生缺页，将该页从栈中移出，并压入栈顶。
④将此时的栈信息写入总栈内容表。
代码：

void LRU(int pnum)
{
	if (search_page2(pnum))//页面在主存中
	{
		LRU_stack* q = p_stack->next;
		while (q)//找到该页所对应的链栈的位置
		{
			if (q->pnum == pnum)
				break;
			q = q->next;
		}
		if (q->next == NULL)
		{
			q = p_stack->next;
			int k = 0;
			while (q)
			{
				in_LRU[f][k++] = q->pnum;
				q = q->next;
			}
			f++;
		}
		else
		{
			LRU_stack* d = p_stack->next;
			while (d->next)//找到栈顶指针
				d = d->next;
			//在链栈中交换两个页面的位置，并不改变页表。
			q->prew->next = q->next;
			q->next->prew = q->prew;
			q->prew = d;
			d->next = q;
			q->next = NULL;
			//将当前链栈信息写入LRU
			q = p_stack->next;
			int k = 0;
			while (q)
			{
				in_LRU[f][k++] = q->pnum;
				q = q->next;
			}
			f++;
		}
	}
	else//页面不在主存中
	{
		int onum;
		int a, b;//分别保存 换出的页 和 换入的页 在页表中的相对位置
		for (int i = 0;i < 6;i++)//找出换入页相对位置
		{
			if (p[i].pnum == pnum)
			{
				b = i;
				break;
			}
		}
		onum = p_stack->next->pnum;
		for (int i = 0;i < 6;i++)//找出换出页相对位置
		{
			if (p[i].pnum == onum)
			{
				a = i;
				break;
			}
		}
		//修改页表
		p[a].flag = 0;
		p[b].flag = 1;
		p[a].add = p[b].add;
		p[b].add = -1;
		p[b].cnum = p[a].cnum;
		p[a].cnum = -1;
		cout << "发生第" << ++cnumber << "次缺页，更新后的页表为：" << endl;
		display_p();
		LRU_stack* q = p_stack->next;
		LRU_stack* d = p_stack->next;
		while (d->next)//找到栈顶指针
			d = d->next;
		q->prew->next = q->next;
		q->next->prew = q->prew;
		q->prew = d;
		d->next = q;
		q->next = NULL;
		q->pnum = pnum;
		q = p_stack->next;
		int k = 0;
		while (q)
		{
			in_LRU[f][k++] = q->pnum;
			q = q->next;
		}
		f++;
	}
}

实验结果：

一、实验内容

模拟请求分页存储管理方式。

二、实验要求

1、模拟请求分页存储管理方式，采用最近最久未使用替换算法；
2、程序要添加适当的注释，程序的书写要采用缩进格式；
3、程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应；
4、程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。

三、实验过程

1、设计思想

1. 设内存大小为4MB，页面大小为4KB。
2. 立进程：由用户输入进程大小，随机数分配给进程页框数；
3. 请求访问：
   [1] 由用户输入一个十进制的逻辑地址；
   [2] 如果页面已装入内存，通过地址变换机构计算其物理地址即可；
   [3] 如果页面未装入内存，查看分配的页框是否已经占满。若占满则使用最近最久未使用替换算法替换页面；若没有占满则直接将页面存入内存。
4. 地址变换机构（十进制）：
   [1] 由用户输入一个十进制的逻辑地址A；
   [2] 则页号为P=INT[A/L]，页内地址为d=[A] MOD L，L为页面大小；
   [3] 查询页表，找到页号对应的物理块号B，计算物理地址B×L+d。
5. 最近最久未使用替换算法：
   赋予每个页面一个访问字段，用于记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择所有页面中t值最大的予以淘汰。

2、数据结构

1.定义一个pcb类，表示每一个进程，含有进程的编号、大小、页表等信息：

class PCB {
private:
	unsigned size;                        //进程大小
	unsigned page_item_num;               //为进程分配的页框数
	unsigned occu;                        //占用的页框数
	unsigned length;                      //页表长度
	vector<page_table_item> page_table;   //页表
public:
	void init(unsigned ps);                             //初始化
	void disp();                                        //显示页表信息
	bool comp(unsigned a);                              //越界检查
	unsigned trans(unsigned a, vector<unsigned>& s);    //查询页表
	void LRU(vector<page_table_item>::iterator p);      //LRU置换算法
};

2.对于每一个页表项，建立类page_table_item，包含访问为、状态位等信息：

class page_table_item {
public:
	page_table_item() {
		chunk_no = NULL;
		state = 0;
		visit = 0;	
	}
public:
	unsigned chunk_no;   //物理块号
	bool state;          //状态位,1表示已调入内存
	unsigned visit;      //访问位
};

四、实验代码

pcb.h

#include<vector>

using namespace std;

class page_table_item {
public:
	page_table_item() {
		chunk_no = NULL;
		state = 0;
		visit = 0;	
	}
public:
	unsigned chunk_no;   //物理块号
	bool state;          //状态位,1表示已调入内存
	unsigned visit;      //访问位
};

class PCB {
private:
	unsigned size;                        //进程大小
	unsigned page_item_num;               //为进程分配的页框数
	unsigned occu;                        //占用的页框数
	unsigned length;                      //页表长度
	vector<page_table_item> page_table;   //页表
public:
	void init(unsigned ps);               //初始化
	void disp();                          //显示页表信息
	bool comp(unsigned a);                              //越界检查
	unsigned trans(unsigned a, vector<unsigned>& s);    //查询页表
	void LRU(vector<page_table_item>::iterator p);      //LRU置换算法
};

pcb.cpp

#include"pcb.h"
#include<ctime>
#include<random>
#include<cmath>
#include<iostream>

using namespace std;

//初始化PCB
void PCB::init(unsigned ps) {
	size = ps;
	uniform_int_distribution<unsigned> u(3, 5);
	default_random_engine e(time(0));
	page_item_num = u(e);
	cout << "为进程分配的页框数为：" << page_item_num << endl;
	occu = 0;
	length = size / 4;
	if (size % 4 != 0)
		length++;
	for (unsigned i = 0; i < length; i++) {
		page_table.push_back(page_table_item());
	}
}

//显示页表信息
void PCB::disp() {
	int no = 0;
	auto i = page_table.begin();
	cout << "页号" << "\t" << "物理块号" << "\t"
		<< "状态位" << "\t" << "访问字段" << "\t" << endl;
	while (i != page_table.end()) {
		if (i->state == 1) {
			cout << no << "\t" << i->chunk_no << "\t\t"
			<< i->state << "\t" << i->visit << "\t\t" << endl;
		}
		no++;
		i++;
	}
}

//越界检查
bool PCB::comp(unsigned a) {
	if (a >= length || a < 0)
		return 1;
	else
		return 0;
}

//查询页表
unsigned PCB::trans(unsigned a, vector<unsigned>& s) {
	auto p = page_table.begin();
	unsigned no,flag=0;
	uniform_int_distribution<unsigned> u(0, unsigned(pow(2, 10.0)));
	default_random_engine e(time(0));
	for (unsigned i = 0; i < a; i++) {
		p++;
	}
	//页在内存中
	if (p->state == 1) {
		return p->chunk_no;
	}
	//页不在内存中
	if (occu < page_item_num) {
		p->state = 1;
		for (auto i = page_table.begin(); i != page_table.end(); i++) {
			i->visit++;
		}
		p->visit=0;
		no = u(e);
		while (!flag) {
			for (auto q = s.begin(); q != s.end(); q++) {
			    if (*q == no) 
					flag = 1;
				break;
			}
			if (!flag) {
				p->chunk_no = no;
				s.push_back(no);
				flag = 1;
			}
			else {
				no++;
				flag = 0;
			}
		}
		occu++;
	}
	else if (occu >= page_item_num) {
		LRU(p);		
	}
	return p->chunk_no;
}

void PCB::LRU(vector<page_table_item>::iterator p) {
	auto q = page_table.begin();
	while (q->state != 1) {
		q++;
	}
	auto index = q;
	while (q != page_table.end()) {
		if(q->visit>index->visit&&q->state==1){//找到访问值最大的
			index = q;
		}
		q++;
	}
	p->state = 1;
	index->state = 0;
	p->chunk_no = index->chunk_no;
	index->chunk_no = NULL;
	for (auto i = page_table.begin(); i != page_table.end(); i++) {
		i->visit++;
	}
	p->visit = 0;
}

exp7.cpp

#include"pcb.h"
#include<iostream>
#include<cmath>
#include<string>

using namespace std;

//内存大小4MB，页面大小4KB
//创建进程
bool create(PCB& p) {
	unsigned psize;
	cout << "请输入进程大小(KB)：";
	cin >> psize;
	p.init(psize); //初始化
	return 0;
}

//地址转换机构
void addr_trans(PCB& pro, vector<unsigned>& s) {
	unsigned addr;
	unsigned page_no, offset;
	cout << "输入十进制地址：";
	cin >> addr;
	page_no = unsigned(addr / 4096);
	//进行越界检查
	while (pro.comp(page_no)) {
		cout << "地址越界，重新输入十进制地址：";
		cin >> addr;
		page_no = unsigned(addr / 4096);
	}
	offset = unsigned(addr % 4096);
	//访问页表
	cout << "物理地址为：" << pro.trans(page_no, s) * 4096 + offset << endl;
}

int main() {
	int choose = 0;
	PCB pro;
	vector<unsigned> s;   //记录占用的物理块号
	cout << "1.创建进程\n"
		<< "2.显示进程页表\n"
		<< "3.请求访问\n"
		<< "4.退出" << endl;
	while (choose != 4) {
		cout << "\n请选择：";
		cin >> choose;
		switch (choose) {
		case 1:
			if (create(pro))
				cout << "创建失败！" << endl;
			else
				cout << "创建成功！" << endl;
			break;
		case 2:
			pro.disp();
			break;
		case 3:
			addr_trans(pro, s);
			break;
		default:
			break;
		}
	}
	return 0;
}

五、实验结果