首页 > 搜索 > 函数的置换的算法,操作系统 实验四:页面置换算法

函数的置换的算法,操作系统 实验四:页面置换算法

互联网 2020-10-20 09:05:01
在线算命,八字测算命理
操作系统 实验四:页面置换算法 16281042 安全1601 一、设计基本信息

1、模拟的虚拟内存的地址为16位,页面大小为1K 2、模拟的物理内存有32K 页面大小等于块的大小为1K,物理地址16位对应程序需要的物理空间为216B,需要216/1K = 64个页面,工作集的大小为 64,维护的物理内存块共32个

二、算法实现 0、程序设计、页面访问序列产生 struct Page{int pagenum;//页号int blocknum;//所存储的块号int presence = 0;//存在位,初始为0表示不存在int modify = 0;//修改位,初始位0,表示未被修改int visit = 0;//访问位,初始值未0表示未被访问}; 页面访问序列产生函数

符合局部访问特性的随机生成算法 1、确定虚拟内存的尺寸N,工作集的起始位置p,工作集中包含的页数e,工作集移动率m(每处理m个页面访问则将起始位置p +1),以及一个范围在0和1之间的值t; 2、生成m个取值范围在p和p + e间的随机数,并记录到页面访问序列串中; 3、生成一个随机数r,0 ≤ r ≤ 1; 4、如果r < t,则为p生成一个新值,否则p = (p + 1) mod N; 5、如果想继续加大页面访问序列串的长度,请返回第2步,否则结束。

实现代码:

int product(int b[1000], int N, int p, int e, int m, double t){int flag = 1;int place = 0;while (flag){for (int i = 0; i p = abs(rand());}else{p = (p + 1) % N;}printf("如果继续加大页面访问序列串的长度请输入:1,否则输入:0\n");scanf("%d", &flag);}return place;} 1、最佳置换算法

特点:性能最好 可操作性差 其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面 基本思想:选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰出内存 具体实现函数:void optimal(int size, Page page[1000], int BLOCK[32]) 函数参数:size为维护的页面访问序列的大小,page为具体的页面访问序列,BLOCK为维护的物理块 辅助函数:int find_optimal(int a, int begin, Page page[1000]) 函数参数:a为页号,begin为开始在页面访问序列寻找的开始位置,page为页面访问序列 函数功能:在页面访问序列中找到最开始访问指定页面a的位置,返回值为在页面访问序列中的位置,-1为未找到 辅助函数:int find_all(int a, int BLOCK[32]) 函数参数:a为页号,BLOCK为维护的物理块 函数功能:在物理块中寻找指定的页面,返回值为是否找到,0为未找到,1为找到

实现代码:

int get_pageplace(int a, Page page[40000], int end){for (int i = 0; i for (int i = 0; i int i = begin;int flag = 1;for (i; i return -1;}} void optimal(int size, Page page[30000], int BLOCK[32]){int num = 0;int deletion = 0;while (num num++;}else{int tag = 0;for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;num++;tag = 1;i = 32;}}if (tag == 0)//未找到空闲块{int b = 0;int change = -1;//决定替换内容的页位置int page_c;//决定替换的页号while (b change = temp;page_c = page[change].pagenum;}if (temp == -1){page_c = BLOCK[b];b = 64;//跳出循环,已找到以后不会使用的页面}b++;}for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;}}deletion++;num++;}}}double rate = (double(deletion) / double(size));printf("最佳置换算法:*****缺页次数:%d,缺页率:%.3f\n", deletion, rate);} 2、先进先出置换算法

特点:简单 性能较差 该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。 基本思想:选择最先进入内存即在内存驻留时间最久的页面换出到外存 具体实现函数:void fifo(int size, Page page[1000], int BLOCK[32]) 函数参数:size为维护的页面访问序列的大小,page为具体的页面访问序列,BLOCK为维护的物理块

实现代码:

void fifo(int size, Page page[30000], int BLOCK[32]){int num = 0;int deletion = 0;while (num num++;}else{int tag = 0;for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;num++;tag = 1;i = 32;}}if (tag == 0)//未找到空闲块{int b = 0;int change = 40000;//决定替换内容的页位置while (b if (page[j].pagenum == BLOCK[b]){if (j BLOCK[i] = page[num].pagenum;page[num].blocknum = i;}}deletion++;num++;}}}double rate = (double(deletion) / double(size));printf("先进先出置换算法:******缺页次数:%d,缺页率:%.3f\n", deletion, rate);} 3、最近最久未使用置换算法

与最佳置换算法比较,最佳置换算法是从“向后看”的观点出发的,即它是依据以后各页的使用情况进行判断;而LRU算法则是“向前看”的,即根据各页以前的使用情况来判断,而页面过去和未来的走向之间并无必然联系。 基本思想:以“最近的过去”作为“最近的将来”的近似,选择最近一段时间最长时间未被访问的页面淘汰出内存 具体实现函数:void LRU(int size, Page page[1000], int BLOCK[32]) 函数参数:size为维护的页面访问序列的大小,page为具体的页面访问序列,BLOCK为维护的物理块

实现代码:

void LRU(int size, Page page[30000], int BLOCK[32]){int num = 0;int deletion = 0;while (num num++;}else{int tag = 0;for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;num++;tag = 1;i = 32;}}if (tag == 0)//未找到空闲块{int b = 0;int change = 40000;//决定替换内容的页位置while (b if (page[j].pagenum == BLOCK[b]){if (j BLOCK[i] = page[num].pagenum;page[num].blocknum = i;}}deletion++;num++;}}}double rate = (double(deletion) / double(size));printf("LRU置换算法:*****缺页次数:%d,缺页率:%.3f\n", deletion, rate);} 4、改进型Clock置换算法

改进型的Clock算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中,同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成一下四种类型的页面。

1类(A =0, M = 0):表示该页面最近既未被访问,又未被修改,是最佳淘汰页。

2类(A =0, M = 1):表示该页面最近未被访问,但已被修改,并不是很好的淘汰页。

3类(A =1, M = 0):表示该页面最近已被访问,但未被修改,该页有可能再被访问。

4类(A =1, M = 1):表示该页最近已被访问且被修改,该页可能再被访问。

基本思想: ① 从查寻指针当前位置起扫描内存分页循环队列,选择A=0且M=0的第一个页面淘汰;若未找到,转② ② 开始第二轮扫描,选择A=0且M=1的第一个页面淘汰,同时将经过的所有页面访问位置0;若不能找到,转①

算法性能:与简单Clock算法相比,可减少磁盘的I/O操作次数,但淘汰页的选择可能经历多次扫描,故实现算法自身的开销增大。 具体实现函数:void clock(int size, Page page[1000], int BLOCK[32]) 函数参数:size为维护的页面访问序列的大小,page为具体的页面访问序列,BLOCK为维护的物理块 实现代码:

void clock(int size, Page page[30000], int BLOCK[32]){int num = 0;int deletion = 0;while (num page[num].visit = 1;num++;}else{int tag = 0;for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;num++;tag = 1;i = 32;}}if (tag == 0)//未找到空闲块{int b = 0;int flag = 0;//判断是否找到替换页面,初始值为0表示未找到int change = 40000;//决定替换页的物理位置while (!flag)//直到找到为止{for (int i = 0; i if (i for (int i = 0; i page[place2].visit = 0;//将所有访问到的页面访问位都置0if (i freeblock[0] = -1;freeblock[1] = -1;//初始化为-1表示没有存储内容int num = 0;int deletion = 0;while (num num++;}else{int tag = 0;for (int i = 0; i BLOCK[i] = page[num].pagenum;page[num].blocknum = i;tag = 1;i = 32;num++;}}if (tag == 0)//未找到空闲块{int b = 0;int change = 40000;//决定替换内容的页位置while (b if (page[j].pagenum == BLOCK[b]){if (j for (int j = 0; j freeblock[j] = page[change].pagenum;BLOCK[i] = freeblock[j];exit = 1;}}if (exit == 0);{for (int j = 0; j exit = 1;freeblock[j] = BLOCK[i];BLOCK[i] = page[num].pagenum;page[num].blocknum = i;}}}if (exit == 0){freeblock[0] = BLOCK[i];BLOCK[i] = page[num].pagenum;page[num].blocknum = i;}}}}}}double rate = (double(deletion) / double(size));printf("PBA算法:****缺页次数:%d,缺页率:%.3f\n", deletion, rate);} 3、运行结果

在这里插入图片描述

4、实验感想

本次的实验还是比较简单的,但是PBA算法的是新啊还是废了点力气因为最开始没有搞清楚算法的基本原理,等清楚原理之后还是很简单的。

github地址

https://github.com/LiXuzeng/2019_OS_LXZ/tree/master/16281042_李许增_实验四

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多