实验二虚拟存储器

操作系统实验

（第二次）

实验二虚拟存储器

一、实验内容

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

页中断。

二、实验目的

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

三、实验题目

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

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

[提示]

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

页号标志主存块号在磁盘上的位置

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

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

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

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

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

计算出欲访问的主存单元地址。如果块长为2 的幂次，则可把块号作为高地址部分， 把单元号作为低地址部分，两者拼接而成绝对地址。若访问的页对应标志为“0”，

则表示该页不在主存，这时硬件发“缺页中断”信号，有操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。

（3）设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则 形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的 执行。当访问的页不在主存时，则输出“* 该页页号”，表示产生了一次缺页中断。 该模拟程序的算法如图2-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”表示未修 改过，格式为：

一

#include"stdio.h"

#include"string.h"

#define size 128 //块长

#define N 12

typedefstruct

{

int pagenum; int flag; int block; int location;//页表定义

}table;

typedefstruct//操作表定义

{

char ope[10]; int pagenum; int address;

}list;

table p1[7] =

{ { 0,1,5,11 },{ 1,1,8,12 },{ 2,1,9,13 },{ 3,1,1,21 },{ 4,0,NULL,22 },{ 5,0,NULL,23 },{ 6,0,NULL,121 } };

void main()

{

list p2[N]; int i, page, flag, memaddress; printf("the Operating command has(+,-,*,int,out,displace)\n"); for (i = 0;i

} } else printf("page over! again\n");

二

#include"iostream"

#include"iomanip"

usingnamespace std;//使用setw()时用到的头文件

#include"stdio.h"

#include"stdlib.h"

#define Max 30

#define Size 10

{

{

Block[i]=-1;

}

} int i; //某进程调入内存中的最大页面数 //系统为某进程分配的最大物理块数 //初始化物理块 void Init(int Block[],int m) for(i=0;i

void creat(int Page[],int n)

{

{

cin>>Page[i];

}

}

void FIFO(int Page[],int Block[],int n,int m)

{//max_stay:比较当前内存中页面驻留的最久时间,count:统计页面置换次数 //get:某物理块是否等待驻入新页面(-1:否)

//flag:标记当前序号页面是否已驻入内存(-1:否)

//block_num:驻留内存时间最长的页面所在的物理块序号

//time[]标记对应序号的物理块中页面驻留时间

int i,j,max_stay=0,count=0;

int get=-1,flag=-1,block_num=-1;

int time[Size];

float p=0.0;

for(i=0;i

{

}

for(i=0;i

{

{

{

get=j;

break;

}

}

for(j=0;j

{

{

flag=j;

break;

}

}

for(j=0;j

{

if(time[j]>max_stay)

{

max_stay=time[j];

block_num=j; //block_num标记当前序号物理块中页面驻留时间最久 } if(Block[j]==Page[i])//物理块j中页面与当前期望调入内存的页面相同 //物理块j即将(/等待)驻入新页面 for(j=0;j

if(flag==-1) //不存在相同页面

{

{

cout

cout

cout

Block[get]=Page[i];

for(j=0;j

{

time[j]++;

}

get=-1;

}

else //页面调度置换，序号block_num的物理块是驻留时间最久的 {

cout

cout

cout

Block[block_num]=Page[i];

time[block_num]=0;

for(j=0;j

{

time[j]++;

}

block_num=-1;

max_stay=0;

count++;

}

}

else //待调入页面与序号flag的物理块中页面相同

{

cout

cout

cout

for(j=0;j

{

time[j]++;

} //存入页面 //已驻入页面的驻留时间加 time[get]=0; //当前物理块重新计时 if(get!=-1) //物理块即将(/等待)驻入新页面

flag=-1;

}

for(j=0;j

{

cout

}

cout

}

p=count*100/n;

cout

}

void main()

{ int n,m,Page[Max],Block[Size];

char p;

cout

{

cout

{cin>>m;

if(m>Size||m

{

cout

cout

}

elsebreak;

}

Init(Block,m);

cout

cin>>n;

cout

creat(Page,n);

cout

FIFO(Page,Block,n,m);

cout

cin>>p;

cout

if(p=='y' || p=='Y') continue;

elsebreak;

}

}