操作系統(tǒng)課程設(shè)計(jì)LRU算法的實(shí)現(xiàn)

1、文檔供參考，可復(fù)制、編制，期待您的好評與關(guān)注！ 操作系統(tǒng)原理課程設(shè)計(jì)報(bào)告姓 名： 黃崧岳 班 級： BX1010 學(xué) 號： 5 指導(dǎo)老師： 蘇慶剛 二一二年 十二 月十四日目 錄一、操作系統(tǒng)原理課程設(shè)計(jì)的目的與要求11目的12要求1二、簡述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境11課程設(shè)計(jì)內(nèi)容12主要功能13實(shí)現(xiàn)環(huán)境2三、任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論21任務(wù)的分析22任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)34思考題的解答和討論10四、 操作系統(tǒng)課程設(shè)計(jì)小結(jié)14五、參考文獻(xiàn)14附錄1426 / 28一、操作系統(tǒng)原理課程設(shè)計(jì)的目的與要求1目的近年來，由于大規(guī)模集成電路（LSI）和超大規(guī)模集成電路（VLSI）技術(shù)的發(fā)展，使存儲

2、器的容量不斷擴(kuò)大，價(jià)格大幅度下降。但從使用角度看，存儲器的容量和成本總受到一定的限制。所以，提高存儲器的效率始終是操作系統(tǒng)研究的重要課題之一。虛擬存儲技術(shù)是用來擴(kuò)大內(nèi)存容量的一種重要方法。學(xué)生應(yīng)獨(dú)立地用高級語言編寫幾個(gè)常用的存儲分配算法，并設(shè)計(jì)一個(gè)存儲管理的模擬程序，對各種算法進(jìn)行分析比較，評測其性能優(yōu)劣，從而加深對這些算法的了解。2要求任務(wù)四采用最近最少使用頁淘汰算法(LRU)實(shí)現(xiàn)。為了比較真實(shí)地模擬存儲管理，可預(yù)先生成一個(gè)大致符合實(shí)際情況的指令地址流。然后模擬這樣一種指令序列的執(zhí)行來計(jì)算和分析各種算法的訪問命中率。二、簡述課程設(shè)計(jì)內(nèi)容、主要功能和實(shí)現(xiàn)環(huán)境1課程設(shè)計(jì)內(nèi)容 最近最少使用頁淘汰算

3、法(LRU)，這是一種經(jīng)常使用的方法。有各種不同的實(shí)施方案，這里采用的是不斷調(diào)整頁表鏈的方法，即總是淘汰頁表鏈鏈?zhǔn)椎捻?，而把新訪問的頁插入鏈尾。如果當(dāng)前調(diào)用頁已在頁表內(nèi)，則把它再次調(diào)整到鏈尾。這樣就能保證最近使用的頁，總是處于靠近鏈尾部分，而不常使用的頁就移到鏈?zhǔn)?，逐個(gè)被淘汰，在頁表較大時(shí)，調(diào)整頁表鏈的代價(jià)也是不小的。2主要功能（1） 菜單函數(shù)int menu_select()：用于顯示主菜單，可在其中選擇1.自定義進(jìn)程數(shù)和塊數(shù)；2.顯示顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)；3.進(jìn)行LRU算法4.退出程序。（2） 最近最久未使用算法函數(shù)void LRU()：此函數(shù)是將隨機(jī)產(chǎn)生的頁面進(jìn)行最近未使用便置換

4、的函數(shù)，也是本程序的主要部分。（3） 自定義進(jìn)程數(shù)和塊數(shù)函數(shù)void Zidingyi()：此函數(shù)是主菜單中的第一個(gè)選項(xiàng)，即用戶可以自定義所需的進(jìn)程數(shù)和塊數(shù)。（4） 顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)函數(shù)void ShowCustomer()：此函數(shù)是用于顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)的情況。（5） 修改塊數(shù)函數(shù)void Xiugaikuaishu()：此函數(shù)是在進(jìn)行LRU算法后，可以在原來的進(jìn)程數(shù)的基礎(chǔ)上，修改塊數(shù)并重新生成一組LRU算法的過程。（6） 顯示每次換頁后的結(jié)果函數(shù)void ShowResult()：此函數(shù)是顯示在LRU算法的執(zhí)行過程中每次換頁的情況。（7） 顯示一定不用換頁的函數(shù)voi

5、d ShowNot()：此函數(shù)是顯示最近使用過的頁面，即不用換頁的結(jié)果。3實(shí)現(xiàn)環(huán)境本次課程設(shè)計(jì)結(jié)合算法的特點(diǎn)，采用Windows操作系統(tǒng)平臺。開發(fā)工具為Microsoft Visual C+6.0。三、任務(wù)的分析、設(shè)計(jì)、實(shí)現(xiàn)和討論1任務(wù)的分析本示例是采用頁式分配存儲管理方案，并通過分析計(jì)算不同頁面淘汰算法情況下的訪問命中率來比較各種算法的優(yōu)劣。另外也考慮到改變頁面大小和實(shí)際存儲器容量對計(jì)算結(jié)果的影響，從而可為算則好的算法、合適的頁面尺寸和實(shí)存容量提供依據(jù)。本程序是按下述原則生成指令序列的：（1） 50%的指令是順序執(zhí)行的。（2） 25%的指令均勻散布在前地址部分。（3） 25%的指令均勻散布在

6、后地址部分。示例中選用最佳淘汰算法（OPT）和最近最少使用頁面淘汰算法（LRU）計(jì)算頁面命中率。公式為假定虛存容量為32K，頁面尺寸從1K至8K，實(shí)存容量從4頁至32頁。2任務(wù)的設(shè)計(jì)與實(shí)現(xiàn)2.1 main( )函數(shù)流程圖：開始進(jìn)入主菜單是否輸入為“1”是否輸入為“2”是否輸入為“3”是否輸入為“4”顯示進(jìn)程數(shù)和塊數(shù)自定義進(jìn)程數(shù)和塊數(shù)進(jìn)入LRU算法退出程序NNNNYYYY結(jié)束2.2 主菜單流程圖：2.3 LRU函數(shù)流程圖：2.4 Zidingyi( )函數(shù)流程圖：2.5 ShowCustomer( )函數(shù)流程圖：2.6 ShowNot( )函數(shù)流程圖：2.7 ShowResult( )函數(shù)流程圖

7、：3操作過程和結(jié)果分析 按1進(jìn)入自定義進(jìn)程數(shù)和塊數(shù)按2顯示進(jìn)程數(shù)，塊數(shù)和隨機(jī)分配頁號按3實(shí)現(xiàn)LRU算法，輸出命中率按1修改物理塊數(shù)，重新實(shí)現(xiàn)LRU算法并輸出命中率按4退出程序FIFO算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，既選擇內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需要把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按照先后測序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，使他總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。 這里，我們用下面的例子，采用FIFO算法進(jìn)行頁面置換。當(dāng)進(jìn)程第一

8、次訪問頁面2時(shí)，將把第七頁換出，因?yàn)樗亲钕缺徽{(diào)入內(nèi)存的；在第一次范文頁面3時(shí)，又將把第零頁換出，因?yàn)樗诂F(xiàn)有的2，0，1三個(gè)頁面中是最老的頁。由下圖可以看出，利用FIFO算法時(shí)進(jìn)行了十二次頁面置換，比最佳置換算法正好多一倍。 結(jié)果分析兩種算法的比較：先進(jìn)先出(FIFO)算法較易實(shí)現(xiàn)，比較適用于具有線性順序特性的程序，而對其他特性的程序則效率不高。缺頁中斷率為最佳算法的23倍；增加可用主存塊的數(shù)量會(huì)導(dǎo)致更多的缺頁，此算法還可能出現(xiàn)抖動(dòng)現(xiàn)象異常。最近最久未被使用(LRU)算法的實(shí)現(xiàn)需要硬件支持，基于程序的局部性原理，所以適用用大多數(shù)程序，此算實(shí)現(xiàn)必須維護(hù)一個(gè)特殊的隊(duì)列頁面淘汰隊(duì)列。關(guān)鍵是確定頁面

9、最后訪問以來所經(jīng)歷的時(shí)間。4思考題的解答和討論（1）設(shè)計(jì)一個(gè)界地址存儲管理的模擬系統(tǒng)，模擬界地址方式下存儲區(qū)的分配和回收過程。提示：必須設(shè)置一個(gè)內(nèi)存分配表，按照分配表中有關(guān)信息實(shí)施存儲區(qū)的分配，并不斷根據(jù)存儲區(qū)的分配和回收修改該表。算法有首次匹配法，循環(huán)首次匹配法和最佳匹配法等?？捎酶鞣N方法的比較來充實(shí)實(shí)習(xí)內(nèi)容?？墒褂盟槠占蛷?fù)蓋等技術(shù)。答：開始選擇菜單0退出程序123分配主存回收主存顯示主存NYNNNYYY （1）數(shù)據(jù)結(jié)構(gòu)及說明 本程序?yàn)榭勺兎謪^(qū)管理方式主存分配回收模擬程序，采用首次適應(yīng)策略。 主要數(shù)據(jù)結(jié)構(gòu)： 空閑區(qū)鏈表FBC，分配區(qū)鏈表ABC： 表中記錄塊的起始地址和大小，塊按照始地址大

10、小從小到大排列。 （2）功能實(shí)現(xiàn) 分配時(shí)，根據(jù)用戶提供的作業(yè)大小，從第一個(gè)空閑塊開始查找，將找到的第一個(gè)足夠大的空閑塊塊分配給該作業(yè)，返回給用戶該塊始地址。如果該塊剩余部分小于特定閾值（本程序?yàn)?k),將該塊整體分配給此作業(yè)，將該塊直接加入分配區(qū)鏈表，若剩余塊大于或等于閾值，將分配塊加入分配區(qū)鏈表，剩余部分作為新的空閑塊.另：程序開始時(shí)已將0到20k分配給操作系統(tǒng)。 回收時(shí)，根據(jù)用戶提供的作業(yè)的始地址，在分配區(qū)表查找，若找到該塊，將其加入空閑區(qū)鏈表，提示用戶釋放成功。若新形成的空閑塊與其前后的空閑塊相連，合并空閑塊形成更大的空閑塊。 顯示，用戶可隨時(shí)選擇查看內(nèi)存分配狀態(tài)圖以及空閑區(qū)表與分配區(qū)表

11、，在分配或回收成功時(shí)，程序自動(dòng)顯示內(nèi)存分配狀態(tài)圖、空閑區(qū)表與分配區(qū)表。（2）自行設(shè)計(jì)或選用一種較為完善的內(nèi)存管理方法，并加以實(shí)現(xiàn)。提示：設(shè)計(jì)一個(gè)段頁式管理的模擬程序或通過一個(gè)實(shí)際系統(tǒng)的消化和分析，編制一個(gè)程序來模擬該系統(tǒng)。答: 分配總空間大小為128，若輸入的進(jìn)程大于該數(shù)，則顯示“占用空間過大，分配失敗”若分配的進(jìn)程大小為0，則顯示“進(jìn)程空間大小錯(cuò)誤”選擇1分配內(nèi)存，輸入內(nèi)存名和占用空間大小即可分配內(nèi)存，顯示的項(xiàng)目有進(jìn)程名、起始地址和長度，已分配的內(nèi)存分配情況會(huì)顯示出來，如上圖?？臻g分配滿則顯示“無空閑區(qū)”選擇2回收內(nèi)存，輸入已分配的內(nèi)存名稱即可回收該內(nèi)存，并顯示剩余的已分配內(nèi)存4、 操作系統(tǒng)

12、課程設(shè)計(jì)小結(jié)頁面置換算法理解比較容易，這次根據(jù)學(xué)號要求實(shí)現(xiàn)的是LRU算法的實(shí)現(xiàn)。分配到我的是兩道思考題，其實(shí)這兩道思考題的算法是差不多的，所以第一題我沒有去編寫只是寫出了大概的思路和算法框圖。其實(shí)這兩種算法的程序編寫比較容易，雖然不全是自己編寫的，一部分是參考的網(wǎng)上的例題，但是通過對每一語句的理解，自己弄懂了整個(gè)程序的執(zhí)行原理。但是，在編寫過程中自己還是遇到了一些問題。最大的一個(gè)問題就是兩個(gè)算法的正確實(shí)現(xiàn)，在程序的編寫時(shí)，兩個(gè)程序是分開進(jìn)行編寫的，分別執(zhí)行起來沒有什么問題，但是把兩個(gè)程序融合在一起后，卻出現(xiàn)了問題，即在執(zhí)行完成一個(gè)算法后再執(zhí)行另外一個(gè)算法時(shí)，開始的數(shù)據(jù)是緊接著上次算法結(jié)果的數(shù)據(jù)

13、進(jìn)行實(shí)驗(yàn)的。這個(gè)問題困擾了我好長時(shí)間，直到現(xiàn)在還沒有很好的解決掉，程序只能分別執(zhí)行一次，如果再進(jìn)行執(zhí)行的話，就會(huì)出現(xiàn)問題。自己的編程技術(shù)不好，程序編的也很繁瑣，但是基本的要求已經(jīng)實(shí)現(xiàn)了，希望這次的實(shí)驗(yàn)是自己動(dòng)手的一個(gè)開始，自己應(yīng)該更加努力，再接再厲。五、參考文獻(xiàn)【1】 計(jì)算機(jī)操作系統(tǒng) 孫雅如 等 編著 西安電子科技大學(xué) 2003【2】 計(jì)算機(jī)操作系統(tǒng)（第2版）吳企淵 等 編著 清華大學(xué)出版社 2003【3】 操作系統(tǒng)教程 徐甲同 編著 西安電子科技大學(xué)出版社.2001附錄LRU算法實(shí)現(xiàn)#include #include #include #define Maxsize 300void Xiug

14、aikuaishu();void Inition();void Zidingyi();void ShowCustomer();void ShowResult();void ShowNot();void LRU();int menu_select();int pageNum = 0; /頁面數(shù)int pagesMaxsize;/存儲頁號int FuzhuMaxsize;/輔助數(shù)組int TimeMaxsize;/記錄頁在內(nèi)存中的時(shí)間int block;/記錄物理塊數(shù)int Fz;/輔助變量int main()for(;) /*循環(huán)無限次*/ switch(menu_select() case 1

15、: Zidingyi(); break; case 2: ShowCustomer(); break; case 3: LRU(); break; case 4: printf(謝謝使用LRU算法!n);printf( Bye Bye-n);exit(0); /*如菜單返回值為13則程序結(jié)束*/ return 0;int menu_select() int n; printf(n);printf( 請求頁式存儲管理中LRU算法的實(shí)現(xiàn) n);printf( n);printf( 1. 自定義進(jìn)程數(shù)和塊數(shù) n);printf( 2. 顯示用戶自定義 n);printf( 3. LRU算法 n);

16、printf( 4. EXIT n);printf( n);printf( n);printf(n);do printf(nttt輸入你的選擇(14):); scanf(%d,&n); while(n4); /*如果選擇項(xiàng)不在13之間則重輸*/ /|如果一個(gè)以上為真，則結(jié)果為真，二者都為假時(shí)，結(jié)果為假return(n); /*返回選擇項(xiàng)，主函數(shù)根據(jù)該數(shù)調(diào)用相應(yīng)的函數(shù)*/ void Zidingyi() /自定義進(jìn)程數(shù)和塊數(shù)int i;system(cls);printf(*n);printf( 頁式儲存管理LRU算法 n);printf(*n);printf(-自定義進(jìn)程數(shù)和塊數(shù)-n);pri

17、ntf(n);printf(請輸入進(jìn)程數(shù)：);scanf(%d,&pageNum);for(i = 0 ; i pageNum ; i+)pagesi = rand()%100; /初始化頁號，初始值在0-100之內(nèi)getchar();printf(請輸入塊數(shù)：);scanf(%d,&block ); getchar();void LRU()/最近最久未使用算法int i,j;int WithOutPages = 0;/記錄缺頁數(shù)printf(*n);printf(-LRU算法結(jié)果顯示:-n);printf(n);ShowNot();for(i = Fz ; i pageNum; i+)int

18、 key = 0;for(j = 0 ; j block ; j+)/判斷該頁是否在物理塊中if(Fuzhuj = pagesi)key = 1;Timej = i;/更新時(shí)間break;if(key = 0)/若該頁不在內(nèi)存中WithOutPages+;int min = Time0;int flag = 0;for(j = 1 ; j Timej)min = Timej;/找到最久的頁面flag = j;Timeflag = i;/記錄時(shí)間Fuzhuflag = pagesi;ShowResult();printf(置換次數(shù)為： %d n,WithOutPages);printf(頁面總數(shù)

19、為： %d n,pageNum); double re = (double)WithOutPages)/(double)pageNum);printf(置換率為： %.2lfn,re);printf(命中率為： %.2lfn,1-re);printf(缺頁次數(shù)為： %d n,WithOutPages+block);printf(頁面總數(shù)為： %d n,pageNum);re = (double)(WithOutPages+block)/(double)pageNum);printf(缺頁率為： %.2lfn,re);printf(*n);printf(-按1修改塊數(shù)，按2返回主菜單-n); p

20、rintf(n); printf( Yes-1，No-2 n); int la; scanf(%d,&la); if(la=1) Xiugaikuaishu(); elseprintf(*n);printf(-n);system(cls); void ShowResult()/顯示每次換頁后的結(jié)果int i;for(i = 0 ; i block ; i+)printf( %d,Fuzhui);printf(n);void Xiugaikuaishu()system(cls);printf(*n);printf(-請輸入需要修改塊的數(shù)目:-n);printf();int a;scanf(%d,

21、&a);block = a;ShowCustomer();/顯示自定義頁面信息LRU();void ShowCustomer()/顯示用戶自定義的進(jìn)程數(shù)和塊數(shù) system(cls);int i;printf(*n);printf(-顯示:-n);printf(進(jìn)程數(shù)為: %dn,pageNum);printf(頁號分別為: );for(i = 0 ; i pageNum ; i+)printf(%d ,pagesi);printf(n);printf(可用物理塊數(shù)為: %dn,block);printf(*n);printf(-按任意鍵可返回主菜單-n);getchar();void Sho

22、wNot()/顯示一定不用換頁的部分Fz = block;int i,j,k=0,key = 0;for(i = 0 ; i Fz ; i+)int flag = 0;for(j = 0 ; j = i-1 ; j+)if(Fuzhuj = pagesi)Timej = i;flag = 1;Fz = Fz+1;key+;if(flag = 0)Timek = i;Fuzhuk = pagesi;k+;for(j = 0 ; j = i-key ; j+)printf( %d,Fuzhuj);printf(n);思考題2：內(nèi)存管理小程序#include #include #include st

23、ruct program char name30; long start; long length; struct program *next;struct space long start; long length; struct space *next;void creat();void allot();void back();void callback(program *r);void sort(space *L);void sort(program *S);void display(space *L);void display(program *S);space *L;program

24、*S;void creat() L=new space; space *p=new space; p-start=0; p-length=128; p-next=NULL; L-next=p; S=new program; S-next=NULL;void allot() program *q; q=new program; cout請輸入進(jìn)程名和占用空間大小:q-nameq-length; if(q-length=0) cout進(jìn)程空間大小錯(cuò)誤.next!=NULL&p-next-lengthlength) r=p; p=p-next; if(p-next=NULL) cout占用空間過大，

25、分配失敗start=p-next-start; q-next=S-next; S-next=q; p-next-length-=q-length; if(p-next-length!=0) p-next-start+=q-length; else if(p-next-next!=NULL) p-next=p-next-next; else r-next=NULL; delete p-next; display(L); display(S);void back() char name30; coutname; program *p; p=S; while(p-next!=NULL) if(str

26、cmp(p-next-name, name)=0) callback(p); return; p=p-next; if(p-next=NULL) cout此進(jìn)程不存在,內(nèi)存回收失敗next; space *p,*q; long n; n=r-length; if(L-next=NULL) space *w=new space; w-start=0; w-length=n; w-next=NULL; L-next=w; t-next=r-next; delete r; cout此進(jìn)程內(nèi)存回收完畢.next; while(p!=NULL&p-startstart) q=p; p=p-next; i

27、f(q-start+q-length=r-start)&(r-start+n=p-start) /上下均空 q-next=p-next; q-length=q-length+p-length+n; t-next=r-next; delete r; else if(r-start+n=p-start) /下鄰空 p-start-=n; p-length+=n; t-next=r-next; delete r; else if(q-start+q-length=r-start) q-length+=n; t-next=r-next; delete r; else space *sp=new space; sp-start=r-start; sp-length=n; sp-next=L-next; L-next=sp; t-next=r-next; de