操作系统实验——内存管理（页面置换算法 OPT、FIFO、LRU）_fifo,opt,lru哪个缺页率高

操作系统实验——内存管理

一、实验目的

1、了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
2、了解程序设计技术和内存泄露的原因

二、实验内容

1、模拟实现请求页式存储管理的几种基本页面置换算法
（1）最佳淘汰算法（OPT）
（2）先进先出的算法（FIFO）
（3）最近最久未使用算法（LRU））

三、实验原理

1、虚拟存储系统
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。
2、页面置换算法
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
（1）最佳淘汰算法（OPT）：选择永不使用或在未来最长时间内不再被访问的页面予以替换。
（2）先进先出的算法（FIFO）：选择在内存中驻留时间最久的页面予以替换。
（3）最近最久未使用算法（LRU）：选择过去最长时间未被访问的页面予以替换。

四、实验流程图以及所需要的数据结构

首先需要定义一个数据结构struct`

struct pageinformation
{
   
	int id;//页面号
	int visit;//被访问标记
};
pageinformation* block;//物理块
pageinformation* page;//页面
int pagenum;//合并的页面数
int a[100];//显示时用的数组

class pager
{
   
private:
	int count;//页面中断次数
	int change;//页面置换次数
	int blocknum = 3;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实验思路：
首先要判断在内存中是否存在当前需要调度的页面，如若有就不用进行缺页中断，如果没有，则需要进行缺页中断
缺页中断情况可以分成两种：
（1）内存中存在空闲位置，直接将当前调度的页面调入内存中（一般出现在调度的开始）
（2）内存中不存在空闲位置，就需要选择内存中的一个页面调出，让当前调度页面进入内存，此过程就是页面置换，淘汰的依据就是上述visit值大者

```cpp
int findreplace()//查找应予以置换的页面
	{
   
		int pos = 0;
		for (int i = 0; i < blocknum; i++)
		{
   
			if (block[i].visit >= block[pos].visit)
				pos = i;
		}
		return pos;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Opt置换算法：淘汰的是未来不再使用或者再未来长时间不再被访问的页面，要对后续的页面进行预读，然后与物理块中的页面进行参照，如果其中的页面在后续没有出现或者出现的最晚，那么该页面的访问引用位置（visit）就最大，就要被淘汰
实现代码：

```cpp
for (int k = 0; k < blocknum; k++)
					{
						for (int j = i; j < pagenum; j++)
						{
							if (block[k].id != page[j].id)
							{
								block[k].visit = 1000;
							}
							else
							{
								block[k].visit = j;
								break;
							}
						}
					}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

FIFO先进先出算法：淘汰的是最先进来的页面，每次调入页面后将该页面的访问引用位置（visit）++ ，则可以计算其在物理块中存在的时间，visit值越大则说明进来的次序最先
代码实现：

space = findspace();
				if (space != -1)
				{
   
					block[space] = page[i];
					show();
				}
				else
				{
   
					change++;
					position = findreplace();
					cout << "即将访问的页面是：" << page[i].id << ",将被置换出的页面是：" << block[position].id << "\n\n";
					block[position] = page[i];
					show();
				}
				for (int i = 0; i < blocknum; i++)
			{
   
				block[i].visit++;//页面进入后，每再进入一个页面停留时间+1；
			}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Lur最近最久未使用和最少使用置换算法：
该算法淘汰的是最近最久未使用的，那么每访问一次页面就都需要将该页面的访问引用位置（visit）置为0；在每一次置换调度后也要增加驻留时间，即：visit++
实现代码：

space = findspace();
				if (space != -1)
				{
   
					block[space] = page[i];
					show();
				}
				else
				{
   
1
2
3
4
5
6
7
8
9