操作系統(tǒng)實驗報告(四)(文檔)

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

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

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

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

頁面尺寸為１Ｋ。②

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

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

先進先出算法（FIFO）。②

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

最佳淘汰算法。④

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

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