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

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

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

3、是一種經(jīng)常使用的方法。有各種不同的實施方案， 這里采用的是不斷調(diào)整頁表鏈的方法，即總是淘汰頁表鏈鏈?zhǔn)椎捻?，而把新訪問的頁插入鏈尾。如果當(dāng)前調(diào)用頁已在頁表內(nèi)，則把它再次調(diào)整到鏈尾。這樣就能保證最近使用的頁，總 是處于靠近鏈尾部分，而不常使用的頁就移到鏈?zhǔn)?，逐個被淘汰，在頁表較大時，調(diào)整頁表鏈的代價也是不小的。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ù)是將隨機產(chǎn)生的頁面進(jìn)行最近未使用 便置換的函數(shù)，也是本

4、程序的主要部分。（3）自定義進(jìn)程數(shù)和塊數(shù)函數(shù) void Zidingyi（）:此函數(shù)是主菜單中的第一個選項，即用戶可以自定義所需的進(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ù) void ShowNot

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

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

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

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

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

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

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

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

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

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

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

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

17、好，程序編的也很繁瑣，但是基本的要求已經(jīng)實現(xiàn)了，希 望這次的實驗是自己動手的一個開始，自己應(yīng)該更加努力，再接再厲。五、參考文獻(xiàn)【1】 計算機操作系統(tǒng) 【2】 計算機操作系統(tǒng) 【3】 操作系統(tǒng)教程孫雅如等編著西安電子科技大學(xué)2003（第2版）吳企淵 等編著清華大學(xué)出版社 2003 徐甲同編著西安電子科技大學(xué)出版社.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;/ 頁面數(shù)int pagesMaxsize; 存儲頁號int FuzhuMaxsize; 輔助數(shù)組int TimeMaxsize;記錄頁在內(nèi)存中的時間int block;/記錄物理塊數(shù)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則程序結(jié)束*/return 0; int menu _select()int n;printf(”i1n");prin tf("|請求頁式存儲管理中 LRU算法的實現(xiàn)| n ”);prin tf("| n ”);prin tf("|1.自定義進(jìn)程數(shù)和塊數(shù)| 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之間則重輸*/ |如果一個以上為真,真，二者都為假時，結(jié)果為假return(n); /*返回選

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

22、 II初始化頁號，初始值在0-100之內(nèi) getchar();printf("請輸入塊數(shù)：”)；scan f("%d",&block );getchar();自定義進(jìn)程數(shù)和塊數(shù)n");void LRU()II最近最久未使用算法 int i,j;int WithOutPages = 0;II 記錄缺頁數(shù)printf(" *printf(”LRU 算法結(jié)果顯示：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)/若該頁不在內(nèi)存中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("置換次數(shù)為：d

24、n”,WithOutPages);printf("頁面總數(shù)為：%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)pageN

25、um); printf("缺頁率為：%.2lfn",re);22printf("*printf(”按1修改塊數(shù)，按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()顯示每次換頁后的結(jié)果int i;for(i = 0

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

27、("cls");int i;printf(" *printf("顯示:n");printf("進(jìn)程數(shù)為：%dn",pageNum); printf("頁號分別為：”)；for(i = 0 ; i < pageNum ; i+)prin tf("%d”,pagesi);prin tf("n");printf("可用物理塊數(shù)為：%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:內(nèi)存管理小程序#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、進(jìn)程名和占用空間大小:"<<endl;cin»q_>n ame»q->le ngth;if(q->le ngth<=0)cout<<"進(jìn)程空間大小錯誤."<<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<<"輸入要回收的進(jìn)程名："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<<"此進(jìn)程不存在，內(nèi)存回收失敗&

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<<"此進(jìn)程內(nèi)存回收完畢."<<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<<"此進(jìn)程內(nèi)存回收完畢."<<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<