实验四 页式虚拟存储管理中地址转换和页式中断 FIFO LRU OPT C++版本教学内容文档格式.docx

1、 /该页存放在磁盘上的位置，即磁盘块号pagen; /页表定义2）地址转换算法的实现 地址转换是由硬件完成的，实验中使用软件程序模拟地址转换过程。在实验中，每个主存块1024字节，则块内地址占10位；主存64KB，则主存共64块，即块号占6位；物理地址共占16位；作业最大64KB，则作业最大占64块，即页号占6位，逻辑地址共占16位。（用主存的大小计算物理地址位数，用最大作业大小计算逻辑地址位数）。在页式虚拟存储管理方式中，作业信息作为副本放在磁盘上，作业执行时仅把作业信息的部分页面装入主存储器，作业执行时若访问的页面在主存中，则进行地址转换，若访问的页面不在主存中，则产生一个“缺页中断”，由

2、操作系统把当前所需要的页面装入主存储器后，再次执行时才可以按上述方法进行地址转换。模拟地址转换流程度3） 缺页中断处理算法的实现缺页处理过程简单阐述如下：a） 根据当前执行指令中逻辑地址的页号查找页表，判断该页是否在主存储器中，若该页标志为“0”，形成缺页中断。中断装置通过交换PSW让操作系统的中断处理程序占用处理器。b） 操作系统处理缺页中断的方法及时查主存分配表，找一个空闲主存块；若无空闲块，查页表，选择一个已在主存的页面，把它暂时调出主存。若在执行过程中该页被修改过，则需将该页信息写回磁盘，否则不比写回；c） 找出该页的位置，启动磁盘读出该页的信息，把磁盘上读出的信息装入第2不找到的主存

3、块，修改页表中该页的标志为“1”；d） 由于产生缺页中断的那条指令还没有执行完，所以页面装入后应该重新执行被中断的指令。当重新执行该指令时，由于要访问的页面已在主存中，所以可以正常执行。关于第二步的查找装入新页面的主存块处理方式，不同系统采用的策略可能有所不同，这里采用局部置换算法，就是每个作业分得一定的主存块，只能在分得的主存块内查找空闲块，若无空闲主存块，则从该作业中选择一个页面淘汰出主存。实验中采用局部置换算法。使用局部置换算法时，存在这样一个问题：就是在分配给作业主存空间时，装入哪些页？有的系统采取不装入任何一页，当执行过程中需要时才将其调入。有点系统采用页面预置的方法，事先估计可能某

4、些页面会先用到，在分配主存块后将这些页面装入。在本实验中采用第二种方法，分配主存空间时将前几页调入主存，假定系统中每个作业分得主存块m 块，则将第 0m-1页装入主存。因为是模拟硬件工作，所有在实验中如果访问的页不再主存中时，则输入该页页号，表示硬件产生缺页中断，然后直接转去缺页中断处理；由于采用页面预置方法，在给定的主存块中一定无空闲块，只能淘汰已在主存的一页；没有启动磁盘的工作，淘汰的页面需要写回磁盘时，用输入页号表示，调入新的一页时，将该页在页表中的存在标志置为“1”，输出页号表示将该页调入主存。当主存中无空闲块时，为装入一个页面，必须按照某种算法从已在主存的页中选择一页，将它暂时调出主

5、存，让出主存空间，用来存放装入的页面，这个工作称为“页面调度”。常用的页面调度算法有：先进现出、最近最少用算法、和最近最不常用算法。在本实验中采用先进现出调度算法。先进现出算法总是选择驻留在主存时间最长的一页调出。实验中把主存储器的页的页号按照进入主存的先后次序拍成队列，每次总是调出对首的页，当装入一个新页后，把新页的页号排入对尾。实验中，用一个数组存放页号的队列。假定分配给作业的主存块数为m，数组可由m个元素组成，p0,p1,p2pm-1;对首指针head;采用页面预置的方法，页号队列的长度总是m，tail等于（head+1）%m。因此可以使用一个指针，只用head即可。在装入一个新的页时，

6、装入页和淘汰页同时执行，当装入一个新的页时，将其页号存入数组：淘汰页的页号phead;phead=新装入页的页号；head=（head+1）%m;实验执行一条指令时，不模拟指令的执行，只是考虑指令执行是否修改页面，若修改页面，则将该页的页表中的修改标志位置“1”，然后输出转换后的物理地址，并输出物理地址来表示一条指令执行完成；如果访问的页不在主存时，则产生缺页中断，然后直接转去缺页中断处理，最后模拟中断返回，就是返回冲进进行地址转换。因为没有实际主存，所有在模拟程序中首先手工输入页表信息，创建该作业的页表；然后循环执行假定的指令，观察地址转换情况。五、练习题采用LRU页面调度算法编程实现上述虚

7、拟页式存储管理的地址转换。源代码#include#define n 64 /页表的最大长度#define length 4 /系统为每个作业分配的主存块数int m;int page_length; /页表的实际长度int plength; /用向量模拟主存int head;void page_interrupt（int）; /缺页中断处理函数void command（unsigned, int）; /命令处理函数void main（） int lnumber,pnumber,write,dnumber; unsigned laddress; int i; coutlnumberdnumber

8、; cin.ignore （）; i=0; while（lnumber!=-1） pagei.lnumber=lnumber; pagei.flag=0; pagei.write=0; pagei.dnumber=dnumber; i+; cout /预先将输入的页调入主存块中 page_length=i;输入主存块号（输入少于或者等于i个数据，若块号数为1，则结束输入）:pnumber; m=0; head=0; while（mlength&pnumber! if（mi） pagem.pnumber=pnumber; pagem.flag=1;/调入主存后，标志为置1 pm=m; /记录主存

9、中的页号 m+; cin.ignore （）; /while输入指令性质（1修改，0不需要，其他结束程序运行）和逻辑地址n 逻辑地址最大能支持2的16次方165535。n输入指令性质：write;输入逻辑地址：laddress; while（write=0|write=1） command（laddress,write）; /将输入的逻辑地址转换成物理地址 if（write!=0&write!=1） break;/main/*中断处理函数，采用先进先出的页面调度算法*/void page_interrupt（int lnumber） int j;发生缺页中断lnumberendl; j=phe

10、ad; phead=lnumber; head=（head+1）%m; if（pagej.write=1）将页 j 写回磁盘第 pagej.dnumber 块！ pagej.flag=0; pagelnumber.pnumber=pagej.pnumber; pagelnumber.flag=1; pagelnumber.write=0;淘汰主存块 pagej.pnumber 中的页 ,从磁盘第 pagelnumber.dnumber10; /取逻辑地址高6位，页号 ad=laddress&0x3ff; /页内地址该逻辑地址的页号为： 页内地址为：ad=page_length） /页号大于页表

11、的长度，则无效页号该页不存在！ return; if（pagelnumber.flag=1） /页号为lnumber 在内存当中 pnumber=pagelnumber.pnumber; paddress=pnumber10|ad;逻辑地址是：laddress 对应物理地址是：paddressconio.hstdio.hstring.h#define N 16#define num 5 /*进程分配物理块数目*/int AN=1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4; /*页表映像*/typedef struct page int address; /*页面地址*/ st

12、ruct page *next;page;struct page *head,*run,*rear;void jccreat（） /*进程分配物理块*/ int i=1; page *p,*q; head=（page *）malloc（sizeof（page）; p=head; for（i=1;=num;i+） q=（page *）malloc（sizeof（page）; p-next=q; q-address=0;next=NULL; p=q; rear=p;int search（int n） page *p; int i=0; while（p-next） if（p-next-address

13、=n） printf（Get it at the page %dn,i+1）; run=p; return 1; p=p-next; return 0;void changeOPT（int n,int position） int total=0; int flag=1; int distancenum; int MAX; int order=0; p=head- q=head- for（i=0;num; distancei=100; while（p）address=0） flag=0;break; if（!flag）address=n; printf（Change the page %dn w

14、hile（q） for（i=position;N;i+） if（q-address=Ai） distancetotal=i-position; total+; q=q- MAX=distance0; for（i=0; if（distanceiMAX） MAX=distancei; order=i; ,order+1）; i=0; while（p） if（i=order） p- i+; p=p- void changeLRU（int n） page *p,*delect; p- break; if（flag） delect=head- head-next=delect-Delect from t

15、he head, and add new to the end.n）; delect- rear-next=delect; rear=delect;float OPT（） int lose=0; float losef; float percent; if（search（Ai）=0） lose+; changeOPT（Ai,i）; losef=lose; percent=1-（losef/N）; return percent;float LRU（） if（search（Ai）=0） changeLRU（Ai）; else p=run- run-next=p- rear-next=p; rear

16、=p;Move it to end of queue.n void main（） /*主函数部分*/ int choice; printf（Select the arithmetic:n（1）OPTn（2）LRUnyour choice is: scanf（%d,&choice）;/*选择页面置换算法*/ jccreat（）; /*创建进程*/ if（choice=1） /*采用OPT算法置换*/ percent=OPT（）; /*计算OPT时的缺页率*/The percent of OPT is %f,percent）; else if（choice=2） /*采用LRU算法置换*/ percent=LRU（）; /*计算LRU时的缺页率*/ else printf（Your choice is invalid. getch（）;