LRU(Least Recently Used)

  • 出发点：在页式存储管理中，如果一页很长时间未被访问，则它在最近一段时间内也不会被访问，即时间局部性，那我们就把它调出（置换出）内存。
  • 为了实现LRU淘汰算法，需要一些特殊的硬件支持。
  • 三种可行方法
  1. 计数器法
  2. 特殊栈法
  3. 寄存器法

下面给出，栈法的简单演示实现代码：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void conduct(int Size, int Num, int A[100]);//处理函数
 5 void print(int a[], int num);//输出函数
 6 
 7 int main()
 8 {
 9     int stack_size, num, i, acess[100];
10     cout << "输入栈空间：" ;
11     cin >> stack_size;
12     cout << "输入进程数(Max=100):" ;
13     cin >> num;
14 
15     cout << "输入进程访页顺序：" ;
16     for(i=0; i<num; i++)
17     {
18         cin >> acess[i];
19     }
20 
21     conduct(stack_size, num, acess);
22 
23     return 0;
24 }
25 
26 void conduct(int Size, int Num, int A[100])
27 {
28     int j, k, Stack[Size];
29     for(j=0; j<Size; j++)
30     {
31         cout << "进入：" << A[j] <<endl;
32         Stack[j]=A[j];//先处理前几个元素
33     }
34     int locate;bool flag;
35     for(j=Size; j<Num; j++)
36     {
37         flag=false;
38         for(k=0; k<Size; k++)
39         {
40             if(Stack[k]==A[j])
41             {
42                 flag=true;
43                 locate=k;
44             }
45         }
46         if(flag==true)//有重复
47         {
48             cout << "重复进程：" << A[j] <<endl;
49             cout << "取出再压栈" <<endl;
50             int tempp;
51             for(k=locate; k<Size; k++)
52             {
53                 Stack[k]=Stack[k+1];
54             }
55             Stack[Size-1]=A[j];
56             cout << "压栈完成" <<endl;
57             cout << "当前顺序：";
58 
59             print(Stack, Size);
60         }
61         else
62         {
63             cout << "非重复，压栈：" << A[j] <<endl;
64             for(k=0; k<Size-1; k++)
65             {
66                 Stack[k]=Stack[k+1];
67             }
68             Stack[Size-1]=A[j];
69             cout << "置换完成。" <<endl;
70             cout << "当前顺序：";
71             print(Stack, Size);
72         }
73     }
74 }
75 
76 void print(int a[], int num)
77 {
78     int k;
79     for(k=0; k<num; k++)
80     {
81         cout << a[k] << "  ";
82     }
83     cout << endl;
84 }
　　Code：：Blocks 17.12 运行通过！

 运行截图：