存储管理与页面置换算法

1、实验二存储管理与页面置换算法一、实验目的通过模拟页式虚拟存储管理中地址转换和页面置换，了解页式虚拟存储管理的思想，掌握页式地址转换过程和缺页中断处理过程。二、实验学时4学时三、实验内容单机模拟页式虚拟存储管理中地址转换和页面置换过程。首先对页表进行初始化；输入要访问的逻辑地址（可为16进制或10进制），程序分离出逻辑地址的页号，查找页表，根据页表完成地址转换，输出转换后的地址；若缺页则提示中断发生，按某种页面置换算法（FIFO，LRU，LFU）进行页面置换，并修改和输出页表，输出绝对地址。最后输出置换情况和缺页次数。四、算法描述1 内存的分配和管理方案在进程创建时必须为它分配一定的内存资源，内

2、存资源的分配与管理有很多方法，从动态性分有静态的和动态的分配方法，从连续性上分有连续的和不连续的分配方案。连续的分配方案是程序的执行速度加快但会使内存出现碎片而不能得到应用，而不连续的分配方案可以使内存碎片得到充分的应用，但由于访问内存次数的增多使程序执行的速度下降。2 内存的分配的过程在作业执行前，向系统提供内存的请求表，在系统为作业创建进程时，要为进程分配内存资源。以分页系统为例，系统首先确定进程需要的页面数量，然后顺序查找位图(系统为每一个页面分配一位内存中的各个页面组成一个数组，如果该位为1说明该位所指示的页正在被使用，如果该位为0说明该位指示的页面空闲若存在所需要的空闲页面则此次分配

3、成功，否则分配失败，若分配成功系统首先把分配出去的页面所属的位置为1，然后形成进程所需的页表。3算法思想本程序有两个功能：一是地址转换；二是模拟页面置换情况。(1地址转换:add_tran将逻辑地址中的页号分离出来，查找页表，将查找到的块号与逻辑地址中的页内偏移量合成实际地址，若查找不到则产生缺页中断，按FIFO的方法置换页面。(a数据结构：arraymax2为页表，其中arrayn0为页号，arrayn1为块号，size_PT表示系统分配给进程的块数，即页表中的页数。（b）地址转换算法思想首先初始化页表：输入分配的块数(页表的大小，然后输入初始页表中的页号和相对应的块号，初始化完成后程序输出

4、初始化后的页表。然后是地址转换：输入16进制逻辑地址，程序分离出逻辑地址的页号，然后查找页表，若缺页则提示中断发生，并修改页表，然后输出转换后的地址，输出页表。(c执行情况 程序提示“please input size of the page table：”，要求输入分配的块数s_PT，即页表的大小。然后根据size_PT，循环输入初始化页表里的页号和对应的块号。用j来表示下一个将会被置换的页面存放位置，初始指向页表中最后一个页面，按照(j+1size_PT循环。然后程序输出页表情况：页号和对应的块号。至此初始化完成。程序提示“input the adderss wanted to be tr

5、anslated (0 exit：”，要求输入要转换的逻辑地址。程序分离出页号后查找页表，查找到则直接输出转换后的地址。否则提示“intermittence occurred, page A has been replaced with page B”。（A代表被置换的页号，B代表置换后的页号。）然后再输出转换后的地址(16进制。输出转换后的地址后，程序还把转换后的页表显示出来，可以清楚地了解页表是否被置换和置换情况。(d结果举例设size_PT为3，初始化页表为Page：1 block：2 ,page：3 block：5，page：6 block：3。输入逻辑地址4ff(程序假设页面大小为1

6、k即1024。则其页号为1，查找页表，不产生缺页中断，块号为2，则输出转换后的地址为8FF，页表不变。输入逻辑地址81a，则其页号为2，查找页表，产生缺页中断，此时j指向page 6，将page6置换为page 2，块号为3。则输出转换后的地址为c1a，页表变为Page：1 block：2，page：3,block：5page：2 block：3。置换后j变成(2+1size_PT：0，指向页表中第一项page 1。（2）页面置换模拟：page_si(a算法思想输入页面序列，缺页时按FIFO的策略进行页面置换，输出置换情况和缺页次数。假设页表大小不超过max，输入的页面数不超过max*lO。(

7、b数据结构arraylmax表示简化了的页表，只包含页号，array2max*lO存放页面序列。size_PT表示分配给该进程的块数，size2表示页面序列长度。page_rep指向下一个将被置换的页面，初始为O，指向页表的第一项。Sum_int用来计算中断次数。(c程序执行流程初始化：输入分配的块数size_PT，然后对页表共size_PT向赋值-1，表示空。输入页面序列，存放于数组array2中。按照size2循环，依次查找页面是否存在于页表中，不存在则置换页面，page_rep初始为0，变化同上。格式化依次输出访问下一个页面后的页表，然后输出缺页中断总次数。(d执行结果举例输入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次中断发生五、参考程序#include “stdio.h”#define max 100 /*定义页面数组大小的上限*/#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的策略进行页面置换。*/*输出置换情况，和缺页次数*/*假设页表大小不超过max，输入的页面数不超过max*1O*/，/*程序执行流程：*/*初始化：输入分配的块数，输入页面序列*/*输出依次访问一个页面后的页表，然后输出缺页中断总次数*/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-address translating，2-page