内存页面置换算法
一个问题
示例实验在编译时可能会报错，因为示例实验使用cpp写的所以要用g++编译，有的Linux可能没有g++编译器
1
| make: g++: Command not found
|
解决方法：装一个呗
1
| sudo apt-get install g++
|
独立实验
Clock
逻辑
使用PageChances数组维护对应页的机会。
每当找到一页已经存在的页，则给该页的机会加一。若该页不存在，则遍历页列表找可以牺牲的页，检查这些页的引用位，如果引用位为 0 则直接置换该页，否则将引用位清零并给该页第二次机会。之后准备换出下一个 FIFO 页。
这里要注意存在的一个问题，可能存在一次遍历找不到可以牺牲的页的情况，需要维护一个布尔值标志是否完成了替换并使用while进行循环。
代码
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
| void Replace::Clock(void){
int i,j,k,next;
InitSpace("CLOCK");
for(k = 0,j =FrameNumber; k < PageNumber; k++) {
bool changed = false;
next = ReferencePage[k];
for(i = 0; i < FrameNumber; i++)
if(next == PageFrames[i]) {
PageChances[i]++;
break;
}
if(i < FrameNumber) {
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
cout << endl;
continue;
}
FaultNumber++;
if (j>0){
for (int m = 0; m < FrameNumber; ++m) {
if (PageFrames[m] == -1){
PageFrames[m] = next;
PageChances[m] = 1;
j--;
break;
}
}
} else{
while (!changed){
for (int m = 0; m < FrameNumber; ++m) {
if (PageChances[m] == 0){
EliminatePage[0] = PageFrames[m];
PageFrames[m] = next;
PageChances[m] = 1;
changed = true;
break;
} else{
PageChances[m] = 0;
}
}
}
}
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
if(EliminatePage[0] >= 0)
cout << "->" << EliminatePage[0] << endl;
else
cout << endl;
}
Report();
}
|
EClock
增强型二次机会（Enhanced Second-Chance） 算法：将引用位和修改位作为一对考虑以改进二次机会算法，这两个位可能有四种类型：(0, 0) 表示最近没有使用也没有修改（最佳置换页）；(0, 1) 表示最近没有使用但已修改（若置换则需要写入到磁盘）；(1, 0) 表示最近使用但尚未修改（此页可能很快会被使用）；(1, 1) 表示最近使用且已经被修改（此页可能很快会被使用并且如果置换需要写入磁盘）。这种方法给已经修改过的页更高的级别，降低了 I/O 操作数量。但找到要置换的页之前，可能需要搜索循环队列多次，每次将级别升高一级并寻找满足的页面。
逻辑
首先，做一些约定：对于PageChances的存储，0=(0,0),1=(0,1),2=(1,0),3=(1,1)。
每当找到一页已经存在的页，则给该页的机会为1或2（(0,1)或(1,0)），则将该页的机会位置为3（(1,1)），若该页机会位为0，则置为2（(1,0)，认为会先读，后写）。
若该页不存在，则遍历页列表找可以牺牲的页，检查这些页的引用位，如果引用位为 0 则直接置换该页，否则将引用位做出如下改变并给该页第二次机会：将(1,0)或(0,1)改为(0,0)，将(1,1)改为(0,1)。之后准备换出下一个 FIFO 页。
这里要注意存在的一个问题，可能存在一次遍历找不到可以牺牲的页的情况，需要维护一个布尔值标志是否完成了替换并使用while进行循环。
代码
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
| void Replace::Eclock (void){
int i,j,k,next;
InitSpace("ECLOCK");
for(k = 0,j =FrameNumber; k < PageNumber; k++) {
bool changed = false;
next = ReferencePage[k];
for(i = 0; i < FrameNumber; i++)
if(next == PageFrames[i]) {
if(PageChances[i] == 2 || PageChances[i] == 1){
PageChances[i] = 3;
} else if(PageChances[i] == 0){
PageChances[i] = 2;
}
break;
}
if(i < FrameNumber) {
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
cout << endl;
continue;
}
FaultNumber++;
if (j>0){
for (int m = 0; m < FrameNumber; ++m) {
if (PageFrames[m] == -1){
PageFrames[m] = next;
PageChances[m] = 2;
j--;
break;
}
}
} else{
while (!changed){
for (int m = 0; m < FrameNumber; ++m) {
if (PageChances[m] == 0 && !changed){
EliminatePage[0] = PageFrames[m];
PageFrames[m] = next;
PageChances[m] = 2;
changed = true;
}else if (PageChances[m] == 1 || PageChances[m] == 2){
PageChances[m] = 0;
}else if (PageChances[m] == 3){
PageChances[m] = 1;
}
}
}
}
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
if(EliminatePage[0] >= 0)
cout << "->" << EliminatePage[0] << endl;
else
cout << endl;
}
Report();
}
|
LFU
逻辑
为每页的条目保留一个引用次数的计数器，该计数器通过Map实现，若存在该页，则级数加一，否则置换计数最小的页，且每个页初始调入时引用次数为一。
一个细节，寻找最小计数的minCount初始化为引用页数，因为总引用数一定小于这一值。
代码
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
| void Replace::Lfu(void){
CountingsMap.clear();
int i,j,k,next;
InitSpace("LFU");
for(k = 0,j = FrameNumber; k < PageNumber; k++) {
int minCount = PageNumber;
int minIndex = 0;
next = ReferencePage[k];
for(i = 0; i < FrameNumber; i++)
if(next == PageFrames[i]){
CountingsMap[next]++;
break;
}
if(i < FrameNumber) {
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
cout << endl;
continue;
}
FaultNumber++;
if (j>0){
for (int m = 0; m < FrameNumber; ++m) {
if (PageFrames[m] == -1){
PageFrames[m] = next;
CountingsMap[next] = 1;
j--;
break;
}
}
} else {
for (int m = 0; m < FrameNumber; ++m) {
if (minCount > CountingsMap[PageFrames[m]]){
minCount = CountingsMap[PageFrames[m]];
minIndex = m;
}
}
CountingsMap[next]++;
EliminatePage[0] = PageFrames[minIndex];
PageFrames[minIndex] = next;
}
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
if(EliminatePage[0] >= 0)
cout << "->" << EliminatePage[0] << endl;
else
cout << endl;
}
Report();
}
|
MFU
代码
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
| void Replace::Mfu(void){
CountingsMap.clear();
int i,j,k,next;
InitSpace("MFU");
for(k = 0,j = FrameNumber; k < PageNumber; k++) {
int maxCount = 0;
int maxIndex = 0;
next = ReferencePage[k];
for(i = 0; i < FrameNumber; i++)
if(next == PageFrames[i]){
CountingsMap[next]++;
break;
}
if(i < FrameNumber) {
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
cout << endl;
continue;
}
FaultNumber++;
if (j>0){
for (int m = 0; m < FrameNumber; ++m) {
if (PageFrames[m] == -1){
PageFrames[m] = next;
CountingsMap[next] = 1;
j--;
break;
}
}
} else {
for (int m = 0; m < FrameNumber; ++m) {
if (maxCount<CountingsMap[PageFrames[m]]){
maxCount = CountingsMap[PageFrames[m]];
maxIndex = m;
}
}
CountingsMap[next]++;
EliminatePage[0] = PageFrames[maxIndex];
PageFrames[maxIndex] = next;
}
for(i = 0; i < FrameNumber; i++)
if(PageFrames[i] >= 0)
cout << PageFrames[i] << " ";
if(EliminatePage[0] >= 0)
cout << "->" << EliminatePage[0] << endl;
else
cout << endl;
}
Report();
}
|
