2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩25頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、<p>  《操作系統(tǒng)》課程設計說明書</p><p>  設計題目: 存儲管理 </p><p>  專 業(yè): 計算機科學與技術 </p><p>  指導教師: </p><p>  班 級:

2、</p><p>  學 號: </p><p>  姓 名: </p><p>  同 組 人: </p><p><b>  計算機科學與工程系</b></p>

3、<p>  2013年 01 月 10 日</p><p><b>  前言</b></p><p>  本模擬系統(tǒng)實現(xiàn)了先進先出頁面淘汰算法(FIFO)、最近最少使用LRU頁面淘汰算法、最近未使用算法NUR、最少訪問頁面算法LFU和最佳淘汰算法OPT。同時系統(tǒng)可以隨意設置當前分配給作業(yè)的物理塊數(shù)。</p><p>  系統(tǒng)運行時,

4、任意輸入一個頁面訪問序列,可以設定不同的頁面置換算法和物理塊數(shù),輸出其頁面淘汰的情況,計算其缺頁次數(shù)和缺頁率。系統(tǒng)結束后,比較同一個頁面訪問序列,可以得出在不同的頁面置換算法和物理塊數(shù)的情況下,其產(chǎn)生的缺頁次數(shù)和缺頁率。</p><p>  使用FIFO算法,由于測試數(shù)據(jù)相同的頁面比較少,所以采用FIFO算法時,需要置換的頁面多,比較繁瑣,沒有優(yōu)化效果,所以FIFO算法性能不好。使用LRU的算法,此組數(shù)據(jù)顯示LR

5、U的算法使用比較繁瑣,總的來說,NUR、LFU、LRU算法介于FIFO和Optimial之間。通過系統(tǒng)模擬得出,optimal算法的性能高,LRU、NUR、LRU算法的性能次之,F(xiàn)IFO的算法性能最差,較少應用;由于optimal算法在實際上難于實現(xiàn),所以實際應用一般用LRU算法。</p><p>  本設計的目的是是熟悉存儲管理的設計方法,加深對請求分頁式存儲管理的</p><p>  

6、認識。設計中用到了數(shù)據(jù)結構中的相關知識,鏈表的操作,通過本設計可以加深的數(shù)據(jù)結構的理解。設計代碼語言用到的是C語言,使用起來比較方便,可以在虛擬機和VC上直接運行。</p><p><b>  目錄</b></p><p><b>  目錄3</b></p><p><b>  一、系統(tǒng)環(huán)境4</b&g

7、t;</p><p>  1.1、硬件環(huán)境4</p><p>  1.2、軟件環(huán)境4</p><p><b>  二、設計目的5</b></p><p><b>  三、總體設計6</b></p><p>  3.1、程序設計組成框圖6</p><

8、;p><b>  3.2、流程圖7</b></p><p><b>  四、詳細設計11</b></p><p>  4.1、數(shù)據(jù)結構11</p><p>  4.1.1頁面類型11</p><p>  4.1.2頁面控制結構11</p><p>  4.2.

9、函數(shù)定義12</p><p>  4.3.變量定義12</p><p>  4.4.算法分析12</p><p>  五、調試與測試14</p><p>  5.1、調試方法14</p><p>  5.2、測試結果的分析與討論14</p><p>  六、設計中遇到的問題15&l

10、t;/p><p>  七、源程序清單16</p><p>  八、總結,收獲與體會25</p><p><b>  九、參考文獻26</b></p><p><b>  一、系統(tǒng)環(huán)境</b></p><p><b>  1.1、硬件環(huán)境</b><

11、/p><p>  PC機一臺,內(nèi)存,2.0GHZ主頻</p><p><b>  1.2、軟件環(huán)境</b></p><p>  設計和實驗將Windows環(huán)境下,gcc和虛擬機軟件VMWare。 </p><p><b>  二、設計目的</b></p><p>  存儲管理的主

12、要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術。本設計的目的是通過請求頁式存儲管理中頁面置換算法模擬設計,了解虛擬存儲技術的特點,掌握請求頁式存儲管理的頁面置換算法。要求:</p><p>  (1)通過隨機數(shù)產(chǎn)生一個指令序列,共320條指令。指令的地址按下述原則生成:</p><p> ?、?0%的指令是順序執(zhí)行的;②25%的指令是均勻分布在前地址部分;③25%的指

13、令是均勻分布在后地址部分。</p><p>  具體的實施方法是:①在[0,319]的指令地址之間隨機選取一起點m;②順序執(zhí)行一條指令,即執(zhí)行地址為m+l的指令;③在前地址[0,m+1]中隨機選取一條指令并執(zhí)行,該指令的地址為m’;④順序執(zhí)行一條指令,其地址為m’+1;⑤在后地址[m’+2,319]中隨機選取一條指令并執(zhí)行;⑥重復上述步驟①~⑤,直到執(zhí)行320次指令。</p><p>  

14、(2)將指令序列變換成為頁地址流。設:①頁面大小為1K;②用戶內(nèi)存容量為4頁到32頁;③用戶虛存容量為32K。</p><p>  在用戶虛存中,按每頁存放10條指令排列虛存地址,即320條指令在虛存中的存放方式為:</p><p>  第0條~第9條指令為第0頁(對應虛存地址為[0,9]);</p><p>  第10條~第19條指令為第1頁(對應虛存地址為[10

15、,19]);</p><p><b>  … … … </b></p><p>  第310條~第319條指令為第31頁(對應虛存地址為[310,319])。</p><p>  按以上方式,用戶指令可組成32頁。</p><p>  (3)計算并輸出下述各種算法在不同內(nèi)存容量下的命中率(要為以下各種算法定義數(shù)據(jù)結構)。

16、</p><p> ?、傧冗M先出的算法(FIFO);</p><p> ?、谧罱钌偈褂盟惴?LRU);</p><p> ?、圩罱畈唤?jīng)常使用算法(NUR/NRU/CLOCK)。</p><p><b>  三、總體設計</b></p><p>  3.1、程序設計組成框圖</p>

17、<p><b>  程序設計組成框圖</b></p><p><b>  3.2、流程圖</b></p><p>  FIFO LRU</p><p><b>  Y</b></p><p><

18、;b>  Y</b></p><p><b>  Y</b></p><p><b>  N</b></p><p><b>  LRU算法</b></p><p><b>  NUR算法</b></p><p>

19、<b>  OPT算法</b></p><p><b>  四、詳細設計</b></p><p>  本程序設計基本按照題目的要求進行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列,然后將指令序列變成相應的頁地址流,并針對不同的算法計算出相應的命中率。</p><p><b>  4.1、數(shù)據(jù)結構&

20、lt;/b></p><p><b>  4.1.1頁面類型</b></p><p>  Typedef struct{</p><p>  Int pn,pfn,count,time;</p><p><b>  }pl_type;</b></p><p>  其中p

21、n為頁號,pfn為面號,count為個周期內(nèi)訪問該頁面次數(shù)time為訪問時間。</p><p>  4.1.2頁面控制結構</p><p>  pfc_struct{</p><p>  intpn,pfn;</p><p>  struct pfc_struct*next;</p><p><b>  

22、}</b></p><p>  typedefstruct pfc_struct pfc_type;</p><p>  pfc_typepfc[xy],*free_head,*busy_head;</p><p>  pfc_type*busy_tail;</p><p><b>  其中:</b>&

23、lt;/p><p>  pfc[xy]定義用戶進程虛頁控制結構,</p><p>  *free_head為空頁面頭的指針,</p><p>  *busy_head為忙頁面頭的指針,</p><p>  *busy_tail為忙頁面尾的指針。</p><p><b>  4.2.函數(shù)定義</b>&l

24、t;/p><p>  (1)void initialize():初始化函數(shù),給每個相關的頁面賦值。</p><p>  (2)void FIFO():計算使用FIFO算法時的命中率。</p><p>  (3)void LRU():計算使用LRU算法時的命中率。</p><p>  (4)void OPT():計算使用OPT算法時的命中率。<

25、;/p><p>  (5)void LFU():計算使用LFU算法時的命中率。</p><p>  (6)void NUR():計算使用NUR算法時的命中率。</p><p><b>  4.3.變量定義</b></p><p>  (1)int a[zllc];指令流數(shù)據(jù)組。</p><p>  (

26、2)int page[zllc];每條指令所屬頁號。</p><p>  (3)int offset[zllc];每頁裝入10條指令后取模運算頁號偏移值。</p><p>  (4)int pf:用戶進程的內(nèi)存頁面數(shù)。</p><p>  (5)int zhihuan:頁面失效次數(shù)。</p><p><b>  4.4.算法分析&l

27、t;/b></p><p>  先進先出算法,即FIFO算法(First-In First-Out algorithm)。這種算法選擇最先調入主存儲器的頁面作為被替換的頁面。它的優(yōu)點是比較容易實現(xiàn),能夠利用主儲存器中頁面調度情況的歷史信息,但是沒有反應程序的局部性。因為最先調入主存的頁面,很有可能是經(jīng)常使用的頁面。</p><p>  最近最少使用算法,即LFU(Least Freq

28、uently used algorithm)。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然這是一種非常合理的算法,因為到目前為止最少使用的頁面,和可能也是將來最少訪問的頁面。該算法即充分利用了主存中嗎調度的歷史信息,又正確反映了程序的局部性。但是這種算法實現(xiàn)起來非常的困難,它要為每個頁面設置一個很長的計數(shù)器,并且要選擇一個固定的時鐘為每個計數(shù)器定時計數(shù)。在選擇被替換頁面時,要從所有的計數(shù)器中選擇一個計數(shù)值最大的計數(shù)器。因此,通常

29、使用如下一種簡單的方法。</p><p>  最久沒有使用算法。即LRU(Least Recently Used Algorithm)。這種算法把近期最久沒有被訪問的頁面作為被替換的頁面。它把LFU算法中要記錄數(shù)量上的多與少簡化成判斷有于無,因此實現(xiàn)起來比較容易。</p><p>  NUR算法在需要淘汰一頁時,從哪些最近一個時期內(nèi)未被訪問的頁面中任選一頁淘汰。只要在頁面中增加一個訪問位即

30、可實現(xiàn)。當某頁被訪問時,訪問位置1.否則,訪問位置0.系統(tǒng)周期性第對所有的引用位清零。當須淘汰一頁時從那些訪問位為0 的頁中選擇一頁進行淘汰。如果引用位全為1或0,NRU算法退化為FIFO算法。</p><p>  最優(yōu)替換算法,即OPT(Optimal Replacement Algorithm).s上面介紹的幾種頁面替換算法主要是以主存儲器中頁面調度情況的歷史信息為依據(jù)的,它假設將來主存儲器中的頁面調度情況與

31、過去一段時間內(nèi)主存儲器中的頁面調度情況是相同的。當然這種假設不總是正確的。最好的算法是選擇將來醉酒不被訪問的頁面作為被替換的頁面,這種算法的命中率是最高的,它就是最有替換算法。要實現(xiàn)OPT算法,唯一的辦法就是讓程序先執(zhí)行一遍,記錄下實際的頁地址流情況。根據(jù)這個頁地址流才能找到藥被替換的頁面。顯然這樣做是不現(xiàn)實的。因此OPT算法只是一種理想化的算法,然而它也是一種很用的算法。實際上,經(jīng)常把這種算法作為評價其他頁面替換算法好壞的標準。在其他

32、條件相同的情況下,哪一種算法的命中率與OPT算法最接近,那么,它就是一種比較好的頁面替換算法。</p><p><b>  五、調試與測試</b></p><p><b>  5.1、調試方法</b></p><p>  利用Vware虛擬機的命令,用touch創(chuàng)建文件,vi 進入文件,然后編寫代碼,運行程序。</p

33、><p>  2、測試結果的分析與討論</p><p><b>  調試運行結果圖</b></p><p>  5.2、測試結果的分析與討論</p><p>  使用FIFO算法需要置換的頁面多,比較繁瑣,沒有優(yōu)化效果,所以FIFO算法性能不好。LRU的算法,此組數(shù)據(jù)顯示LRU的算法使用比較繁瑣,總的來說,NUR、LFU、L

34、RU算法介于FIFO和Optimial之間。通過系統(tǒng)模擬得出,optimal算法的性能高,LRU、NUR、LRU算法的性能次之,F(xiàn)IFO的算法性能最差,較少應用;由于optimal算法在實際上難于實現(xiàn),所以實際應用一般用LRU算法。</p><p>  六、設計中遇到的問題</p><p>  本次課程設計中我們遇到的問題是,一開始沒有弄清楚rand和sand函數(shù)的使用方法,以至于運行時的

35、到的結果與實際算起來的不相符,后來查閱資料,上網(wǎng)瀏覽搜索相關信息后,終于弄明白了是怎么回事。</p><p>  函數(shù)rand()是真正的隨機數(shù)生成器,而srand()會設置供rand()使用的隨機數(shù)種子。如果你在第一次調用rand()之前沒有調用srand(),那么系統(tǒng)會為你自動調用srand()。而使用同種子相同的數(shù)調用 srand()會導致相同的隨機數(shù)序列被生成。 </p><p>

36、  srand((unsigned)time(NULL))則使用系統(tǒng)定時/計數(shù)器的值做為隨機種子。每個種子對應一組根據(jù)算法預先生成的隨機數(shù),所以,在相同的平臺環(huán)境下,不同時間產(chǎn)生的隨機數(shù)會是不同的,相應的,若將srand(unsigned)time(NULL)改為srand(TP)(TP為任一常量),則無論何時運行、運行多少次得到的“隨機數(shù)”都會是一組固定的序列,因此srand生成的隨機數(shù)是偽隨機數(shù)。</p><p&

37、gt;  還有就是開始代碼編寫完了之后,運行時OPT算法結果出錯。這個問題是在我們討論并仔細查看OPT算法的內(nèi)容后修改的。</p><p><b>  七、源程序清單</b></p><p>  #include<stdlib.h></p><p>  #include<stdio.h></p><p

38、>  #include<time.h></p><p>  #define TRUE 1</p><p>  #define FALSE 0</p><p>  #define INVALID -1</p><p>  #define zllc 320 //指令流長</p><p>  #define

39、 xy 32 //虛頁長</p><p>  #define clear 50 //清零周期</p><p>  typedef struct //頁面結構</p><p><b>  {</b></p><p>  int pn;//頁號</p><p>  int pfn;//頁面框架號<

40、;/p><p>  int count; //計數(shù)器</p><p>  int time;//時間</p><p><b>  }pc;</b></p><p>  pc pl[xy];//頁面線性結構</p><p>  typedef struct pfc_struct//頁面控制結構,調度算法

41、的控制結構</p><p><b>  {</b></p><p><b>  int pn;</b></p><p><b>  int pfn;</b></p><p>  struct pfc_struct *next;</p><p>  }pf

42、c_type;</p><p>  pfc_type pfc[xy],*free_head,*busy_head,*busy_tail;</p><p>  int zhihuan,a[zllc];//a[] 為指令序列</p><p>  int page[zllc],offset[zllc];//地址信息</p><p>  int in

43、itialize(int);//初始化模塊</p><p>  int FIFO(int);//FIFO調度算法</p><p>  int LRU(int);//LRU調度算法</p><p>  int LFU(int);//LFU調度算法</p><p>  int NUR(int);//NUR調度算法</p><p

44、>  int OPT(int);//OPT調度算法</p><p><b>  /*主函數(shù)*/</b></p><p>  int main()</p><p><b>  {</b></p><p><b>  int s,i;</b></p><p

45、>  srand((unsigned)time(NULL));</p><p>  s = rand()%320;</p><p>  for(i=0;i<zllc;i += 4)</p><p><b>  {</b></p><p>  if(s<0||s>319)</p>&l

46、t;p><b>  {</b></p><p>  printf("When i == %d,Error,s==%d",i,s);</p><p><b>  exit(0);</b></p><p><b>  }</b></p><p><b

47、>  a[i] = s;</b></p><p>  a[i+1] = a[i]+1;</p><p>  a[i+2] = rand()%(a[i+1]+1);</p><p>  a[i+3] = a[i+2] + 1;</p><p>  s = rand()%(319-a[i+3]) +a[i+3]+1;</p

48、><p>  if(a[i+2]>318||s>319)</p><p><b>  {</b></p><p>  printf("a[%d+2],a number which is:%d and s == %d\n",i,a[i+2],s);</p><p><b>  }<

49、;/b></p><p><b>  }</b></p><p>  for(i=0;i<zllc;i++)//將指令序列變換為頁地址流</p><p><b>  {</b></p><p>  page[i] = a[i]/10;</p><p>  offs

50、et[i] = a[i]%10;</p><p><b>  }</b></p><p>  for(i=4;i<=32;i++)</p><p><b>  {</b></p><p>  printf("%2d page frames:\t",i);</p>

51、<p><b>  FIFO(i);</b></p><p><b>  LRU(i);</b></p><p><b>  LFU(i);</b></p><p><b>  NUR(i);</b></p><p><b>  O

52、PT(i);</b></p><p><b>  }</b></p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  /*初始化相關的數(shù)據(jù)結構,pf表示內(nèi)存的塊數(shù)*/</p><p>

53、;  int initialize(int pf)</p><p><b>  {</b></p><p><b>  int i;</b></p><p>  zhihuan = 0;</p><p>  for(i=0;i<xy;i++)</p><p><b

54、>  {</b></p><p>  pl[i].pn = i;</p><p>  pl[i].pfn = INVALID;//質頁面控制結構中的頁號,頁面為空</p><p>  pl[i].count = 0;//頁面控制結構中訪問次數(shù)</p><p>  pl[i].time = -1;//訪問時間</p>

55、;<p><b>  }</b></p><p>  for(i=0;i<pf-1;i++)//建立pfc[i-1]與pfc[i]之間的聯(lián)系</p><p><b>  {</b></p><p>  pfc[i].next = &pfc[i+1];</p><p>  

56、pfc[i].pfn = i;</p><p><b>  }</b></p><p>  pfc[pf-1].next = NULL;</p><p>  pfc[pf-1].pfn = pf-1;</p><p>  free_head = &pfc[0];//空頁面隊列的頭指針為pfc[0]</p&g

57、t;<p><b>  return 0;</b></p><p><b>  }</b></p><p>  /*先進先出算法,pf為用戶進程的內(nèi)存頁面數(shù)*/</p><p>  int FIFO(int pf)</p><p><b>  {</b></

58、p><p><b>  int i;</b></p><p>  pfc_type *p;//中間變量</p><p>  initialize(pf);//初始化數(shù)據(jù)結構</p><p>  busy_head = busy_tail = NULL;//忙頁面頭隊列,為隊列鏈接</p><p>  

59、for(i=0;i<zllc;i++)</p><p><b>  {</b></p><p>  if(pl[page[i]].pfn == INVALID)//頁面失效</p><p><b>  {</b></p><p>  zhihuan++;//失效次數(shù)</p>&l

60、t;p>  if(free_head == NULL)//無空閑頁面</p><p><b>  {</b></p><p>  p = busy_head->next;//保存忙頁面的下一個頁面</p><p>  pl[busy_head->pn].pfn = INVALID;//把這個頁面換出,更新它的數(shù)據(jù)成員</

61、p><p>  free_head = busy_head;//釋放忙頁面隊列的第一個頁面</p><p>  free_head->next = NULL;//表明此頁面是空的組后一面</p><p>  busy_head = p;//更新頁面的頭隊列指針</p><p><b>  }</b></p>

62、<p>  p = free_head->next;</p><p>  free_head->pn = page[i];</p><p>  pl[page[i]].pfn = free_head->pfn;</p><p>  free_head->next = NULL;//使busy的尾為空</p><

63、;p>  if(busy_tail == NULL)</p><p><b>  {</b></p><p>  busy_tail = busy_head = free_head;</p><p><b>  }</b></p><p><b>  else</b>&l

64、t;/p><p><b>  {</b></p><p>  //把剛剛換進來的接在busy_tail的后面</p><p>  busy_tail->next = free_head;</p><p>  busy_tail = free_head;</p><p><b>  }&

65、lt;/b></p><p>  free_head = p;//下一個空頁面</p><p><b>  }</b></p><p><b>  }</b></p><p>  printf("FIFO:%6.4f|",1-(float)zhihuan/320);<

66、;/p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  /*最近最久未使用算法*/</p><p>  int LRU(int pf)</p><p><b>  {</b></p>

67、<p>  int min,minj,i,j,present_time;//minj為最小值下標</p><p>  initialize(pf);</p><p>  present_time=0;</p><p>  for(i=0;i<zllc;i++)</p><p><b>  {</b><

68、;/p><p>  if(pl[page[i]].pfn == INVALID)//頁面失效</p><p><b>  {</b></p><p>  zhihuan++;</p><p>  if(free_head == NULL)//無空閑頁面</p><p><b>  {<

69、/b></p><p>  min = 32767;//設置最大值</p><p>  for(j=0;j<xy;j++)//找出time最下值</p><p><b>  {</b></p><p>  if(min>pl[j].time&&pl[j].pfn!=INVALID)<

70、;/p><p><b>  {</b></p><p>  min = pl[j].time;</p><p><b>  minj = j;</b></p><p><b>  }</b></p><p><b>  }</b><

71、;/p><p>  free_head = &pfc[pl[minj].pfn];//騰出一個單元</p><p>  pl[minj].pfn = INVALID;</p><p>  pl[minj].time = 0;</p><p>  free_head->next= NULL;</p><p>&

72、lt;b>  }</b></p><p>  pl[page[i]].pfn = free_head->pfn;//有空閑頁面改為有效</p><p>  pl[page[i]].time =present_time;</p><p>  free_head = free_head->next;//減少一個free頁面</p>

73、;<p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b></p><p>  pl[page[i]].time = present_time;//命中則增加該頁面的訪問次數(shù)</p><p><b&

74、gt;  }</b></p><p>  present_time++;</p><p><b>  }</b></p><p>  printf("LRU:%6.4f|",1-(float)zhihuan/320);</p><p><b>  return 0;</b

75、></p><p><b>  }</b></p><p>  /*最近未使用算法*/</p><p>  int NUR(int pf)</p><p><b>  {</b></p><p>  int i,j,dp,cont_flag,old_dp;//這個算法用

76、count用于訪問位</p><p>  initialize(pf);</p><p><b>  dp = 0;</b></p><p>  for(i=0;i<zllc;i++)</p><p><b>  {</b></p><p>  if(pl[page[i

77、]].pfn == INVALID)//頁面失效</p><p><b>  {</b></p><p>  zhihuan++;</p><p>  if(free_head == NULL)//無空閑頁</p><p><b>  {</b></p><p>  cont

78、_flag = TRUE;</p><p>  old_dp = dp;</p><p>  while(cont_flag)//找到一訪問位count為0的頁面</p><p><b>  {</b></p><p>  if(pl[dp].count == 0 && pl[dp].pfn != INV

79、ALID)</p><p><b>  {</b></p><p>  cont_flag = FALSE;</p><p><b>  }</b></p><p>  else//下一個頁面</p><p><b>  {</b></p>

80、<p>  pl[dp].count = 0;</p><p><b>  dp++;</b></p><p>  if(dp==xy)//32個頁面找一遍,開始新的循環(huán)</p><p><b>  dp=0;</b></p><p><b>  }</b><

81、/p><p><b>  }</b></p><p>  free_head = &pfc[pl[dp].pfn];</p><p>  pl[dp].pfn = INVALID;</p><p>  free_head->next = NULL;</p><p><b>  

82、}</b></p><p>  pl[page[i]].pfn = free_head->pfn;</p><p>  pl[page[i]].count = 1;</p><p>  free_head->pn = page[i];</p><p>  free_head = free_head->next;&

83、lt;/p><p><b>  }</b></p><p><b>  else</b></p><p><b>  {</b></p><p>  pl[page[i]].count = 1;</p><p><b>  }</b>&

84、lt;/p><p>  if(i%clear == 0)</p><p>  for(j=0;j<xy;j++)</p><p>  pl[j].count = 0;</p><p><b>  }</b></p><p>  printf("NUR:%6.4f|",1-(

85、float)zhihuan/320);</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  /*最少訪問頁面算法*/</p><p>  int LFU(int pf)</p><p><b>  {&

86、lt;/b></p><p>  int i,j,min,minpage;</p><p>  initialize(pf);</p><p>  for(i=0;i<zllc;i++)</p><p><b>  {</b></p><p>  if(pl[page[i]].pfn

87、== INVALID)//頁面失效</p><p><b>  {</b></p><p>  zhihuan++;</p><p>  if(free_head == NULL)//無空閑頁面</p><p><b>  {</b></p><p>  min = 3276

88、7;//獲取count的使用頻率最小的內(nèi)存</p><p>  for(j=0;j<xy;j++)</p><p><b>  {</b></p><p>  if(min>pl[j].count&&pl[j].pfn!=INVALID)</p><p><b>  {</b&

89、gt;</p><p>  min = pl[j].count;</p><p>  minpage=j;</p><p><b>  }</b></p><p><b>  }</b></p><p>  free_head = &pfc[pl[minpage].p

90、fn];</p><p>  pl[minpage].pfn = INVALID;</p><p>  pl[minpage].count=0;</p><p>  free_head->next=NULL;</p><p><b>  }</b></p><p>  pl[page[i]]

91、.pfn = free_head->pfn;</p><p>  pl[page[i]].count++;</p><p>  free_head = free_head->next;//減少一個free頁面</p><p><b>  }</b></p><p><b>  else</b&

92、gt;</p><p><b>  {</b></p><p>  pl[page[i]].count = pl[page[i]].count+1;</p><p><b>  }</b></p><p><b>  }</b></p><p>  pr

93、intf("LFU:%6.4f",1-(float)zhihuan/320);</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  /*最佳置換算法*/</p><p>  int OPT(int pf)</

94、p><p><b>  {</b></p><p>  int i,j,k,l,max,maxpage;</p><p>  initialize(pf);</p><p>  for(i = 0; i < zllc; i++)</p><p><b>  {</b><

95、;/p><p>  if(pl[page[i]].pfn == INVALID)//頁面失效</p><p><b>  { </b></p><p>  zhihuan++;</p><p>  max = maxpage = 0;</p><p>  if(free_head == NULL)

96、//無頁面空閑</p><p><b>  {</b></p><p>  for(j = 0; j < pf; j++)</p><p><b>  {</b></p><p><b>  l = 1;</b></p><p>  for(k =

97、 i + 1; k < zllc; k++)</p><p><b>  {</b></p><p>  if(pfc[j].pn == page[k])</p><p><b>  {</b></p><p>  if(max < l)</p><p><

98、b>  {</b></p><p><b>  max = l;</b></p><p>  maxpage = j;</p><p><b>  }</b></p><p><b>  break;</b></p><p><b

99、>  }</b></p><p><b>  l++;</b></p><p><b>  }</b></p><p>  if(k == 320)</p><p>  maxpage = j;</p><p><b>  }</b>&

100、lt;/p><p>  free_head = &pfc[maxpage];</p><p>  free_head->next = NULL;</p><p>  pl[pfc[maxpage].pn].pfn = INVALID;</p><p><b>  }</b></p><p&g

101、t;  pl[page[i]].pfn = free_head->pfn;</p><p>  free_head->pn = pl[page[i]].pn ;</p><p>  free_head = free_head->next ;</p><p><b>  }</b></p><p><

102、;b>  }</b></p><p>  printf("OPT:%6.4f\n",1-(float)zhihuan/320);</p><p><b>  return 0;</b></p><p><b>  }</b></p><p>  八、總結,收獲

103、與體會</p><p>  在本次操作系統(tǒng)課程設計,我采用C實現(xiàn)請求頁式管理缺頁中段模擬設計的隨機和LRU淘汰算法。首先,應了解虛擬存儲器和頁式存儲管理的有關內(nèi)容,并掌握隨機和LRU淘汰算法的核心思想及具體的流程。然后,在這個基礎上,結合所掌握的C編程方法和技巧,編寫正確的算法。</p><p>  隨機淘汰算法比較容易實現(xiàn),當需要調入一個新頁面進入內(nèi)存時,用rand()函數(shù)產(chǎn)生的隨機數(shù),

104、作為將要被淘汰的內(nèi)存物理塊號,然后修改頁表內(nèi)容即可。LRU算法就顯得復雜一些,其核心問題在于怎樣找到內(nèi)存中最近最少使用的那個頁面。 最初設計這個算法時,出現(xiàn)了一點問題,在某種情況下,會淘汰剛剛被訪問過的頁面。經(jīng)過修改,彌補了這個不足之處,算法的運行結果正確。 </p><p>  從這次的課程設計中,我有很大收獲。首先,鞏固了所學的有關頁式存儲管理的相關知識,更深層次地理解并掌握了LRU和隨機淘汰算法的

105、精髓。通過使用C語言模擬LRU和隨機算法實現(xiàn)請求頁式管理,進一步提高了我的編程能力,并且有助于將操作系統(tǒng)和C有機地結合起來,使我更加明白了學科之間是緊密聯(lián)系的。 此外,經(jīng)過這次課程設計,我更加感悟到了,僅僅學習書本上的理論知識是不夠的,要在平時多進行實際操作,這樣才能融會貫通,更加牢固地掌握所學知識。在以后的學習過程中,我應該更加深入學習有關C的內(nèi)容,提高自己的動手能力。</p><p><b>  九

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論