LRU(Least Recently Used)最近未使用置换算法--c实现
在OS中，一些程序的大小超过内存的大小（比如好几十G的游戏要在16G的内存上跑），便产生了虚拟内存的概念
我们通过给每个进程适当的物理块（内存），只让经常被调用的页面常驻在物理块上，不常用的页面就放在外存，等到要用的时候再从外存调入，从而实现虚拟内存
但是因为给的每个进程的物理块大小不可能是无限的，如果该进程的物理块用完了这时候又要调入新的页面进来的话，就需要用到置换算法，其中的一个算法就叫
————>LRU(Least Recently Used)最近未使用置换算法
一、代码思想
这个算法的思想就是把已经很久没用过的页面，调出物理块然后加入新的准备调入进来的页面，对于每个物理块有两个元素
【页面号丨此页面至上次被访问以来的时间t】
我用了二维数组buffer[][2]来实现，buffer[i][0]表示的是在第i个物理块里的页面号，buffer[i][1]示的是在第i个物理块里的页面号已经有多久没用被调用过了
二，全部代码
1 #include <iostream> 2 using namespace std; 3 4 int max(int arr[][2], int n) 5 { 6 int ans = 0; 7 for (int i = 0; i < n; i++) 8 { 9 if (arr[i][1] > arr[ans][1]) 10 { 11 ans = i; 12 } 13 } 14 return ans; 15 } 16 17 void check(int buffer[][2],int n) 18 { 19 for (int i = 0; i < 3; i++) 20 { 21 cout << buffer[i][0] << ' '; 22 } 23 cout << endl << "--------" << endl; 24 } 25 26 int exist_page_in_buffer(int buffer[][2], int page, int buffer_size) 27 { 28 for (int i = 0; i < buffer_size; i++) 29 { 30 if (buffer[i][0] == page) 31 { 32 return i; 33 } 34 } 35 return -1; 36 } 37 38 void one_turn(int buffer[][2], int i) 39 { 40 for (int k = 0; k < i; k++) 41 { 42 buffer[k][1]++; 43 } 44 } 45 46 void least_recently_used(int buffer[][2], int page[], int buffer_size, int page_size) 47 { 48 for (int i = 0; i < buffer_size; i++)//初始化buffer 49 { 50 buffer[i][0] = -1; 51 buffer[i][1] = 0; 52 } 53 for(int i = 0, j = 0; j < page_size;)//当页面全部调用完成时（j >= page_size），算法结束 54 { 55 //i是当前物理块中已经有多少页面了，j是已经有多少页面进行过置换了 56 if (exist_page_in_buffer(buffer, page[j], i) != -1 )//当前的页面page[j]已经存在于物理块buffer之中 57 { 58 one_turn(buffer, i); //过了一个调用周期 59 buffer[exist_page_in_buffer(buffer, page[j], i)][1] = 0;//这个page又被调用一次，所以t为0 60 check(buffer, i); 61 j++; 62 } 63 else//当前的页面page[j]不存在于物理块buffer之中 64 { 65 if (i < buffer_size)//如果物理块还没有满的话，直接加一个页面进来，就不进行置换了 66 { 67 buffer[i][0] = page[j]; 68 one_turn(buffer, i); 69 check(buffer, i); 70 i++; //当前物理块中的页面个数加一，因为buffer没满，加到满为止 71 j++; 72 } 73 else//物理块已经满了，进行LRU的查找置换 74 { 75 int temp = max(buffer, buffer_size);//找一个最久没有被调用的页面进行置换 76 buffer[temp][0] = page[j]; 77 one_turn(buffer, buffer_size); 78 buffer[temp][1] = 0;//这个page被置换进来调用一次，所以t为0 79 check(buffer, i); 80 j++; 81 } 82 } 83 } 84 } 85 86 int main() 87 { 88 int page[] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 }; 89 int buffer[3][2]; 90 int n = sizeof(page)/sizeof(int); 91 least_recently_used(buffer, page, 3, 20); 92 }
View Code
三、代码解释
首先主函数调用LRU算法，函数least_recently_used进入函数栈，page的数据来源我会在下面给出例题
1 int main() 2 { 3 int page[] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 }; 4 int buffer[3][2]; 5 int n = sizeof(page)/sizeof(int); 6 least_recently_used(buffer, page, 3, 20); 7 }
View Code
然后调用函数least_recently_used，首先进行对于buffer的初始化，然后进行循环调用页面，当页面全部调用完成时（j >= page_size），算法结束
1 void least_recently_used(int buffer[][2], int page[], int buffer_size, int page_size) 2 { 3 for (int i = 0; i < buffer_size; i++)//初始化buffer 4 { 5 buffer[i][0] = -1; 6 buffer[i][1] = 0; 7 } 8 for(int i = 0, j = 0; j < page_size;)//当页面全部调用完成时（j >= page_size），算法结束 9 { 10 //i是当前物理块中已经有多少页面了，j是已经有多少页面进行过置换了 11 if (exist_page_in_buffer(buffer, page[j], i) != -1 )//当前的页面page[j]已经存在于物理块buffer之中 12 { 13 one_turn(buffer, i); //过了一个调用周期 14 buffer[exist_page_in_buffer(buffer, page[j], i)][1] = 0;//这个page又被调用一次，所以t为0 15 check(buffer, i); 16 j++; 17 } 18 else//当前的页面page[j]不存在于物理块buffer之中 19 { 20 if (i < buffer_size)//如果物理块还没有满的话，直接加一个页面进来，就不进行置换了 21 { 22 buffer[i][0] = page[j]; 23 one_turn(buffer, i); 24 check(buffer, i); 25 i++; //当前物理块中的页面个数加一，因为buffer没满，加到满为止 26 j++; 27 } 28 else//物理块已经满了，进行LRU的查找置换 29 { 30 int temp = max(buffer, buffer_size);//找一个最久没有被调用的页面进行置换 31 buffer[temp][0] = page[j]; 32 one_turn(buffer, buffer_size); 33 buffer[temp][1] = 0;//这个page被置换进来调用一次，所以t为0 34 check(buffer, i); 35 j++; 36 } 37 } 38 } 39 }
View Code
再解释一下每个函数的作用
max，这个就是从buffer里找到最久没用调用过的页面，返回他的所在物理块的位置
1 int max(int arr[][2], int n) 2 { 3 int ans = 0; 4 for (int i = 0; i < n; i++) 5 { 6 if (arr[i][1] > arr[ans][1]) 7 { 8 ans = i; 9 } 10 } 11 return ans; 12 }
View Code
check，检查函数的运行情况
1 void check(int buffer[][2],int n) 2 { 3 for (int i = 0; i < 3; i++) 4 { 5 cout << buffer[i][0] << ' '; 6 } 7 cout << endl << "--------" << endl; 8 }
View Code
exist_page_in_buffer，每次调入页面时，都先检查一遍这个页面有没有已经被调入到当前的物理块中，如果在，返回此页面在物理块中的位置，如果不在，返回-1
1 int exist_page_in_buffer(int buffer[][2], int page, int buffer_size) 2 { 3 for (int i = 0; i < buffer_size; i++) 4 { 5 if (buffer[i][0] == page) 6 { 7 return i; 8 } 9 } 10 return -1; 11 }
View Code
one_turn，过了一个调用周期（主要就是为了让其他的page距离上次被调用的时间t++）
1 void one_turn(int buffer[][2], int i) 2 { 3 for (int k = 0; k < i; k++) 4 { 5 buffer[k][1]++; 6 } 7 }
View Code
四、书上例题和运行结果
运算结果如下
7 -1 -1
——–
7 0 -1
——–
7 0 1
——–
2 0 1
——–
2 0 1
——–
2 0 3
——–
2 0 3
——–
4 0 3
——–
4 0 2
——–
4 3 2
——–
0 3 2
——–
0 3 2
——–
0 3 2
——–
1 3 2
——–
1 3 2
——–
1 0 2
——–
1 0 2
——–
1 0 7
——–
1 0 7
——–
1 0 7
——–