操作系統(tǒng)實(shí)驗(yàn)報(bào)告(四)(文檔)

XXXX大學(xué)實(shí)驗(yàn)報(bào)告||實(shí)驗(yàn)名稱實(shí)驗(yàn)四存儲(chǔ)器管理實(shí)驗(yàn)課程名稱操作系統(tǒng)||專業(yè)班級(jí)：學(xué)生姓名:學(xué)號(hào)：成績(jī)：指導(dǎo)教師：實(shí)驗(yàn)日期：華北電力大學(xué)實(shí)驗(yàn)報(bào)告第頁(yè)共頁(yè)一、實(shí)驗(yàn)?zāi)康募耙笠?、?shí)驗(yàn)?zāi)康? 存儲(chǔ)器管理的主要功能是，合理地分配內(nèi)存空間，數(shù)據(jù)存儲(chǔ)和查詢。其中，請(qǐng)求頁(yè)式存儲(chǔ)管理是一種具有虛擬空間技術(shù)的存儲(chǔ)器管理系統(tǒng)。 本實(shí)驗(yàn)的目的是，設(shè)計(jì)請(qǐng)求頁(yè)式存儲(chǔ)管理中的頁(yè)面置換算法，加深了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握各種頁(yè)面置換的算法。二、實(shí)驗(yàn)要求 （１）通過(guò)隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共３２０條指令。指令的地址按下述原則生成：①

５０％的指令是順序執(zhí)行的。②

２５％的指令均勻分布在低地址部分。③

２５％的指令均勻分布在高地址部分。具體實(shí)施的方法是：①在［０，３１９］的指令地址之間隨機(jī)產(chǎn)生一個(gè)起點(diǎn)m；②順序執(zhí)行一條指令，即執(zhí)行m＋１處的執(zhí)行；③在地址［０，m＋１］中隨機(jī)選取一條指令執(zhí)行，該指令的地址為m１；④順序執(zhí)行一條指令，即執(zhí)行m1＋１處的執(zhí)行；⑤在地址［m1＋2,319］中隨機(jī)選取一條指令執(zhí)行；⑥重復(fù)上述步驟直到執(zhí)行了３２０條指令為止。（２）將指令序列改變?yōu)轫?yè)地址流，并假設(shè)：①

頁(yè)面尺寸為１Ｋ。②

用戶的內(nèi)存容量為４頁(yè)到３２頁(yè)。③

用戶的虛存容量為３２Ｋ。 在用戶虛存中，按每Ｋ存放１０條指令來(lái)排列虛存地址，即３２０條指令在虛存放方式為：第０條～第９條為０號(hào)頁(yè)（對(duì)應(yīng)的虛存地址為［０，９］）。第１０條～第１９條為１號(hào)頁(yè)（對(duì)應(yīng)的虛存地址為［１０，１９］）?！?１０條～第3１９條為3１號(hào)頁(yè)（對(duì)應(yīng)的虛存地址為［3１０，3１９］）。按上述方式，用戶指令可組成32頁(yè)。（3）計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。①

先進(jìn)先出算法（FIFO）。②

最近最少使用算法（LRU）。③

最佳淘汰算法。④

最少訪問(wèn)頁(yè)面算法（LFR）。其中，命中率為： 命中率=(1+缺頁(yè)次數(shù))/頁(yè)地址流長(zhǎng)度 本實(shí)驗(yàn)中，頁(yè)的地址流長(zhǎng)度為320，頁(yè)面失效次數(shù)為每次訪問(wèn)響應(yīng)指令時(shí)，該指令對(duì)應(yīng)的頁(yè)面不在內(nèi)存中的次數(shù)。3．隨機(jī)數(shù)的產(chǎn)生方法 在VC中設(shè)計(jì)到隨機(jī)數(shù)有兩個(gè)函數(shù)srand()andrand()。srand()的作用是是一個(gè)種子，提供每次獲得隨機(jī)數(shù)的基數(shù)而已，rand()根據(jù)種子而產(chǎn)生隨機(jī)數(shù)。注意 1：srand()里的值必須是動(dòng)態(tài)變化的，否則得到的隨機(jī)數(shù)就是一個(gè)固定數(shù) 2：如果我們想得到一個(gè)0-60的隨機(jī)數(shù)那么可以寫成 inti; srand(GetTickCount()); i=rand()%60;二、實(shí)驗(yàn)所需儀器、設(shè)備、材料PC機(jī)三、實(shí)驗(yàn)原理 1、分頁(yè)請(qǐng)求系統(tǒng) 為了能實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)和置換功能，系統(tǒng)必須提供必要的硬件支持，其中，最重要的是：（1）請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。它是在分頁(yè)的頁(yè)表機(jī)制上增加若干個(gè)項(xiàng)而形成的，作為請(qǐng)求分頁(yè)的數(shù)據(jù)結(jié)構(gòu)；（2）缺頁(yè)中斷機(jī)構(gòu)。每當(dāng)用戶程序要訪問(wèn)的頁(yè)面尚未調(diào)入內(nèi)存時(shí)，便產(chǎn)生一缺頁(yè)中斷，以請(qǐng)求OS將所缺的頁(yè)面調(diào)入內(nèi)存；（3）地址變換機(jī)構(gòu)。它同樣是在分頁(yè)的地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。為了實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)還須得到OS的支持，在實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)功能時(shí)，石油OS將所需的頁(yè)從外存調(diào)入內(nèi)存；在實(shí)現(xiàn)置換功能時(shí)，也是由OS將內(nèi)存的某些頁(yè)調(diào)至外存。2、頁(yè)面置換算法一、最佳（Optimal）置換算法 采用最佳置換算法可保證獲得最低的缺頁(yè)率。但由于人們目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不在被訪問(wèn)的，因而該算法也是無(wú)法實(shí)現(xiàn)的，但是可利用該算法去評(píng)價(jià)其它算法。圖6-3示出了利用最佳置換算法時(shí)的置換圖。由圖可看出，采用最佳置換算法，只發(fā)生了6次頁(yè)面置換。二、先進(jìn)先出頁(yè)面置換算法 該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中的駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁(yè)面經(jīng)常被訪問(wèn)，含有全局變量、常用函數(shù)、例程等的頁(yè)面，F(xiàn)IFO置換算法并不能保證這些頁(yè)面不被淘汰。三、最近最久未使用LRU置換算法1、LRU（LeastRecentlyUsed）算法的描述 FIFO置換算法之所以性能較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。而最近最久未使用（LRU）的頁(yè)面置換算法，，則是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái)的使用情況，只能利用“最近的過(guò)去”作為“最近的將來(lái)”的近似。因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。2、LRU算法的硬件支持

把LRU算法作為頁(yè)面置換算法是比較好的，它對(duì)于各種類型的程序都能適用，但實(shí)現(xiàn)起來(lái)有相當(dāng)大的難度，因?yàn)樗笙到y(tǒng)具有較多的支持硬件。所要解決的問(wèn)題有： 1.一個(gè)進(jìn)程在內(nèi)存中的各個(gè)頁(yè)面各有多久時(shí)間未被進(jìn)程訪問(wèn)； 2.如何快速地知道哪一頁(yè)最近最久未使用的頁(yè)面。為此，須利用以下兩類支持硬件：（1）寄存器用于記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況。實(shí)頁(yè)/RR7R6R5R4R3R2R1R0101010010210101100300O00100401101011511010110600101011700000111801101101（2）棧 可利用一個(gè)特殊的棧來(lái)保存當(dāng)前使用的各個(gè)頁(yè)面的頁(yè)面號(hào)。每當(dāng)進(jìn)程訪問(wèn)某頁(yè)面時(shí)，便將該頁(yè)面的頁(yè)面號(hào)從棧中移出，將它壓入棧頂。四、Clock置換算法1、簡(jiǎn)單的Clock置換算法 利用Clock算法時(shí)，只須為每頁(yè)設(shè)置一位訪問(wèn)位，在將內(nèi)存中的所有頁(yè)面都通過(guò)鏈接指針鏈成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位被置1。置換算法在選擇一頁(yè)淘汰時(shí)，只須檢查其訪問(wèn)位。2、改進(jìn)型Clock置換算法 在將一個(gè)頁(yè)面換出時(shí)，如果該頁(yè)已被修改過(guò)，便須將它重新寫到磁盤上；但如果該頁(yè)未被修改過(guò)，則不必將它拷回磁盤。同時(shí)滿足兩條件的頁(yè)面作為手癬淘汰的頁(yè)。由訪問(wèn)位A和修改位M可以組合成下面四種類型的頁(yè)面：1類（A=0，M=0）。表示該頁(yè)最近既未被訪問(wèn)、又未被修改，是最佳淘汰頁(yè)。2類（A=0，M=1）。表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。3類（A=1，M=0）。最近已被訪問(wèn)，但未被修改，該頁(yè)有可能再被訪問(wèn)。4類（A=1，M=1）。最近已被訪問(wèn)且被修改，該頁(yè)有可能再被訪問(wèn)。 在內(nèi)存中的每個(gè)頁(yè)必定是這四類頁(yè)面之一，在進(jìn)行頁(yè)面置換時(shí)，可采用與簡(jiǎn)單Clock算法相類似的算法，其差別在于須同時(shí)檢查訪問(wèn)位和修改位，以確定該頁(yè)是四類頁(yè)面中的那一種。此算法稱為改進(jìn)型Clock算法。其執(zhí)行過(guò)程可分成以下三步： （1）從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找A=0且M=0的第一類頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問(wèn)位A。 （2）如果第一步失敗，即查找一周后未遇到第一類頁(yè)面，則開始第二輪掃描，尋找A=0且M=1的第二類頁(yè)面，將所遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。在第二輪掃描期間，將所有經(jīng)過(guò)的頁(yè)面的訪問(wèn)位置0。 （3）如果第二步也失敗，即未找到第二類頁(yè)面，則將指針?lè)祷氐介_始的位置，并將所有的訪問(wèn)位復(fù)0。然后，重復(fù)第一步，如果仍失敗，必要時(shí)在重復(fù)第二步，此時(shí)就一定能夠找到被淘汰的頁(yè)。五、其它置換算法1、最少使用（LeastFrequentlyUsed）置換算法 在采用該算法時(shí)，應(yīng)為在內(nèi)存中的每個(gè)頁(yè)面設(shè)置一移位寄存器，用來(lái)記錄該頁(yè)面被訪問(wèn)的頻率，該置換算法選擇在最近時(shí)期使用最少的頁(yè)面作為淘汰頁(yè)。2、頁(yè)面緩沖算法（PageBufferingAlgorithm） 雖然LRU和Clock置換算法都比FIFO算法好，但它們都需要一定的硬件支持，置換一個(gè)已修改的頁(yè)的開銷要大。而頁(yè)面緩沖算法則既改善分頁(yè)系統(tǒng)的性能，又可采用一種較簡(jiǎn)單的置換策略。六、請(qǐng)求分頁(yè)系統(tǒng)的性能分析1、缺頁(yè)率對(duì)有效訪問(wèn)的時(shí)間的影響 缺頁(yè)時(shí)須先調(diào)入該頁(yè)的情況時(shí)，有效訪問(wèn)時(shí)間表示為：有效訪問(wèn)時(shí)間=（1-p）ma+p缺頁(yè)中斷時(shí)間。2、缺頁(yè)中斷時(shí)間的組成（1）缺頁(yè)中斷時(shí)間服務(wù)時(shí)間；（2）將缺頁(yè)中斷讀入的時(shí)間；（3）進(jìn)程重新執(zhí)行時(shí)間。 由于CUP速度很快，所以其中地（1）和（3）兩部分可以不超過(guò)1ms;而將一磁盤塊讀入內(nèi)存的時(shí)間，則包括尋道時(shí)間、旋轉(zhuǎn)時(shí)間和數(shù)據(jù)傳送時(shí)間三部分，大體上是24ms。由此可得知缺頁(yè)中斷時(shí)間約為25ms。此處尚未考慮到進(jìn)程可能因排隊(duì)等待所花費(fèi)的時(shí)間。將上述數(shù)據(jù)代入到工集有效訪問(wèn)時(shí)間四：實(shí)驗(yàn)步驟此實(shí)驗(yàn)尚未完全做出，程序無(wú)法正常運(yùn)行。實(shí)驗(yàn)心得操作系統(tǒng)的實(shí)驗(yàn)和數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)有不同也有相同之處，因?yàn)橹徽莆樟薈語(yǔ)言這一種高級(jí)語(yǔ)言方式，所以在編程方式上和數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)相同。但是操作系統(tǒng)的實(shí)驗(yàn)問(wèn)題更加專業(yè)化，和計(jì)算機(jī)的操作原理中的進(jìn)程調(diào)度有關(guān)，更加側(cè)重于計(jì)算機(jī)內(nèi)部的程序和進(jìn)程的運(yùn)行。在一學(xué)期的操作系統(tǒng)課上，我們不僅僅學(xué)到了有關(guān)的專業(yè)知識(shí)，還在點(diǎn)滴之間學(xué)到了生活和學(xué)習(xí)的方式方法