操作系統(tǒng)課程設計lru面置換算法

1、操作系統(tǒng)功能模擬設計實驗題 目:lru置換算法（C編寫）學生：計號學號：1104032022專業(yè)：網(wǎng)絡工程班級：11網(wǎng)絡工程二班實驗題目LRU頁面調(diào)度算法處理缺頁中斷一、實驗目的：了解和掌握寄存器分配和存分配的有關(guān)技術(shù)二、實驗容（1）首先對LRU頁面調(diào)度算法原理進行深刻的理解和掌握；（2）選擇一種熟悉的編程語言來實現(xiàn)對一組訪問序列進行部的cache更新；（3）根據(jù)LRU頁面調(diào)度算法算法的要求設計相應的數(shù)據(jù)結(jié)構(gòu)，如：記錄訪問序列的數(shù)組、 模擬存cache的數(shù)組等等；（4）顯示每個訪問數(shù)進入cache的操作并顯示出每次訪問后存中序列的狀態(tài)。三、實驗環(huán)境Windows系統(tǒng)，c語言四、實驗主要步驟（包

2、括使用的數(shù)據(jù)結(jié)構(gòu)的說明）1、初始化及使用數(shù)據(jù)結(jié)構(gòu)開始的階段，產(chǎn)生隨機的訪問序列，并用了結(jié)構(gòu)體：struct pageint pageframe10: / 表示頁表int flag；/標記是否有頁面置換int length；/用來訪問序列的長度int page_count；頁框的數(shù)目int page serial 20 ；/存取隨機產(chǎn)生的訪問序列組int count；/用來標識頁框是否被裝滿int k；/用于記錄訪問頁表的指針int pagetimeElO；/用來記錄頁框里面的數(shù)被訪問的過后到再一次被訪問所經(jīng)歷的的時間p；并初始化這些量；void init（） /初始化所有頁表int i:p.

3、flag=0；for （i=0；i10；i+）p. pageframei=-l:p. pag etime HO；）for （i=0；i20；i+）p.page seriali=-l；2、LRU頁面調(diào)度算法原理LRU頁面調(diào)度算法是對要訪問cache的訪問序列進行更新的，當頁表還是空的時候， 進來要訪問的頁如果頁表里面有的話，就對它的訪問記錄加一，如果也表里面沒有切頁 表么有填滿，就像頁表里面添加。如果在頁表填滿以后，再一次有也要訪問的時候，在 判斷頁表里面有沒有要訪問的頁，如果沒有則看頁表里面的的序列哪一個頁是最近最長 時間都沒有被訪問的，就將此頁給替換程現(xiàn)在要訪問的頁。3、創(chuàng)建訪問的序列和頁框

4、void create()int i,s；printf(Bn請輸入頁框數(shù)目：n)；scanf(%d，&p. page_count)；printf(n請輸入要隨機生成訪問序列的長度:n)；/自定義隨機生成訪問序列的長度scanf(%d，&p. length)；srand(randO)；/初始化隨機數(shù)隊列的種子s=(float) rand() / 32767) * 50 + p. length： / 隨機產(chǎn)生頁面序列長度for(i=0；is；i+) 產(chǎn)生隨機訪問序列p. page seriali = (float) rand() / 32767) * 16 ； /隨機數(shù)的大小在 OTO 之間pri

5、ntf(nnnn)；printf (” : nn)；for (i=0； ip. length； i+)printf(%d ,p.page seriali);printf(Bnnnn)；printf (T*r)；printf(nnn)；4、在cache中查找要訪問的頁int f indpage(int kt int count) /在這里k用于接收從lru函數(shù)傳來的訪問序 列的數(shù)值int m=k；int n=count；int i;int j； 用來做標記for(i二0；i=0)p.pagetimei+；if(p pageframei=m)p.pagetimei-；j=l;elseif(i=p.

6、 page_count)j=0；if(j=l)if(p count=p. page count-1)p. flag3；return -3；在這里表示頁框里有要訪問的頁，但是頁框沒有填滿，不需要置換所以返回-3elsep. flag=-l； /表示在此時也表里有要訪問的頁，但是此時頁表也 滿了，但是也不缺頁，所以用flag來表示不缺頁return T；else if(p count=p pagecount-l)p. flag=O；return 0；在這里表示沒有訪問到頁表里面的頁，但是頁表沒有別填滿，但不需要置換所以返回0elsep. flag=-2；/在這里p. flag=-2表示沒有訪問到頁

7、表，且頁框需要被置換所以返回-2return -2；)六、顯示存中的序列void displayinfoO int n；printf (n訪問3d :存tp. page serial t):for (n=0； n二0)printf (rT%3d，p. pageframetn)；elseprintf(n ”)；)printf(n ”)；if (p. flag=-2| |p. flag=0)/p. flag=-1表示也表里面有訪問的頁，但是頁框沒有滿，p. flag=-2表示頁表里面沒有要訪問的頁，但是頁框也被填滿了printf (=缺頁)；printf (nnn)；七.此實驗的執(zhí)行程序圖五. 設

8、計不同實驗數(shù)據(jù)，記錄實驗結(jié)果并分析。 P學習爆作袞艇序沒i+mbugLRU.r旦J旦操作系統(tǒng)實驗一 姓名：計號班級li網(wǎng)工二班學號.1104032022 請輸人頁框數(shù)目：請輸入要隨機生成訪問序刃的長度:IM H 2 2 4 2 5 15 3 15頁頁頁頁頁頁頁 h.shshxn. hxhshv 4U4H-4U 4U 4H-L4U4U O0R1220151515continue缺予冰俗* 5022425 5 35 A1 1 1s 回口 一口 m問問m回口一口. x srn訪訪B亠呢 yri:J訪pr-O學習嚴作丟烷程序沒計gbugLRU心丨=丨回|六、實驗總結(jié)及體會通過這次的實驗，我對LRU頁面

9、置換算法有了更深的了解，LRU置換算法是理想性的 算法，因為使用LRU置換算法要花費很大的系統(tǒng)開銷，所以在實際系統(tǒng)中并不會直接采 用.通過這個LRU頁面缺頁調(diào)度算法的設計，我覺得對這個算法的原理理解的更加的深刻, 雖然在設計的過程中也遇到了很多問題，例如怎么去判定存cache中的每個數(shù)在訪問后 怎么去標記他的時間問題，還有怎樣去表示開始時的存cache中的頁表沒有被填滿的缺 頁和頁表被填滿時候的缺頁狀態(tài)。七、源程序清單及注釋。(打印一份源程序并附上注釋。)#include#includeint t；struct pageint pageframe10 ； / 表示頁表int vpage；int

10、 flag:/標記是否有頁面置換int length；/用來訪問序列的長度int page count；/頁框的數(shù)目int page serial 20:/存取隨機產(chǎn)生的訪問序列組int count；用來標識頁框是否被裝滿int k；用于記錄訪問頁表的指針int pagetimeElO；/用來記錄頁框里面的數(shù)被訪問的過后到再一次被訪問所經(jīng)歷的的時間p;void init() /初始化所有頁表int i:p. f lag二0；for(i=0;i10：i+)p. pageframei二T;p. pagetimei=0；for(i=0；i20；i+)p. page seriali=-l;void c

11、reate()int i,s；printf(n請輸入頁框數(shù)目：n)；scanf (w%d* &p. page count)；printf(Bn請輸入要隨機生成訪問序列的長度:n)； 自定義隨機生成訪問序 列的長度scanf (w%d*.&p. length):srand(randO)；初始化隨機數(shù)隊列的”種子s=(float) rand() / 32767) * 50 + p. length； / 隨機產(chǎn)生頁面序列長度for(i=0:is；i+)產(chǎn)生隨機訪問序列p. page seriali = (float) rand() / 32767) * 16 ； /隨機數(shù)的大小在 OTO 之間pr

12、i nt f(wnnnnH;printf C: nM)；for(i=0；ip. length；i+)printf(M%d ,p.page seriali):printf(wnnnnH);printf (,rMe*H)；printf (wnnn,T)； int findpage(int k, int count) /在這里k用于接收從Ini函數(shù)傳來的訪問序列的 數(shù)值int m=k；int n=count；int i;int j; /用來做標記for(i-0；i=0)p.pagetimei+；if(p. pageframei=-m)p.paget；j=l；elseif(i=p. page coun

13、t)j=0；if(j=l)if (p. count=p. page count-1)p. flag=-3；return -3；柱這里表示頁框里有要訪問的頁但是頁框沒有填滿，不需要置換所以返回-3elsep. flag=-l；表示在此時也表里有要訪問的頁，但是此時頁表也滿了，但是也不缺頁，所以用flag來表示不缺頁return 1:elseif(p. count-p. page count-1)p. flag=0；return 0；在這里表示沒有訪問到頁表里面的頁，但是頁表沒有別填滿，但不需要置換所以返回0)elsep. fbg=-2；/在這里p. flag-2表示沒有訪問到頁表且頁框需要被置換

14、所以返回-2return -2； )void displayinfoO int n；printf (w訪問3d :存,p. page serial t):for(n-0；np. page count；n+) / 頁框信息if (p.pageframen 二0) printf C*%3dMtp pageframen)；elseprintf(”)；printf( )；if (p. flag=-2 p. flag=0)/p. flag=-1表示也表里面有訪問的頁，但是頁框沒有滿，p. flag=-2表示頁表里面沒有要訪問的頁，但是頁框也被填滿了printf(M =缺頁);printf (wnH)；

15、void lru() int time二0；int m；/用于接收findpage返回的標int count 1=0； 這個只是用來記錄缺頁的次數(shù) p. k=0；ini t ()；create ();p. count-0；for(t=0;tp. length：t+)m=findpage(p page serialt,p count)；if (p. count=p. page count-1) / 開始時不計算缺頁if(m=0)/頁不存在則裝入頁面p. pageframeEp. k=p. pageserial t；/把要調(diào)入的頁面放入一個空的頁框里/printf (M%d，,p pageframep k)；p. k二(p k+1) % p. page_count；p.count+；else /正常缺頁置換if(m=-2)/頁不存在則置換頁面for(i-0；ip pagetimetime)time；p. k=time；p.pagetimep k=0；p. pageframeEp k二p page serial t；/pk=(pk+l) % p. page_count；/count 1+；缺頁次數(shù)加一次displayinfoO ;/顯示當前頁框里面