LRU(Least Recently Used)最近未使用置换算法--c实现
2021-03-06 11:28
标签：数据 个数 idt view iostream 来源 class 时间 else 在OS中，一些程序的大小超过内存的大小（比如好几十G的游戏要在16G的内存上跑），便产生了虚拟内存的概念 我们通过给每个进程适当的物理块（内存），只让经常被调用的页面常驻在物理块上，不常用的页面就放在外存，等到要用的时候再从外存调入，从而实现虚拟内存 但是因为给的每个进程的物理块大小不可能是无限的，如果该进程的物理块用完了这时候又要调入新的页面进来的话，就需要用到置换算法，其中的一个算法就叫 ————>LRU(Least Recently Used)最近未使用置换算法 这个算法的思想就是把已经很久没用过的页面，调出物理块然后加入新的准备调入进来的页面，对于每个物理块有两个元素 【页面号丨此页面至上次被访问以来的时间t】 我用了二维数组buffer[][2]来实现，buffer[i][0]表示的是在第i个物理块里的页面号，buffer[i][1]示的是在第i个物理块里的页面号已经有多久没用被调用过了 首先主函数调用LRU算法，函数least_recently_used进入函数栈，page的数据来源我会在下面给出例题 然后调用函数least_recently_used，首先进行对于buffer的初始化，然后进行循环调用页面，当页面全部调用完成时（j >= page_size），算法结束 再解释一下每个函数的作用 max，这个就是从buffer里找到最久没用调用过的页面，返回他的所在物理块的位置 check，检查函数的运行情况 exist_page_in_buffer，每次调入页面时，都先检查一遍这个页面有没有已经被调入到当前的物理块中，如果在，返回此页面在物理块中的位置，如果不在，返回-1 one_turn，过了一个调用周期（主要就是为了让其他的page距离上次被调用的时间t++） 四、书上例题和运行结果 运算结果如下 7 -1 -1 LRU(Least Recently Used)最近未使用置换算法--c实现 标签：数据 个数 idt view iostream 来源 class 时间 else 原文地址：https://www.cnblogs.com/luoyoucode/p/14299906.html一、代码思想
二，全部代码
1 #include
三、代码解释
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 }
1 void least_recently_used(int buffer[][2], int page[], int buffer_size, int page_size)
2 {
3 for (int i = 0; i //初始化buffer
4 {
5 buffer[i][0] = -1;
6 buffer[i][1] = 0;
7 }
8 for(int i = 0, j = 0; j //当页面全部调用完成时（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 //如果物理块还没有满的话，直接加一个页面进来，就不进行置换了
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 }
1 int max(int arr[][2], int n)
2 {
3 int ans = 0;
4 for (int i = 0; i )
5 {
6 if (arr[i][1] > arr[ans][1])
7 {
8 ans = i;
9 }
10 }
11 return ans;
12 }
1 void check(int buffer[][2],int n)
2 {
3 for (int i = 0; i 3; i++)
4 {
5 cout 0] ‘ ‘;
6 }
7 cout "--------" endl;
8 }
1 int exist_page_in_buffer(int buffer[][2], int page, int buffer_size)
2 {
3 for (int i = 0; i )
4 {
5 if (buffer[i][0] == page)
6 {
7 return i;
8 }
9 }
10 return -1;
11 }
1 void one_turn(int buffer[][2], int i)
2 {
3 for (int k = 0; k )
4 {
5 buffer[k][1]++;
6 }
7 }
--------
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
--------
文章标题：LRU(Least Recently Used)最近未使用置换算法--c实现
文章链接：http://soscw.com/index.php/essay/60836.html