LRU算法(LRU Algorithm)

Posted on Edited on Word count in article: 3.4k Reading time ≈ 3 mins.

This is famous LRU algorithm. It is used to improve cache hit rate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//LRU algorithm
//author:chillyCreator
//in the page_information, the bigger number means the newer page.
//if the number in the page_information is -1, it means no page is in this position. 
#include<iostream>
using namespace std;
bool isNotIn(int p_page_num);
bool isNotFull(int& position);
void insert(int p_page_num,int position);
int delOldPage();
const int MAX_INT = 32767;
int process_num;//the total number of process pages
int page_size;//the total number of pages
int page_num=0;//the number of page which in the page array 
int miss=0;//
int* page_information;//the page information array
int* page;//the page array
int old=0;//how old is a page?
int main()
{
 cout << "how many pages of processes ?"<<endl;
 cin >> process_num ;
 cout << "how many pages in the memory?"<<endl; 
 cin >> page_size;
 page_information = new int[page_size];
 page = new int[page_size];
 int i;
 for(i=0; i<page_size; i++)
 { 
  page[i] = -1;
  page_information[i] = -1;
 }
 int user_test;
 cout << "input 1 is user test, 2 is auto test"<<endl;
 cin >> user_test;
 switch(user_test)
 {
 case 1:
  for(i=0; i < process_num; i++)
  {
   int process_page_num;
   cin >> process_page_num;
   cout <<"input process page num is :" <<process_page_num<<endl;
   if(isNotIn(process_page_num))
   {
    miss++;
    int temp_position;
    if(isNotFull(temp_position))
    { 
     insert(process_page_num,temp_position);
     page_num++;
    }
    else
    {
     temp_position = delOldPage();
     insert(process_page_num,temp_position);
    }
   }
  }
 break;
 default:
  for(i=0; i < process_num; i++)
  {
   int process_page_num = rand();
   cout << process_page_num<<endl;
   if(isNotIn(process_page_num))
   {
    miss++;
    int temp_position;
    if(isNotFull(temp_position))
    { 
     insert(process_page_num,temp_position);
     page_num++;
    }
    else
    {
     temp_position = delOldPage();
     insert(process_page_num,temp_position);
    }
   }
  }
  break;
 }
 cout <<"miss is " <<miss << "/t the total process num is "<<process_num<<endl;
 cout << endl;
 cout <<"the miss percentage is miss/process_num = "<<double(miss)/process_num<<endl;
 return 0;
}
//the process page is in the page array?;
bool isNotIn(int p_page_num)
{
 for(int i=0; i<page_size; i++)
 {
  if(page[i]==p_page_num)
   return false;
 }
 return true;
}
//the page array is full or not.
//and return the empty position
bool isNotFull(int& position)
{
 if(page_size <= page_num)
  return false;
 int i;
 for(i=0; i<page_size; i++)
 {
  if(page_information[i]==-1)
   break;
 }
 position = i;
 return true;
}
//insert a process page to the page in an empty position.
//and the function protect the primite: old from flowover error. 
void insert(int p_page_num,int position)
{
  old++;
  if(old==MAX_INT)
  { 
   old = 1;
   for(int i=0; i<page_size; i++)
   {
    if(page_information[i]!=-1)
     page_information[i] = old;
   }
  }
  old++;
  page[position] = p_page_num;
  page_information[position] = old;
}
int delOldPage()
{
 int i;
 int min=page_information[0],min_i=0;
 for(i=1; i<page_size; i++)
 {
  if(min > page_information[i])
  {
   min = page_information[i];
   min_i = i;
  }
 }
 return min_i;
}