存儲(chǔ)管理與頁(yè)面置換算法

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

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

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

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

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

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

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

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

9、 if_quit1; /*if_quit1退出子程序標(biāo)志*/int i,j；/*j表示下一個(gè)將被置換的頁(yè)面位置*/int add_logic,add_sys;/*邏輯地址和絕對(duì)地址*/int if_page;/*中斷標(biāo)志*/if_quit1=0;/*退出標(biāo)志*/*初始化頁(yè)表*/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”;/*輸出初始化頁(yè)表*/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”；/*頁(yè)面置換模擬：輸入頁(yè)面序列，缺頁(yè)

13、時(shí)按FIFO的策略進(jìn)行頁(yè)面置換。*/*輸出置換情況，和缺頁(yè)次數(shù)*/*假設(shè)頁(yè)表大小不超過(guò)max，輸入的頁(yè)面數(shù)不超過(guò)max*1O*/，/*程序執(zhí)行流程：*/*初始化：輸入分配的塊數(shù)，輸入頁(yè)面序列*/*輸出依次訪問(wèn)一個(gè)頁(yè)面后的頁(yè)表，然后輸出缺頁(yè)中斷總次數(shù)*/void page_si(/*主程序*/void main(int if_quitO；/*if-quit0退出主程序標(biāo)志*/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