操作系统课程实验

实验四页式虚拟存储管理中地址转换和缺页中断、实验目的深入了解页式存储管理如何实现地址转换；进一步认识页式虚拟存储管理中如何处理缺页中断。、实验预备知识页式存储管理中地址转换的方法；页式虚拟存储的缺页中断处理方法。、实验内容编写程序完成页式虚拟存储管理中地址转换过程和模拟缺页中断的处理。实验具体包括：首先对给定的地址进行地址转换工作， 若发生缺页则先进行缺页中断处理， 然后再进行地址转换；最后编写主函数对所做工作进行测试。假定主存64KB，每个主存块1024字节，作业最大支持到64KB，系统中每个作业分得主存块4块。四、提示与讲解页式存储管理中地址转换过程很简单，假定主存块的大小为 2n字节，主存大小为2m字节和逻辑地址m位，则进行地址转换时，首先从逻辑地址中的高 m-n位中取得页号，然后根据页号查页表，得到块号，并将块号放入物理地址的高 m'-n位，最后从逻辑地址中取mnn-1 0图6页式存储管理系统地址转换示意图得低n位放入物理地址的低n位就得到了物理地址，过程如图 6所示。地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程， 模拟地址转换的流程如图7所示（实验中假定主存64KB，每个主存块1024字节，即n=10,m'=16，物理地址中块号6位、块内地址10位；作业最大64KB，即m=16，逻辑地址中页号6位、页内地址10位）。在页式虚拟存储管理方式中， 作业信息作为副本放在磁盘上， 作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中， 则按上述方式进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断” ，由操作系统把当前所需的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。 页式虚拟存储管理方式中页表除页号和该页对应的主存块号外，至少还要包括存在标志（该页是否在主存） ，磁盘位置（该页的副本在磁盘上的位置）和修改标志（该页是否修改过） 。这样，在实验中页表格式如图7

膜页年晰从页表中职得庆号~pnumb^取邕乏辑地址扃dd「膜页年晰从页表中职得庆号~pnumb^取邕乏辑地址扃dd「ws&的页0Inumber（高乱Z）和页内地耻ad；Inumber^laddress^Wad=Iaddress&0x3ff立并块号和块肉坦址形成物理地址paddress：paddress~pnumber«10|ad查页表第Inumber行所示。页表用数组模拟，在实验中页表数据结构定义为：definen32definen32struct{intInumber;//intflag;intpnumber;intwrite;intdnumber;}page【n];中，若该〃表示该页是否在主存，“1”表示在主存，0”表示不在主存〃该页所在主存块的块号〃该页是否被修改过，“1”表示修改过，0”表示没有修改过〃该页存放在磁盘上的位置，即磁盘块号〃页表定义缺页处理过程简单阐述如下：（1） 根据当前执行指令中逻辑地址的页号查页表，判断该页是否在主存储器页标志为“。”，形成缺页中断。中断装置通过交换 PSW让操作系统的中断处理程序占用处理器；（2） 操作系统处理缺页中断的方法就是查主存分配表，找一个空闲主存块；若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该页被修改过，贝嚅将该页信息写回磁盘，否则不必写回； 图7模拟地址转换的流程图（3）找出该页的磁盘位置，启动磁盘读出该页信息，把磁盘上读出的信息装入第 2步找到的主存块，修改页表中该页的标志为“ 1”；（4） 由于产生缺页中断的那条指令没有执行完，所以页面装入后应重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可正常执行。关于第2步的查找装入新页面的主存块处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块， 只能在分得的主存块内查找空闲块，若无空闲主存块，则从该作业中选择一个页面淘汰出主存。实验中使用局部置换算法。使用局部置换算法时，存在这样一个问题：就是在分配给作业主存空间时， 装入哪些页？有的系统采取不装入任何一页， 当执行过程中需要时才将其调入。 有的系统采用页面预置的方法，就是估计可能某些页面会先用到， 在分配主存块后将这些页面装入。 实验中，采用第二种方法，分配主存空间时将前几页调入主存，假定系统中每个作业分得主存块 m（m=4）块，则将第0~m-1页装入主存。因为是模拟硬件工作，所以实验中如果访问的页不在主存时， 则输出该页页号，表示硬件产生缺页中断，然后直接转去缺页中断处理； 由于采用页面预置方法，在给定的主存块中定无空闲块，只能淘汰已在主存的一页；没有启动磁盘的工作，淘汰的页需要写回磁盘时，用输出页号表示，调入新的一页时， 将该页在页表中的存在标志置为“ 1”，输出页号表示将该页调入主存。主存中无空闲块时， 为装入一个页面，必须按某种算法从已在主存的页中选择一页， 将它暂时调出主存，让出主存空间，用来存放需装入的页面，这个工作称为“页面调度” 。如何选择调出的页是很重要的， 常用的页面调度算法有先进先出算法、 最近最少用算法和最近最不常用算法。实验中使用先进先出调度算法。 先进先出调度算法总是选择驻留在主存时间最长的一页调出。先进先出算法简单， 易实现。可以把在主存储器的页的页号按进入主存的先后次序排成队列，每次总是调出队首的页，当装入一个新页后，把新页的页号排入队尾。实验中，用一个数组存放页号的队列。假定分配给作业的主存块数为 m,数组可由m个元素组成，p[0],p[1]p[m-1]；队首指针head;采用页面预置的方法，页号队列的长度总是m,tail等于(head+1)%m。因此可以使用一个指针，只用 head即可。在装入一个新的页时，装入页和淘汰页同时执行，当装入一个新的页时，将其页号存入数组：淘汰页的页号=p[head];p[head]=新装入页的页号；head=(head+1)%m;实验中，采用先进先出页面置换算法的缺页中断流程如图 8所示。页号为Inumber第j页修改结束输出:*Inumber输出：页号第j页修改结束输出:*Inumber输出：页号j输出：页vInumber修改页表;第j页存在标志改为”0"第luriEb丽[•存任唏志改"'T第InunntoH页修改标志改为0".Mlnumb否三捉存成丸以F乍顷顼|淘汰页的贞号j=p[head]:p[head]=lnumb&rhead=(head+1)%ml图8采用先进先出页面置换算法的缺页中断流程图实验执行一条指令时，不模拟指令的执行，只是考虑指令执行是否修改页面， 若修改页面，则将该页的页表中修改标志位置 “1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令执行完成；如果访问的页不在主存时，则产生缺页中断，然后直接转去缺页中断处理，最后模拟中断返回，就是返回重新进行地址转换。一条指令执行的模拟流程如图 9所示。因为没有实际主存，所以在模拟程序中首先手工输入页表信息， 创建该作业的页表；然后循环执行假定的指令，观察地址转换情况。

第InumEr页歹理地站改贝内容:结束图9•-条指令执行的模拟流程图形成物理地址第Inumbe「页修改标志改为‘‘T'取指令中敢页号第InumEr页歹理地站改贝内容:结束图9•-条指令执行的模拟流程图形成物理地址第Inumbe「页修改标志改为‘‘T'取指令中敢页号inumt^r查贞表第Inumber栏采用LRU页面调度算法编程实现上述虚拟页式存储管理的地址转换。//模拟实验中假定的页表长度六、参考程序//模拟实验中假定的页表长度六、参考程序#definen64#definelength10struct{intInumber;intflag; //intpnumber;intwrite; //intdnumber;}page[n]; //intm;intpage_length;intp[length];inthead;表示页是否在主存，“1”表示在，0'”表示不在〃该页所在主存块的块号该页是否被修改过，“1”表示修改过，0”表示没有修改过〃该页存放在磁盘上的位置，即磁盘块号页表定义//m为作业在主存中的主存块块数//页表实际长度//存放在主存中页的页号〃主存中页号队列头指针page_interrupt(lnumber)intInumber;{intj;printf(" 发生缺页中断*%d\n",lnumber);//淘汰页j=p[head];p[head]=lnumber;head=(head+1)%m;if(page[j].write==1)printf("将页%d写回磁盘第%d块\n",j,page[j].dnumber);page[j].flag=0; //第j页存在标志改为“0”page[lnumber].pnumber=page[j].pnumber;page[lnumber].flag=1; //第Inumber页存在标志改为“0”page[lnumber].write=O; //第lunmber 页修改标志改为“1”printf(”淘汰主存块%2d中的^%2d，从磁盘第％d块中调入^%2d\n",page[j].pnumber,j,page[lnumber].dnumber,lnumber);}//缺页中断处理函数结束command(laddress,write)unsignedladdress;intwrite;{unsignedpaddress,ad,pnumber,lnumber;kk://取出逻辑地址laddress的页号lnumber(高6位)和页内地址adlnumber=laddress>>10;ad=laddress&0x3ff;if(lnumber>=page_length){printf(" 不存在该页\n”);return;}if(page[lnumber].flag==1) //页在主存{pnumber=page[lnumber].pnumber; //从页表中取得块号paddress=pnumber<<10|ad; //合并块号和块内地址 形成 物理地址paddressprintf厂 逻辑地址是：%x 对应物理地址是：％x\n",laddress,paddress);if(write==1) //如果需要写，修改页的修改标志位page[lnumber].write=1;}else{page_interrupt(lnumber); //缺页中断gotokk;}}//命令处理函数结束main(){intlnumber,flag,pnumber,write,dnumber;unsignedladdress;inti;//输入页表的信息，创建页表 pageprintf(- 输入页表的信息，创建页表(若页号为一 1,则结束输入))\n");printf(- 输入页号和辅存地址:，scanf(" %i%i”,&lnumber,&dnumber);『0;while(lnumber!=-1){page[i].lnumber=lnumber;page[i].flag=0;page[i].write=0;page[i].dnumber=dnumber;i++;printf(- 输入页号和辅存地址:，scanf("%d%d",&lnumber,&dnumber);}page_length=i;printf(- 输入主存块号，主存块数要小于 %d,(以一1结束):",i);scanf("%d",&pnumber);m=0;head=0;while(pnumber!=-1){if(m<=i){page[m].pnumber=pnumber;page[m].f