請求頁式管理的頁面置換算法

1、實(shí) 驗(yàn) 報(bào) 告課程：操作系統(tǒng)班級：姓名：學(xué)號成績：指導(dǎo)教師：實(shí)驗(yàn)日期：實(shí)驗(yàn)密級：預(yù)習(xí)程度：實(shí)驗(yàn)時(shí)間：儀器組次：必修/選修：實(shí)驗(yàn)序號：實(shí)驗(yàn)名稱：訪問實(shí)驗(yàn)二 請求頁式管理中的置換算法實(shí)驗(yàn)?zāi)康呐c要求：1 .采用FIFO （先進(jìn)先出）置換算法，發(fā)生缺頁中斷時(shí)，給出相應(yīng)的字地址及頁號， 計(jì)算缺頁中斷率。2 .采用LFU （最不經(jīng)常使用）置換算法，發(fā)生缺頁中斷時(shí)，給出相應(yīng)的字地址及頁號， 計(jì)算缺頁中斷率。實(shí)驗(yàn)儀器:名稱型號數(shù)量微機(jī)1一、實(shí)驗(yàn)內(nèi)容1 .假設(shè)有一個(gè)用戶進(jìn)程P的地址空間為n （n=60）頁，系統(tǒng)已在內(nèi)存中給 該進(jìn)程分配有 m （m<n m=8個(gè)頁面，且該進(jìn)程的第 0、5、6頁（p0、p5、

2、p6） 已經(jīng)裝入內(nèi)存，頁長為1K。 根據(jù)進(jìn)程訪問的字地址序列，采用不同的置換算法，分別計(jì)算缺頁中斷率。2 .進(jìn)程依次要訪問的字地址序列 （訪問申），在01024*n-1 （061439）中模擬隨機(jī)發(fā)生，訪問序列的隨機(jī)生成規(guī)則為：50%的字地址前向順序增長，25%的字地址均勻分布在前地址（低地址）部分，25%的字地址均勻分布在后地址（高地址） 部分， 為了減少模擬次數(shù)，前向順序遞增產(chǎn)生的字地址如小于1024*n-513（60927）則自動加512。模擬訪問用長度為100。以n=60為例，字地址序列（訪 問串）的隨機(jī)生成方法如下：（ 1）在 0 ， 61439之間隨機(jī)產(chǎn)生起始字地址，當(dāng)前訪問的字地

3、址記為k；（ 2）前向順序遞增產(chǎn)生的字地址為k+1+512；（ 3）前地址（低地址）在0 ， k-1 內(nèi)隨機(jī)產(chǎn)生；（ 4）后地址（高地址）在k+1 ， 61439內(nèi)隨機(jī)產(chǎn)生；（ 5）重復(fù)順序遞增、前地址區(qū)間隨機(jī)產(chǎn)生、后地址區(qū)間隨機(jī)產(chǎn)生的過程，概率分別為：50%、 25%、 25%。二、實(shí)驗(yàn)要求1 .采用FIFO （先進(jìn)先出）置換算法，發(fā)生缺頁中斷時(shí)，給出相應(yīng)的字地址 及頁號，計(jì)算缺頁中斷率。2 .采用LFU （最不經(jīng)常使用）置換算法，發(fā)生缺頁中斷時(shí)，給出相應(yīng)的字 地址及頁號，計(jì)算缺頁中斷率。三、實(shí)驗(yàn)思路首先應(yīng)該確認(rèn)全局變量，比如：物理塊大小、進(jìn)程數(shù)量；建立一個(gè)結(jié)構(gòu)體用于記錄頁面號和頁面調(diào)度次數(shù)

4、，并定義好所要使用的變量，如記錄調(diào)入頁面的序號隊(duì)列queuepsize>初始化情況下已經(jīng)分配的頁面數(shù) rearp、在查找時(shí)是否有相 同頁面flag （初值為1表示沒有）、在LFU中最先進(jìn)去的頁面號frontlea。隨機(jī)數(shù)產(chǎn)生序列函數(shù)：此函數(shù)比較簡單，按照要求寫出即可。首先隨機(jī)產(chǎn)生存儲塊號，并將其列入調(diào)入頁面序號隊(duì)列，然后用另一個(gè)隨機(jī)變量suiji,保證重復(fù)順序遞增、前地址區(qū)間隨機(jī)產(chǎn)生、后地址區(qū)間隨機(jī)產(chǎn)生的概率是50%、 25%、25%，有下面是具體實(shí)現(xiàn)部分。void Build() /產(chǎn)生頁面調(diào)度的頁面隨機(jī)序列 int i=0;int suiji;int k; /表示隨機(jī)出來的存儲塊號p

5、rintf(" 產(chǎn)生頁面調(diào)度的頁面隨機(jī)序列:n");srand(time(NULL);k=rand()%(61440);yi+=k; dosuiji=rand()%4+1;switch(suiji) case 1:case 2:if(k<61440 - 513)yi+=(k+1+512);k=k+1+512;break;case 3:k=rand()%k;yi+=k;break;case 4:k=rand()%(61439 - k) + k;yi+=k;break;default:break;while(i<100);for(i=0; i<100; i+)

6、printf("%2d ",yi/1024);if(i%6=5)printf("n");printf("n");FIFO 算法：在 FIFO 算法中存在三種情況，分別為：存在相同的進(jìn)程、不存在相同的進(jìn)程但是存在空閑物理塊、不存在相同的進(jìn)程并且不存在空閑物理塊。根據(jù)這三種情況編寫FIFO 函數(shù)，并且在這些情況中，還需要使用到查找空閑物理塊的子函數(shù)，在不存在相同的進(jìn)程并且不存在空閑物理塊的情況時(shí)即為發(fā)生缺頁中斷。( 1)查找空閑物理塊函數(shù)：int searchpb()/鷹找空閑物理塊，成功返回值是物理塊號，否則就是-1int j,m;fo

7、r(j=0; j<Blocksize; j+)if(Blockj.num = -1)m = j;return m; break;return -1;( 2) FIFO 函數(shù)(省略在程序中)；( 3) 缺頁中斷率的計(jì)算：根據(jù)公式缺頁中斷率=缺頁次數(shù)/調(diào)用程序次數(shù)，即可得出缺頁中斷率。LFU 思路：最不經(jīng)常使用頁面淘汰算法LFU( least frequently used) 。該算法在需要淘汰某一頁時(shí)，首先淘汰到當(dāng)前時(shí)間為止，被訪問次數(shù)最少的那一頁。這只要在頁表中給每一頁增設(shè)一個(gè)訪問計(jì)數(shù)器即可實(shí)現(xiàn)。每當(dāng)該頁被訪問時(shí)，訪問計(jì)數(shù)器加1，而發(fā)生一次缺頁中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁，并將所有的

8、計(jì)數(shù)器清零。在此函數(shù)執(zhí)行過程中，還需要調(diào)用查找計(jì)數(shù)值最小頁面的函數(shù)、計(jì)數(shù)器清零函數(shù)。( 1)查找計(jì)數(shù)值最小頁面的函數(shù)：int searchleast() /查找計(jì)數(shù)值最小的頁面，返回其頁號int k;int least;least=frontlea;for(k=0;k<Blocksize;k+)if(Blockk.count < Blockleast.count)least=k; return least;( 2)計(jì)數(shù)器清零函數(shù)：void empty()int i;for(i=0;i<Blocksize;i+) Blocki.count=0;/計(jì)數(shù)器置零( 3) LFU 函數(shù)

9、：省略在程序中( 4) 缺頁中斷率的計(jì)算：根據(jù)公式缺頁中斷率=缺頁次數(shù)/調(diào)用程序次數(shù)，即可得出缺頁中斷率。程序流程圖先進(jìn)先出結(jié)構(gòu)最不經(jīng)常使用結(jié)構(gòu)五、運(yùn)行結(jié)果截圖1、隨即地址生成下:“ tudy操作系統(tǒng)實(shí)里20122、FIFIO 算法F:studyV吳作系統(tǒng)供驗(yàn)201243104 ° F:study便作系驗(yàn)2012437 7?2 2 26 6 65 5 501407 y 12 3 35 6 2?53 5 G 27 3U10 1845521101213121313200 Q10141616164141424646272827 30 30 31 31 48 48 49 49 53 49 S

10、3 53 54 54 1018 10 18 10 18 10 1R 18 £ 18 45 18 45 18 45 18 45 45 52 52 1I 0 1 U1 0 0 12 0 1212 13 13 20 13 20 20 10 10 1431 4848 494? S353 5454 1054 1010 1818 4545 5245 5245 524S 5252 152 152 152 152 1i a0 1212 1312 1312 1313 2013 2。20 1010 14 工匕1414 1616 413s30 31 30 3131 31 48 31 48 31 48 48

11、 49 48 49 49 53 49 53 53 54 54 1U 10 18 18 45 1R 45 45 52 52 11 0 1 01 0 1 00 12 0 12S 12 0 12 0 1212 13 13 2020 10 2s 10 20 10 10 14 1R 1414 1G 16 41 16 41 41 42 42 4622 4134 4235 4635 4636 2?42 46 2746 2? 2027 28 027 28 028 0 2128 0 21 220 21 22 344848 4949 534? 534，5353 5453 5454 in54 1010 1818 4

12、545 5252 152 11 00 1212 1312 1312 1312 1313 2013 2013 2U13 2013 20 2。1010 1414 1614 1614 1616 411& 4141 4242 4642 4646 2727 2821 22 34 3521 22 34 3522 34 35 3634 35 36 42430212234430212234b2122343b6 22 34 35 36 426 22 34 35 36 423G 42 4336 42 4342 43 543 5 643 5 62 27S6 1 256 2 2731 27 2818 28 2

13、y48 29 5243 55 66 77 227 2222 1313 1413 1414 00 11 21 22 272? 2828 296 77 2222 1313 1414 1414 00 1 。11 22 2727 2827 2628 2929 5227 2fi 2929 29 5229 52 5352 53 5653 56 5852 S3 S653 5G 5856 58 3158 31 1831 18 4831 18 48 4931 18 48 4918 48 49 5U18 48 49 5048 49 SB 51231184849318484y5B948495051749505110

14、175051102* ' F：5rudy2O12431(降？ ) -Debug2.3、LFU* 丫：文郎浜2。124引。-甥程（實(shí)置？）二。曲叫乙,，-m算法270 0:10 E盾 C! Q 2?l300 G；10 58 6： 0 271e 30;031U U；1 M bU b： HZ*M 3M：H JI瑞A RI1 R SA G： E) 2?fl 30!n 3iR 4A! W4900!10 G盾 ©： O 2?lQ M0 31Q 40：3 49 ：S3a S3;1 B 5g 6： 0 271e 3。i0 31B 48：3 49 ： 30539知1 Q 5H 6： 0 2?l

15、6皿;0 31Q 4S： 3 49 ： E)E2001 B GU C ： B 27 15詢Q 31B 4fl! R 49： 3R54I日i 0 mi e ci a a?iS 30 I0 311 B 4SI 3 49 I IQ54a 53 iB 548 6；0 271 30；0 31B 48：3 4f； 30108卬1 Q 54B IQ! Q 271e 30!a 31B 4SI 3 4f： 3Qm01 B U4a IB ： B 271fl 2BIa 21B 4S! R 49! ?Risi a S3 ii & 54118 IB I Q IB 1S 3010 311 B 4BI 3 4fI-

16、Kia 5310 54B 1U： M ISK 4b 1也31U 4S： U 4f； 30528 S1 B 540 IB! 0 18fi 45 1a 52B 431 0 4f： 3Q1sB S4Q1 口"e 4518 52Q 1:3 49：1i a i! 8 541i e igi 0 isie 45iB 521 B ±1 a 4fI 30uU 531附549 IB： W IBM 4b 10 52Ml： » B： 3B12a is0 54e IB： B IBe 45& 52B 1； 3 B： 3Q13a is：Q 138 IB： Q IB6 45S 1!3 B

17、： 3Q1Za 1216 130 IB： a ISS 450 52b 1； a e: 3013U 12! 0 130 IB： B 18的4b：0 52時(shí) 1； 博 et 3B13R 1 7i 0 iaR IQ! n 1RR 4E8版F) 1! H 6： 3QF:study皆作系統(tǒng)供秘20124310-翔程（實(shí)險(xiǎn)2 ）供藥二Debug實(shí)驗(yàn)2.20；012 ；0130 20；018 ：0 45：! &52 1：0111 00；301!812：0130 20：018：0 451! 052!：0111 00：30R：n12:013R 20：018：0 45：! 0S2I! 011：3R!3R0

18、1012 1013 10 26 1010 1e 4CII 0C2 11 0111 901300；012 :0130 20；018 Je 45ii 052 i：011：00：301U：V12：913H 2Id：9IS；U 4b! 9b2：S11：匕t)：3914!812：0130 20：010：0 14：! 0521：0111 08：3016!012 !0138 20!010!e 141! 01& !1 01!1 00;3016 1012 1013 10 2010101e i4i1 016 11 0111 08130±O 1a12 ；9139 2M；91U：S 14：Ulb01

19、100；30AA 1 TJ. 1Q12：0130 20；010：0 14：016041!00：30AA 1 f .1 012 !013R 20：010:a 141n041!00:3042 1012 J013 10 201010!e i4ii 016 11 04111 042 130i846 ；0130 20；010：e 14：816041042 S30AC 1 勺。I046；0130 20：010：0 14：016041042!3027 Sn46 ：A27R 20：A10：A 141016fl41042 ：3028:046 !0270 2S!010!6 14101&041042 !30

20、0；846 ；0270 28；00：0 14：016041042 S3021：u46：9279 28；99；8 21：(J16S41kJ42 ；3922：046：027Q 28：00：0 211022041042 !3022!046 !0278 2S!00!6 211022041042 :30341046 102718 28 1001e 2111 022 11 03411 042 1303b；46 I027U 28；90；S Zl：U22 ：S341035 ：3035：046 !0278 28!00!0 211022 10341035 !3036：Q36 :偽270 28!00：R 211R2

21、2 10241035 !3R ' F:study讀作系統(tǒng)供的20124310-會程（實(shí)驗(yàn)2 ）慳苑二Debug實(shí)瞼2.- ' F:study讀作系統(tǒng)壯血20124310-翔程（實(shí)臉2）供藥二Debug實(shí)驗(yàn)2.- c IX> < < JJL i053 ；056 i058；031 1i e27；028 502911 052 :30A4 Q 1 ±O I853：056!058：031 I e18：028：02911 052：30AC) 1 HO in53!0561fl58:031 11 018:048：。291：352:3R40 10CO 105G I0C

22、O 1031 1i e10 1040 1029 11 952 130 i053 ：056 ；058；031 ：i e18：048 50491：052 S30AU 1T7 1VS3 !956 !958；931 ； k)18：948：S49：匕52 :39匚。OU 1853：056；058：031 1 e18：048：049!1 050：3050!053 :056 !65S!031 !i e18:048 :04911 050:3051 ：051 1056 1058 101 1i e181048 104911 0501301U；a51 ；9W：958；9311 M18；a48 5S4y050；302

23、：Q51：010!g2：031I 018：048：049050：303!051 !010!e2!03i a18:048 !049050:3091051 1010102!03 1i e91048 !04911 058!307；851 ：010；02：03 1e9；87；e49050；3017：051：010：02：03109；07:017058：305：n51 JA10：R2：A3 1e9：07：01705 :302;051 !010!02：03 169:07!01705 :301 ；81:010；02；03 1e9：07；01705 ：309：u1 ：9(J!92：93； M9;U7:w17k

24、Jb：390：01:00：02;0311 09：07：01705：300;01 !00!82!03 11 69:07:01705 ;301 ；01 100102103 1i e9107101711 05 130U：1 ；00：02；93 1y ；97;91705 ；3021 !01 ;00!021 :03 109:07!01705 !3022 !Q1 ;偽fl!a21 :022 1a9:R7:01705 !V ' F:study讀作系統(tǒng)供的20124310-會程（實(shí)驗(yàn)2 ）慳苑二Debug實(shí)瞼2.-10： O 5110 10! 0 58； 0 31： 0 18； 0 480 490 5

25、0： 30八2： 8 51!0 10： 0 2： 0 31! 0 18： 0 480 490 58： 303! R 5110 10! Q 2! 0 3! 0 1R： 0 48fl 49ft 50: 309: 0 51!0 10! Q 21 0 3 ! 0 9: 0 480 490 50: 3075 0 5110 10： 0 2； 0 3 ： 6 9: 0 70 490 50； 301?! U bl 1SIS； H 21 9 3： Hi 95 9 7S 17U b»： 395: 0 51；0 10： 0 2： 0 3： 0 9： 0 70 170 5： 302: 0 5110 101

26、8 2! 0 3 ! 6 9: 0 70 1703011 8 1 11 0 101 0 21 0 3 1 e 91 0 711 0 1711 0 5 1 309； U 10 0；» 2； (J 3： e V： U 70 17。S： 300： 8 10 0： 0 2： 0 3： 0 9： 0 70 1?0 5： 300: 0 10 0!0 2! 0 2： R 9! R 70 17a 5：11 0 1 11 0 010 21 0 31 e 91 0 ?1 0 1711 0 5 1 300； 8 10 0；0 2； 0 3： 0 9： 8 70 17i0 5； 3021： 8 100； 6

27、 21：03：09：070 1710 5； 3022! fl 10 0； 。21； A 22! fl 9! % 70 1713 5： 3051: 0 10 0! Q 21! 0 22: 0 5U 0 70 17!0 5: 3018； 8 10 0；0 21； 0 22； 0 51； 0 180 17!0 5； 30195 U 1S 9； H 21： 9 22； H 51： U 18S 191kJ S： 302： 0 10 0： 0 21： 0 22： 0 51： 0 180 19：0 2: 30,FU算法中斷率0.64G00GPress any 】9y to continue.V五、實(shí)驗(yàn)體會此

28、次的實(shí)驗(yàn)不是很難，不論是FIFO 還是 LFU 算法，都只需分成3 部分考慮， 即物理塊中有相同頁面、物理塊中沒有相同頁面但有空閑、缺頁中斷這3 種情況。 只要分別根據(jù)不同情況的算法編寫對應(yīng)代碼即可，而其余部分的代碼兩種算法均相同。隨機(jī)生成要訪問的字地址部分較復(fù)雜，但根據(jù)老師提供的算法我也順利完成了。通過此次實(shí)驗(yàn)，我對FIFO、 LFU 算法有了更加詳細(xì)的認(rèn)識，對課上所學(xué)的只是有了一次實(shí)際的應(yīng)用，對其有了更加深刻的理解。附錄：#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<str

29、ing.h>#include<time.h># define Blocksize 8/物理塊的大小# define Procount 60/進(jìn)程的頁面數(shù)# define psize 100/進(jìn)程的大小# define OneK 1024/一個(gè)頁面的大小typedef struct pageint num;/*記錄頁面號*/int count; /*記錄最近調(diào)度此頁面的次數(shù)*/Page;/* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實(shí)現(xiàn)設(shè)計(jì)*/Page BlockBlocksize; /*內(nèi)存單元數(shù)*/int temppsizeBlocksize + 1=0;/* 暫保存內(nèi)存當(dāng)前的狀態(tài)：緩

30、沖區(qū)*/int queuepsize;/*記錄調(diào)入頁面序號*/int phbBlocksize;int frontp=0;int rearp=3;/初始化情況下，內(nèi)存中已經(jīng)分配3個(gè)頁面int flag=1;/標(biāo)志是否有相同頁面，如有則0，沒有則1int frontlea=0; /標(biāo)志最先進(jìn)去的頁面號int FIFO_break=0;int LFU_break=0;void build() /產(chǎn)生頁面調(diào)度的頁面隨機(jī)序列int i=0;int suiji;int k;/表示隨機(jī)出來的存儲塊號printf(" 產(chǎn)生頁面調(diào)度的頁面隨機(jī)序列:n");srand(time(NULL);

31、k=rand()%(OneK * Procount);queuei+=k/1024;dosuiji=rand()%4+1;switch(suiji)case 1:case 2:if(k<Procount*OneK - 513)queuei+=(k+1+512)/1024;k=k+1+512;break;case 3:k=rand()%k;queuei+=k/1024;break;case 4:k=rand()%(61439 - k) + k;queuei+=k/1024;break;default:break;while(i<psize);for(i=0;i<psize;i+

32、)printf("%2d ",queuei);if(i+1)%5=0)printf("n");printf("n");int searchpb()/鷹找空閑物理塊，成功返回值是物理塊號，否則就是-1int j,m;for(j=0; j<Blocksize; j+)if(Blockj.num = -1)m = j;return m;break;return -1;void Init()初始化內(nèi)存int i;for(i=0;i<Blocksize;i+)Blocki.num=-1;Blocki.count=0;Block0.n

33、um=0;Block1.num=5;Block2.num=6;void empty()int i;for(i=0;i<Blocksize;i+) Blocki.count=0;/計(jì)數(shù)器置零void empty_temp()int i,k;for(i=0;i<psize;i+)for(k=0;k<Blocksize +1;k+) tempik=0;int FIFO()int i,p,k;for(i=0;i<psize;i+)for(k=0;k<Blocksize;k+)/查找是否有相同頁面if(queuei = Blockk.num) flag=0;if(flag=

34、1)/沒有查找到相同頁面則開始調(diào)入頁面if(searchpb()!=-1) /物理塊有空閑p=searchpb();Blockp.num=queuei;rearp=(rearp+1) % Blocksize;else/發(fā)生缺頁中斷Blockfrontp.num=queuei;frontp=(frontp+1) % Blocksize; FIFO_break+;flag=1;p=frontp;tempi0=queuei;for(k=1;k<Blocksize + 1;k+)tempik=Blockp.num;p=(p+1) % Blocksize;for(i=0;i<psize;i+)for(k=0;k<