LRU置換算法和銀行家算法實(shí)驗(yàn)報(bào)告

1、計(jì)算機(jī)操作系統(tǒng)實(shí) 驗(yàn) 報(bào) 告課程名稱(chēng)計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)項(xiàng)目名稱(chēng)LRU置換算法和銀行家算法學(xué)號(hào)班級(jí)計(jì)姓名專(zhuān)業(yè)實(shí)驗(yàn)地點(diǎn)12J-661實(shí)驗(yàn)室 濟(jì)南大學(xué)信息科學(xué)與技術(shù)學(xué)院2013年12月10日一、實(shí)驗(yàn)概述1. 實(shí)驗(yàn)名稱(chēng)LRU置換算法2. 實(shí)驗(yàn)?zāi)康模?）了解內(nèi)存分頁(yè)管理策略（2）掌握調(diào)頁(yè)策略（3）掌握一般常用的調(diào)度算法（4）學(xué)會(huì)各種存儲(chǔ)分配算法的實(shí)現(xiàn)方法。（5）了解頁(yè)面大小和內(nèi)存實(shí)際容量對(duì)命中率的影響。3. 實(shí)驗(yàn)內(nèi)容FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決

2、策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。 二、實(shí)驗(yàn)環(huán)境進(jìn)行實(shí)驗(yàn)使用的操作系統(tǒng)：windowXP編譯器：VS語(yǔ)言：C#三、實(shí)驗(yàn)過(guò)程1. 設(shè)計(jì)思路和流程圖2. 算法實(shí)現(xiàn)最近最久未使用(LRU)的頁(yè)面置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似，因此，

3、LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。3. 需要解決的問(wèn)題及解答LRU的實(shí)現(xiàn)（需要“堆棧”支持）可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問(wèn)頁(yè)面的編號(hào)，而棧底則是最近最久未使用頁(yè)面的頁(yè)面號(hào)。4. 主要數(shù)據(jù)結(jié)構(gòu)、實(shí)現(xiàn)代碼及其說(shuō)明5. 源程序并附上注釋import java.io.BufferedReader;import jav

4、a.io.InputStreamReader;public class LRU int blockCount;int seriaCount;static int num=0;int address;int stack;BufferedReader br;public static void main(String args) int address = 7, 0,1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1;LRU lru = new LRU();lru.init();lru.display();public void init()

5、try br = new BufferedReader(new InputStreamReader(System.in);catch (Exception e) e.printStackTrace();System.exit(0);blockCount = 3;stack = new intblockCount;System.out.println("請(qǐng)輸入訪問(wèn)內(nèi)存的塊序列的個(gè)數(shù)為3:");seriaCount = readInt();System.out.println("讀入的訪問(wèn)序列是:");address = readIntArray();pub

6、lic void display() boolean flag;System.out.println("-");System.out.print("最近最久未使用頁(yè)面置換算法（LRU）頁(yè)面置換序列：");for (int i = 0; i< address.length; i+) int j =0;flag =false;int t, temp =addressi;while(stackj != addressi) t= stackj;stackj= temp;temp= t;j+; if(temp = 0 | j = stack.length)

7、break;if (j< stack.length)stackj= temp;if (temp != 0&& j != stack.length)flag= true;try java.lang.Thread.sleep(500); catch(InterruptedException e) e.printStackTrace();for (int m= 0; m < i - blockCount + 1; m+)System.out.print(" ");for (int m =0; m < stack.length; m+)System

8、.out.print(stackm+ " ");System.out.print(",");if(flag)num=num;elsenum+;System.out.println("");System.out.println("總?cè)表?yè)數(shù)："+num);public int readInt() try String s =br.readLine();return Integer.parseInt(s); catch (Exception e) return 3;public int readIntArray() tr

9、y String s =br.readLine();System.out.println(s);String tmp= s.split(" ");int value =new inttmp.length;for (int i =0; i < value.length; i+)valuei= Integer.parseInt(tmpi);return value; catch (Exception e) System.out.println(e);return null;6. 程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果四、實(shí)驗(yàn)體會(huì)通過(guò)這次的實(shí)驗(yàn)，我對(duì)LRU頁(yè)面置換算法有了更深的了解，L

10、RU置換算法是理想性的算法，因?yàn)槭褂肔RU置換算法要花費(fèi)很大的系統(tǒng)開(kāi)銷(xiāo)，所以在實(shí)際系統(tǒng)中并不會(huì)直接采用LRU算法。本次實(shí)驗(yàn)通過(guò)java程序?qū)RU頁(yè)面置換算法的模擬，并沒(méi)有設(shè)置自動(dòng)執(zhí)行的功能，而且內(nèi)存的塊序列也得手動(dòng)進(jìn)行輸入，在程序的設(shè)計(jì)上沒(méi)有完全達(dá)到實(shí)驗(yàn)的要求，但基本實(shí)現(xiàn)了實(shí)驗(yàn)要求的全部功能。一、實(shí)驗(yàn)概述1. 實(shí)驗(yàn)名稱(chēng)銀行家算法模擬2. 實(shí)驗(yàn)?zāi)康模?）理解利用銀行家算法避免死鎖的問(wèn)題；（2）在了解和掌握銀行家算法的基礎(chǔ)上，編制銀行家算法通用程序，將調(diào)試結(jié)果顯示在計(jì)算機(jī)屏幕上，并檢測(cè)機(jī)算和筆算的一致性。（3）理解和掌握安全序列、安全性算法3. 實(shí)驗(yàn)內(nèi)容（1）了解和理解死鎖；（2）理解利用銀行家

11、算法避免死鎖的原理；（3）使用某種編程語(yǔ)言模擬該算法。二、實(shí)驗(yàn)環(huán)境進(jìn)行實(shí)驗(yàn)使用的操作系統(tǒng)：windowXP編譯器：VS語(yǔ)言：C三、實(shí)驗(yàn)過(guò)程1. 設(shè)計(jì)思路和流程圖Y所有finish都為true？輸出安全序列NYN存在Finishi =false&&Needij< Availablej初始化Work和FinishFinishi=true，Workj=Workj+ Allocationj所有進(jìn)程都找完了？Y開(kāi)始 安全性算法流程圖2. 算法實(shí)現(xiàn)算法：n：系統(tǒng)中進(jìn)程的總數(shù)m：資源類(lèi)總數(shù)Available: ARRAY1.m of integer;Max: ARRAY1.n,1.m

12、of integer;Allocation: ARRAY1.n,1.m of integer;Need: ARRAY1.n,1.m of integer;Request: ARRAY1.n,1.m of integer;符號(hào)說(shuō)明：Available 可用剩余資源Max 最大需求Allocation 已分配資源Need 需求資源Request 請(qǐng)求資源當(dāng)進(jìn)程pi提出資源申請(qǐng)時(shí)，系統(tǒng)執(zhí)行下列步驟：(“=”為賦值符號(hào)，“=”為等號(hào))step（1）若Request<=Need, goto step（2）；否則錯(cuò)誤返回step（2）若Request<=Available, goto step

13、（3）；否則進(jìn)程等待step（3）假設(shè)系統(tǒng)分配了資源，則有：Available=Available-Request;Allocation=Allocation+Request;Need=Need-Request若系統(tǒng)新?tīng)顟B(tài)是安全的，則分配完成若系統(tǒng)新?tīng)顟B(tài)是不安全的，則恢復(fù)原狀態(tài)，進(jìn)程等待為進(jìn)行安全性檢查，定義數(shù)據(jù)結(jié)構(gòu)：Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;安全性檢查的步驟：step (1): Work=Available;Finish=false;step (2) 尋找滿足條件的i：a.Finish=false;b.Need&l

14、t;=Work;如果不存在，goto step(4)step(3) Work=Work+Allocation;Finish=true;goto step(2)step (4) 若對(duì)所有i,Finish=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)3. 需要解決的問(wèn)題及解答4. 主要數(shù)據(jù)結(jié)構(gòu)、實(shí)現(xiàn)代碼及其說(shuō)明我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請(qǐng)求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，

15、否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。5. 源程序并附上注釋#include "malloc.h"#include "stdio.h"#include "stdlib.h"#define alloclen sizeof(struct allocation)#define maxlen sizeof(struc

16、t max)#define avalen sizeof(struct available)#define needlen sizeof(struct need)#define finilen sizeof(struct finish)#define pathlen sizeof(struct path)struct allocationint value;struct allocation *next;struct maxint value;struct max *next;struct available /*可用資源數(shù)*/int value;struct available *next;s

17、truct need /*需求資源數(shù)*/int value;struct need *next;struct pathint value;struct path *next;struct finishint stat;struct finish *next;int main()int row,colum,status=0,i,j,t,temp,processtest;struct allocation *allochead,*alloc1,*alloc2,*alloctemp;struct max *maxhead,*maxium1,*maxium2,*maxtemp;struct avail

18、able *avahead,*available1,*available2,*workhead,*work1,*work2,*worktemp,*worktemp1;struct need *needhead,*need1,*need2,*needtemp;struct finish *finihead,*finish1,*finish2,*finishtemp;struct path *pathhead,*path1,*path2;printf("n請(qǐng)輸入系統(tǒng)資源的種類(lèi)數(shù):");scanf("%d",&colum);printf("請(qǐng)

19、輸入現(xiàn)時(shí)內(nèi)存中的進(jìn)程數(shù):");scanf("%d",&row);printf("請(qǐng)輸入已分配資源矩陣:n");for(i=0;i<row;i+)for (j=0;j<colum;j+)printf("請(qǐng)輸入已分配給進(jìn)程 p%d 的 %c 種系統(tǒng)資源:",i,'A'+j);if(status=0)allochead=alloc1=alloc2=(struct allocation*)malloc(alloclen);alloc1->next=alloc2->next=NULL;s

20、canf("%d",&allochead->value);status+;elsealloc2=(struct allocation *)malloc(alloclen);scanf("%d,%d",&alloc2->value);if(status=1)allochead->next=alloc2;status+;alloc1->next=alloc2;alloc1=alloc2;alloc2->next=NULL;status=0;printf("請(qǐng)輸入最大需求矩陣:n");for(i

21、=0;i<row;i+)for (j=0;j<colum;j+)printf("請(qǐng)輸入進(jìn)程 p%d 種類(lèi) %c 系統(tǒng)資源最大需求:",i,'A'+j);if(status=0)maxhead=maxium1=maxium2=(struct max*)malloc(maxlen);maxium1->next=maxium2->next=NULL;scanf("%d",&maxium1->value);status+;elsemaxium2=(struct max *)malloc(maxlen);sca

22、nf("%d,%d",&maxium2->value);if(status=1)maxhead->next=maxium2;status+;maxium1->next=maxium2;maxium1=maxium2;maxium2->next=NULL;status=0;printf("請(qǐng)輸入現(xiàn)時(shí)系統(tǒng)剩余的資源矩陣:n");for (j=0;j<colum;j+)printf("種類(lèi) %c 的系統(tǒng)資源剩余:",'A'+j);if(status=0)avahead=available

23、1=available2=(struct available*)malloc(avalen);workhead=work1=work2=(struct available*)malloc(avalen);available1->next=available2->next=NULL;work1->next=work2->next=NULL;scanf("%d",&available1->value);work1->value=available1->value;status+;elseavailable2=(struct av

24、ailable*)malloc(avalen);work2=(struct available*)malloc(avalen);scanf("%d,%d",&available2->value);work2->value=available2->value;if(status=1)avahead->next=available2;workhead->next=work2;status+;available1->next=available2;available1=available2;work1->next=work2;wo

25、rk1=work2;available2->next=NULL;work2->next=NULL;status=0;alloctemp=allochead;maxtemp=maxhead;for(i=0;i<row;i+)for (j=0;j<colum;j+)if(status=0)needhead=need1=need2=(struct need*)malloc(needlen);need1->next=need2->next=NULL;need1->value=maxtemp->value-alloctemp->value;statu

26、s+;elseneed2=(struct need *)malloc(needlen);need2->value=(maxtemp->value)-(alloctemp->value);if(status=1)needhead->next=need2;status+;need1->next=need2;need1=need2;maxtemp=maxtemp->next;alloctemp=alloctemp->next;need2->next=NULL;status=0;for(i=0;i<row;i+)if(status=0)finihe

27、ad=finish1=finish2=(struct finish*)malloc(finilen);finish1->next=finish2->next=NULL;finish1->stat=0;status+;elsefinish2=(struct finish*)malloc(finilen);finish2->stat=0;if(status=1)finihead->next=finish2;status+;finish1->next=finish2;finish1=finish2;finish2->next=NULL; /*Initiali

28、zation compleated*/status=0;processtest=0;for(temp=0;temp<row;temp+)alloctemp=allochead;needtemp=needhead;finishtemp=finihead;worktemp=workhead;for(i=0;i<row;i+)worktemp1=worktemp;if(finishtemp->stat=0)for(j=0;j<colum;j+,needtemp=needtemp->next,worktemp=worktemp->next)if(needtemp->value<=worktemp->value)processtest+;if(processtest=colum)for(j=0;j<colum;j+)worktemp1->value+=alloctemp->value;worktemp1=worktemp1->next;alloctemp=alloctemp->next;if(status=0)pathhead=path1=path2