操作系统lab4-页面置换算法的模拟

实验目的

1、掌握请求分页存储管理的常用理论：页面置换算法。

2、理解请求分页中的按需调页机制。

实验内容

独立地用高级语言编写和调试一个模拟页式虚拟存储管理中硬件的地址转换和缺页中断的处理过程的程序，并用下述一种常用页面置换算法处理缺页中断并计算访问命中率。

(1) 先进先出算法。

(2) 最近最久未使用算法。

(3) 最优算法。

实验分析

1.为了装入一个页面而必须调出一页时，如果被选中调出的页面在执行中没有修改过，则不必把该页重新写到磁盘上（因磁盘上已有副本）。因此，在页表中可以增加是否修改过的标志，当执行“存”指令、“写”指令时把对应页的修改标志置成“1”，表示该页修改过，否则为“0”，表示该页未修改过。页表格式如表3-1所示。

2.设计一个地址转换程序来模拟硬件的地址转换和缺页中断处理过程。当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可用输出转换后的绝对地址来表示一条指令已完成。当访问的页不在主存时则输出“*该页页号”来表示硬件产生了一次缺页中断。模拟地址转换的程序流程如图3-1所示。

3.编制一个FIFO页面调度程序。FIFO页面调度算法总是先调出作业中最先进入主存的那一页，因此，可以用一个数组来构成页号队列。数组中每个元素是该作业已在主存的页面号，假定分配给作业的主存块数为m，且该作业开始的m页已装入主存，则数组可由m个元素组成：

P[0]，P[1]，…，P[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

在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT调出的页号”和“IN要装入的新页页号”来模拟一次调出和装入的过程。模拟程序的流程见图3-1。

4.假定主存的每块长度为1024个字节，现有一个共7页的作业，其副本已在磁盘上。系统为该作业分配了4块主存块，且该作业的第0页至第3页已经装入主存，其余3页尚未装入主存，该作业的页表见表3-2所示。

如果该作业依次执行的指令序列如表3-3所示。

依次执行上述的指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）

5.为了检查程序的正确性，可自行确定若干组指令序列，运行设计的程序，核对执行结果。

步骤1：创建页表

假定主存的每块长度为1024个字节，现有一个共7页的作业，其副本已在磁盘上。系统为该作业分配了4块主存块，且该作业的第0页至第3页已经装入主存，其余3页尚未装入主存，该作业的页表见表3-2所示。

步骤2：编制一个FIFO页面调度程序。

FIFO页面调度算法总是先调出作业中最先进入主存的那一页，因此，可以用一个数组来构成页号队列。数组中每个元素是该作业已在主存的页面号，假定分配给作业的主存块数为m，且该作业开始的m页已装入主存，则数组可由m个元素组成：

P[0]，P[1]，…，P[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

在实验中不必实际地启动磁盘执行调出一页和装入一页的工作，而用输出“OUT调出的页号”和“IN要装入的新页页号”来模拟一次调出和装入的过程。模拟程序的流程见图3-1。

步骤3：执行指令序列来调试所设计的程序

如果该作业依次执行的指令序列如表3-3所示。

依次执行上述的指令序列来调试你所设计的程序（仅模拟指令的执行，不必考虑指令序列中具体操作的执行）

代码

#include<iostream>
#include<string>
using namespace std;const int PGN = 7;	
const int ODN = 12;	
const int M = 4;struct Page {int mark;	//标志int mb_id;	//主存块号int isAltered;	//是否修改int dk_loc;	//磁盘位置
}pgtb[PGN];struct Order {string o;int pg_id;	//页号int pg_ad;	//页内地址
}od[ODN];int p[PGN];void InitPGTB();
void FIFO();
void InitOD();
void InitP();
void OutPut();int main() {InitP();InitOD();InitPGTB();FIFO();return 0;
}void FIFO() {int k = 0;for (int i = 0; i < ODN; i++) {cout << "\n---当前指令---\n"<< "~~操作      " << od[i].o << "\n"<< "~~页号      " << od[i].pg_id << "\n"<< "~~页内地址  " << od[i].pg_ad << "\n";cout << "---操作结果---" << endl;int t = od[i].pg_id;if (pgtb[t].mark == 1) {cout << "==绝对物理地址:";long long tmp = 1024 * (long)pgtb[t].mb_id + od[i].pg_ad;cout << tmp << endl;if (od[i].o=="存") {pgtb[t].isAltered = 1;}}else {cout << "* " << t << endl;int j = p[k];if (pgtb[j].mark == 1) {cout << "OUT " << j << endl;}cout << "IN " << t << endl;pgtb[j].mark = 0;pgtb[t].mark = 1;pgtb[t].mb_id = pgtb[j].mb_id;pgtb[j].mb_id = -1;pgtb[j].isAltered = 0;pgtb[t].isAltered = 0;p[k] = t;k = (k + 1) % M;}OutPut();}
}void InitOD() {cout << "---初始化指令集---" << endl;for (int i = 0; i < ODN; i++) {cin >> od[i].o;cin >> od[i].pg_id;cin >> od[i].pg_ad;}
}void InitP() {for (int i = 0; i < PGN; i++) {p[i] = i;}
}void InitPGTB() {cout << "\n---初始化作业页表---" << endl;for (int i = 0; i < PGN; i++) {cin >> pgtb[i].mark;cin >> pgtb[i].mb_id;cin >> pgtb[i].isAltered;cin >> pgtb[i].dk_loc;}
}void OutPut() {int out = 48;for (int i = 0; i < out; i++)		cout << "*";cout << endl;cout << "页号\t标志   主存块号 修改标志  在磁盘上的位置" << endl;for (int i = 0; i < out; i++)		cout << "*";cout << endl;for (int i = 0; i < PGN; i++) {cout << i << "\t"<< pgtb[i].mark << "\t"<< pgtb[i].mb_id << "\t"<< pgtb[i].isAltered << "\t  "<< pgtb[i].dk_loc << endl;}for (int i = 0; i < out; i++)		cout << "*";cout << endl;
}

测试用例

+ 0 070
移位 4 053
+ 1 050
+ 5 023
X 2 015
存 1 037
存 3 021
取 2 078
取 0 056
+ 4 001
- 6 040
存 6 084

1 5 0 011
1 8 0 012
1 9 0 013
1 1 0 021
0 -1 0 022
0 -1 0 023
0 -1 0 121

运行结果