广东金融学院实验报告

课程名称：大学计算机Ⅰ

 

第二篇：操作系统实验报告 实验三

昆明理工大学信息工程与自动化学院学生实验报告

（ 20## —2013   学年第二  学期）

课程名称：操作系统                 开课实验室：信自楼445    20## 年  5 月 16  日

一、实验要求

对给定的一个页面走向序列，请分别用先进先出算法和二次机会算法，计算淘汰页面的顺序、缺页次数和缺页率，具体的页面走向可参考教材例题或习题。

    二、实验目的

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。通过本次实验，要求学生通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解，通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

三、实验原理及基本技术路线图（方框原理图）

用C或C++语言模拟实现请求式分页管理。要求实现：页表的数据结构、分页式内存空间的分配及回收（建议采用位图法）、地址重定位、页面置换算法（从FIFO,LRU,NRU中任选一种）。

提示：可先用动态申请的方式申请一大块空间，然后假设该空间为内存区域，对该空间进行页框的划分、分配等。

程序功能结构图：

流程图：

数据结构定义:

          我提供定义了两个类。第一个类就是页面类，在这类里面包括一些重要的数据成员。有页号（page_no），页框号（frame_no），页面是否在内存的标志（flag（1表示在内存，0表示不在内存）），访问次数（times）。另一个类是进程控制块类PCB。类的数据成员有 id（进程编号），name（进程名），size（进程大小），*p（页类指针）。在本类中，有一些成员函数:构造函数（用来初始化本类的所有数据），displayPCB（输出函数），convert（地址映射函数），allocation（分配函数），restore（回收函数）。另外还有一些类外的函数：initMemorySpace（初始化内存空间的函数），displayMemorySpace（输出内存空间的状态1（表示占用）0（表示空））。

四、所用仪器、材料（设备名称、型号、规格等）。

计算机一台

五、实验方法、步骤

程序代码：

#include<iostream>

#include<string>

#include<ctime>

using namespace std;

const int frame_size=1024;//页框长度，固定为 1k

const int page_size=1024;//页面长度，固定为 1k

const int memory_size=102400;//内存容量，固定为 100k

const int frame_number=memory_size/frame_size;//   100k/1k=100 frames

int *memory;//指针变量，用来存内存的状态1还是0。

void initMemorySpace()//初始化内存空间

{

   int i,ran,times;

   time_t t;//定义time_t对象 t

   t=time(0);

   srand(t);//随机改变每秒

   times=0;//变量times初始化为0，变量的功能是检查内存空间是否有一半空了没。

   memory=new int[frame_number];//申请内存空间，有frame_number 这么大的空间

   for(i=0;i<frame_number;i++)//首选循环页框数次

       memory[i]=1;//初始化全部为1

   do

   {

       ran=rand()%frame_number;//随机空间位置

       if(memory[ran]==0)continue;//如果当前的位置已经是空 就要再循环

       else//否则

       {

           memory[ran]=0;//内存空间在ran的位置为0（空）

           times++;//times变量增加一个

       }

   }while(times<=(frame_number/2));//空的空间还没到内存空间的一半，再循环

}

void displayMemorySpace()//输出内存空间状态，1还是0

{

   int i;

   cout<<"内存空间（0 表示空，1表示占用）"<<endl;

   for(i=0;i<frame_number;i++)//循环页框数次

   {

       cout<<memory[i]<<"   ";//输出1或者0

       if((i+1)%10==0)cout<<endl;//到第10个列 回车一次

   }

}

class page//定义页表类 page

{

public:

   int logic_no;//定义页号变量

   int frame_no;//定义页框号变量

   int flag;//定义内存标志变量，1 表示在内存, 0表示不在

   int times;//定义访问次数变量

};

class PCB//定义进程控制块类 PCB

{

private:

   static int id;//定义静态进程编号变量

   string name;//定义进程名为字符串类

   int size;//定义进程大小

   int page_number;//定义页面总数变量

   int given_frame;//定义系统给的页框数变量

   page *p;//类page的指针变量

public:

   PCB();//本类的构造函数

   void displayPCB();//输出进程和页表的重要信息

   void convert();//地址映射函数，也有淘汰方法（最近最少使用方法LRU）

   int allocation(int);//分配函数。函数里 是按到页框号分配的

   void restore();//回收函数。用来回收内存空间

};

int PCB::id=0;//初始化进程编号

void PCB::restore()//实现restore函数在类外

{

   int i;

   for(i=0;i<given_frame;i++)//循环given_frame次

   {

       memory[p[i].frame_no]=0;//请求到的页框号的内存空间改到被占用

   }

}

int PCB::allocation(int frame_no)//实现allocation函数体在类外部

{

       if(memory[frame_no]==0)//如果内存空间是空的话

           {

               memory[frame_no]=1;//改该空间位置到1

               return 1;//返回1

           }

       return 0;//如果对应的页框号在内存没有空间的话，返回0

}

PCB::PCB()//实现构造函数体

{

   int i,j,unused_page,*random_page,*page_no_array;

   time_t t;

   t=time(0);

   srand(t);

   id++;//自动增加进程编号一个

   cout<<"请输入进程名:";

   cin>>name;//输入进程名

   size=3072+rand()%48128;//初始化进程大小，随机从 3 页数 到 50 页

   page_number=(size/1024);//计算出页面数，进程大小除以一个页面的长度

   given_frame=(page_number*2)/3;//固定页框数只是总页面数的三分之二

   unused_page=page_number-given_frame;//空页面

   p=new page[page_number];//动态初始化类page的指针对象p

   random_page=new int[given_frame];//动态初始化random_page指针变量

   page_no_array=new int[page_number];//动态初始化page_no_array指针变量

   for(i=0;i<given_frame;i++)//循环given_frame次数

       {

           while(1)

           {

               int record=0;

               random_page[i]=rand()%page_number;//随机从0到page_number-1

               for(j=0;j<i;j++)

               {

                   if(random_page[i]==random_page[j]) record++;//如果当前随机的值等于以前值

               }

               if(record==0)break;//如果当前随机的值不等于以前值

           }

       }

   for(i=0;i<page_number;i++)//循环page_number次

       {

           int record=0;

           for(j=0;j<given_frame;j++)

           {

               if(random_page[j]==i)record++;

           }

           if(record==0) page_no_array[i]=0;//如果第i个没有在random_page中，所以赋值为0

           else page_no_array[i]=1;//否则第i个就赋值为1

       }

   for(i=0;i<page_number;i++)//循环page_number次

   {

       if(page_no_array[i]==1)//如果第i的page_no_array等于1，表示要放也页面

       {

           p[i].logic_no=i;//赋i的值给页号

           do

           {

               while(1)

               {

                   int record=0;

                   p[i].frame_no=rand()%frame_number;//随机页框号，从0到frame_number-1

                   for(int j=0;j<i;j++)

                   {

                       if(p[i].frame_no==p[j].frame_no) record++;

                   }

                   if(record==0)break;//如果当前随机的值没有跟以前的值一样的话，结束 loop while（1）

               }

           }while((allocation(p[i].frame_no))==0);//如果要放到内存的位置不为空的话，再循环

           p[i].flag=1;//页面在内存

           p[i].times=1;//初始化访问次数为1

       }

       else//如果第i的page_no_array不等于1，表示是空页面

       {

           p[i].logic_no=i;//赋i的值给该页号

           p[i].frame_no=-1;//赋-1给页框号，表示不在内存

           p[i].flag=0;//赋0给flag，表示不在内存

           p[i].times=0;//赋0给times，表示不在内存

       }

   }

}

void PCB::displayPCB()//实现displayPCB函数体

{

   int i;

   cout<<"进程 ID: "<<id<<endl<<"进程名: "<<name<<endl<<"进程大小: "<<size<<endl;

   cout<<"页号\t页框号\t内存标志   访问次数"<<endl;

   for(i=0;i<page_number;i++)

   {

       cout<<" "<<p[i].logic_no<<"\t  "<<p[i].frame_no<<"\t   "<<p[i].flag<<"\t      "<<p[i].times<<endl;

      

   }

}

void PCB::convert()//实现地址映射函数体

{

   int logicAddress,logicNumber,physicsAddress,innerAddress,physicsNumber,temppage,time,i;

   //定义逻辑地址变量，逻辑页号，物理地址，页内地址，物理块号变量，和一些暂用变量

   time=1000;//初始化time为1000表示最大访问次数

   char ch;

   do

   {

       cout<<"Please input logic address: ";

       cin>>hex>>logicAddress;//输入逻辑地址 为16进制

       logicNumber=logicAddress>>10;//算出逻辑页号为高位

       if(page_number-1<logicNumber) {cout<<"你输入的逻辑地址超过页表"<<endl;}

       else

       {

           cout<<"Page No: "<<logicNumber<<endl;

           innerAddress=logicAddress & 0x03ff;//页内地址为低10位

           cout<<"Inner Address: "<<innerAddress<<endl;

           if(p[logicNumber].flag==1)//如果算出的逻辑页号在内存，所以可以直接转换到物理地址，只要改对应页面的访问次数

           {

               p[logicNumber].times++;//对应的访问次数增加一个

           }

           else

           {

               for(i=0;i<page_number;i++)//循环所有页面在页表中，哪一个有最少的访问次数

               {

                   if(p[i].flag==1)//只要在内存才找比较

                   {

                       if(p[i].times<time)//如果当前的访问次数比最大的访问次数小

                       {

                           time=p[i].times;//把最小的访问次数赋给变量time

                           temppage=p[i].logic_no;//然后把该页面的页号赋给要 temppage（要淘汰的页面）

                       }

                   }

               }

               cout<<"Page No:"<<temppage<<" need to be replaced"<<endl;

               p[temppage].flag=0;//要淘汰的页面的内存标志的值改为0

               p[temppage].times=0;//要淘汰的页面的访问次数改为0

               p[logicNumber].frame_no=p[temppage].frame_no;//把要淘汰的页面的页框号 赋给新的页面

               p[logicNumber].flag=1;//新的页面的内存标志改为1

               p[logicNumber].times++;//新的页面的访问次数增加

               p[temppage].frame_no=-1;//要淘汰页面的页框号该为-1

           }

           physicsNumber=p[logicNumber].frame_no;//按逻辑页号找到页框号

           cout<<"Physics Number: "<<physicsNumber<<endl;

           physicsAddress=physicsNumber<<10|innerAddress;//按页框号和页内地址算出物理地址

           cout<<"Physic Address: "<<physicsAddress<<endl;

           displayPCB();//输出进程和页表信息

           displayMemorySpace();//输出内存信息的状态

       }

       cout<<"是否继续进程请求分页(Y/N)?：";

       do

       {

           ch=getchar();//输入一个字符

           ch=toupper(ch);//转换它到大字

       }while(ch!='Y'&&ch!='N');//如果输入不是y或者n的话，再输入

   }while(ch=='Y');//输入y的话，再循环loop do

}

void main()//主函数

{

   initMemorySpace();//初始化内存空间

   displayMemorySpace();//输出内存空间状态

   PCB p;//定义

   p.displayPCB();//输出进程和页表的信息

   cout<<endl;

   p.convert();//调用地址映射函数

}

六、实验过程原始记录(数据、图表、计算等)

运行截图：

七、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸）

通过这次存储管理的实验，自己加强了自己用数据结构和程序语言解决问题的能力，同时也对课本的知识有了更深入的了解和体会。实现实验以前我对页表和示法很陌生。但是通过完成本次实验以后让我对它们有了一定的解，加深认识了页表的工作原理，同时也对前面进程的知识进行了复习。程序中我们运用了逻辑地址变量，逻辑页号，物理地址，页内地址，物理块号变量等，这些都是储存管理的基本知识，重要的是对进程进行分页，认识了几种非常重要的置换算法，理想页面置换算法、先进先出页面置换算法、最近最少使用页面置换算法、最近未使用页面置换算法，这些都是操作系统中非常重要的一些算法，虽然在程序的编写过程中有很大的困难，但通过书本和同学的帮助把程序艰难的完成了，因此，此次试验还是有一定的收获。