开始 取一条指令 取指令中访问的页号=>L 查页表 是 形成绝对地址 是 置L页修改标志”1” 输出绝对地址 是 取一条指令 否 模拟硬件 结束 地址转换 否(产生缺页中断) 页标志=1? 是”存”指令? 否 输出“﹡页号” 有后继指令? j∶= P[k] 模拟FIFO页面调度 是 输出“OUTj” 输出“IN L” j页的修改标志=1? 否 P[k]∶=L k∶=(k+1) mod m 修改页表
图3-1 地址转换和FIFO页面调度流程
当产生缺页中断后,操作系统总是选择P[k]所指出的页面调出,然后执行
P[k]∶=要装入的新页页号 k∶=(k+1)mod m
在实验中不必实际地启动磁盘执行调出一页和装入一页的工作,而用输出“OUT调出的页号”和“IN要装入的新页页号”来模拟一次调出和装入的过程。模拟程序的流程见图3-1。
(4) 假定主存的每块长度为1024个字节,现有一个共7页的作业,其副本已在磁盘上。系统为该作业分配了4块主存块,且该作业的第0页至第3页已经装入主存,其余3页尚未装入主存,该作业的页表见
表3-2所示。
表3-2 作业的页表 页号 0 1 2 3 4 5 6 标志 1 1 1 1 0 0 0 主存块号 5 8 9 1 修改标志 0 0 0 0 0 0 0 在磁盘上的位置 011 012 013 021 022 023 121
如果该作业依次执行的指令序列如表3-3所示。
表3-3 作业依次执行的指令序列 操作 + + × 存 取 - 页号 0 1 2 3 0 6 页内地址 070 050 015 021 056 040 操作 移位 + 存 取 + 存 页号 4 5 1 2 4 6 页内地址 053 023 037 078 001 084
依次执行上述的指令序列来调试你所设计的程序(仅模拟指令的执行,不必考虑指令序列中具体操作的执行)
(5) 为了检查程序的正确性,可自行确定若干组指令序列,运行设计的程序,核对执行结果。
四、代码:
#include
int address;//地址 int page;//页号 int block;//块号 struct pageTable *next;
};
typedef struct pageTable PAGETABLE; PAGETABLE *pt;
const int first_memory = 1000;//内存首地址 int work[320];//作业
int index, offset;//index是作业的页号,offset为页内偏移地址 PAGETABLE*oldPtr;//minPtr指向驻留时间最久的页 int count1;//记数器,用于记录发生的缺页数 bool is_LRU = false;//是否是LRU算法 void init(); void insertPage();
void pushback_Page(PAGETABLE *, PAGETABLE *); void print(PAGETABLE *); void run(int); void find_FIFO(); void find_LRU(); void main(void) {
int i = 0; while (1) {
cout << \ << endl; cout << \先进先出算法(FIFO)\ << endl; cout << \最久未使用算法(LRU)\ << endl; cout << \程序结束\ << endl; cin >> i; if (i == 1) { }
else if (i == 2) {
cout << \ << endl; is_LRU = false; init();//构造页表和内存
}
}
}
cout << \ << endl; is_LRU = true;
init();//构造页表和内存
else if (i == 0) { }
exit(1);
void init() {
for (int f = 0; f<53; f++)//作业运行 {
for (int k = 0; k<320; k++)//初始化作业 { }
work[k] = k;
oldPtr = pt->next;//初始化最久的页面 cout << \页表初始状态为:\ << endl; print(pt); double rate;
int count = 0;//记数器初值为0 srand(time(NULL)); pt = new PAGETABLE; pt->next = NULL;
for (int i = 0; i<4; i++) { }
insertPage();
}
int m, m1, m2; m = rand() % 320; if (m == 319)
m = 318;
run(m); print(pt); run(m + 1); print(pt);
}
if (m == 0)
m1 = 0;
else
m1 = rand() % m;
run(m1); print(pt); run(m1 + 1); print(pt);
m2 = rand() % (320 - m) + m - 1; if (m2<0)
m2 = 318;
if (m2 == 319)
m2 = 318;
run(m2); print(pt); run(m2 + 1); print(pt);
rate = (double)count / 318 * 100;
cout << \缺页率为:\ << rate << \ << endl;
/* 构建页表*/ void insertPage() {