虚拟内存页面置换算法（操作系统）_页面置换算法模拟实验内容和步骤

作者：知新_RL | 2024-02-29 03:19:24

踩

页面置换算法模拟实验内容和步骤

虚拟内存页面置换算法

1.实验目的

通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。

2.实验内容

问题描述：
设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
程序要求：
1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率。
实现提示：
用C++语言实现提示：
1）程序中变量定义参考（根据需要可添加）如下：
const int MaxNumber=100;
int PageOrder[MaxNumber];
int Simulate[MaxNumber][MaxNumber];
int PageCount[MaxNumber];
int PageNum,LackNum;
double LackPageRate;
bool found;
2）页面置换的实现过程如下：
变量初始化；
接收用户输入最小物理块数m，页面个数n，页面序列P1, … ,Pn，选择算法1-FIFO，2-OPI，3-LRU；
根据用户选择的算法进行页面的分配和置换，输出页面置换算法的模拟过程；
计算选择算法的缺页次数和缺页率；
输出选择算法的缺页次数和缺页率。

3.程序主要构成部分及其算法说明

1.初始化
先将后续用到的各种变量和数组进行初始化，之后开始为初始为空的物理块分配页面至物理块被填满，分配时先使用两个for循环判断页面是否已经在物理块内，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，将该页面加入物理块中，相应的变量进行改变（时间复杂度为O（n3）），直到物理块被填满。

void initial(){ 
    int i,j,k;
    int z=0; 
    bool found;
    LackPageNum = BlockNum; 
    LackPageRate = 0.0;
    for(int i = 0;i<PageNum;i++){
        PageCount[i] = 0; 
        VirtualQueue[i] = -1;  
    }
    for(int i=0;i<BlockNum;i++){
        for (int j=0;j<PageNum;j++){
            Simulate[i][j]=-1; 
        }
    }
    for (int i = 0;i<PageNum;i++){ 
        found = false;
        timeOfLRU[i] = 0;
        for (int j = 0;j<BlockNum;j++){
            if (VirtualQueue[j] == PageOrder[i]) 
               {
                found = true;
               }
        }
        if (!found){ 
            VirtualQueue[z] = PageOrder[i]; 
            for(int j=0;j<=z;j++){
            Simulate[j][i]=VirtualQueue[j]; 
            }
            z++;
            for (int k = 0;k<i;k++){
                timeOfLRU[k]++;  
            }
        }
        else{
            timeOfLRU[i] = 0;  
        }
        if(z==BlockNum){ 
            break;
           }
    }
}
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

2.FIFO
首先调用初始化方法将物理块填满，并设置一个指针point，使它总是指向最老的页面，然后从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，缺页数+1，并且替换到物理块中最老的页面，改变point的值，使其指向新队列中最老的页面（时间复杂度为O（n3））。

void FIFO(){
	cout<<"当前选择的算法:FIFO"<<endl;
    initial();
	int i,j,k;
    int point = 0;
    for (int i = BlockNum;i<PageNum;i++){
        found = false;
        for (int k = 0;k<BlockNum;k++){
            if (VirtualQueue[k] == PageOrder[i]){ 
                found = true;
            }
        }
        if (!found){  
            LackPageNum++; 
            VirtualQueue[point] = PageOrder[i]; 
             for(int j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j]; 
            }
            point++; 
            if (point == BlockNum) 
                point = 0;
        }
    }
    output();
    LackPageRate = (LackPageNum * 1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;
}
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

3.OPI
首先调用初始化方法将物理块填满，并设置变量distance用于保存物理块内页面下次被访问的距离和一个指针point，使它指向最远距离的物理块页面，然后从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，则直接遍历下一个页面（时间复杂度为O（n²）），如果不存在，缺页数+1，分别计算每个物理块的距离，之后让point指向距离最远的页面，然后替换物理块中距离最远的页面（时间复杂度为O（n4））。

void OPI(){
	cout<<"当前选择的算法:OPI"<<endl;
    int i,j,s,k,m,t;
    initial();
    int distance;  
    int point;  
 
    for(i = BlockNum;i<PageNum;i++){
        found = false;
        for (k = 0;k<BlockNum;k++){
            if (VirtualQueue[k] == PageOrder[i]){ 
                found = true;
            }
        }
        if (!found){
            LackPageNum++;
            for (s = 0;s < BlockNum;s++){
                distance = 1;
                for (t = i;t<PageNum;t++){   
                    if (VirtualQueue[s] != PageOrder[t])
                        distance++;
                    else
                        break;
                }
                PageCount[s] = distance; 
            }
            point = 0;
            for (m = 1;m < BlockNum;m++){
                if (PageCount[point] < PageCount[m])
                    point = m;
            }
            VirtualQueue[point] = PageOrder[i];
            for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j]; 
            }
        }
    }
    output();
    LackPageRate = (LackPageNum*1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;
}
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

4.LRU
首先调用初始化方法将物理块填满，设置一个指针point，使其指向最近最久未使用的页面。从未分配的页面处开始分配，算法与初始化方法中的算法类似，如果已经存在，命中的页面时间归0，其余页面时间+1，再遍历下一个页面（时间复杂度为O（n3）），如果不存在，缺页数+1，比较得到队列中最近最久未被访问的页面，让point指向该页面，再让其余的页面时间+1，再替换该页面，该页面时间为0（时间复杂度为O（n3））。

void LRU(){
	cout<<"当前选择的算法:LRU"<<endl;
    int i,j,s,k; 
    initial();
    int point; 
 
    for(i = BlockNum;i<PageNum;i++){
        found = false;
        for (k = 0;k<BlockNum;k++){
            if (VirtualQueue[k] == PageOrder[i])   
                  found = true;
        }
        if (!found){
            LackPageNum++;
            point = 0;
            for (j = 1;j<BlockNum;j++){
                if (timeOfLRU[point]<timeOfLRU[j])
                    point = j;
            }
 
            for (s = 0;s<BlockNum;s++){
                if (VirtualQueue[s] != VirtualQueue[point])
                    timeOfLRU[s]++;
            }
            VirtualQueue[point] = PageOrder[i];
              for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=VirtualQueue[j]; 
            }
            timeOfLRU[point] = 0;
        }
        else{   
            for (s = 0;s<BlockNum;s++){
                if (VirtualQueue[s] != PageOrder[i])
                    timeOfLRU[s]++;
                else
                    timeOfLRU[s] = 0;
            }
    }
    }
    output();
    LackPageRate = (LackPageNum*1.0)/PageNum;
    cout<<"LackPageNum: "<<LackPageNum<<endl;
    cout<<"LackPageRate: "<<LackPageRate<<endl;
}
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

4.运行结果

1.首先输入物理块数，页面个数和页面序列，之后程序输出对应的数据验证，并提示选择算法
在这里插入图片描述

2.输入对应的数字程序执行对应的算法，并打印输出页面置换算法的模拟过程，输出选择算法的缺页数和缺页率。

在这里插入图片描述

5.程序源码

#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdlib.h>
using namespace std;
 
#define MaxNumber 100
int PageOrder[MaxNumber];  //页面序列
int Simulate[MaxNumber][MaxNumber];//存放输出的数组 
int PageCount[MaxNumber]; //当前内存距离下一次出现的距离
int BlockNum;//物理块数
int PageNum; //页面个数
int LackNum; //缺页数 
double  LackPageRate;   //缺页率
bool found; //页面是否命中 
int timeOfLRU[MaxNumber];   //记录物理块中各个页面最近使用时间 
int memoryPage[MaxNumber];   //虚拟队列
int choose;

void input();  //输入
void initial();  //初始化物理块
void FIFO();    
void OPI();     
void LRU();   
void chooseAlgorithm();//选择算法
void output(); //输出 


int main(){
    input();
   	chooseAlgorithm();
    return 0;
}
 
void input(){
 	ifstream readData;
	readData.open("data.txt");
	readData>>BlockNum;
	readData>>PageNum;
	for (int i=0;i<PageNum;i++)
	{
		readData>>PageOrder[i];
	}
	
	cout<<"最小物理块数 = "<<BlockNum<<endl;
	cout<<"页面个数 = "<<PageNum<<endl;
	cout<<"页面序列:"<<endl;
	for (int i = 0;i<PageNum;i++)
	{
		cout<<PageOrder[i]<<" ";
	}
	cout<<endl;
}
 
void initial(){//初始化 
    int i,j,k;
    int z=0;	//判断初始化物理块是否填满
    bool found;
    LackNum = BlockNum;//缺页数=物理块数+缺页次数
    LackPageRate = 0.0;
 
    for(int i = 0;i<PageNum;i++){
        PageCount[i] = 0;  //初始化距离
        memoryPage[i] = -1;  //初始化队列
    }
    for(int i=0;i<BlockNum;i++){
        for (int j=0;j<PageNum;j++){
            Simulate[i][j]=-1;//初始化
        }
    }
 
    for (int i = 0;i<PageNum;i++){//初始化物理块
        found = false;
        timeOfLRU[i] = 0;
        for (int j = 0;j<BlockNum;j++){
            if (memoryPage[j] == PageOrder[i])//页面命中
               {
                found = true;
               }
        }          
        if (!found){  //当有新的进程进入到队列时，便计算其对应的距离
            memoryPage[z] = PageOrder[i];//小于物理块数时，页面顺序进入队列
            for(int j=0;j<=z;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值
            }
            z++;
            for (int k = 0;k<i;k++){
                timeOfLRU[k]++;   //之前的页面对应的时间+1
            }
        }
        else{
            timeOfLRU[i] = 0;  //重新更新为0，表示最近刚刚使用
        }
        if(z==BlockNum){ //物理块被填满，结束循环 
            break;
           }
    }
}
 
void FIFO(){
	cout<<"当前选择的算法:FIFO"<<endl;
    initial();
	int i,j,k;
    int point = 0;
	//分配内存
    for (int i = BlockNum;i<PageNum;i++){
        found = false;
        for (int k = 0;k<BlockNum;k++){
            if (memoryPage[k] == PageOrder[i]){   //页面命中
                found = true;
            }
        }
 
        if (!found){   //如果页面不在队列中，则进行相应的处理
            LackNum++;  //缺页数加1
            memoryPage[point] = PageOrder[i];//页面替换队列中最老的
            for(int j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值
            }
            point++;//后移
            if (point == BlockNum)//当指向队尾时后，重新指向队首
                point = 0;
        }
    }
    output();//输出物理块状态
    LackPageRate = (LackNum * 1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;
}

void OPI(){
	cout<<"当前选择的算法:OPI"<<endl;
    int i,j,s,k,m,t;
    initial();
    int distance;   //表示队列每个值距离下一次访问的距离
    int point;  //指向最长时间未被访问的下标
 
    for(i = BlockNum;i<PageNum;i++){
        found = false;
        for (k = 0;k<BlockNum;k++){
            if (memoryPage[k] == PageOrder[i]){  //页面命中
                found = true;
            }
        }
        if (!found){
            LackNum++;
            //计算当前队列每一页对应的下一次出现的距离
            for (s = 0;s < BlockNum;s++){
                distance = 1;
                for (t = i;t<PageNum;t++){   //向后找离他最远的
                    if (memoryPage[s] != PageOrder[t])
                        distance++;
                    else
                        break;
                }
                PageCount[s] = distance;//当前内存距离下一次出现的距离
            }
            //向后比较队列内最长时间不被访问的并淘汰，置换页面
            point = 0;
            for (m = 1;m < BlockNum;m++){
                if (PageCount[point] < PageCount[m])
                    point = m;
            }
            memoryPage[point] = PageOrder[i];
            for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值
              }
        }
    }
    output();
    LackPageRate = (LackNum*1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;
}
 
void LRU(){
	cout<<"当前选择的算法:LRU"<<endl;
    int i,j,s,k; 
    initial();
    int point;//指向最长时间未被访问的下标
 
    for(i = BlockNum;i<PageNum;i++){
        found = false;
        for (k = 0;k<BlockNum;k++){
            if (memoryPage[k] == PageOrder[i])   //页面命中
                  found = true;
        }
 
        if (!found){
            LackNum++;
            //向前比较队列内最长时间不被访问的并淘汰，置换页面
        	point  = 0;
        	for(j = 1;j<BlockNum;j++){
        		if (timeOfLRU[point]<timeOfLRU[j])
		            point = j;
            }
 
            for (s = 0;s<BlockNum;s++){//其余页面对应的时间要+1
                if (memoryPage[s] != memoryPage[point])
                    timeOfLRU[s]++;                            
            }
            
            memoryPage[point] = PageOrder[i];
            for(j=0;j<=BlockNum;j++){
            Simulate[j][i]=memoryPage[j];//保存当前序列的值
            }
            timeOfLRU[point] = 0;
        } 
        
        else{   //负责更新当前对应页面的时间
            for (s = 0;s<BlockNum;s++){//其余页面对应的时间要+1
                if (memoryPage[s] != PageOrder[i])
                    timeOfLRU[s]++;
                else
                    timeOfLRU[s] = 0;
            }
        }
    }
    output();
 
    LackPageRate = (LackNum*1.0)/PageNum;
    cout<<"缺页数：: "<<LackNum<<endl;
    cout<<"缺页率：: "<<LackPageRate<<endl;
}
 
void chooseAlgorithm()
{
	cout<<"请选择算法“1-先进先出(FIFO)页面置换算法，2-最佳(Optimal)置换算法，3-最近最久未使用(LRU)页面置换算法，0-结束”"<<endl;
	cin>>choose;
	cout<<endl;
	if (choose==1)
	{
		FIFO();
		chooseAlgorithm();
	}
		else if(choose==2)
		{
			OPI();
			chooseAlgorithm();
		}
		else if(choose==3){
            LRU();
            chooseAlgorithm();
		}
 
		else if(choose==0){
          exit(0);
		}
	else
	{
		cout<<"输入错误“1-首次适应算法FF，2-循环首次适应算法NF，3-最佳适应算法BF，4-最坏适应算法WF，0-退出”"<<endl;
		chooseAlgorithm();  
	}
}

void output(){
    int i,j;
    for(i=0;i<PageNum;i++){
        cout<<PageOrder[i]<<"  ";
    }
    cout<<endl;
    for(i=0;i<BlockNum;i++){
        for(j=0;j<PageNum;j++){
                if(Simulate[i][j]==-1){
                    cout<<"   ";
                }else{
            cout<<"  "<<Simulate[i][j];
        }
        }
        cout<<endl;
    }
}
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

输入数据格式

3
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
1
2
3

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/163447