請求頁式存儲管理程序說明.doc

請求頁式存儲管理 1. 設(shè)計(jì)要求設(shè)計(jì)一個請求頁式存儲管理方案。并編寫模擬程序?qū)崿F(xiàn)之。頁面淘汰算法采用 FIFO頁面淘汰算法，并且在淘汰一頁時，只將該頁在頁表中抹去。而不再判斷它是否被改寫過，也不將它寫回到輔存。方案提示： 1、產(chǎn)生一個需要訪問的指令地址流，它是一系列需要訪問的指令的地址。為不失一般性，你可以適當(dāng)?shù)兀ㄓ萌斯ぶ付ǖ胤椒ɑ蛴秒S機(jī)數(shù)產(chǎn)生器）生成這個序列，使得 50的指令是順序執(zhí)行的。25的指令均勻地散布在前地址部分，25的地址是均勻地散布在后地址部分。2、指定合適的頁面尺寸（例如以 1K或2K為1頁）； 3、指定內(nèi)存頁表的最大長度，并對頁表進(jìn)行初始化； 4、每訪問一個地址時，首先要計(jì)算該地址所在的頁的頁號，然后查頁表，判斷該頁是否在主存如果該頁已在主存，則打印頁表情況；如果該頁不在主存且頁表未滿，則調(diào)入一頁并打印頁表情況；如果該頁不足主存且頁表已滿，則按 FIFO頁面淘汰算法淘汰一頁后調(diào)入所需的頁，打印頁表情況； 逐個地址訪問，直到所有地址訪問完畢。2. 問題分析分頁存儲管理，是將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，在為進(jìn)程分配內(nèi)存時，以塊為單位將進(jìn)程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中系統(tǒng)為每個進(jìn)程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。一個頁表中包含若干個表目，表目的自然序號對應(yīng)于用戶程序中的頁號，表目中的塊號是該頁對應(yīng)的物理塊號。請求頁式存儲管理方式是一種實(shí)現(xiàn)虛擬存儲器的方式，是指在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動態(tài)裝入其它頁面。當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。請求頁式存儲管理主要需要解決以下問題：系統(tǒng)如何獲知進(jìn)程當(dāng)前所需頁面不在主存；當(dāng)發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入主存；當(dāng)主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。本程序中采用先來先服務(wù)的淘汰方式。3. 算法與數(shù)據(jù)結(jié)構(gòu)請求分頁存儲管理方式當(dāng)中用到的主要數(shù)據(jù)結(jié)構(gòu)就是頁表項(xiàng)。與普通分頁管理存儲方式當(dāng)中的頁表項(xiàng)相比，請求分頁存儲管理方式的頁表項(xiàng)要進(jìn)行相應(yīng)的補(bǔ)充，共程序在換進(jìn)、換出內(nèi)存時參考。具體而言，請求分頁存儲管理方式的頁表項(xiàng)一般包括以下幾項(xiàng)：頁號、駐留位、內(nèi)存塊號、外存地址、訪問位、修改位、（存取控制、輔存地址）。其中，中斷位表示該頁是在內(nèi)存還是在外存；訪問位表示該頁最近被訪問過，根據(jù)訪問位來決定淘汰哪頁；修改位用于查看此頁是否在內(nèi)存中被修改過。本程序中采用的頁表項(xiàng)數(shù)據(jù)結(jié)構(gòu)如下(由于以上所述的有些域在程序中用不到，因此進(jìn)行了相應(yīng)的簡化)：typedef struct pa /頁表項(xiàng)的數(shù)據(jù)結(jié)構(gòu)int pn; /頁號int bn; /物理塊號bool s; /狀態(tài)位int ad; /外存地址 pageitem;另外，為了使用先進(jìn)先出的頁面置換方法，還需要定義一個FIFO鏈表。具體數(shù)據(jù)結(jié)構(gòu)如下：typedef struct p /頁標(biāo)置換的FIFO鏈表int num; /記錄頁號struct p *next; flink;4. 程序流程圖5. 運(yùn)行結(jié)果演示本程序利用VC編寫，在Visual Studio環(huán)境中調(diào)試通過。運(yùn)行程序，將會提示輸入指令的邏輯地址，輸入之后，程序?qū)凑照埱蠓猪摯鎯芾矸绞絹砉芾韮?nèi)存中的物理塊。程序的運(yùn)行過程及運(yùn)行結(jié)果如下： 歡迎使用請求分頁存儲管理方式模擬程序請輸入一個指令地址(00006144): 0100 此指令頁號為0 此頁面已調(diào)入內(nèi)存當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000請輸入一個指令地址(00006144): 1240 此指令頁號為1 此頁面已調(diào)入內(nèi)存當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000 1 47 1 21024請輸入一個指令地址(00006144): 0333 此指令頁號為0 此頁面已在內(nèi)存中當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000 1 47 1 21024請輸入一個指令地址(00006144): 0431 此指令頁號為0 此頁面已在內(nèi)存中當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000 1 47 1 21024請輸入一個指令地址(00006144): 5146 此指令頁號為5 此頁面已調(diào)入內(nèi)存當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000 1 47 1 21024 5 235 1 25120請輸入一個指令地址(00006144): 6487請輸入一個指令地址(00006144): 5478 此指令頁號為5 此頁面已在內(nèi)存中當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 0 0 1 20000 1 47 1 21024 5 235 1 25120請輸入一個指令地址(00006144): 4234 此指令頁號為4 此頁面已調(diào)入內(nèi)存,頁號為0的頁面被置換出來當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 1 47 1 21024 4 188 1 24096 5 235 1 25120請輸入一個指令地址(00006144): 2014 此指令頁號為1 此頁面已在內(nèi)存中當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 1 47 1 21024 4 188 1 24096 5 235 1 25120請輸入一個指令地址(00006144): 2654 此指令頁號為2 此頁面已調(diào)入內(nèi)存,頁號為1的頁面被置換出來當(dāng)前內(nèi)存中物理塊的情況 頁號 物理塊號 狀態(tài)位 外存地址 2 94 1 22048 4 188 1 24096 5 235 1 25120請輸入一個指令地址(00006144