2.完整代码
FIFO.cpp
#include<stdlib.h> #include<iostream> using namespace std; const int blocklen = 128; const int M = 4;//主存页面数 const int N = 12;//指令数 int m = 4; int n = 12; int k = 0;//FIFO的指针 const int PageSize = 7;//作业需要的页面数 int pageSize = 7; struct PAGE { int flag;//标志 int blockNum;//主存块号 int diskPos;//在磁盘上位置 int editFlag;//修改标志 PAGE() { flag = blockNum = diskPos = editFlag = 0; } }; int P[M];//主存 struct instruct { string op;//操作 int pageNum;//页号 int unitNum;//单元号 void print() { cout << "Operation:" << op << " Page num:" << pageNum << " Unit num:" << unitNum << endl; } instruct(string _op="",int _pageNum=0,int _unitNum=0 ) { op = _op; pageNum = _pageNum; unitNum = _unitNum; } }; instruct inst[105]; PAGE page[105]; void input() {//手动输入 cout << "input the size of pages in main storage:"; cin >> m; cout << "input the size of pages of the process:"; cin >> pageSize; cout << "input the number of instructions:"; cin >> n; for (int i = 0; i < m; i++) { cout << "input flag,blockNum,diskPos:"; int flag, blocknum, diskpos; cin >> flag>>blocknum>>diskpos; page[i].flag = flag; if (flag == 1) { P[k] = i; k = (k + 1) % m; } page[i].blockNum = blocknum; page[i].diskPos = diskpos; } for (int i = 0; i < n; i++) { cout << "input operation,pagenum,unitnum:"; string op; int pagenum, unitnum; cin >> op; cin >> pagenum >> unitnum; inst[i] = { op,pagenum,unitnum }; } k = 0; return; } void init() {//输入实验指导书上内容 page[0].flag = 1; page[0].blockNum = 5; page[0].diskPos = 011; page[1].flag = 1; page[1].blockNum = 8; page[1].diskPos = 012; page[2].flag = 1; page[2].blockNum = 9; page[2].diskPos = 013; page[3].flag = 1; page[3].blockNum = 1; page[3].diskPos = 021; page[4].diskPos = 022; page[5].diskPos = 023; page[6].diskPos = 121; inst[0] = { "+",0,70 }; inst[1] = { "+",1,50 }; inst[2] = { "*",2,15 }; inst[3] = { "save",3,21 }; inst[4] = { "get",0,56 }; inst[5] = { "-",6,40 }; inst[6] = { "move",4,53 }; inst[7] = { "+",5,23 }; inst[8] = { "save",1,37 }; inst[9] = { "get",2,78 }; inst[10] = { "+",4,1 }; inst[11] = { "save",6,84 }; P[0] = 0; P[1] = 1; P[2] = 2; P[3] = 3; } void interrupt(int L) {//中断处理 int j = P[k];//要调出的页面 if (page[j].editFlag == 1) cout << "out J!" << j << endl;//调出当前页 page[j].flag = 0; cout << "in L" << L << endl;//调入页面 P[k] = L; k = (k + 1) % m; page[L].flag = 1;//将页装入主存 } void cpuwork() { for (int i = 0; i < n; i++) { int L = inst[i].pageNum;//取指令中访问的页号 inst[i].print(); if (page[L].flag == 1) {//查页表 int addr = page[L].blockNum * blocklen + inst[i].unitNum;//输出绝对地址 if (inst[i].op == "save")//是否为存指令 page[L].editFlag = 1; cout << "absolute address:" << addr << endl; } else { cout << "******interrupt!*****\n"; interrupt(L); i--;//重新查页表 } cout << "********************************\npages in main storage\n"; for (int i = 0; i <m; i++) cout << "Page num:" << P[i] << " Block num:" << page[P[i]].blockNum << " Edit Flag:" << page[P[i]].editFlag <<" Disk pos:" << page[P[i]].diskPos <<endl; cout << "********************************\n\n" cout << "********************************\npages of the work\n"; for (int i = 0; i <pageSize; i++) cout << "Page num:" << i <<" flag:" <<page[i].flag<<" Block num:" << page[i].blockNum << " Edit Flag:" << page[i].editFlag <<" Disk pos:" << page[i].diskPos <<endl; cout << "********************************\n\n"; } } int main() { int choose; cout << "Choose input:1. auto 2.by hand"; cin >> choose; if (choose == 1) init(); else input(); cpuwork(); }
LRU.cpp
#include<stdlib.h> #include<iostream> using namespace std; const int blocklen = 128; const int M = 4;//主存页面数 const int N = 12;//指令数 int m = 4; int n = 12; int k = 0;//FIFO的指针 const int PageSize = 7;//作业需要的页面数 int pageSize = 7; struct PAGE { int flag;//标志 int blockNum;//主存块号 int diskPos;//在磁盘上位置 int editFlag;//修改标志 PAGE() { flag = blockNum = diskPos = editFlag = 0; } }; int P[50];//主存 struct instruct { string op;//操作 int pageNum;//页号 int unitNum;//单元号 void print() { cout << "Operation:" << op << " Page num:" << pageNum << " Unit num:" << unitNum << endl; } instruct(string _op = "", int _pageNum = 0, int _unitNum = 0) { op = _op; pageNum = _pageNum; unitNum = _unitNum; } }; instruct inst[105]; PAGE page[105]; void input() { cout << "input the size of pages in main storage:"; cin >> m; cout << "input the size of pages of the process:"; cin >> pageSize; cout << "input the number of instructions:"; cin >> n; for (int i = 0; i < m; i++) { cout << "input flag,blockNum,diskPos:"; int flag, blocknum, diskpos; cin >> flag >> blocknum >> diskpos; page[i].flag = flag; if (flag == 1) { P[k] = i; k = (k + 1) % m; } page[i].blockNum = blocknum; page[i].diskPos = diskpos; } for (int i = 0; i < n; i++) { cout << "input operation,pagenum,unitnum:"; string op; int pagenum, unitnum; cin >> op; cin >> pagenum >> unitnum; inst[i] = { op,pagenum,unitnum }; } k = 0; return; } void init() {//实验指导书上的页表 page[0].flag = 1; page[0].blockNum = 5; page[0].diskPos = 011; page[1].flag = 1; page[1].blockNum = 8; page[1].diskPos = 012; page[2].flag = 1; page[2].blockNum = 9; page[2].diskPos = 013; page[3].flag = 1; page[3].blockNum = 1; page[3].diskPos = 021; page[4].diskPos = 022; page[5].diskPos = 023; page[6].diskPos = 121; inst[0] = { "+",0,70 }; inst[1] = { "+",1,50 }; inst[2] = { "*",2,15 }; inst[3] = { "save",3,21 }; inst[4] = { "get",0,56 }; inst[5] = { "-",6,40 }; inst[6] = { "move",4,53 }; inst[7] = { "+",5,23 }; inst[8] = { "save",1,37 }; inst[9] = { "get",2,78 }; inst[10] = { "+",4,1 }; inst[11] = { "save",6,84 }; P[0] = 0; P[1] = 1; P[2] = 2; P[3] = 3; } void interrupt(int L) {//中断服务 int j = P[m - 1];//栈底页面调出 if (page[j].editFlag == 1) cout << "out J!" << j << endl;//调出该页面 page[j].flag = 0; cout << "in L" << L << endl; P[3] = P[2]; P[2] = P[1]; P[1] = P[0]; P[0] = L;//调整主存中的页面 page[L].flag = 1; } void cpuwork() { for (int i = 0; i < n; i++) { int L = inst[i].pageNum;//取指令访问的页号 inst[i].print(); if (page[L].flag == 1) { int addr = page[L].blockNum * blocklen + inst[i].unitNum;//形成绝对地址 if (inst[i].op == "save") page[L].editFlag = 1; cout << "absolute address:" << addr << endl; int pos = 0;//调整主存中的页面 for (int i = 1; i <m; i++) { if (P[i] == L) { pos = i; break; } } if(pos!=0) for (int i = pos; i >= 1; i--) P[i] = P[i - 1]; P[0] = L; } else { cout << "******interrupt!*****\n"; interrupt(L); i--; } cout << "********************************\npages in main storage\n"; for (int i = 0; i < m; i++) cout << "Page num:" << P[i] << " Block num:" << page[P[i]].blockNum << " Edit Flag:" << page[P[i]].editFlag << " Disk pos:" << page[P[i]].diskPos << endl; cout << "********************************\n\n"; cout << "********************************\npages of the work\n"; for (int i = 0; i <pageSize; i++) cout << "Page num:" << i <<" flag:" <<page[i].flag<<" Block num:" << page[i].blockNum << " Edit Flag:" << page[i].editFlag <<" Disk pos:" << page[i].diskPos <<endl; cout << "********************************\n\n"; } } int main() { int choose; cout << "Choose input:1. auto 2.by hand"; cin >> choose; if (choose == 1) init(); else input(); cpuwork();
(4)程序运行结果
打印初始页表，每次调出（要调出一页时）和装入的页号，执行最后一条指令后在主存中的页面号（即数组的值）。
FIFO算法
图为初始页表，与实验指导书是完全一致的。
执行到第5条指令，调出第0页时，装入了第6页。因为修改标志位为0，所以不必将“0”调出并输出。
执行到第6条指令，调出第1页时，装入了第4页。因为修改标志位为0，所以同样不必将“1”调出并输出。
执行到第7条指令，调出第2页时，装入了第5页。因为修改标志位为0，所以同样不必将“2”调出并输出。
执行到第8条指令，调出第3页时，装入了第1页。因为修改标志位为1，所以需要将“3”输出。
执行到第9条指令，调出第6页时，装入了第2页。因为修改标志位为0，所以同样不必将“6”调出并输出。
执行到最后一条指令，调出第4页时，装入了第6页。因为修改标志位为0，所以同样不必将“4”调出并输出。同时，图10也是执行完最后一条指令时主存中的页面号。
LRU算法
图为初始页表，无论采用哪种算法，其与实验指导书是完全一致的。
图为第一次中断时，将数组底部的1调出，将6调入。并修改栈内情况。
图为第二次中断时，将数组底部的2调出，将4调入。并修改栈内情况。
图为第三次中断时，将数组底部的3调出，将5调入。并修改栈内情况。由于3的修改标志位为1，所以需要将3输出。
图为第四次中断时，将数组底部的0调出，将1调入。并修改栈内情况。
图为第五次中断时，将数组底部的6调出，将2调入。并修改栈内情况。
图为第六次中断时，将数组底部的5调出，将6调入。并修改栈内情况。
全部指令运行完成后，留在主存中的页面号。
五、思考题
如果你有兴趣的话，可把两种页面调度算法都做一下，比较两种调度算法的效率（哪种调度算法产生缺页中断的次数少）；分析在什么情况下采用哪种调度算法更有利？
如上文，已实现并运行两种页面调度算法。其中，FIFO算法产生了6次缺页中断，缺页中断率为6/12=50%。LRU算法产生了6次缺页中断，缺页中断率为6/12=50%。对于实验指导书给的数据，两种算法效率相同。缺页中断次数相同在大多数情况下尤其是执行循环语句时，LRU算法更有利。
