甘肃龙网

  1. 首页 > 生活 > >

LRU 最近最久未使用置换算法的C++实现( 二 )

生活百科算法

<< "|是否缺页|" << endl;for (int i = 0; i < m; i++){cout << "|" << setw(4) << vis[i] << "|";for (int j = 0; j < n; j++){if (state[i][j] != -1)cout << setw(4) << state[i][j];elsecout << "";}if (miss[i] == 1) //输出“是”和“否”比较丑cout << "|1|" << endl;elsecout << "|0|" << endl;}cout << "缺页次数：" << miss_num << endl;miss_rate = (double)miss_num / m;cout << "缺页率：" << miss_num << "/" << m << "=" << setprecision(2) << miss_rate << endl;return;}int main(){init();for (int i = 0; i < m; i++){LRU(vis[i]);}display();return 0;}
程序运行时的初值及运行结果 初值
分配给该进程的页块数：3

LRU 最近最久未使用置换算法的C++实现

文章插图
页面访问序列的长度：20
访问序列：1 2 5 6 0 3 6 5 3 6 5 6 0 4 2 7 0 4 3 5
运行结果
思考题FIFO算法
与前文LRU算法的实现不同的是，在FIFO算法中，[1001]记录页面进入内存的时间 。算法实现如下：
//FIFO算法void FIFO(int a){//检查请求访问的页是否在进程的内存中if (flag[a] == false){miss[now_time] = 1; //此次标记：缺页miss_num++;if (now_num == n) //内存已满{int min_time = 0x3f3f3f, min_num = -1; //被替换的页的入内存时间最早的页和位置//在内存中的页中，先进先出（将入内存时间最早的页移出内存）for (int i = 0; i < now_num; i++){if (l_time[memory[i]] < min_time){min_time = l_time[memory[i]];min_num = i;}}flag[a] = true;//将当前访问的页“是否在内存中”的标记设为1flag[memory[min_num]] = 0; //将被替换的页“是否在内存中”的标记设为0memory[min_num] = a;//当前页替换最早入内存的页}else //内存未满{flag[a] = true;memory[now_num] = a; //当前页进入内存的下一个位置now_num++;//内存中页的个数加1}l_time[a] = now_time; //更新当前页的入内存时间为当前时间}else{miss[now_time] = 0; //标记：未缺页}//保存内存中页面的序列for (int i = 0; i < n; i++){state[now_time][i] = memory[i];}now_time++; //访问完一个页面，当前时间加1return;}
运行结果
NRU算法（CLOCK）
简单的NRU算法是给每一帧关联一个附加位，称为使用位 。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位置为0 。
对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联 。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧 。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧 。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页 。
int u[1001];//记录页面的使用位int point;//指针
算法实现如下：
//NRU算法void NRU(int a){//检查请求访问的页是否在进程的内存中if (flag[a] == false){miss[now_time] = 1; //此次标记：缺页miss_num++;int num; //被替换的页的位置if (now_num == n) //内存已满{//指针遍历内存while (1){if (u[memory[point]] == 1){u[memory[point]] = 0; //将使用位为1的页面置为0}else //若使用位为0，被替换{num = point;flag[a] = true;//将当前访问的页“是否在内存中”的标记设为1flag[memory[num]] = 0; //将被替换的页“是否在内存中”的标记设为0memory[num] = a;//当前页替换最久未使用过的页break;}point++;if (point >= n - 1){point %= (n - 1);}}}else //内存未满{flag[a] = true;memory[now_num] = a; //当前页进入内存的下一个位置u[now_num] = 1;//使用位：置为1now_num++;//内存中页的个数加1point = now_num;//指针指向下一位置}}else{miss[now_time] = 0; //标记：未缺页u[now_num] = 0; //使用位：置为0}//保存内存中页面的序列for (int i = 0; i


上一篇：关于I/O——内存与CPU与磁盘之间的关系

下一篇：蚯蚓每小时能爬多少米