存儲管理與頁面置換算法

1、實驗二存儲管理與頁面置換算法一、實驗目的通過模擬頁式虛擬存儲管理中地址轉(zhuǎn)換和頁面置換，了解頁式虛擬存儲管理的思想，掌握頁式地址轉(zhuǎn)換過程和缺頁中斷處理過程。二、實驗學時4學時三、實驗內(nèi)容單機模擬頁式虛擬存儲管理中地址轉(zhuǎn)換和頁面置換過程。首先對頁表進行初始化；輸入要訪問的邏輯地址（可為16進制或10進制），程序分離出邏輯地址的頁號，查找頁表，根據(jù)頁表完成地址轉(zhuǎn)換，輸出轉(zhuǎn)換后的地址；若缺頁則提示中斷發(fā)生，按某種頁面置換算法（FIFO，LRU，LFU）進行頁面置換，并修改和輸出頁表，輸出絕對地址。最后輸出置換情況和缺頁次數(shù)。四、算法描述1 內(nèi)存的分配和管理方案在進程創(chuàng)建時必須為它分配一定的內(nèi)存資源，內(nèi)

2、存資源的分配與管理有很多方法，從動態(tài)性分有靜態(tài)的和動態(tài)的分配方法，從連續(xù)性上分有連續(xù)的和不連續(xù)的分配方案。連續(xù)的分配方案是程序的執(zhí)行速度加快但會使內(nèi)存出現(xiàn)碎片而不能得到應用，而不連續(xù)的分配方案可以使內(nèi)存碎片得到充分的應用，但由于訪問內(nèi)存次數(shù)的增多使程序執(zhí)行的速度下降。2 內(nèi)存的分配的過程在作業(yè)執(zhí)行前，向系統(tǒng)提供內(nèi)存的請求表，在系統(tǒng)為作業(yè)創(chuàng)建進程時，要為進程分配內(nèi)存資源。以分頁系統(tǒng)為例，系統(tǒng)首先確定進程需要的頁面數(shù)量，然后順序查找位圖(系統(tǒng)為每一個頁面分配一位內(nèi)存中的各個頁面組成一個數(shù)組，如果該位為1說明該位所指示的頁正在被使用，如果該位為0說明該位指示的頁面空閑若存在所需要的空閑頁面則此次分配

3、成功，否則分配失敗，若分配成功系統(tǒng)首先把分配出去的頁面所屬的位置為1，然后形成進程所需的頁表。3算法思想本程序有兩個功能：一是地址轉(zhuǎn)換；二是模擬頁面置換情況。(1地址轉(zhuǎn)換:add_tran將邏輯地址中的頁號分離出來，查找頁表，將查找到的塊號與邏輯地址中的頁內(nèi)偏移量合成實際地址，若查找不到則產(chǎn)生缺頁中斷，按FIFO的方法置換頁面。(a數(shù)據(jù)結構：arraymax2為頁表，其中arrayn0為頁號，arrayn1為塊號，size_PT表示系統(tǒng)分配給進程的塊數(shù)，即頁表中的頁數(shù)。（b）地址轉(zhuǎn)換算法思想首先初始化頁表：輸入分配的塊數(shù)(頁表的大小，然后輸入初始頁表中的頁號和相對應的塊號，初始化完成后程序輸出

4、初始化后的頁表。然后是地址轉(zhuǎn)換：輸入16進制邏輯地址，程序分離出邏輯地址的頁號，然后查找頁表，若缺頁則提示中斷發(fā)生，并修改頁表，然后輸出轉(zhuǎn)換后的地址，輸出頁表。(c執(zhí)行情況 程序提示“please input size of the page table：”，要求輸入分配的塊數(shù)s_PT，即頁表的大小。然后根據(jù)size_PT，循環(huán)輸入初始化頁表里的頁號和對應的塊號。用j來表示下一個將會被置換的頁面存放位置，初始指向頁表中最后一個頁面，按照(j+1size_PT循環(huán)。然后程序輸出頁表情況：頁號和對應的塊號。至此初始化完成。程序提示“input the adderss wanted to be tr

5、anslated (0 exit：”，要求輸入要轉(zhuǎn)換的邏輯地址。程序分離出頁號后查找頁表，查找到則直接輸出轉(zhuǎn)換后的地址。否則提示“intermittence occurred, page A has been replaced with page B”。（A代表被置換的頁號，B代表置換后的頁號。）然后再輸出轉(zhuǎn)換后的地址(16進制。輸出轉(zhuǎn)換后的地址后，程序還把轉(zhuǎn)換后的頁表顯示出來，可以清楚地了解頁表是否被置換和置換情況。(d結果舉例設size_PT為3，初始化頁表為Page：1 block：2 ,page：3 block：5，page：6 block：3。輸入邏輯地址4ff(程序假設頁面大小為1

6、k即1024。則其頁號為1，查找頁表，不產(chǎn)生缺頁中斷，塊號為2，則輸出轉(zhuǎn)換后的地址為8FF，頁表不變。輸入邏輯地址81a，則其頁號為2，查找頁表，產(chǎn)生缺頁中斷，此時j指向page 6，將page6置換為page 2，塊號為3。則輸出轉(zhuǎn)換后的地址為c1a，頁表變?yōu)镻age：1 block：2，page：3,block：5page：2 block：3。置換后j變成(2+1size_PT：0，指向頁表中第一項page 1。（2）頁面置換模擬：page_si(a算法思想輸入頁面序列，缺頁時按FIFO的策略進行頁面置換，輸出置換情況和缺頁次數(shù)。假設頁表大小不超過max，輸入的頁面數(shù)不超過max*lO。(

7、b數(shù)據(jù)結構arraylmax表示簡化了的頁表，只包含頁號，array2max*lO存放頁面序列。size_PT表示分配給該進程的塊數(shù)，size2表示頁面序列長度。page_rep指向下一個將被置換的頁面，初始為O，指向頁表的第一項。Sum_int用來計算中斷次數(shù)。(c程序執(zhí)行流程初始化：輸入分配的塊數(shù)size_PT，然后對頁表共size_PT向賦值-1，表示空。輸入頁面序列，存放于數(shù)組array2中。按照size2循環(huán)，依次查找頁面是否存在于頁表中，不存在則置換頁面，page_rep初始為0，變化同上。格式化依次輸出訪問下一個頁面后的頁表，然后輸出缺頁中斷總次數(shù)。(d執(zhí)行結果舉例輸入size_

8、PT為2輸入頁面序列為1，3，5，4，5，-1(-1表示輸入結束輸出為1，1 3，5 3，5 4，5 4there has been 4 intermittences occurred表示有4次中斷發(fā)生五、參考程序#include “stdio.h”#define max 100 /*定義頁面數(shù)組大小的上限*/#define size_pa 1024void add_tran(int arraymax2;/*頁表，其中arrayn0為頁號，arrayn1為塊號*/int size_PT；int no_page,no_block;/* no_page,no_block 分別是頁號和塊號*/int

9、 if_quit1; /*if_quit1退出子程序標志*/int i,j；/*j表示下一個將被置換的頁面位置*/int add_logic,add_sys;/*邏輯地址和絕對地址*/int if_page;/*中斷標志*/if_quit1=0;/*退出標志*/*初始化頁表*/printf(“n please input size of the page table: ”;scanf(“%d”,&size_PT;j=size_PT-1;printf(“n now initialize the page table, please input page number and block numb

10、er n”;for(i=0；I=size_PT;i+printf(“page number:”scanf(“%d”,&no_page;printf(“block number:”scanf(“%d”,&no_block;arrayi0=no_page;arrayi1=no_block;printf(“initializing complete”;/*輸出初始化頁表*/printf(“nPage table: n”;for(i=0;i printf(“page:%5d”,arrayi0;printf(“block:%5d”,arrayi1; printf(“n”；printf(“n”；/*地址變

11、換*/while(if_quitl=0if_page=1；pdntf(“n input the address wantted to be translated(0 exit：；scanf(“%x”，add_logic；if(add_logic=0 if_quitl=1；elseno_page=add_logic/size-pa；for(i=0；i ； i+ if(armyi0=no_pageadd_sys=add_logic%size_pa+arrayi1*size_pa；if_page=0；else if_page=if_page*l；if(if_page=1add-sys=addlogi

12、c%size-pa+arrayj1*size-pa;printf(n intermittence occured，page%d has been replaced with page%n”，arrayjO，no_page；arrayj0=no_page；j=(j+1%size_PT；prinf(“the target address is：%xn”，add_sys；printf(“nPage table：n”；for(i=0；i ； i+ prinf(“page：%d”，arrayiO；printf(“block：%d”，arrayi1；prinf(“n”；/*頁面置換模擬：輸入頁面序列，缺頁

13、時按FIFO的策略進行頁面置換。*/*輸出置換情況，和缺頁次數(shù)*/*假設頁表大小不超過max，輸入的頁面數(shù)不超過max*1O*/，/*程序執(zhí)行流程：*/*初始化：輸入分配的塊數(shù)，輸入頁面序列*/*輸出依次訪問一個頁面后的頁表，然后輸出缺頁中斷總次數(shù)*/void page_si(/*主程序*/void main(int if_quitO；/*if-quit0退出主程序標志*/int n_func;if_quit0=0;while(if_quit0=0printf(“n please input number of the funotion you want to executen”；printf(“l(fā)-address translating，2-page