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
149
150
151
152
153
154
155
156
157
158
159
160
| #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 = i;//初始顺序为1 2 3 ……
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 LRU_search(int data, iNode ihead, int m,int ni)
{
iNode pt = ihead->next;
int flag = 0;//监控是否存在置换
int temp = 0;
while (pt != NULL) {
if (pt->data == data) {
flag = 1;
temp = pt->order;
pt->order = ni;
break;
}
pt = pt->next;
}
pt = ihead->next;
//存在置换，m计数器+1
if (flag == 0) {
m++;
//刷新页面顺序，最新置换的页面为页面最大数，确保下次置换掉的事order=0的页面
while (pt != NULL) {
if (pt->order == 0) {
pt->data = data;
pt->order = ni -1;
}
else{
pt->order --;
}
pt = pt->next;
}
}
//不存在页面置换时，更新页面最近访问
else
{
while (pt != NULL) {
if (pt->order>temp) {
pt->order--;
}
pt = pt->next;
}
}
return m;
}
int LRU_run(eNode eHead, iNode ihead,int m,int ni)
{
eNode pt = eHead->next;
int no = 0;
while (pt != NULL) {
m = LRU_search(pt->data,ihead,m,ni);
printf("%d:页面%d置换:",no++,pt->data);
Output(ihead);
pt = pt->next;
}
return m;
}
void LRU()
{
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 = LRU_run(eHead, iHead, m,ni);
printf("缺页率为：%f\n",(float)m/ne);
}
int main(int argc, const char * argv[]) {
LRU();
return 0;
}
|
