当前位置:   article > 正文

存储管理之虚拟存储器实现(页面置换算法的模拟)

存储管理之虚拟存储器实现

页面置换算法

先进先出算法(FIFO): 先进先出算法是最简单的分页替换算法,是指每次有新的分页需要调入时,会选择调入内存时间最久的分页换出。它简单,容易实现,但这种绝对的公平方式容易导致效率的降低。
--------发生缺页中断时,即最先进来的淘汰出去
在这里插入图片描述

最近最久未使用算法(LRU)算法: 即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的。即最近最少使用的页面予以淘汰。
--------发生缺页中断时,选择未使用时间最长的页面置换出去
在这里插入图片描述
最佳置换算法(OPT): 这是一种理想情况下的页面置换算法,但实际上是不可能实现的。
--------发生缺页中断时,看后面在物理块中的页面序列,查看谁出现的最晚,谁被淘汰。

大家可以做几道例题就基本理解了。

以下是这三种算法的模拟,使用的是队列存储和set进行查询;对于效率不是特别好,只是一个基本的模拟
要求: 设计主界面以灵活选择某算法。2.用随机数方法产生页面走向。3.假定初始时页面都不在内存。

内容: 编程序实现先进先出算法(FIFO)、最近最久未使用算法(LRU)算法、最佳置换算法(OPT)的具体实现过程,并计算访问命中率。
代码如下:

#include<bits/stdc++.h>
using namespace std;

vector<int> a;	//随机数产生的页面走向 
queue <int> q;	//存页面--模拟 
unordered_set<int> se;	//队列存在的数 
int cnt;	//缺页次数
int Size;	//物理块数 
int option;	//菜单选择 
int n;	//页面序列的个数 

void init()
{
	cnt = 0;
	se.clear();
	while (!q.empty())	q.pop();
}


void Print(queue<int> qq)
{
	while (!qq.empty())
	{
		printf("%d ", qq.front());
		qq.pop(); 
	}
	puts("");
}
void FIFO()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))	//此页面已存在,无需操作
		{
			printf("	 无中断,命中:");
			Print(q);
			continue;
		} 
		se.insert(a[i]);
		if (q.size() == Size)
		{
			se.erase(q.front());
			q.pop();	
		}
		cnt++;
		q.push(a[i]);
		printf("	第%d次缺页中断:", cnt);
		Print(q);
	}
	printf("	FIFO算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	FIFO算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
} 

void LRU()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))		//此页面已存在,进行更新 
		{
			queue <int> p;
			while (!q.empty())
			{
				int x = q.front();
				q.pop();
				if (x == a[i])	continue;
				p.push(x);
			} 
			q = p;
			q.push(a[i]);
			printf(" 	无中断,命中:");
			Print(q);
			continue;
		}
		se.insert(a[i]);
		if (q.size() == Size)
		{
			se.erase(q.front());
			q.pop();	
		}
		cnt++;
		q.push(a[i]);
		printf("	第%d次缺页中断:", cnt);
		Print(q);
	}
	printf("	LRU算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	LRU算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}

void OPT()
{
	init();
	for (int i = 0; i < a.size(); i++)
	{
		if (se.count(a[i]))	//已经存在,不进行操作
		{
			printf("	 无中断,命中:");
			Print(q);
			continue;
		}
		if (q.size() < Size)	
		{
			cnt++;
			se.insert(a[i]);
			q.push(a[i]);
			printf("	第%d次缺页中断:", cnt);
			Print(q);
			continue;
		}
		unordered_set<int> t;
		queue <int> p;
		for (int j = i + 1; j < a.size(); j++)
		{
			if(!se.count(a[j]))	continue;
			if (t.size() == Size - 1)	break;
			t.insert(a[j]);
		}
		int f = 1;
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			if (!t.count(x) && f)
			{
				se.erase(x);
				f = 0;
				continue;
			}
			p.push(x);
		}
		q = p;
		q.push(a[i]);
		se.insert(a[i]);
		cnt++;
		printf("	第%d次缺页中断:", cnt);
		Print(q);	
	}
	printf("	OPT算法缺页次数:%d, 缺页率:%%%.2lf\n", cnt, 1.0*cnt/n*100);
	printf("	OPT算法命中次数:%d, 命中率:%%%.2lf\n", n-cnt, (1 - 1.0*cnt/n) * 100);
}

void menu()
{
	printf("-------------------------菜单-----------------------------\n");
	printf("		1、随机产生作业和物理块数\n");
	printf("		2、自己输入作业和物理块数\n");
	printf("		3、先进先出算法(FIFO)\n");
	printf("		4、最近最久未使用算法(LRU)\n");
	printf("		5、最佳置换算法(OPT)\n");
	printf("		6、重现菜单\n");
	printf("		0、退出系统\n");
	printf("	请注意:在选择过1或2后才能选择3、4、5,否则会发生错误!\n");
} 

void random()
{
    a.clear();
	srand((unsigned) (time(NULL)));	//随机数更新 
	Size = rand()%5 + 2; //随机数[2, 6] 
	n = rand()%20 + 5;	//随机数[5, 24]
	printf("分配的物理块数为%d,页面序列共%d个,如下:\n", Size, n);
	for (int i = 0; i < n; i++)
	{
		int x = rand()%(n / 2) + 1;	//随机数[1, n / 2]
		a.push_back(x);
		printf("%d ",x);
	}
	puts(""); 	
}
void Scanf()
{
    a.clear();
	printf("请问输入分配的物理块数:") ;
	scanf("%d", &Size);
	printf("请问页面序列共多少个:");
	scanf("%d", &n);
	printf("请输入:"); 
	for (int i = 0; i < n; i++)
	{
		int x;	scanf("%d", &x); 
		a.push_back(x);
	}
}


int main()
{
	menu();
	
	while(1)
	{
		printf("请选择:");
		scanf("%d", &option);
		if (option == 0)
		{
			printf("\n     成功退出!!\n");
			break;
		}
		switch (option)
		{
			case 1:	random();	break;
			case 2:	Scanf();	break;
		 	case 3:	FIFO();		break;
		 	case 4:	LRU();		break;
		 	case 5:	OPT();		break;
		 	case 6:	menu();		break;
		 	default:	printf("输入错误,请您确认无误后再次输入!\n");
		}
	} 
	
	return 0;
}

  • 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

结果截图:
在这里插入图片描述

如果有错误,欢迎大哥们指出来!!

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

闽ICP备14008679号