页面置换算法源程序实验报告.doc

页面置换一目的和要求（一）目的 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。 本实验的目的是通过请求页式管理中页面置换算法的模拟设计，来了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。（二）要求 模拟页式虚拟存储管理中硬件的地址转换和缺页中断，并用先进先出调度算法（FIFO）处理缺页中断。二实验内容（1）为了装入一个页面而必须调出一页时，如果被选中调出的页面在执行中没有修改过，则不必把该页写到磁盘上。因此，在页表中可以增加是否修改过的标志，当执行“存”指令 “写”指令是把对应页的修改标志置“1”表示该页修改过，为“0”表示该页没有修改过。 （2）设计一个地址转换程序来模拟硬件的地址转换和缺页中断。当访问的页在主存时则形成绝对地址，但不去模拟指令的执行，可用输出转换后的绝对地址来表示一条指令已完成。当访问的页不在主存时则输出“*该页页号”来表示硬件产生了一次缺页中断。调用模拟地址转换程序。 （3）编制一个FIFO页面调试程序。FIFO页面调试算法总是先调出作业中最先进入主存的那一页，因此，可以用一个数组来构成页号队列。数组中每个元素是该作业已在主存的页面好，假定分配给作业的主存块数为m，且该作业开始的m页已装入主存，则数组可有m个元素组成：P0，P1,Pm-1 她们的初值为：P0:=0,P1:=1,Pm-1:=m-1用一指针k指示当要装入新页时应调出的页在数组的位置,k的初值为0。当产生缺页中断后,操作系统总是选择Pk所指出的页面调出,然后执行: Pk:=要装入的新页页号 K:=(k+1)mod m （4）假定主存的每块长度为1024个字节,现有一个共7页的作业,其副本也已在磁盘上.系统为该作业分配了4块主存块,且该作业的第0页至第3页已经装入主存,其余3页尚未装入主存,该作业的页表如下:页号标志主存块号修改标志在磁盘上的位置0150011118001221900133110021400002250000236000121假设该作业依次执行的指令如下:操作页号页内地址+0070+1050*2015存3021取0056-6040三实验流程图开始取一条指令取指令中访问的页号=L查 页 表页标记=1？形成绝对地址是“存”指令？置L页修改标记“1”输出绝对地址输出“*页号”有后继指令？取一条指令结 束J:=PkJ页的修改标记=1？输出“OUTj”输出“INL”Pk:=L k:=(k+1) mod m修改页面是否是否否（产生缺页中断）是否四实验程序#include #include #include #include #define N 6/实验中假定的页表长度#define M 4/主存物理块数structint lnumber; /页号 int flag; /表示该页是否在主存，1表示在主存，0表示不在主存 int pnumber; /该页所在主存块的块号 int write; /该页是否被修改过，1表示修改过，0表示没有修改过 int dnumber; /该页存放在磁盘上的位置，即磁盘块号pageN; /页表定义int pM;/用数组模拟FIFO算法中的队列(使用循环队列)int head;void initial(void);int do_mmap(int);/模拟地址转换void do_page_fault(int);/缺页中断处理程序void run_first_instructon(int);/执行进程的第一条指令void run_a_instruction(int);/CPU执行一条指令void print_page_and_fifoqueue(void);/输出页表和FIFO队列main()int laddress, paddress;/逻辑地址，物理地址int lnumber, ad, pnumber;/页号，页内地址和物理块号initial();print_page_and_fifoqueue();/输出页表和FIFO队列run_first_instructon(0x0000);/运行进程的第一条指令的地址cout输入下一条指令的逻辑地址(032767)(-1 to end)laddress;while(laddress32767)cout输入错误! 请重新输入下一条指令的逻辑地址(032767)(-1 to end)laddress;while(laddress!=-1)lnumber=laddress10;/取逻辑地址的页号lnumberif(pagelnumber.flag=1)/指令所在的页面已装入在内存中paddress=do_mmap(laddress);/形成物理地址coutpaddress输出转换后的物理地址endl;run_a_instruction(paddress);cout此指令执行是否修改所在页lnumber=lnumberchange;if(tolower(change)=y)pagelnumber.write=1;print_page_and_fifoqueue();else/缺页中断coutlnumber输出该页的页号表示硬件产生缺页中断endl;do_page_fault(lnumber);/直接转去缺页中断处理continue;/本循环结束，重新执行指令coutladdress;while(laddress32767)/输入正确性检测cout输入错误! 请重新输入下一条指令的逻辑地址(032767)(-1 to end)laddress;cout进程运行结束!endl;system(PAUSE);return 0; /手工初始化页表和pM队列void initial(void)int i;for(i=0; i=5; i+)pagei.lnumber=i;if(i=M-1)/预装入算法初始化页表的前四项cout输入页号为 ipagei.pnumber;pagei.flag=1;/存在标志置1/初始化FIFO的队列head=0;for(i=0; i=M-1; i+)pi=i;/输出页表和FIFO队列void print_page_and_fifoqueue(void)int i;cout输出页表！n;coutsetw(10)lnumbersetw(9)flagsetw(10)pnumbersetw(10)writesetw(10)dnumberendl;for(i=0; i=N-1; i+)coutsetw(7)pagei.lnumbersetw(10)pagei.flagsetw(10)pagei.pnumbersetw(10)pagei.writesetw(10)pagei.dnumberendl;cout输出FIFO对列:n;coutsetw(10)NOsetw(40)page(已在主存的页号lnumber)n;couthead=headendl;for(i=0; i=M-1;i+)coutsetw(10)isetw(15)pi10;/取逻辑地址的页号lnumberad=laddress&0x3ff;/页内地址pnumber=pagelnumber.pnumber;/从页表中取得块号pnumberpaddress=pnumber10|ad;return paddress;/CPU执行一条指令，输出物理地址表示指令执行完成void run_a_instruction(int paddress)coutpaddress 输出物理地址表示指令执行完成10;/取逻辑地址的页号if(pagelnumber.flag=1)paddress=do_mmap(laddress);/形成物理地址coutpaddress输出转换后的物理地址endl;run_a_instruction(paddress);cout此指令执行(0x0000)是否修改所在页面lnumber=lnumberchange;if(tolower(change)=y)/若指令执行完时修改了页面，则置write标志位位1pagelnumber.write=1;print_page_and_fifoqueue();cout*第一条指令执行完成(地址为0x0000)*endl;/页面写回磁盘void write_to_harddisk(int j)coutj输出已修改的淘汰的页号表示该页写回了磁盘endl;/缺页中断处理程序void do_page_fault(int lnumber)int j;/j是选择淘汰的页j=phead;phead=lnumber;/lnumber是新装入的页号head=(head+1)%M;/若淘汰出主存的页j已修改，则写会磁盘if(pagej.write=1)write_to_harddisk(j);/页j写回磁盘/修改页表pagej.flag=0;/页表中第j页的存在标志为0pagelnumber.flag=1;/页表第lnumber的存在标志为1pagelnumber.write=0;/页表第lnumber的修改标志为0pagelnumber.pnumber=pagej.pnumber;/第拉怒目布尔页的主存块号为第j页原主存块号coutlnumber输出该页表示该页调入了主存endl;cout按任意键将查看“页面置换”之后的页