实验二 虚拟存储器
一、实验内容
模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺 页中断。
二、实验目的
在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的 扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办 法扩充的主存储器称为虚拟存储器。通过本实验帮助同学理解在分页式存储管理中怎样实现 虚拟存储器。
三、实验题目
第二题：用先进先出（FIFO ）页面调度算法处理缺页中断。 [提示]：
（1） 在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个 中断事件。如果主存中已经没有空闲块，则可用 FIFO 页面调度算法把该作业中最先 进入主存的一页调出，存放到磁盘上，然后再把当前要访问的页装入该块。调出和 装入后都要修改页表页表中对应页的标志。
（2） FIFO 页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组 来表示该作业已在主存的页面 个。例如： 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 指示当要装入新页时，应。假定作业被选中时，把开始的m 个页面装 入主存， 则数组的元素可定为 m淘汰的页在数组中的位置，k 的初值为“0”。 当产生缺页中断后，操作系统选择 P[k]所指出的页面调出，然后执行： P[k]:=要装入页的页号 k:=(k+1) mod m
再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。
（3） 编制一个 FIFO 页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有 修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖 因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修 改过，格式为：
由于是模拟调度算法，所以，不实际启动输出一页和装入一页的程序，而用输出调 出的页号和装入的页号来代替一次调出和装入的过程。 把第一题中程序稍作修改 与本题结合起来，FIFO 页面调度模拟算法如图 2-2。
（4） 磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同 第一题中（4）所示。于是增加了“修改标志”后的初始页表为：
以及执行了最后一条指令后的数组 P 的值。
（5） 为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行 的结果。
四、数据结构及符号说明
typedefstruct Page_Table//页表 {
struct Page_Table *next; //定义指向下一个结点的指针 int Page_Num; //页号 int flag; //标志 int Block_Num; //主存块号 int Modify_Flag; //修改标志
int place; //在磁盘上的位置 }*P_Page; //指向该页表的指针
typedefstruct Instruction //指令序列 {
struct Instruction *next; //定义指向下一个节点的指针
char operation[100]; //定义操作名，并分配空间 int L; //定义页号 int Unit_Num; //定义单元号
}*P_Ins; //指向该指令序列表的指针 int Ins_Num; //总指令序列数
五，源代码
#include #include usingnamespace std;
typedefstruct Page_Table//页表 {
struct Page_Table *next; //定义指向下一个结点的指针 int Page_Num; //页号 int flag; //标志 int Block_Num; //主存块号 int Modify_Flag; //修改标志
int place; //在磁盘上的位置 }*P_Page; //指向该页表的指针
//初始化页表
void Init_Page(P_Page&H2) {
H2 = (P_Page)malloc(sizeof (Page_Table)); //建立头结点 H2->next = NULL ;
P_Page p = H2; //定义一个指针 p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 0; p->flag = 1; p->Block_Num = 5; p->Modify_Flag = 0; p->place = 011;
p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 1; p->flag = 1; p->Block_Num = 8; p->Modify_Flag = 0; p->place = 012;
p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 2; p->flag = 1; p->Block_Num = 9; p->Modify_Flag = 0; p->place = 013;
p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 3; p->flag = 1; p->Block_Num = 1; p->Modify_Flag = 0; p->place = 021;
p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 4; p->flag = 0; p->Modify_Flag = 0; p->place = 022; p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 5; p->flag = 0; p->Modify_Flag = 0; p->place = 023; p = p->next = (P_Page)malloc(sizeof (Page_Table));
p->Page_Num = 6; p->flag = 0; p->Modify_Flag = 0; p->place = 121; p->next = H2->next; }
typedefstruct Instruction //指令序列 {
struct Instruction *next; //定义指向下一个节点的指针 char operation[100]; //定义操作名，并分配空间 int L; //定义页号 int Unit_Num; //定义单元号
}*P_Ins; //指向该指令序列表的指针 int Ins_Num; //总指令序列数
//初始化指令序列表
void Initialization(P_Ins&H1) {
cout > Ins_Num; int Num = Ins_Num;
H1 = (P_Ins)malloc(sizeof (Instruction )); //建立头结点 H1->next = NULL ;
P_Ins p = H1; //定义一个指针
cout
p = p->next = (P_Ins)malloc(sizeof (Instruction )); cout
cin >> p->operation >> p->L >> p->Unit_Num; p->next = NULL ; }
p->next = H1->next; }
//FIFO页面调度模拟算法
void FIFO(P_Ins&H1, P_Page&H2) {
cout
int p[7], k = 0, Ab_ADD, j,temp; //定义p 数组，k 的初值，绝对地址，缺页中断中的j 变量，临时变量temp
for (int i = 0; i
p[i] = i; //数组p 的初始化
P_Ins p1 = H1; p1 = p1->next; //定义一个指令序列表的指针 do
{
P_Page p2 = H2; p2 = p2->next;//定义一个页表的指针
while (p1->L != p2->Page_Num){ p2 = p2->next; } //确定取指令中访问的页号 if (p2->flag == 1) //判断改业标志是否为1 {
Ab_ADD = p2->Block_Num * 128 + p1->Unit_Num;//计算绝对地址
if (string (p1->operation) ==string (" 存" ) ) //判断是否为存指令，字符串的比较
{
p2->Modify_Flag = 1; //修改标志置为1 cout
else cout
p1 = p1->next; //取下一条指令 } else {
P_Page p3 = H2; p3 = p3->next; //定义页表的一个指针p3 j = p[k];
while (p3->Page_Num != j){ p3 = p3->next; } //用指针代替j 页 if (p3->Modify_Flag == 1) {
//模拟一次调出和装入的过程
cout L L; k = (k + 1) % 4;
p2->Page_Num = p3->Page_Num; p3->Page_Num = p1->L;//调换两页 //调换修改标志
temp = p3->Modify_Flag; p3->Modify_Flag = p2->Modify_Flag; p2->Modify_Flag = temp; } else {
cout L L; k = (k + 1) % 4;
p2->Page_Num = p3->Page_Num; p3->Page_Num = p1->L;
temp = p3->Modify_Flag; p3->Modify_Flag = p2->Modify_Flag; p2->Modify_Flag = temp; } }
} while (p1 != H1->next);//是否有后继指令的判断 cout
cout
cout
void main() {
P_Ins H1; P_Page H2;
Initialization(H1);//指令序列初始化 Init_Page(H2);//页表初始化
FIFO(H1, H2);//先进先出页面调度模拟算法 }
六、运行结果
七、结果分析与实验体会
本次实验是通过模拟FIFO （先进先出）调度算法处理缺页中断，主要思想是先把进程调入页面，按次序链接成一个队列，并设置指针一直指向最先进入主存的页面。然后将该页面调出，调入输入的页面。通过对先进先出FIFO 算法的模拟实现，加深了对内存管理调度的理解，理解了其如何分配内存的过程，本程序较简单但在实现过程中遇到很多问题，一开始总是出错，程序运行出的结果不对，没有成功实现FIFO 算法，发现自己对内存管理调度理解还不够。