muchener's blogs

操作系统LFU算法

字数统计: 647阅读时长: 3 min
2016/11/03 Share

最不经常使用的页面先淘汰(LFU-Least Frequent Used):淘汰到目前为止访问次数最少的页面。对每一页设访问计数器,缺页中断时清零。

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
147
148
#include <stdio.h>
#include <stdlib.h>
//定义外存结构体
typedef struct Extermal{
int data;
struct Extermal* next;

}Ex,*eNode;
//定义内存结构体
typedef struct Intermal{
int data;//页号
int order;//进入顺序
struct Intermal* next;
}In, *iNode;

//外存中页号输入
eNode InputE(int n)
{
int data;
eNode p = NULL, t = NULL;
eNode eHead = (eNode)malloc((sizeof(Ex)));
if (NULL == eHead) {
printf("error\n");
exit(EXIT_FAILURE);
}
eHead->data = 0;
eHead->next = NULL;
t = eHead;
for (int i = 0; i < n; i++) {
p = (eNode)malloc((sizeof(Ex)));
if (NULL == p) {
printf("error\n");
exit(EXIT_FAILURE);
}
scanf("%d",&data);
p->data = data;
p->next = NULL;
t->next = p;
t = p;
}
return eHead;
}
//根据内存页面大小创建内存
iNode CreatiNode(int n)
{
iNode p = NULL, t = NULL;
iNode iHead = (iNode)malloc((sizeof(In)));
if (NULL == iHead) {
printf("error\n");
exit(EXIT_FAILURE);
}
iHead->data = -1;
iHead->next = NULL;
t = iHead;
for (int i = 0; i < n; i++) {
p = (iNode)malloc((sizeof(In)));
if (NULL == p) {
printf("error\n");
exit(EXIT_FAILURE);
}
p->data = -1;//把初始数据值置为-1
p->order = 0;//初始次数都为0
p->next = NULL;
t->next = p;
t = p;
}
return iHead;
}
//输出
void Output(iNode iHead)
{
iNode pt = iHead->next;
while (pt != NULL) {
if (pt->data == -1) {
pt = pt->next;
continue;
}
printf("%d ",pt->data);
pt = pt->next;
}
printf("\n");
}
int LFU_search(int data, iNode ihead, int m,int ni)
{
iNode pt = ihead->next;
int flag = 0;//监控是否存在置换
while (pt != NULL) {
if (pt->data == data) {
flag = 1;
pt->order ++;
break;
}
pt = pt->next;
}
pt = ihead->next;
iNode min = pt;
//存在置换,m计数器+1
if (flag == 0) {
m++;
//查找最小值order,替换data并把order置1
while (pt != NULL) {
if (pt->order < min->order) {
min = pt;
}
pt = pt->next;
}
min->data = data;
min->order = 1;

}
return m;
}

int LFU_run(eNode eHead, iNode ihead,int m,int ni)
{
eNode pt = eHead->next;
int no = 0;
while (pt != NULL) {
m = LFU_search(pt->data,ihead,m,ni);
printf("%d:页面%d置换:",no++,pt->data);
Output(ihead);
pt = pt->next;
}
return m;
}
void LFU()
{
eNode eHead;
iNode iHead;
int ne,ni,m = 0;
//输入外存
printf("输入外存中存储个数:\n");
scanf("%d",&ne);
printf("分别输入所需要的页面,以空格分开\n");
eHead = InputE(ne);
//创建内存
printf("输入内存中有页面的个数\n");
scanf("%d",&ni);
iHead = CreatiNode(ni);
m = LFU_run(eHead, iHead, m,ni);
printf("缺页率为:%f\n",(float)m/ne);

}

int main(int argc, const char * argv[]) {
LFU();
return 0;
}
CATALOG