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
| #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 FIFO_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;
break;
}
pt = pt->next;
}
//存在置换时，将order为1的页面置换掉，然后将这个order置为页面数，然后其他order-1
if (flag == 0) {
m++;
pt = ihead->next;
while (pt != NULL) {
if (pt->order == 0) {
pt->data = data;
pt->order = ni -1;
}
else{
pt->order --;
}
pt = pt->next;
}
}
return m;
}
int FIFO_run(eNode eHead, iNode ihead,int m,int ni)
{
eNode pt = eHead->next;
int no = 0;
while (pt != NULL) {
m = FIFO_search(pt->data,ihead,m,ni);
printf("%d:页面%d置换:",no++,pt->data);
Output(ihead);
pt = pt->next;
}
return m;
}
void FIFO()
{
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 = FIFO_run(eHead, iHead, m,ni);
printf("缺页率为：%f\n",(float)m/ne);
}
int main(int argc, const char * argv[]) {
FIFO();
return 0;
}
|
