操作系統(tǒng)課程設(shè)計--請求頁式存儲管理

1、操作系統(tǒng)課程設(shè)計-請求頁式存儲管理操作系統(tǒng)課程設(shè)計請求頁式存儲管理 學(xué)院： 學(xué)號：姓名：輔導(dǎo)老師：設(shè)計四：1.設(shè)計目的請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本設(shè)計通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點(diǎn)，掌握請求頁式管理的頁面置換算法。2.設(shè)計內(nèi)容：通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成： 50% 的指令是順序執(zhí)行的； 25% 的指令是均勻分布在前地址部分； 25% 的指令是均勻分布在后地址部分。具體的實(shí)施方法是：在 0,319 的指令地址之間隨機(jī)選取一起點(diǎn) m；順序執(zhí)行一條指令；在前地址0,m+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地

2、址為 m； 順序執(zhí)行一條指令，其地址為 m+1；在后地址 m+2,319 中隨機(jī)選取一條指令并執(zhí)行 ；重復(fù)上述步驟 ， 直到執(zhí)行 320 次指令。將指令序列變換成為頁地址流設(shè)：頁面大小為 1K；用戶內(nèi)存容量為 4 頁到 32 頁 ；用戶虛存容量為 32K 。在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的存放方式為：第 0 條 第 9 條指令為第 0 頁 ( 對應(yīng)虛存地址為 0,9)；第 10 條 第 19 條指令為第 1 頁 ( 對應(yīng)虛存地址為 10,19 ) ；第 310 條 第 319 條指令為第 31 頁 ( 對應(yīng)虛存地址為 310,319) 。按以

3、上方式，用戶指令可組成 32 頁。計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。先進(jìn)先出的算法 (FIFO)；最近最少使用算法 (LRR)；最少訪問頁面算法 (LFR)；最近最不經(jīng)常使用算法 (NUR)。3實(shí)驗(yàn)環(huán)境每個學(xué)生一臺微機(jī)，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個學(xué)生上機(jī)時間不少于24個小時。（1）、分頁請求系統(tǒng)為了能實(shí)現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持，其中，最重要的是：（1）請求分頁的頁表機(jī)制。它是在分頁的頁表機(jī)制上增加若干個項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；（2）缺頁中斷機(jī)構(gòu)。每當(dāng)用戶程序要訪問的頁面

4、尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁面調(diào)入內(nèi)存；（3）地址變換機(jī)構(gòu)。它同樣是在分頁的地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。為了實(shí)現(xiàn)請求調(diào)頁還須得到OS的支持，在實(shí)現(xiàn)請求調(diào)頁功能時，石油OS將所需的頁從外存調(diào)入內(nèi)存；在實(shí)現(xiàn)置換功能時，也是由OS將內(nèi)存的某些頁調(diào)至外存。4實(shí)驗(yàn)提示提示：A.命中率=1-頁面失效次數(shù)/頁地址流長度 B.本實(shí)驗(yàn)中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。 C.關(guān)于隨機(jī)數(shù)產(chǎn)生方法，采用TC系統(tǒng)提供函數(shù)RAND()和RANDOMIZE()來產(chǎn)生。5.自己對算法的理解 FIFO頁面置換算法原理簡述在分配內(nèi)存頁面數(shù)(A

5、P)小于進(jìn)程頁面數(shù)(PP)時，當(dāng)然是最先運(yùn)行的AP個頁面放入內(nèi)存。這時有需要處理新的頁面，則將原來內(nèi)存中的AP個頁面最先進(jìn)入的調(diào)出(是以稱為FIFO)，然后將新頁面放入。以后如果再有新頁面需要調(diào)入，則都按的規(guī)則進(jìn)行。算法特點(diǎn)：所使用的內(nèi)存頁面構(gòu)成一個隊列。 LRU頁面置換算法原理算述當(dāng)分配內(nèi)存頁面數(shù)(AP)小于進(jìn)程頁面數(shù)(PP)時，當(dāng)然是把最先執(zhí)行的AP個頁面放入內(nèi)存。當(dāng)需要調(diào)頁面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁面全部不空閑時，選擇將其中最長時間沒有用到的那個頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面(稱為LRU)。算法特點(diǎn)：每個頁面都有屬性來表示有多長時間未被CPU使用的信息。LFU即最不經(jīng)常使用頁

6、置換算法1 原理簡述要求在頁置換時置換引用計數(shù)最小的頁，因?yàn)榻?jīng)常使用的頁應(yīng)該有一個較大的引用次數(shù)。但是有些頁在開始時使用次數(shù)很多，但以后就不再使用，這類頁將會長時間留在內(nèi)存中，因此可以將引用計數(shù)寄存器定時右移一位，形成指數(shù)衰減的平均使用次數(shù)。LRU算法的硬件支持把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實(shí)現(xiàn)起來有相當(dāng)大的難度，因?yàn)樗笙到y(tǒng)具有較多的支持硬件。所要解決的問題有：1.一個進(jìn)程在內(nèi)存中的各個頁面各有多久時間未被進(jìn)程訪問；2.如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩類支持硬件：（1）寄存器用于記錄某進(jìn)程在內(nèi)存中各頁的使用情況。實(shí)頁/R

7、R7R6R5R4R3R2R1R0101010010210101100300O001004011010115110101106001 01011700000111801101101（2）?？衫靡粋€特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。算法特點(diǎn):LFU算法并不能真正反映出頁面的使用情況，因?yàn)樵诿恳粫r間間隔內(nèi)，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10000次是等效的。 NUR頁面置換算法原理簡述所謂“最近未使用”，首先是要對“近”作一個界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次進(jìn)程

8、頁面處理工作中，都沒有處理到的頁面。那么可能會有以下幾種情況：如果這樣的頁面只有一個，就將其換出，放入需要處理的新頁面。如果有這樣的頁面不止一個，就在這些頁面中任取一個換出(可以是下標(biāo)最小的，或者是下標(biāo)最大的)，放入需要處理的頁面。如果沒有一個這樣的頁面，就隨意換出一個頁面(可以是下標(biāo)最小的，或者是下標(biāo)最大的)。算法特點(diǎn)：有一個循環(huán)周期，每到達(dá)這個周期，所有頁面存放是否被CPU處理的信息的屬性均被置于初始態(tài)(沒有被訪問)。6實(shí)驗(yàn)流程圖 開 始生成地址流輸入算法號S1S4形成地址頁號用戶內(nèi)存空間msize=2Msize32 OPT()FIFO()LRU()LFU()Msize加1S= 是否用其他算法繼續(xù)結(jié) 束NY1234YN提示出錯，重新輸入7. 實(shí)驗(yàn)運(yùn)行結(jié)果等等。8. 實(shí)驗(yàn)源程序#include<iostream>#include<>using namespace std;const int MaxNum=320;實(shí)驗(yàn)體會通過上面的截圖可以發(fā)現(xiàn)，實(shí)驗(yàn)中指令是由隨機(jī)函數(shù)產(chǎn)生的,然后根據(jù)產(chǎn)生的指令算出需要訪問的頁面.在本次實(shí)驗(yàn)中我寫了四個頁面置換算法(先進(jìn)先出)FIFO算法和(最