操作系統(tǒng)課程設(shè)計(jì)(LRU算法)完整版內(nèi)含代碼

1、 操作系統(tǒng)課程設(shè)計(jì) LRU頁面調(diào)度算法 學(xué) 號(hào)： 姓 名： 學(xué) 院： 專 業(yè)： 班 級(jí)： 指導(dǎo)老師： 日 期： 目 錄 一、實(shí)驗(yàn)題目1二、課程設(shè)計(jì)的目的1三、設(shè)計(jì)內(nèi)容1四、設(shè)計(jì)要求1五、設(shè)計(jì)思想1六、主要數(shù)據(jù)結(jié)構(gòu)及其說明2七、硬件支持3八、源程序文件3九、程序運(yùn)行結(jié)果7十、實(shí)驗(yàn)體會(huì)8一 實(shí)驗(yàn)題目 LRU頁面調(diào)度算法二 課程設(shè)計(jì)的目的 操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既 動(dòng)手又動(dòng)腦，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合一起，獨(dú)立分析和解 決實(shí)際問題的機(jī)會(huì)。1.進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。2. 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。3.提高學(xué)生調(diào)試程序

2、的技巧和軟件設(shè)計(jì)的能力。4.提高學(xué)生分析問題、解決問題以及綜合利用C語言進(jìn)行程序設(shè)計(jì)的能力。三 設(shè)計(jì)內(nèi)容 程序應(yīng)模擬實(shí)現(xiàn)LRU算法思想，對(duì)n個(gè)頁面實(shí)現(xiàn)模擬調(diào)度。四 設(shè)計(jì)要求1不同的功能使用不同的函數(shù)實(shí)現(xiàn)（模塊化），對(duì)每個(gè)函數(shù)的功能和調(diào)用接口要注釋清楚。對(duì)程序其它部分也進(jìn)行必要的注釋。2對(duì)系統(tǒng)進(jìn)行功能模塊分析、畫出總流程圖和各模塊流程圖。3用戶界面要求使用方便、簡(jiǎn)潔明了、美觀大方、格式統(tǒng)一。所有功能可以反復(fù)使用，最好使用菜單。4通過命令行相應(yīng)選項(xiàng)能直接進(jìn)入某個(gè)相應(yīng)菜單選項(xiàng)的功能模塊。5所有程序需調(diào)試通過。五 設(shè)計(jì)思想最近最久未使用（LRU）頁調(diào)度算法是選擇最近最久未使用的頁面予以淘汰。算法賦予每

3、個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間，當(dāng)所要訪問的頁面在內(nèi)存塊中時(shí)，就不淘汰頁面，否則，淘汰頁面中時(shí)間最長(zhǎng)的，即淘汰最近最久未使用的頁面。 Lru(ai,b) Init(b,c) 輸入頁面號(hào) 開始輸出queuei 缺頁次數(shù)和缺頁率是否繼 續(xù)? y n 結(jié)束 算法流程圖 六 主要數(shù)據(jù)結(jié)構(gòu)及其說明程序執(zhí)行是穩(wěn)定的，高效的。在LRU算法中，要找出最近最久未使用的頁面的話，就必須設(shè)置有關(guān)的訪問記錄項(xiàng)，且每一次訪問這些記錄項(xiàng)，葉面都必須更新這些記錄項(xiàng)。這個(gè)記錄項(xiàng)在此程序中為：typedef struct pageint num;/*記錄頁面號(hào)*/int time;/*記錄調(diào)入

4、內(nèi)存時(shí)間*/Page;/頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì) 如此，顯然要花費(fèi)較大的系統(tǒng)開銷（包括時(shí)間和空間上的），這也是實(shí)際系統(tǒng)中不采用LRU算法的直接原因，但由于其頁面置換的優(yōu)越性，實(shí)際系統(tǒng)中常使用LRU的近似算法。七 硬件支持 為了了解一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁面各有多少時(shí)間未被進(jìn)程訪問，以及如何快速的知道哪一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：寄存器或棧。寄存器：為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器。棧：可利用一個(gè)特殊的棧來保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)。每當(dāng)進(jìn)程訪問某頁面時(shí)，便將該頁面的頁面號(hào)從戰(zhàn)中移出，將它壓入棧頂。因此，棧頂始

5、終是最新被訪問頁面的編號(hào)，而棧底則是最近最久未使用頁面的頁面號(hào)。八 源程序文件 #include<stdio.h> #include<conio.h> #include<stdlib.h> #define M 3 /物理塊數(shù) #define N 10 /頁面數(shù) #define Myprintf1 printf("t*ttnn");/表格控制 #define Myprintf2 printf("*nn");/表格控制 typedef struct page int num;/*記錄頁面號(hào)*/int time;/*記錄調(diào)入

6、內(nèi)存時(shí)間*/ Page;/頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)Page bM;/內(nèi)存單元數(shù)int cMN;/暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)int queue100;/記錄調(diào)入隊(duì)列int K;/調(diào)入隊(duì)列計(jì)數(shù)變量/初始化內(nèi)存單元、緩沖區(qū)void Init(Page *b,int cMN) int i,j; for(i=0;i<N;i+) bi.num=-1; bi.time=N-i-1; for(i=0;i<M;i+) for(j=0;j<N;j+) cij=-1;/取得在內(nèi)存中停留最久的頁面，默認(rèn)狀態(tài)下為最早調(diào)入的頁面int GetMax(Page *b) int i; int

7、max=-1; int tag=0; for(i=0;i<M;i+) if(bi.time>max) max=bi.time; tag=i; return tag;/判斷頁面是否已在內(nèi)存中int Equation(int fold,Page *b) int i; for(i=0;i<M;i+) if(fold=bi.num) return i; return -1;/LRU核心部分void Lru(int fold,Page *b) int i; int val; val=Equation(fold,b); if(val>=0) bval.time=0; for(i=0

8、;i<M;i+) if(i!=val) bi.time+; else queue+K=fold;/記錄調(diào)入頁面 val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;i<M;i+) if(i!=val) bi.time+; /主程序void main() start:K=-1; int i,j; int aN; Myprintf1; printf("nttt歡迎使用LRU頁面調(diào)度算法nn"); Myprintf1; printf("請(qǐng)輸入所要訪問的各個(gè)頁面號(hào)：n"); for(i=0;i<

9、N;i+) scanf("%d",&ai);Init(b,c); /調(diào)用 for(i=0;i<N;i+) Lru(ai,b); c0i=ai; /記錄當(dāng)前的內(nèi)存單元中的頁面 for(j=0;j<M;j+) cji=bj.num; /結(jié)果輸出printf("內(nèi)存狀態(tài)為:n");Myprintf2; for(j=0;j<N;j+) printf("|%2d",aj);printf("|n");Myprintf2; for(i=0;i<M;i+) for(j=0;j<N;j+) if

10、(cij=-1) printf("|%2c",32); else printf("|%2d",cij); printf("|n"); Myprintf2; printf("n調(diào)入隊(duì)列為："); for(i=0;i<K+1;i+) printf("%3d",queuei); printf("n缺頁次數(shù)為:%6dn缺頁率:%16.6f",K+1,(float)(K+1)/N); printf("n是否繼續(xù)!t y?"); char y; if(getch()='y') system("cls"); printf("n"); goto start; else printf(&qu