实验六 虚拟存储器

一、实验内容

模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。

二、实验目的

在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现虚拟存储器。

三、实验题目

本实验有三道题目，其中第一题必做，第二，三题中可任选一个。

第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中断。

[提示]

（1）       分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：

其中，标志----用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。

主存块号----用来表示已经装入主存的页所占的块号。

在磁盘上的位置----用来指出作业副本的每一页被存放在磁盘上的位置。

（2）       作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：

                 绝对地址=块号×块长+单元号

计算出欲访问的主存单元地址。如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

（3）       设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“* 该页页号”，表示产生了一次缺页中断。该模拟程序的算法如图6-1。

图6-1  地址转换模拟算法

（4）       假定主存的每块长度为128个字节；现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存；该作业的页表为：

如果作业依次执行的指令序列为：

（5）       运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。

第二题：用先进先出（FIFO）页面调度算法处理缺页中断。

[提示]：

（1）       在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页表页表中对应页的标志。

（2）       FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。例如：

           P[0]，P[1]，….，P[m-1]

其中每一个P[i]（i=0，1，….，m-1）表示一个在主存中的页面号。它们的初值为：

    P[0]:=0，P[1]:=1，….，P[m-1]:=m-1

用一指针k指示当要装入新页时，应淘汰的页在数组中的位置，k的初值为“0”。

当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行：

P[k]:=要装入页的页号

    k:=(k+1) mod m

再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。

（3）       编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：

 

由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。

把第一题中程序稍作修改，与本题结合起来，FIFO页面调度模拟算法如图6-2。

（4）       磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。于是增加了“修改标志”后的初始页表为：

  

按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组P的值。

（5）       为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

第三题：用最近最少用（LRU）页面调度算法处理缺页中断。

[提示]

(1)    在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用LRU页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。调出和装入后都要修改页表页表中对应页的标志。

(2)    LRU页面调度算法总是淘汰该作业中距现在最久没有访问过的那一页，因此可以用一个数组来表示该作业已在主存的页面。数组中的第一个元素总是指出当前刚访问的页号，因此最久没被访问的页总是由最后一个元素指出。如果主存中只有四块空闲块且执行第一题提示（4）假设的指令序列，采用LRU页面调度算法，那麽在主存中的页面变化情况如下：

(3)    编制一个LRU页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出。参看第二题中提示（3）。模拟调度算法不实际启动输出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替。把第一题中的程序稍作

改动，与本题集合起来，LRU页面调度模拟算法如图6-3。

(4)    按第一题中提示（4）的要求，建立一张初始页表，表中为每一页增加“修改标志”位（参考第二题中提示（4））。然后按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组中的值。

(5)    为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。

四、实验报告

（1）       （第一题必做，第二题和第三题任选其一）。

（2）       程序中使用的数据结构及符号说明。

（3）       打印初始页表，每次调出（要调出一页时）和装入的页号，执行最后一条指令后在主存中的页面号（即数组的值）。

思考题

如果你有兴趣的话，可把两种页面调度算法都做一下，比较两种调度算法的效率（哪种调度算法产生缺页中断的次数少）；分析在什麽情况下采用哪种调度算法更有利？

五、实验答案

第二篇：操作系统实验五虚拟存储器管理

操作系统实验

实验五 虚拟存储器管理

学号     

姓名     

班级      11电子A   

华侨大学电子工程系

实验五 虚拟存储器管理

实验目的

1、理解虚拟存储器概念。

2、掌握分页式存储管理地址转换盒缺页中断。

实验内容与基本要求

1、模拟分页式存储管理中硬件的地址转换和产生缺页中断。

    分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存。作业执行时，指令中的逻辑地址指出了参加运算的操作存放的页 号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式“绝对地址=块号×块长+单元号”计算出欲访问的主存单元地址。如果块长为2 的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而 成绝对地址。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则 形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“* 该页页号”，表示产生了一次缺页中断。 

2、用先进先出页面调度算法处理缺页中断。

    FIFO 页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m 个页面装入主存，则数组的元素可定为m 个。

实验报告内容

1、分页式存储管理和先进先出页面调度算法原理。

    分页式存储管理的基本思想是把内存空间分成大小相等、位置固定的若干个小分区，每个小分区称为一个存储块，简称块，并依次编号为0，1，2，3,……，n块，每个存储块的大小由不同的系统决定，一般为2的n次幂，如1KB，2 KB，4 KB等，一般不超过4 KB。而把用户的逻辑地址空间分成与存储块大小相等的若干页，依次为0，1，2，3，……，m页。当作业提出存储分配请求时，系统首先根据存储块大小把作业分成若干页。每一页可存储在内存的任意一个空白块内。此时，只要建立起程序的逻辑页和内存的存储块之间的对应关系，借助动态地址重定位技术，原本连续的用户作业在分散的不连续存储块中，就能够正常投入运行。

    先进先出页面调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。

程序流程图。

1、地址转换程序流程图

 

2、FIFO页面置换算法程序流程图

 

程序及其注释

#include

#include

#define SizeOfPage 100

#define SizeOfBlock 128

#define M 4//主存中放4个页面

struct info//页表信息结构体

{

       bool flag;//页标志，1表示该页已在主存，0表示该页不在主存

       long block;//块号

       long disk;//在磁盘上的位置

       bool dirty;//更新标志

}pagelist[SizeOfPage];

long po;//队列标记

long P[M];//假设内存中最多允许M个页面

void init_ex1()

{

       memset(pagelist,0,sizeof(pagelist));//内存空间初始化

       /*分页式虚拟存储系统初始化*/

       pagelist[0].flag=1;

       pagelist[0].block=5;

       pagelist[0].disk=011;

       pagelist[1].flag=1;

       pagelist[1].block=8;

       pagelist[1].disk=012;

       pagelist[2].flag=1;

       pagelist[2].block=9;

       pagelist[2].disk=013;

       pagelist[3].flag=1;

       pagelist[3].block=1;

       pagelist[3].disk=021;

}

void work_ex1()//模拟分页式存储管理中硬件的地址转换和产生缺页中断过程

{

       bool stop=0;

       long p,q;//页号，单元号

       char s[128];//初始定义块长

       do

    {

              printf("请输入指令的页号和单元号:\n");

              if(scanf("%ld%ld",&p,&q)!=2)

              {

                     scanf("%s",s);

                     if(strcmp(s,"exit")==0)//如果输入的为“exit”那么就退出，进入重选页面

                     {

                            stop=1;

                     }

              }

              else

              {

                     if(pagelist[p].flag)//如果该页标志flag为1，说明该页已在主存中

                     {

                printf("绝对地址=%ld\n",pagelist[p].block*SizeOfBlock+q);//计算出绝对地址，绝对地址=块号x块长（默认128）+单元号

                     }

                     else

                     {

                            printf("*%ld\n",p);//如果该页标志flag为0，说明该页不在主存，则产生了一次缺页中断

                     }

              }

       }while(!stop);

}

void init_ex2()

{

/*以下部分为先进先出（FIFO）页面调度算法处理缺页中断的初始化，其中也包含了对于当前的存储器内容的初始化*/

       po=0;

       P[0]=0;P[1]=1;P[2]=2;P[3]=3;//对内存中的4个页面进行初始化，并且使目前排在第一位的为0

       memset(pagelist,0,sizeof(pagelist));//内存空间初始化

       pagelist[0].flag=1;

       pagelist[0].block=5;

       pagelist[0].disk=011;

       pagelist[1].flag=1;

       pagelist[1].block=8;

       pagelist[1].disk=012;

       pagelist[2].flag=1;

       pagelist[2].block=9;

       pagelist[2].disk=013;

       pagelist[3].flag=1;

       pagelist[3].block=1;

       pagelist[3].disk=021;

}

void work_ex2()//模拟FIFO算法的工作过程

{

       long p,q,i;

       char s[100];

       bool stop=0;

       do

       {

              printf("请输入指令的页号、单元号，以及是否为内存指令:\n");

              if(scanf("%ld%ld",&p,&q)!=2)

              {

                     scanf("%s",s);

                     if(strcmp(s,"exit")==0)//如果输入的为“exit”就退出，进入重选界面

                     {

                            stop=1;

                     }

              }

              else

              {

                     scanf("%s",s);

                            if(pagelist[p].flag)//如果该页标志flag为1，说明该页已在主存中

                            {

                                   printf("绝对地址=%ld\n",pagelist[p].block*SizeOfBlock+q);//计算绝对地址

                                   if(s[0]=='Y'||s[0]=='y')//内存指令

                                   {

                                          pagelist[p].dirty=1;//修改标志为1

                                   }

                            }

                            else

                            {

                                   if(pagelist[P[po]].dirty)//当前的页面被更新过，需把更新后的内容写回外存

                                   {

                                          pagelist[P[po]].dirty=0;

                                   }

                                   pagelist[P[po]].flag=0;//将flag置0，表明当前页面已被置换出去

                                   printf("out%ld\n",P[po]);//显示根据FIFO算法被置换出去的页面

                                   printf("in%ld\n",p);//显示根据FIFO算法被调入的页面

                                   pagelist[p].block=pagelist[P[po]].block;//块号相同

                                   pagelist[p].flag=1;//将当前页面flag置1,表明已在主存中

                                   P[po]=p;//保存当前页面所在的位置

                                   po=(po+1)%M;

                            }

              }

       }while(!stop);

       printf("数组P的值为:\n");

              for(i=0;i

              {

                     printf("P[%ld]=%ld\n",i,P[i]);

              }

}

void select()//选择哪种方法进行

{

       long se;

       char s[128];

       do

       {

     

              printf("请选择题号(1/2):");

              if(scanf("%ld",&se)!=1)

              {

                     scanf("%s",&s);

                     if(strcmp(s,"exit")==0)//如果输入为exit则退出整个程序

                     {

                            return;

                     }

              }

              else

              {

                     if(se==1)//如果se=1说明选择的模拟分页式存储管理中硬件的地址转换和产生缺页中断

                     {

                            init_ex1();//初始化

                            work_ex1();//进行模拟

                     }

                     if(se==2)//如果se=2说明选择的是FIFO算法来实现页面的置换

                     {

                            init_ex2();//初始化

                            work_ex2();//进行模拟

                     }

              }

       }while(1);

}

int main()

{

       select();//选择题号

    return 0;

}

程序运行结果及结论

通过这次虚拟存储器管理的实验，我基本的了解了分页式存储管理和先进先出页面调度算法原理，和操作的方法，还有许多方面不足，有待改进！