實(shí)驗(yàn)四 頁(yè)式虛擬存儲(chǔ)管理中地址轉(zhuǎn)換和頁(yè)式中斷 FIFO LRU OPT C++版本

1、實(shí)驗(yàn)四 頁(yè)式虛擬存儲(chǔ)管理中地址轉(zhuǎn)換和頁(yè)式中斷 FIFO一、實(shí)驗(yàn)?zāi)康纳钊肓私忭?yè)式存儲(chǔ)管理如何實(shí)現(xiàn)地址轉(zhuǎn)換；進(jìn)一步認(rèn)識(shí)頁(yè)式虛擬存儲(chǔ)管理中如何處理缺頁(yè)中斷以及頁(yè)面置換算法。二、實(shí)驗(yàn)主要內(nèi)容編寫程序完成頁(yè)式虛擬存儲(chǔ)管理中地址轉(zhuǎn)換過(guò)程和模擬缺頁(yè)中斷的處理。實(shí)驗(yàn)具體內(nèi)容包括：首先對(duì)給定的地址進(jìn)行轉(zhuǎn)換工作，若發(fā)現(xiàn)缺頁(yè)則先進(jìn)行缺頁(yè)中斷處理，然后再進(jìn)行地址轉(zhuǎn)換；最后編寫主函數(shù)對(duì)所做工作進(jìn)行測(cè)試。假定主存64KB，每個(gè)主存塊1024字節(jié)，作業(yè)最大支持到64KB，系統(tǒng)中每個(gè)作業(yè)分得主存塊4塊。三、實(shí)驗(yàn)原理1）地址轉(zhuǎn)換過(guò)程：首先從邏輯地址中的高位取得頁(yè)號(hào)，然后根據(jù)頁(yè)號(hào)查頁(yè)表，得到塊號(hào)；然后從邏輯地址中的低位取得頁(yè)內(nèi)地

2、址，將塊號(hào)和頁(yè)內(nèi)地址合并即得到物理地址。2）缺頁(yè)中斷處理根據(jù)頁(yè)號(hào)查找頁(yè)表，判斷該頁(yè)是否在主存儲(chǔ)器中，若該頁(yè)標(biāo)志位“0”，形成缺頁(yè)中斷。操作系統(tǒng)讓調(diào)出中斷處理程序處理中斷。四、實(shí)驗(yàn)方法與步驟實(shí)現(xiàn)地址轉(zhuǎn)換與缺頁(yè)中斷處理，主要考慮三個(gè)問(wèn)題：第一，設(shè)計(jì)頁(yè)式虛擬存儲(chǔ)管理方式中頁(yè)表的數(shù)據(jù)結(jié)構(gòu)；第二，地址轉(zhuǎn)換算法的實(shí)現(xiàn)；第三，缺頁(yè)中斷處理算法的實(shí)現(xiàn)。1)         設(shè)計(jì)頁(yè)表的數(shù)據(jù)結(jié)構(gòu)頁(yè)式虛擬存儲(chǔ)管理方式中頁(yè)表除了頁(yè)號(hào)和該頁(yè)對(duì)應(yīng)的主存塊號(hào)外，至少還要包括存在標(biāo)志（該頁(yè)是否在主存），磁盤位置（該頁(yè)的副本在磁盤上的位置）和修改標(biāo)

3、志（該頁(yè)是否修改過(guò)）。在實(shí)驗(yàn)中頁(yè)表用數(shù)組模擬，其數(shù)據(jù)結(jié)構(gòu)定義如下：struct int lnumber; /頁(yè)號(hào) int flag; /表示頁(yè)是否在主存中，“1”表示在，“0”表示不在 int pnumber; / 該頁(yè)所在主存塊的塊號(hào) int write; /該頁(yè)是否被修改過(guò)，“1”表示修改過(guò)，“0“表示沒(méi)有修改過(guò) int dnumber; /該頁(yè)存放在磁盤上的位置，即磁盤塊號(hào)pagen; /頁(yè)表定義2）地址轉(zhuǎn)換算法的實(shí)現(xiàn) 地址轉(zhuǎn)換是由硬件完成的，實(shí)驗(yàn)中使用軟件程序模擬地址轉(zhuǎn)換過(guò)程。在實(shí)驗(yàn)中，每個(gè)主存塊1024字節(jié)，則塊內(nèi)地址占10位；主存64KB，則主存共64塊，即塊號(hào)占6位；物理地址共占

4、16位；作業(yè)最大64KB，則作業(yè)最大占64塊，即頁(yè)號(hào)占6位，邏輯地址共占16位。（用主存的大小計(jì)算物理地址位數(shù)，用最大作業(yè)大小計(jì)算邏輯地址位數(shù)）。在頁(yè)式虛擬存儲(chǔ)管理方式中，作業(yè)信息作為副本放在磁盤上，作業(yè)執(zhí)行時(shí)僅把作業(yè)信息的部分頁(yè)面裝入主存儲(chǔ)器，作業(yè)執(zhí)行時(shí)若訪問(wèn)的頁(yè)面在主存中，則進(jìn)行地址轉(zhuǎn)換，若訪問(wèn)的頁(yè)面不在主存中，則產(chǎn)生一個(gè)“缺頁(yè)中斷”，由操作系統(tǒng)把當(dāng)前所需要的頁(yè)面裝入主存儲(chǔ)器后，再次執(zhí)行時(shí)才可以按上述方法進(jìn)行地址轉(zhuǎn)換。              

5、60;         模擬地址轉(zhuǎn)換流程度3）  缺頁(yè)中斷處理算法的實(shí)現(xiàn)缺頁(yè)處理過(guò)程簡(jiǎn)單闡述如下：a) 根據(jù)當(dāng)前執(zhí)行指令中邏輯地址的頁(yè)號(hào)查找頁(yè)表，判斷該頁(yè)是否在主存儲(chǔ)器中，若該頁(yè)標(biāo)志為“0”，形成缺頁(yè)中斷。中斷裝置通過(guò)交換PSW讓操作系統(tǒng)的中斷處理程序占用處理器。b) 操作系統(tǒng)處理缺頁(yè)中斷的方法及時(shí)查主存分配表，找一個(gè)空閑主存塊；若無(wú)空閑塊，查頁(yè)表，選擇一個(gè)已在主存的頁(yè)面，把它暫時(shí)調(diào)出主存。若在執(zhí)行過(guò)程中該頁(yè)被修改過(guò)，則需將該頁(yè)信息寫回磁盤，否則不比寫回；c) 找出該頁(yè)的位置，啟動(dòng)磁盤讀出該頁(yè)的

6、信息，把磁盤上讀出的信息裝入第2不找到的主存塊，修改頁(yè)表中該頁(yè)的標(biāo)志為“1”；d) 由于產(chǎn)生缺頁(yè)中斷的那條指令還沒(méi)有執(zhí)行完，所以頁(yè)面裝入后應(yīng)該重新執(zhí)行被中斷的指令。當(dāng)重新執(zhí)行該指令時(shí)，由于要訪問(wèn)的頁(yè)面已在主存中，所以可以正常執(zhí)行。關(guān)于第二步的查找裝入新頁(yè)面的主存塊處理方式，不同系統(tǒng)采用的策略可能有所不同，這里采用局部置換算法，就是每個(gè)作業(yè)分得一定的主存塊，只能在分得的主存塊內(nèi)查找空閑塊，若無(wú)空閑主存塊，則從該作業(yè)中選擇一個(gè)頁(yè)面淘汰出主存。實(shí)驗(yàn)中采用局部置換算法。使用局部置換算法時(shí)，存在這樣一個(gè)問(wèn)題：就是在分配給作業(yè)主存空間時(shí)，裝入哪些頁(yè)？有的系統(tǒng)采取不裝入任何一頁(yè)，當(dāng)執(zhí)行過(guò)程中需要時(shí)才將其調(diào)入

7、。有點(diǎn)系統(tǒng)采用頁(yè)面預(yù)置的方法，事先估計(jì)可能某些頁(yè)面會(huì)先用到，在分配主存塊后將這些頁(yè)面裝入。在本實(shí)驗(yàn)中采用第二種方法，分配主存空間時(shí)將前幾頁(yè)調(diào)入主存，假定系統(tǒng)中每個(gè)作業(yè)分得主存塊m 塊，則將第 0m-1頁(yè)裝入主存。因?yàn)槭悄M硬件工作，所有在實(shí)驗(yàn)中如果訪問(wèn)的頁(yè)不再主存中時(shí)，則輸入該頁(yè)頁(yè)號(hào)，表示硬件產(chǎn)生缺頁(yè)中斷，然后直接轉(zhuǎn)去缺頁(yè)中斷處理；由于采用頁(yè)面預(yù)置方法，在給定的主存塊中一定無(wú)空閑塊，只能淘汰已在主存的一頁(yè)；沒(méi)有啟動(dòng)磁盤的工作，淘汰的頁(yè)面需要寫回磁盤時(shí)，用輸入頁(yè)號(hào)表示，調(diào)入新的一頁(yè)時(shí)，將該頁(yè)在頁(yè)表中的存在標(biāo)志置為“1”，輸出頁(yè)號(hào)表示將該頁(yè)調(diào)入主存。當(dāng)主存中無(wú)空閑塊時(shí)，為裝入一個(gè)頁(yè)面，必須按照某種

8、算法從已在主存的頁(yè)中選擇一頁(yè)，將它暫時(shí)調(diào)出主存，讓出主存空間，用來(lái)存放裝入的頁(yè)面，這個(gè)工作稱為“頁(yè)面調(diào)度”。常用的頁(yè)面調(diào)度算法有：先進(jìn)現(xiàn)出、最近最少用算法、和最近最不常用算法。在本實(shí)驗(yàn)中采用先進(jìn)現(xiàn)出調(diào)度算法。先進(jìn)現(xiàn)出算法總是選擇駐留在主存時(shí)間最長(zhǎng)的一頁(yè)調(diào)出。實(shí)驗(yàn)中把主存儲(chǔ)器的頁(yè)的頁(yè)號(hào)按照進(jìn)入主存的先后次序拍成隊(duì)列，每次總是調(diào)出對(duì)首的頁(yè)，當(dāng)裝入一個(gè)新頁(yè)后，把新頁(yè)的頁(yè)號(hào)排入對(duì)尾。實(shí)驗(yàn)中，用一個(gè)數(shù)組存放頁(yè)號(hào)的隊(duì)列。假定分配給作業(yè)的主存塊數(shù)為m，數(shù)組可由m個(gè)元素組成，p0,p1,p2pm-1;對(duì)首指針head;采用頁(yè)面預(yù)置的方法，頁(yè)號(hào)隊(duì)列的長(zhǎng)度總是m，tail等于(head+1)%m。因此可以使用一個(gè)

9、指針，只用head即可。在裝入一個(gè)新的頁(yè)時(shí)，裝入頁(yè)和淘汰頁(yè)同時(shí)執(zhí)行，當(dāng)裝入一個(gè)新的頁(yè)時(shí)，將其頁(yè)號(hào)存入數(shù)組：淘汰頁(yè)的頁(yè)號(hào)phead;phead=新裝入頁(yè)的頁(yè)號(hào)；head=(head+1)%m;實(shí)驗(yàn)執(zhí)行一條指令時(shí)，不模擬指令的執(zhí)行，只是考慮指令執(zhí)行是否修改頁(yè)面，若修改頁(yè)面，則將該頁(yè)的頁(yè)表中的修改標(biāo)志位置“1”，然后輸出轉(zhuǎn)換后的物理地址，并輸出物理地址來(lái)表示一條指令執(zhí)行完成；如果訪問(wèn)的頁(yè)不在主存時(shí)，則產(chǎn)生缺頁(yè)中斷，然后直接轉(zhuǎn)去缺頁(yè)中斷處理，最后模擬中斷返回，就是返回沖進(jìn)進(jìn)行地址轉(zhuǎn)換。因?yàn)闆](méi)有實(shí)際主存，所有在模擬程序中首先手工輸入頁(yè)表信息，創(chuàng)建該作業(yè)的頁(yè)表；然后循環(huán)執(zhí)行假定的指令，觀察地址轉(zhuǎn)換情況。五

10、、練習(xí)題采用LRU頁(yè)面調(diào)度算法編程實(shí)現(xiàn)上述虛擬頁(yè)式存儲(chǔ)管理的地址轉(zhuǎn)換。源代碼#include<iostream.h>#define n 64 /頁(yè)表的最大長(zhǎng)度#define length 4 /系統(tǒng)為每個(gè)作業(yè)分配的主存塊數(shù)structint lnumber; /頁(yè)號(hào)int flag; /表示頁(yè)是否在主存中，“1”表示在，“0”表示不在int pnumber; / 該頁(yè)所在主存塊的塊號(hào)int write; /該頁(yè)是否被修改過(guò)，“1”表示修改過(guò)，“0“表示沒(méi)有修改過(guò)int dnumber; /該頁(yè)存放在磁盤上的位置，即磁盤塊號(hào)pagen; /頁(yè)表定義int m;int page_len

11、gth; /頁(yè)表的實(shí)際長(zhǎng)度int plength; /用向量模擬主存int head;void page_interrupt(int); /缺頁(yè)中斷處理函數(shù)void command(unsigned, int); /命令處理函數(shù)void main()int lnumber,pnumber,write,dnumber;unsigned laddress;int i;cout<<"輸入頁(yè)表的信息，創(chuàng)建頁(yè)表（頁(yè)號(hào)從0開(kāi)始，若頁(yè)號(hào)為1，則結(jié)束輸入）n"cout<<"請(qǐng)輸入頁(yè)號(hào)和輔存地址："cin>>lnumber>>

12、;dnumber;cin.ignore ();i=0;while(lnumber!=-1)pagei.lnumber=lnumber;pagei.flag=0;pagei.write=0;pagei.dnumber=dnumber;i+;cout<<"請(qǐng)輸入頁(yè)號(hào)和輔存地址:"cin>>lnumber>>dnumber;/預(yù)先將輸入的頁(yè)調(diào)入主存塊中page_length=i;cout<<"輸入主存塊號(hào)(輸入少于或者等于"<<i<<"個(gè)數(shù)據(jù)，若塊號(hào)數(shù)為1，則結(jié)束輸入):&quo

13、t;cin>>pnumber; cin.ignore ();m=0;head=0;while(m<length&&pnumber!=-1)if(m<i)pagem.pnumber=pnumber;pagem.flag=1;/調(diào)入主存后，標(biāo)志為置1pm=m; /記錄主存中的頁(yè)號(hào)m+;cout<<"輸入主存塊號(hào)(輸入少于或者等于"<<i<<"個(gè)數(shù)據(jù)，若塊號(hào)數(shù)為1，則結(jié)束輸入):"cin>>pnumber; cin.ignore (); /whilecout<<

14、"輸入指令性質(zhì)（1修改，0不需要，其他結(jié)束程序運(yùn)行）和邏輯地址n"<<"邏輯地址最大能支持2的16次方165535。n"cout<<"輸入指令性質(zhì)："cin>>write;cin.ignore ();cout<<"輸入邏輯地址："cin>>laddress;cin.ignore ();while(write=0|write=1)command(laddress,write); /將輸入的邏輯地址轉(zhuǎn)換成物理地址cout<<"輸入指令性質(zhì)

15、："cin>>write;cin.ignore ();if(write!=0&&write!=1) break;cout<<"輸入邏輯地址："cin>>laddress;cin.ignore ();/while/main/*中斷處理函數(shù)，采用先進(jìn)先出的頁(yè)面調(diào)度算法*/void page_interrupt(int lnumber) int j;cout<<"發(fā)生缺頁(yè)中斷"<<lnumber<<endl;j=phead;phead=lnumber;head=(

16、head+1)%m;if(pagej.write=1)cout<<"將頁(yè) "<<j<<" 寫回磁盤第 "<<pagej.dnumber<<" 塊！n"pagej.flag=0;pagelnumber.pnumber=pagej.pnumber;pagelnumber.flag=1;pagelnumber.write=0;cout<<"淘汰主存塊 "<<pagej.pnumber<<" 中的頁(yè) "<

17、;<j<<" ,從磁盤第 "<<pagelnumber.dnumber<<" 塊中調(diào)入頁(yè) "<<lnumber<<endl;/*地址轉(zhuǎn)換函數(shù)，將邏輯地址轉(zhuǎn)換成物理地址，如果要查找的頁(yè)不在主存當(dāng)中則產(chǎn)生缺頁(yè)中斷*/void command(unsigned laddress,int write) unsigned paddress,ad,pnumber;int lnumber;kk:lnumber=laddress>>10; /取邏輯地址高6位，頁(yè)號(hào)ad=laddress&

18、;0x3ff; /頁(yè)內(nèi)地址cout<<"該邏輯地址的頁(yè)號(hào)為："<<lnumber<<" 頁(yè)內(nèi)地址為："<<ad<<endl;if(lnumber>=page_length) /頁(yè)號(hào)大于頁(yè)表的長(zhǎng)度，則無(wú)效頁(yè)號(hào)cout<<"該頁(yè)不存在！n"return;if(pagelnumber.flag=1) /頁(yè)號(hào)為lnumber 在內(nèi)存當(dāng)中 pnumber=pagelnumber.pnumber;paddress=pnumber<<10|ad;cout<

19、;<"邏輯地址是："<<laddress<<" 對(duì)應(yīng)物理地址是："<<paddress<<endl;if(write=1) /該頁(yè)被修改過(guò)pagelnumber.write=1;else /頁(yè)號(hào)為lnumber不在內(nèi)存當(dāng)中，則產(chǎn)生缺頁(yè)中斷page_interrupt(lnumber);goto kk;/command頁(yè)式存儲(chǔ)管理OPT ，LRU實(shí)驗(yàn)報(bào)告 一、實(shí)驗(yàn)?zāi)康模赫莆辗猪?yè)式存儲(chǔ)管理的基本概念和實(shí)現(xiàn)方法。要求編寫一個(gè)模擬的分頁(yè)式管理程序，并能對(duì)分頁(yè)式存儲(chǔ)的頁(yè)面置換算法進(jìn)行編寫和計(jì)算各個(gè)算法的缺頁(yè)率。

20、二、程序設(shè)計(jì)：首先創(chuàng)建頁(yè)面鏈指針數(shù)據(jù)結(jié)構(gòu)，并設(shè)計(jì)頁(yè)面映像表，采用數(shù)組的方法給定頁(yè)面映像。申請(qǐng)緩沖區(qū)，將一個(gè)進(jìn)程的邏輯地址空間劃分成若干個(gè)大小相等的部分，每一部分稱做頁(yè)面或頁(yè)。每頁(yè)都有一個(gè)編號(hào)，叫做頁(yè)號(hào)，頁(yè)號(hào)從0開(kāi)始依次編排，如0，1，2。設(shè)置等大小的內(nèi)存塊。初始狀態(tài)：將數(shù)據(jù)文件的第一個(gè)頁(yè)面裝入到該緩沖區(qū)的第0塊。設(shè)計(jì)頁(yè)面置換算法，這里分別采用最佳頁(yè)面置換算法OPT和最近最久未使用置換算法LRU,并分別計(jì)算它們的缺頁(yè)率，以比較它們的優(yōu)劣。三、算法說(shuō)明： 執(zhí)行程序時(shí)，當(dāng)主存沒(méi)有可用頁(yè)面時(shí)，為了選擇淘汰主存中的哪一頁(yè)面，騰出1個(gè)空閑塊以便存放新調(diào)入的頁(yè)面。淘汰哪個(gè)頁(yè)面的首要問(wèn)題是選擇何種置換算法。該

21、程序采用人工的方法選擇，依置換策略選擇一個(gè)可置換的頁(yè)，并計(jì)算它們的缺頁(yè)率以便比較。/*分頁(yè)式管理實(shí)驗(yàn)-源程序*/#include<stdlib.h>#include<conio.h>#include<stdio.h>#include<string.h>#define N 16#define num 5 /*進(jìn)程分配物理塊數(shù)目*/int AN=1,2,3,4,5,6,7,8,5,2,3,2,7,8,1,4; /*頁(yè)表映像*/typedef struct page int address; /*頁(yè)面地址*/struct page *next; pag

22、e;struct page *head,*run,*rear;void jccreat() /*進(jìn)程分配物理塊*/ int i=1;page *p,*q;head=(page *)malloc(sizeof(page); p=head;for(i=1;i<=num;i+)q=(page *)malloc(sizeof(page);p->next=q; q->address=0; q->next=NULL;p=q; rear=p;int search(int n)page *p;int i=0;p=head;while(p->next)if(p->next-&

23、gt;address=n)printf("Get it at the page %dn",i+1);run=p;return 1;p=p->next;i+;return 0;void changeOPT(int n,int position)int i;int total=0;int flag=1;int distancenum;int MAX;int order=0;page *p,*q;p=head->next;q=head->next;for(i=0;i<num;i+)distancei=100;i=0;while(p)if(p->add

24、ress=0)flag=0;break;p=p->next;i+;if(!flag)p->address=n;printf("Change the page %dn",i+1);elsewhile(q)for(i=position;i<N;i+)if(q->address=Ai)distancetotal=i-position;total+;q=q->next;MAX=distance0;for(i=0;i<num;i+)if(distancei>MAX)MAX=distancei;order=i;printf("Chan

25、ge the page %dn",order+1);i=0;while(p)if(i=order)p->address=n;i+;p=p->next;void changeLRU(int n)int i=0;int flag=1;page *p,*delect;p=head->next;while(p)if(p->address=0)flag=0;p->address=n;printf("Change the page %dn",i+1);break;p=p->next;i+;if(flag)delect=head->next;head->next=delect->next;printf("Delect from the head, and add new to the end.n");delect->address=n;rear->next=delect;rear=delect;rear->next=NULL;float OPT()int i;int lose=0;float losef;float percent;for(