实习五-虚拟存储器实验报告

实习五虚拟存储器一、实习内容模拟分页式虚拟存储管理中硬件的地址转换和缺页中断，以及选择页面调度算法处理缺页中断。二、实习目的在计算机系统中，为了提高主存利用率，往往把辅助存储器（如磁盘）作为主存储器的扩充，使多道运行的作业的全部逻辑地址空间总和可以超出主存的绝对地址空间。用这种办法扩充的主存储器称为虚拟存储器。通过本实习帮助同学理解在分页式存储管理中怎样实现虚拟存储器。三、实习题目本实习有三个题，其中第一题必做，第二、第三题中可任选一个。第一题：模拟分页式存储管理中硬件的地址转换和产生缺页中断。[提示]：(1)分页式虚拟存储系统是把作业信息的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：页号标志主存块号在磁盘上的位置其中，标志——用来表示对应页是否已经装入主存，标志位=1，则表示该页已经在主存，标志位=0，则表示该页尚未装入主存。主存块号——用来表示已经装入主存的页所占的块号。在磁盘上的位置——用来指出作业副本的每一页被存放在磁盘上的位置。(2)作业执行时，指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式：绝对地址=块号块长+单元号计算出欲访问的主存单元地址。如果块长为2的幂次，则可把块号作为高地址部分，把单元号作为低地址部分，两者拼接而成绝对地址。按计算出的绝对地址可以取到操作数，完成一条指令的执行。若访问的页对应标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，由操作系统按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。(3)设计一个“地址转换”程序来模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“*该页页号”，表示产生了一次缺页中断。该模拟程序的算法如图5-1。(4)假定主存的每块长度为128个字节；现有一个共七页的作业，其中第0页至第3页已经装入主存，其余三页尚未装入主存；该作业的页表为：015011118012219013311021400225002360121如果作业依次执行的指令序列为：操作页号单元号操作页号单元号+0070移位4053+1050+50232015存1037存3021取2078取0056+4001-6040存6084运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。第二题：用先进先出（FIFO）页面调度算法处理缺页中断。[提示]：(1)在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用FIFO页面调度算法把该作业中最先进入主存的一页调出，存放到磁盘上。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。(2)FIFO页面调度算法总是淘汰该作业中最先进入主存的那一页，因此可以用一个数组来表示该作业已在主存的页面。假定作业被选中时，把开始的m个页面装入主存，则数组的元素可定为m个。例如：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指示当要装入新页时，应淘汰的页在数组中的位置，K的初值为“0”。当产生缺页中断后，操作系统选择P[k]所指出的页面调出，然后执行：P[k]：=要装入页的页号k：=(k+1)modm再由装入程序把要访问的一页信息装入到主存中。重新启动刚才那条指令执行。(3)编制一个FIFO页面调度程序，为了提高系统效率，如果应淘汰的页在执行中没有修改过，则可不必把该页调出（因在磁盘上已有副本）而直接装入一个新页将其覆盖。因此在页表中增加是否修改过的标志，为“1”表示修改过，为“0”表示未修改过，格式为：页号标志主存块号修改标志在磁盘上的位置由于是模拟调度算法，所以，不实际地启动调出一页和装入一页的程序，而用输出调出的页号和装入的页号来代替一次调出和装入的过程。把第一题中程序稍作改动，与本题结合起来，FIFO页面调度模拟算法如图5-2。(4)如果一个作业的副本已在磁盘上，在磁盘上的存放地址以及已装入主存的页和作业依次执行的指令序列都同第一题中（4）所示。于是增加了“修改标志”后的初始页表为：页号标志主存块号修改标志在磁盘上的位置0150011118001221900133110021400022500023600121按依次执行的指令序列，运行你所设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后的数组P的值。(5)为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。第三题：用最近最少用（LRU）页面调度算法处理缺页中断。[提示]：(1)在分页式虚拟存储系统中，当硬件发出“缺页中断”后，引出操作系统来处理这个中断事件。如果主存中已经没有空闲块，则可用LRU页面调度算法把该作业中距现在最久没有被访问过的一页调出，存放到磁盘上。然后再把当前要访问的页装入该块。调出和装入后都要修改页表中对应页的标志。(2)LRU页面调度算法总是淘汰该作业中距现在最久没被访问过的那页，因此可以用一个数组来表示该作业已在主存的页面。数组中的第一个元素总是指出当前刚访问的页号，因此最久没被访问过的页总是由最后一个元素指出。如果主存只有四块空闲块且执行第一题中提示（4）假设的指令序列，采用LRU页面调度算法，那么在主存中的页面变化情况如下：306451246230645124123064512012306451当产生缺页中断后，操作系统总是淘汰由最后一个元素所指示的页，再把要访问的页装入淘汰页所占的主存块中，页号登记到数组的第一个元素中，重新启动刚才那条指令执行。(3)编制一个LRU页面调度程序，为了提高系统效率，如果淘汰的页在执行中没有修改过，则可不必把该页调出。参看第二题中提示（3）。模拟调度算法不实际地启动调出一页和装入一页的程序而用输出调出的页号和装入的页号来代替。把第一题中程序稍作改动，与本题结合起来，LRU页面调度模拟算法如图5-3。(4)按第一题中提示（4）的要求，建立一张初始页表，页表中为每一页增加“修改标志”位（参考第二题中提示（4））。然后按依次执行的指令序列，运行设计的程序，显示或打印每次调出和装入的页号，以及执行了最后一条指令后数组中的值。(5)为了检查程序的正确性，可再任意确定一组指令序列，运行设计的程序，核对执行的结果。四源程序(1)程序中使用的数据结构及符号说明typedefstruct//作业{charname[10];//作业名称intpageNum;//页号intoffset;//单元号,偏移位移}Job;typedefstruct//页表{intpageNum;//页号intmflag;//标志(是否在内存)intblockNum;//主存块号intalterFlag;//修改标志intposition;//在磁盘上的位置}PageTable;(2)打印一份源程序并附上注释#includestdio.h#includestring.htypedefstruct//作业{charname[10];//作业名称intpageNum;//页号intoffset;//单元号,偏移位移}Job;typedefstruct//页表{intpageNum;//页号intmflag;//标志(是否在内存)intblockNum;//主存块号intalterFlag;//修改标志intposition;//在磁盘上的位置}PageTable;voidInitPageTable(PageTable*pt){intblockNum[5]={0,5,8,9,1};intposition[5]={0,11,12,13,21};for(inti=1;i5;i++){pt[i].pageNum=i-1;pt[i].mflag=1;pt[i].blockNum=blockNum[i];pt[i].alterFlag=0;pt[i].position=position[i];}}voidInitJob(Job*job){constchar*name[12]={+,+,*,存,取,-,移位,+,存,取,+,存};intpf[12]={0,1,2,3,0,6,4,5,1,2,4,6};intoffset[12]={70,50,15,21,56,40,53,23,37,78,1,84};for(inti=0;i12;i++){strcpy(job[i].name,name[i]);job[i].pageNum=pf[i];job[i].offset=offset[i];}}voidFIFODiaoDu(Jobjob,PageTable*pt){if(pt[1].alterFlag==1)printf(页面%d已经被修改,故页面%d写回磁盘,页面%d调入内存\n,pt[1].pageNum,pt[1].pageNum,job.pageNum);elseprintf(页面%d调出内存,页面%d调入内存\n,pt[1].pageNum,job.pageNum);inttemp[2]={pt[1].blockNum,pt[1].position};//暂存调出页面信息,容纳新页for(inti=1;i5;i++)//数组模拟内存中放置页块队列,先进来的在队首，后进来的在队尾pt[i-1]=pt[i];pt[4].pageNum=job.pageNum;pt[4].blockNum=temp[0];pt[4].position=temp[1];if(strcmp(job.name,存)==0)//存操作,修改标志置1pt[4].alterFlag=1;elsept[4].alterFlag=0;}voidprintPageTable(PageTable*pt){printf(页号标志主存块号修改标志在磁盘上的位置\n);for(inti=1;i5;i++)printf(%d%d%d%d%d\n,pt[i].pageNum,pt[i].mflag,pt[i].blockNum,pt[i].alterFlag,pt[i].position);}voidprintJob(Job*job){printf(作业名页号单元号\n);for(inti=0;i12;i++)printf(%4s%d%d\n,job[i].name,job[i].pageNum,job[i].offset);}intmain(void){Jobjob[12];InitJob(job);printf(作业依次执行的指令序列:\n);printJob(job);PageTablept[5];InitPageTable(pt);printf(初始内存表:\n);printPageTable(pt);printf(\n********************************作业执行开始*******************************\n\n);for(inti=0;i12;i++){intj=0;for(j=1;j5;j++){if(job[i].pageNum==pt[j].pageNum)//作业所需页面在内存中{if(strcmp(job[i].name,存)==0)//存操作修改指令置1pt[j].alterFlag=1;break;}}if(j==5)//缺页中断{printf(********************缺页中断**********************\n);FIFODiaoDu(job[i],pt);//先进先