LRU頁(yè)面調(diào)度算法實(shí)現(xiàn)

1、精品LRU 頁(yè)調(diào)度算法實(shí)現(xiàn)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)學(xué)生姓名指導(dǎo)教師姓名感謝下載載精品2014 年3月15 日一、設(shè)計(jì)目的、內(nèi)容與要求（一）目的：操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，獨(dú)立分析和解決實(shí)際問(wèn)題的機(jī)會(huì)。（ 1）進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。（ 2）培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。（ 3）提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。（ 4）提高學(xué)生分析問(wèn)題、解決問(wèn)題以及綜合利用C 語(yǔ)言進(jìn)行程序設(shè)計(jì)的能力。（二）內(nèi)容：程序應(yīng)模擬實(shí)現(xiàn)LRU 算法思想，對(duì) n 個(gè)頁(yè)面實(shí)現(xiàn)模擬調(diào)度

2、。（三）要求：1. 不同的功能使用不同的函數(shù)實(shí)現(xiàn) （模塊化），對(duì)每個(gè)函數(shù)的功能和調(diào)用接口要注釋清楚。對(duì)程序其它部分也進(jìn)行必要的注釋。2. 對(duì)系統(tǒng)進(jìn)行功能模塊分析、畫(huà)出總流程圖和各模塊流程圖。感謝下載載精品3. 用戶界面要求方便、簡(jiǎn)潔明了、美麗大方、格式統(tǒng)一。所有功能可以反復(fù)使用，最好使用菜單。4. 通過(guò)命令相應(yīng)選項(xiàng)能直接進(jìn)入某個(gè)相應(yīng)菜單選項(xiàng)的功能模塊。所有程序需調(diào)試通過(guò)。二、算法的基本思想LRU 是 Least Recently Used近期最少使用算法。內(nèi)存管理的一種頁(yè)面置換算法，對(duì)于在內(nèi)存中但又不用的數(shù)據(jù)塊（內(nèi)存塊）叫做 LRU，Oracle 會(huì)根據(jù)哪些數(shù)據(jù)屬于LRU 而將其移出內(nèi)存而騰出

3、空間來(lái)加載另外的數(shù)據(jù)。什么是 LRU 算法？LRU 是 Least Recently Used的縮寫(xiě)，即最少使用頁(yè)面置換算法，是為虛擬頁(yè)式存儲(chǔ)管理服務(wù)的。關(guān)于操作系統(tǒng)的內(nèi)存管理， 如何節(jié)省利用容量不大的內(nèi)存為最多的進(jìn)程提供資源，一直是研究的重要方向。 而內(nèi)存的虛擬存儲(chǔ)管理，是現(xiàn)在最通用，最成功的方式在內(nèi)存有限的情況下，擴(kuò)展一部分外存作為虛擬內(nèi)存， 真正的內(nèi)存只存儲(chǔ)當(dāng)前運(yùn)行時(shí)所用得到信息。這無(wú)疑極大地?cái)U(kuò)充了內(nèi)存的功能，極大地提高了計(jì)算機(jī)的并發(fā)度。虛擬頁(yè)式存儲(chǔ)管理，則是將進(jìn)程所需空間劃分為多個(gè)頁(yè)面，內(nèi)存中只存放當(dāng)前所需頁(yè)面， 其余頁(yè)面放入外存的管理方式。程序中用到了 if ，switch選擇語(yǔ)句，

4、和 for 循環(huán)語(yǔ)句進(jìn)行編程。If 語(yǔ)句基本格式為：If （表達(dá)式）語(yǔ)句 1else感謝下載載精品語(yǔ)句 2Switch 語(yǔ)句基本格式為：Switch ( 表達(dá)式 )case常量表達(dá)式 1；語(yǔ)句序列 1case常量表達(dá)式 2；語(yǔ)句序列 2三、主要功能模塊流程圖（ 1）主菜單流程圖 :Init ；I=0I <blockYPrintf( “%d” ,Fuzhui;)I +NPrintf( “ n” )(2)main 函數(shù)流程圖：感謝下載載開(kāi)始進(jìn)入主菜單是否輸入為“ 1”精品是否輸入為是否輸入為是否輸入為NNN“2”“3”“4”YYYY自定義塊數(shù)和顯示進(jìn)程數(shù)和進(jìn)入 LRU 算法退出進(jìn)程數(shù)塊數(shù)N結(jié)

5、束(3)LRU 程序流程圖：感謝下載載精品開(kāi)始頁(yè)數(shù)是否已滿？NY該頁(yè)是否在物找到最久的頁(yè)面，N退出 LRU 算法理塊中更新時(shí)間，置換Y更新時(shí)間結(jié)束（ 4）自定義函數(shù)流程圖：Init ；I=0I <pageNumYPagesi=rand()%100;I +NGetchar90;四、系統(tǒng)測(cè)試感謝下載載精品（ 1）顯示主菜單：（ 2）選擇 1：（ 3）選擇 3：感謝下載載精品（ 4）選擇 1：（ 4）輸入要修改塊的：感謝下載載精品五、結(jié)論通過(guò)這兩周的課設(shè)，我不僅復(fù)習(xí)了C 語(yǔ)言的相關(guān)知識(shí)，還對(duì)操作系統(tǒng)有了進(jìn)一步的理解和掌握。實(shí)驗(yàn)中，通過(guò)LRU（最近最久未使用）算法實(shí)現(xiàn)了頁(yè)面調(diào)度模擬實(shí)驗(yàn)。 LRU

6、 與其他幾種調(diào)度算法在原理上既有區(qū)別又有聯(lián)系。要想充分掌握 LRU 算法，也要會(huì)使用其他幾種算法。雖然在程序設(shè)計(jì)中， 出現(xiàn)了一些錯(cuò)誤， 但是經(jīng)過(guò)同學(xué)的幫助和輔導(dǎo)老師的細(xì)心指導(dǎo)，我已經(jīng)將錯(cuò)誤糾正了。 使程序達(dá)到預(yù)想的結(jié)果， 能夠?qū)崿F(xiàn)簡(jiǎn)單的頁(yè)面調(diào)度。通過(guò)此次實(shí)驗(yàn)， 我發(fā)現(xiàn)自己在編程方面還有許多不足的地方，以后要多加動(dòng)手編寫(xiě)，提高自己的編程能力。最后感謝同學(xué)的幫助和輔導(dǎo)老師的悉心指導(dǎo)，使我順利完成此次實(shí)驗(yàn)。六、源程序#include <stdio.h>#include <stdlib.h>感謝下載載精品#include <time.h>#define Maxsiz

7、e 50void Xiugaikuaishu();void Inition();void Zidingyi();void ShowCustomer();void ShowResult();void ShowNot();void LRU();int menu_select(); /菜單函數(shù)int pageNum = 0;int pagesMaxsize;/存儲(chǔ)頁(yè)號(hào)int FuzhuMaxsize;/輔助數(shù)組int TimeMaxsize;/記錄頁(yè)在內(nèi)存中的時(shí)間int physicalblock;/記錄物理塊數(shù)int Fz;/ 輔助變量int main()for(;)switch(menu_sel

8、ect()感謝下載載精品case 1: Zidingyi();break;case 2: ShowCustomer();break;case 3: LRU();break;case 4:exit(0);return 0;int menu_select()int n;printf("*歡迎進(jìn)入主界面*n");printf("*請(qǐng)求頁(yè)式存儲(chǔ)管理中LRU 算法的實(shí)現(xiàn)*n");printf("*n");printf("*1. 自定義進(jìn)程數(shù)和塊數(shù)*n");printf("*2. 顯示用戶自定義*n");p

9、rintf("*3.LRU 算法*n");printf("*4.EXIT*n");感謝下載載精品printf("*n");printf("*n");doprintf("n輸入你的選擇(14):");scanf("%d",&n);while(n<1|n>4);return(n);void Zidingyi()int i;system("cls");printf("*n");printf("頁(yè)式儲(chǔ)存管理-LRU

10、 算法n");printf("*n");printf("-自定義進(jìn)程數(shù)和塊數(shù)-n");printf("請(qǐng)輸入進(jìn)程數(shù)：");scanf("%d",&pageNum);getchar();printf("請(qǐng)輸入塊數(shù)：");scanf("%d",&physicalblock );感謝下載載精品getchar();printf("請(qǐng)依次輸入頁(yè)號(hào)引用串(中間用空格隔開(kāi)):");for(i = 0 ; i < pageNum ; i+)

11、scanf("%d",&pagesi);void LRU()int i,j;int ReplacePages = 0;/記錄置換次數(shù)printf("*n");printf("-LRU算法結(jié)果顯示-n");printf("n");ShowNot();for(i = Fz ; i < pageNum; i+)int key = 0;for( j = 0 ; j < physicalblock ; j+)/判斷該頁(yè)是否在物理塊中if(Fuzhuj = pagesi)key = 1; /該頁(yè)在內(nèi)存中Ti

12、me j = i;/更新時(shí)間感謝下載載精品break;if(key = 0)/若該頁(yè)不在內(nèi)存中ReplacePages+;/ 缺頁(yè)次數(shù)加1int min = Time0;int flag = 0;for(j = 1 ; j < physicalblock ; j+)if(min > Timej)min = Timej;/ 找到最久的頁(yè)面flag = j;Timeflag = i;/記錄時(shí)間Fuzhuflag = pagesi;ShowResult();printf("頁(yè)面總數(shù)為：%dn",pageNum);感謝下載載精品printf("置換次數(shù)為： %

13、dn",ReplacePages);double re1 = (double)ReplacePages)/(double)pageNum);printf("置換率為：%.2lfn",re1);printf("命中率為：%.2lfn",1-re1);printf("缺頁(yè)次數(shù)為：%d n",ReplacePages+physicalblock);double re2 = (double)(ReplacePages+physicalblock)/(double)pageNum);printf("缺頁(yè)率為：%.2lfn&q

14、uot;,re2);printf("*n");printf("-按 1 修改塊數(shù)，按2 返回主菜單 -n");printf("n");printf("Yes-1 ，No-2n");int la;scanf("%d",&la);if(la=1)Xiugaikuaishu();elseprintf("*n");printf("-n");system("cls");感謝下載載精品void ShowResult()/顯示每次換頁(yè)后的結(jié)果

15、int i;for(i = 0 ; i < physicalblock ; i+)printf("%d",Fuzhui);printf("n");void Xiugaikuaishu()system("cls");printf("*n");printf("-請(qǐng)輸入需要修改塊的數(shù)目-n");int a;scanf("%d",&a);physicalblock = a;ShowCustomer();/顯示自定義頁(yè)面信息感謝下載載精品LRU();void ShowCu

16、stomer()/顯示用戶自定義的進(jìn)程數(shù)和塊數(shù)system("cls");int i;printf("*n");printf("-顯示 -n");printf("進(jìn)程數(shù)為 :%dn",pageNum);printf("頁(yè)號(hào)分別為 :");for(i = 0 ; i < pageNum ; i+)printf("%d",pagesi);printf("n");printf("可用物理塊數(shù)為:%dn",physicalblock);printf("*n");printf("-按任意鍵可返回主菜單-n");getchar();void ShowNot()/顯示一定不用換頁(yè)的部分感謝下載載精品Fz = physicalblock;int i,j,k=0,key = 0;for(i = 0 ; i < Fz ; i