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

1、上孝甩SHANGHAI DIANJI UNIVERSITY操作系統(tǒng)原理課程設計報告姓名：黃崧岳班級：BX1010學號：5扌旨導老師：蘇慶岡I二一二年十二月十四日一、操作系統(tǒng)原理課程設計的目的與要求 11目的12要求1二、簡述課程設計內容、主要功能和實現(xiàn)環(huán)境 11課程設計內容12主要功能13實現(xiàn)環(huán)境2三、任務的分析、設計、實現(xiàn)和討論 21任務的分析22任務的設計與實現(xiàn) 34思考題的解答和討論 10四、操作系統(tǒng)課程設計小結 14五、參考文獻14附錄14操作系統(tǒng)原理課程設計的目的與要求1目的近年來，由于大規(guī)模集成電路（LSI）和超大規(guī)模集成電路（VLSI ）技術的發(fā)展，使存 儲器的容量不斷擴大，價格

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

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

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

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

6、最佳淘汰算法（OPT）和最近最少使用頁面淘汰算法（LRU ）計算頁面命中 率。公式為命中率=1 -頁面失效次數 頁地址流長度3#假定虛存容量為32K，頁面尺寸從1K至8K，實存容量從4頁至32頁。#2任務的設計與實現(xiàn)2.1 ma in()函數流程圖:42.2主菜單流程圖:inm;11printfl入 你0renrrnlji),2.3 LRU函數流程圖:62.4 Zidingyi()函數流程圖:inti;i-0piiges:100;岸 whim);2.5 ShowCustomer(函數流程圖:o("cm；i-0printtVtd *bpagesi汁十72.6 ShowNot()函數流程

7、圖:82.7 ShowResult()函數流程圖:9#pr'Tlttr1 %d",Fu7hui；i+pTinttrn"：#3操作過程和結果分析按1進入自定義進程數和塊數請求頁式存儲管理中LRU譚法的實現(xiàn)12 3 4利義 矍 程自法 進UMTT 義用RUEX 定一憑 自顯#輸入你的選擇#按2顯示進程數，塊數和隨機分配頁號10覽 JOCKXHHBEXX JOCKKJOC” KUH WBHHHHOCJtK ICX)0000( JOC)1 W lOOCK 100(童 Wit JCK見不:進程斂為：20頁號分別為： 4167 34 B 6924 ?B 5862 B4 

8、3;45 Bl 27 G1 VI 95422736町用物理塊數為，1曲任意鍵 可返回 主菜.單按3實現(xiàn)LRU算法，輸出命中率11#LRU算法結果顯示;9-454259-420 52 80:414141078781 188:27換為：為為：一 書備詈一 總罷一 s頁面頁一 頁置4叩缺一#按1修改塊數，按2遞回主菜單Wes1, No2#按1修改物理塊數，重新實現(xiàn) LRU算法并輸出命中率27&191958178顯示:34417ZT別為27町用物理塊數為:按任意鍵可返回王菜單UW算袪結果顯黃:454S4561616161424241412.b81813i12EZ2l2l0B 0 0 17fhj

9、 為為；為為.24總忌率 95換頁面頁 置畳命缺-按1修改塊數按2返回主菜單Wes1, No2 2_請求頁式存儲管理中LRU算法的實現(xiàn)按4退出程序12 3 4數 塊和義 墊疋 程自法 進fin 義用RUEK 定不L 自顯12#輸入你的選擇= 4 謝謝使用算迭？Bye ByeA-APress any keu to continueFIFO算法該算法總是淘汰最先進入內存的頁面，既選擇內存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單，只需要把一個進程已調入內存的頁面，按照先后測序鏈接成一個隊列，并設置一個指針，使他總是指向最老的頁面。但該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經常被

10、訪問，比如，含有全局變量、常用函數、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。這里，我們用下面的例子，采用FIFO算法進行頁面置換。當進程第一次訪問頁面 2時，將把第七頁換出，因為它是最先被調入內存的；在第一次范文頁面3時，又將把第零頁換出，因為他在現(xiàn)有的2，0，1三個頁面中是最老的頁。由下圖可以看出，利用 FIFO算法時進行了十二次頁面置換，比最佳置換算法正好多一倍。結果分析一一兩種算法的比較：先進先出（FIFO）算法較易實現(xiàn)，比較適用于具有線性順序特性的程序，而對其他特性的程序 則效率不高。缺頁中斷率為最佳算法的23倍；增加可用主存塊的數量會導致更多的缺頁，此算法還可能出現(xiàn)抖動

11、現(xiàn)象異常。最近最久未被使用（LRU）算法的實現(xiàn)需要硬件支持，基于程序的局部性原理，所以適用用大 多數程序，此算實現(xiàn)必須維護一個特殊的隊列一一頁面淘汰隊列。關鍵是確定頁面最后訪問以來 所經歷的時間。4思考題的解答和討論（1 ）設計一個界地址存儲管理的模擬系統(tǒng)，模擬界地址方式下存儲區(qū)的分配和回收過程。提示：必須設置一個內存分配表， 按照分配表中有關信息實施存儲區(qū)的分配，并不斷根據存儲區(qū)的分配和回收修改該表。算法有首次匹配法，循環(huán)首次匹配法和最佳匹配法等?？捎酶鞣N方法的比較來充實實習內容?？墒褂盟槠占蛷蜕w等技術。答：開始（1 ）數據結構及說明本程序為可變分區(qū)管理方式主存分配回收模擬程序，采用首次

12、適應策略。主要數據結構：空閑區(qū)鏈表FBC，分配區(qū)鏈表ABC :表中記錄塊的起始地址和大小，塊按照始地址大小從小到大排列。（2）功能實現(xiàn) 分配時，根據用戶提供的作業(yè)大小，從第一個空閑塊開始查找，將找到的第一個足夠大的空閑塊塊分配給該作業(yè)，返回給用戶該塊始地址。如果該塊剩余部分小于特定閾值（本程序為2k）,將該塊整體分配給此作業(yè)，將該塊直接加入分配區(qū)鏈表，若剩余塊大于或等于閾值，將分配塊加入分配區(qū)鏈表，剩余部分作為新的空閑塊另：程序開始時已將0到20k分配給操作系統(tǒng)。 回收時，根據用戶提供的作業(yè)的始地址，在分配區(qū)表查找，若找到該塊，將其加入空閑區(qū)鏈表，提示用戶釋放成功。 若新形成的空閑塊與其前后的

13、空閑塊相連，合并空閑塊形成更大的空閑塊。 顯示，用戶可隨時選擇查看內存分配狀態(tài)圖以及空閑區(qū)表與分配區(qū)表，在分配或回收成功時，程序自動顯示內存分配狀態(tài)圖、空閑區(qū)表與分配區(qū)表。編制一個程(2)自行設計或選用一種較為完善的內存管理方法，并加以實現(xiàn)。 提示：設計一個段頁式管理的模擬程序或通過一個實際系統(tǒng)的消化和分析, 序來模擬該系統(tǒng)。答：分配總空間大小為128,若輸入的進程大于該數，則顯示“占用空間過大，分配失敗”若分配的進程大小為 0,則顯示“進程空間大小錯誤”1603070b閑區(qū)情況： 無空閑區(qū)了.長.g *C: Docu*ent s and Sett ingsAdB.in.ist rat orB

14、y DocuAent sDebugCppl. exe Sb-內名名名Jt:a=纏粗 長鼎始 己己-己- - 0 tSI - -Ir:! -!r 況:7分； 第存:a:b 區(qū)地問名名 空起進進進：30（：40：58睛按鍵選搖：1犧輸入進翟名和占用空I可大小:CC58:址址址 乩也也也 壇始始 己己己己 酉_已一已_已 分a b C 存:a:b:c選擇1分配內存，輸入內存名和占用空間大小即可分配內存，顯示的項目有進程名、起始地址和長度，已分配的內存分配情況會顯示出來，如上圖?？臻g分配滿則顯示“無空閑區(qū)” *C: Docu>ent s and Sett ingsAdB.inist rat or

15、By DocuAent sDebugCppl. exe*CC58空閑區(qū)情況: 氏空閑區(qū)了.內名名名進進進進：0aa起.：30 f ：40bb起始地址：30起始地址:西長度汚&cc熒黯爲和程名: 迸翟內存回收完畢.ccg=5a=纏粗 彼鼎始 卡 己己-己一 - 酉走 況:0分；擇 舟存:a:b選 區(qū)地內名名 鍵 i K 按 空起逬進逬 請選擇2回收內存，輸入已分配的內存名稱即可回收該內存，并顯示剩余的已分配內存17四、操作系統(tǒng)課程設計小結頁面置換算法理解比較容易，這次根據學號要求實現(xiàn)的是 LRU算法的實現(xiàn)。分配到我的是兩道思考題，其實這兩道思考題的算法是差不多的，所以第一 題我沒有去編寫

16、只是寫出了大概的思路和算法框圖。其實這兩種算法的程序編寫 比較容易，雖然不全是自己編寫的，一部分是參考的網上的例題，但是通過對每 一語句的理解，自己弄懂了整個程序的執(zhí)行原理。 但是，在編寫過程中自己還是 遇到了一些問題。最大的一個問題就是兩個算法的正確實現(xiàn)，在程序的編寫時，兩個程序是分 開進行編寫的，分別執(zhí)行起來沒有什么問題，但是把兩個程序融合在一起后，卻 出現(xiàn)了問題，即在執(zhí)行完成一個算法后再執(zhí)行另外一個算法時， 開始的數據是緊 接著上次算法結果的數據進行實驗的。 這個問題困擾了我好長時間，直到現(xiàn)在還 沒有很好的解決掉，程序只能分別執(zhí)行一次，如果再進行執(zhí)行的話，就會出現(xiàn)問 題。自己的編程技術不

17、好，程序編的也很繁瑣，但是基本的要求已經實現(xiàn)了，希 望這次的實驗是自己動手的一個開始，自己應該更加努力，再接再厲。五、參考文獻【1】 計算機操作系統(tǒng) 【2】 計算機操作系統(tǒng) 【3】 操作系統(tǒng)教程孫雅如等編著西安電子科技大學2003（第2版）吳企淵 等編著清華大學出版社 2003 徐甲同編著西安電子科技大學出版社.2001附錄LRU算法實現(xiàn)#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>#defi ne Maxsize 300 void Xiugaikuaishu(); void In itio

18、 n();void Zidi ngyi(); void ShowCustomer();void ShowResult();void ShowNot();void LRU();int menu _select();int pageNum = 0;/ 頁面數int pagesMaxsize; 存儲頁號int FuzhuMaxsize; 輔助數組int TimeMaxsize;記錄頁在內存中的時間int block;/記錄物理塊數int Fz;輔助變量int mai n()for(;) /*循環(huán)無限次*/switch(me nu _select()case 1: Zidi ngyi();break;

19、case 2: ShowCustomer();break;case 3: LRU();break;case 4:printf(”謝謝使用LRU算法!n");printf(” Bye ByeA-An");exit(0);/*如菜單返回值為13則程序結束*/return 0; int menu _select()int n;printf(”i1n");prin tf("|請求頁式存儲管理中 LRU算法的實現(xiàn)| n ”);prin tf("| n ”);prin tf("|1.自定義進程數和塊數| n");prin tf(&quo

20、t;|2.顯示用戶自定義| n");prin tf("|3.LRU算法| n");19prin tf("|4.EXIT1 n ”);prin tf("|1 n ”);prin tf("|1 n ”);printf(”|1n");doprintf("nttt 輸入你的選擇(14):");scan f("%d", &n);while(n< 1|n>4); /*如果選擇項不在13之間則重輸*/ |如果一個以上為真,真，二者都為假時，結果為假return(n); /*返回選

21、擇項，主函數根據該數調用相應的函數*/則結果為void Zidi ngyi()II自定義進程數和塊數int i;system("cls");printf(” *n");printf(”頁式儲存管理一LRU算法printf(” *n");printf(” 自定義進程數和塊數 n");prin tf("n");printf("請輸入進程數：”)；scan f("%d",&pageNum);for(i = 0 ; i < pageNum ; i+)pagesi = rand()%100;

22、 II初始化頁號，初始值在0-100之內 getchar();printf("請輸入塊數：”)；scan f("%d",&block );getchar();自定義進程數和塊數n");void LRU()II最近最久未使用算法 int i,j;int WithOutPages = 0;II 記錄缺頁數printf(" *printf(”LRU 算法結果顯示：n");prin tf("n");ShowNot();for(i = Fz ; i < pageNum; i+)21int key = 0;for

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

24、n”,WithOutPages);printf("頁面總數為：%d n”,pageNum);double re = (double)WithOutPages)/(double)pageNum); printf("置換率為：%.2lfn",re);printf("命中率為：.2lfn",1-re);printf("缺頁次數為：%d n”,WithOutPages+block);printf("頁面總數為：%d n”,pageNum);re = (double)(WithOutPages+block)/(double)pageN

25、um); printf("缺頁率為：%.2lfn",re);22printf("*printf(”按1修改塊數，按2返回主菜單n");#prin tf("n");printf(”Yes-1，No-2 n");in t la;sea nf("%d",&la);if(la=1)Xiugaikuaishu();elseprintf(” *n “);printf("system("cls");void ShowResult()顯示每次換頁后的結果int i;for(i = 0

26、 ; i < block ; i+)printf(" %d",Fuzhui);prin tf("n"); void Xiugaikuaishu()system("cls");printf(" *printf(”請輸入需要修改塊的數目 ：n ”);prin tf("");int a;scan f("%d", &a);block = a;ShowCustomer();顯示自定義頁面信息LRU();void ShowCustomer()顯示用戶自定義的進程數和塊數 system

27、("cls");int i;printf(" *printf("顯示:n");printf("進程數為：%dn",pageNum); printf("頁號分別為：”)；for(i = 0 ; i < pageNum ; i+)prin tf("%d”,pagesi);prin tf("n");printf("可用物理塊數為：%dn",block);printf(" *printf(” 按任意鍵可返回主菜單 n");getchar();voi

28、d ShowNot()顯示一定不用換頁的部分 Fz = block;int i,j,k=O,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+)prin tf("%d",Fuzhuj); prin tf("n&

29、quot;);思考題2:內存管理小程序#in clude <iostream.h>#in clude <stdio.h>#in elude <stri ng.h> struct programchar n ame30;long start;long len gth;struct program *n ext;struct spacelong start;long len gth;struct space *n ext;void creat();void allot();void back();void callback(program *r);void so

30、rt(space *L);void sort(program *S);void display(space *L);void display(program *S);space *L; program *S;void creat()L=new space;space *p=new space; p->start=0;p->le ngth=128;p-> next=NULL;L_>n ext=p;S=new program;S-> next=NULL;void allot()program *q;q=new program;cout<<"請輸入

31、進程名和占用空間大小:"<<endl;cin»q_>n ame»q->le ngth;if(q->le ngth<=0)cout<<"進程空間大小錯誤."<<endl;delete q;return;space *p,*r;P=L;r=p;while(p-> next!=NULL&&p-> next->le ngth<q->le ngth)r=p;p=p->n ext;if(p-> next=NULL)cout<<&

32、quot;占用空間過大，分配失敗"<<endl;delete q;return;elseq->start=p->n ext->start;q->n ext=S->n ext;S_>n ext=q;p-> next->le ngth-=q->le ngth;if(p->n ext->le ngth!=O)p_>n ext->start+=q->le ngth;elseif(p-> next-next!=NULL)p->n ext=p->n ext- >n ext;el

33、ser->n ext=NULL;delete p->n ext;display(L);display(S);void back()char n ame30;cout<<"輸入要回收的進程名："cin»n ame;program *p;p=S;while(p-> next!=NULL)if(strcmp(p->n ext- >n ame, n ame)=0)callback(p);return;p=p->n ext;if(p-> next=NULL)cout<<"此進程不存在，內存回收失敗&

34、quot;<<endl;void callback(program *t)program *r;r=t- >n ext;space *p,*q;long n;n=r->le ngth;if(L-> next=NULL)space *w=new space;w->start=0;w->le ngth=n;w-> next=NULL;L->n ext=w;t->n ext=r- >n ext;delete r;cout<<"此進程內存回收完畢."<<endl;27display(L);di

35、splay(S);return;p=L->n ext;while(p!=NULL&&p->start<r->start)q=p;p=p->n ext;上下均空if(q->start+q->le ngth=r->start )&&( r->start+ n=p->start) /q_>n ext=p->n ext;q->le ngth=q_>le ngth+p_>le ngth+n;t->n ext=r- >n ext;delete r;else if(r->

36、;start+ n=p->start) / 下鄰空p->start-=n;p->le ngth+=n;t->n ext=r- >n ext;delete r;else if(q->start+q->le ngth=r->start)q->le ngth+=n;t->n ext=r- >n ext;delete r;elsespace *sp=new space;sp->start=r->start;sp->le ngth=n;sp->n ext=L->n ext;L->n ext=sp;t-&

37、gt;n ext=r- >n ext;delete r;cout<<"此進程內存回收完畢."<<endl;display(L);display(S);void display(space *L)sort(L);space *p=L->n ext;cout<<e ndl<<"空閑區(qū)情況："<<e ndl;if(p=NULL) cout<<"無空閑區(qū)了 ."<<endl; return;while(p!=NULL)cout<<"起始地址:"<<p->start<<"長度:"<<p->length<<endl;p=p->n ext;void display(program *S)sort(S);program *p=S->n ext;cout<<e ndl<