专注app软件定制开发操作系统实验

专注app软件定制开发页面置换算法（、LRU、OPT）

概念：

1.专注app软件定制开发最佳置换算法（OPT）（专注app软件定制开发理想置换算法）：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。
2.先进先出置换算法（FIFO）：是最简单的页面置换算法。这种算法的基本思想是：当需要淘汰一个页面时，总是选择驻留主存时间最长的页面进行淘汰，即先进入主存的页面先淘汰。其理由是：最早调入主存的页面不再被使用的可能性最大。
3．最近最久未使用（LRU）算法：这种算法的基本思想是：利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

题目：

编写一个程序，实现本章所述的FIFO、LRU和最优页面置换算法。首先，生成一个随机的页面引用串，其中页码范围为0-9.将这个随机页面引用串应用到每个算法，并记录每个算法引起的缺页错误的数量。实现置换算法，一遍页面帧的数量可以从1~7。

代码

#include <stdio.h>#include <stdlib.h>#include <time.h>int numbers[20]={7,0,1,2,                 0,3,0,4,                 2,3,0,3,                 2,1,2,0,                 1,7,0,1};//本地数据，与课本一致，方便测试int nums=0;//输入栈的个数，为了方便使用，int stack[20][7]={10};void begin();void randomnum();//用于产生随机数void init();//初始化void FIFO();//FIFO算法void LRU();//LRU算法void OPT();//最优页面置换算法（OPT）void print();//输出int main() {    begin();    FIFO();    LRU();    OPT();    return 0;}void begin()//开始菜单界面{    int i,j,k;    printf("请输入页面帧的数量(1-7)：");    scanf("%d",&nums);    for(k=0;;k++)    {        printf("是否使用随机数产生输入串（0：是，1：否）");        scanf("%d",&j);        if(j==0)        {            randomnum();            break;        }        else if(j==1)        {            break;        }        else        {            printf("请输入正确的选择！\");        }    }    printf("页面引用串为：\");    for(i=0;i<20;i++)    {        printf("%d  ",numbers[i]);    }    printf("\");    init();}void randomnum()//如果需要使用随机数生成输入串，调用该函数{    srand(time(0));//设置时间种子    for(int i = 0; i < 20; i++) {        numbers[i] = rand() % 10;//生成区间0`9的随机页面引用串    }}void init()//用于每次初始化页面栈中内容，同时方便下面输出的处理{    int i,j;    for(i=0;i<20;i++)        for(j=0;j<nums;j++)            stack[i][j]=10;}void print()//输出各个算法的栈的内容{    int i,j;    for(i=0;i<nums;i++)    {        for(j=0;j<20;j++)        {            if(stack[j][i]==10)                printf("*  ");            else                printf("%d  ",stack[j][i]);        }        printf("\");    }}void FIFO()//FIFO算法{    init();    int i,j=1,n=20,k,f,m;    stack[0][0]=numbers[0];    for(i=1;i<20;i++)    {        f=0;        for(m=0;m<nums;m++)        {            stack[i][m]=stack[i-1][m];        }        for(k=0;k<nums;k++)        {            if(stack[i][k]==numbers[i])            {                n--;                f=1;                break;            }        }        if(f==0)        {            stack[i][j]=numbers[i];            j++;        }        if(j==nums)            j=0;    }    printf("\");    printf("FIFO算法：\");    print();    printf("缺页错误数目为：%d\",n);}void LRU()//LRU算法{    int i,j,m,k,sum=1,f;    int sequence[7]={0};//记录序列    init();    stack[0][0]=numbers[0];    sequence[0]=nums;    for(i=1;i<nums;i++)//前半部分，页面空置的情况    {        for(j=0;j<nums;j++)        {            stack[i][j]=stack[i-1][j];        }        for(j=0;j<nums;j++)  //判断要插入的是否在栈中已经存在        {            f=0;            if(stack[i][j]==numbers[i])            {                f=1;                sum--;                sequence[j]=nums;                break;            }        }        for(j=0;j<nums;j++)        {            if(sequence[j]==0&&f==0)            {                stack[i][j]=numbers[i];                sequence[i]=nums;//最近使用的优先级列为最高                break;            }        }        for(j=0;j<i;j++)//将之前的优先级序列都减1        {            if(sequence[j]!=0)               sequence[j]--;        }        //sequence[i]=nums;        sum++;    }    for(i=nums;i<20;i++)//页面不空，需要替换的情况    {        int f;        f=0;        for(j=0;j<nums;j++)        {            stack[i][j]=stack[i-1][j];        }        for(j=0;j<nums;j++)//判断输入串中的数字，是否已经在栈中        {            if(stack[i][j]==numbers[i])            {                f=1;                k=j;                break;            }        }        if(f==0)//如果页面栈中没有，不相同        {            for(j=0;j<nums;j++)//找优先序列中为0的            {                if(sequence[j]==0)                {                    m=j;                    break;                }            }            for(j=0;j<nums;j++)            {                sequence[j]--;            }            sequence[m]=nums-1;            stack[i][m]=numbers[i];            sum++;        }        else//如果页面栈中有，替换优先级        {           if(sequence[k]==0)//优先级为最小优先序列的           {               for(j=0;j<nums;j++)               {                   sequence[j]--;               }               sequence[k]=nums-1;           }           else if(sequence[k]==nums-1)//优先级为最大优先序列的           {               //无需操作           }           else//优先级为中间优先序列的           {               for(j=0;j<nums;j++)               {                   if(sequence[k]<sequence[j])                   {                       sequence[j]--;                   }               }               sequence[k]=nums-1;           }        }    }    printf("\");    printf("LRU算法：\");    print();    printf("缺页错误数目为：%d\",sum);}void OPT()//OPT算法{    int i,j,k,sum=1,f,q,max;    int seq[7]={0};//记录序列    init();    stack[0][0]=numbers[0];    seq[0]=nums-1;    for(i=1;i<nums;i++)//前半部分，页面空置的情况    {        for(j=0;j<nums;j++)        {            stack[i][j]=stack[i-1][j];        }        for(j=0;j<nums;j++)  //判断要插入的是否在栈中已经存在        {            f=0;            if(stack[i][j]==numbers[i])            {                f=1;                sum--;                //b++;                seq[j]=nums;                break;            }        }        for(j=0;j<nums;j++)        {            if(seq[j]==0&&f==0)            {                stack[i][j]=numbers[i];                seq[j]=nums;//最近使用的优先级列为最高                break;            }//            else if(seq[j]==0&&f==1){//                b++;//                sum--;//                seq[j]=nums-1;//                break;//            }        }        for(j=0;j<nums;j++)//将之前的优先级序列都减1        {            if(seq[j]!=0)               seq[j]--;        }        sum++;    }    for(i=nums;i<20;i++)//后半部分，页面栈中没有空的时候情况    {        //k=nums-1;//最近的数字的优先级        for(j=0;j<nums;j++)//前面的页面中内容赋值到新的新的页面中        {            stack[i][j]=stack[i-1][j];        }        for(j=0;j<nums;j++)        {            f=0;            if(stack[i][j]==numbers[i])            {                f=1;                break;            }        }        if(f==0)//页面中没有，需要替换的情况        {            for(q=0;q<nums;q++)//优先级序列中最大的就是最久不会用的，有可能出现后面没有在用过的情况            {                seq[q]=20;            }            for(j=0;j<nums;j++)//寻找新的优先级            {                for(q=i+1;q<20;q++)                {                    if(stack[i][j]==numbers[q])                    {                        seq[j]=q-i;                        break;                    }                }            }            max=seq[0];            k=0;            for(q=0;q<nums;q++)            {                if(seq[q]>max)                {                    max=seq[q];                    k=q;                }            }            stack[i][k]=numbers[i];            sum++;        }        else        {            //页面栈中有需要插入的数字，无需变化，替换的优先级也不需要变化        }    }    printf("\");    printf("OPT算法：\");    print();    printf("缺页错误数目为：%d\",sum);}
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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346

运行结果截图：

总结

设置多个数组，一个用来模仿栈，一个用来存要存取的页面，还有在OPT算法和LRU算法中，记录栈中每个数据的替换优先级。
之前的代码写的有点烂，重新看了一次才感觉之前的有多烂，哈哈哈哈哈，这个代码能在linux上跑通的，在windows上肯定也没得问题