虚拟存储

实验目的

页面置换算法也称为页面淘汰算法，是用来选择换出页面的算法。

• 解决：需要调入页面时，选择内存中哪个或哪些物理页面被置换
• 目标：把未来不再使用的或在以后一段时间内较少使用的页面调出

实验原理

先进先出算法

基本思想是淘汰最先进入内存的页面，即选择在内存驻留时间最长的页面予以淘汰。实现简单。按页面调入内存的先后链结为队列，设置一个替换指针，总是指向最先进入内存的页面。缺点在与进程实际运行规律不符，性能不好。

算法流程图如下

最佳页面置换算法

基本思想是所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，可保证获得最低的缺页率。

算法流程图如下

最近最久未使用页面置换算法

基本思想：最近未访问的页面，将来一段时间也不会访问。利用局部性原理，根据一个进程在执行过程中过去的页面访问踪迹来推测未来的行为。最近的过去 → 最近的将来 思想：选择最近最久未使用的页面予以淘汰。利用页表中的访问字段，记录页面自上次被访问以来所经历的时间t，需要淘汰页面时，选择在内存页面中t值最大的，即最近最久未使用的页面予以淘汰

算法流程图如下

实验内容

算法实现

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
int n,j=0;
struct page {
	int num;
	int visit=65535;
	struct page* next = NULL;
};
typedef struct page Page;
struct PageQueue
{
	Page* head;
	Page* tail;
};
void initQueue(struct PageQueue* rq) {
	rq->head = NULL;
	rq->tail = NULL;
}
void EnQueue(struct PageQueue* rq, Page* p) {
	if (!rq->head) {
		rq->head = p;
		rq->tail = p;
	}
	else {
		rq->tail->next = p;
		rq->tail = p;
		p->next = NULL;
	}
}
void Dequeue(struct PageQueue* rq, Page** p) {
	if (rq->head != NULL) {
		*p = rq->head;
		rq->head = rq->head->next;
		if (rq->head == NULL) {
			rq->tail = NULL;
		}
		(*p)->next = NULL;  // Ensure the dequeued PCB points to NULL
	}
}
int Find(int n1, struct PageQueue rq) {
	int i = 0;
	Page* p = rq.head;
	while(p){
		if (p->num == n1) return 1;
		p = p->next;
	}
	return 0;
}
int Getleast(struct PageQueue* rq, int a[]) {
	int maxv = 0, num=0;
	Page* q = rq->head;
	while (q) {
		int k = 0;
		while (a[k] != 0) {
			if (q->num == a[k]) { q->visit = k; break; }
			k++;
		}if (maxv < q->visit) { maxv = q->visit; num = q->num; }
		q = q->next;
	}
	return num;
}
int Getleastr(struct PageQueue* rq) {
	int num = 0,minv=65535;
	Page* q = rq->head;
	while (q) {
		int k = 0;
		if (minv > q->visit) { minv = q->visit; num = q->num; }
		q = q->next;
	}
	return num;
}
void Delete(struct PageQueue* rq, int num) {
	Page* p1 = rq->head; Page* p2;
		if (p1->num ==num) Dequeue(rq, &p2);
		if (p1->num != num) {
			while (p1->next->num != num)
			{
				p1 = p1->next;
			}
			if (p1->next == rq->tail)rq->tail = p1;
			if (p1->next)p1->next = p1->next->next;
	}
}
void Print(struct PageQueue rq) {
	Page* p = rq.head;
	while (p) {
		cout << p->num << '\t';
		p = p->next;
	}
}
void FIFO(struct PageQueue* rq, int a[]) {
	int i = 0,count=0; 
	while (a[i] != 0) {
		Page* p = new page;
		if (!Find(a[i], *rq)) {
			cout << "在" << a[i] << "处产生缺页中断";
			if(count>=n)Dequeue(rq, &p); 
			p->num = a[i]; p->next = NULL;
			EnQueue(rq, p);
			Print(*rq);
			cout << endl;
			count++;
		}
		i++;
	}
	cout << "缺页次数" << count << "缺页率" << count * 1.0 / j << endl;
}
void OPT(struct PageQueue* rq, int a[]){
	int i = 0, count = 0,num1=0;
	while (a[i] != 0) {
		Page* p = new page;
		if (!Find(a[i], *rq)) {
			cout << "在" << a[i] << "处产生缺页中断";
			if (count >= n) {
				num1 = Getleast(rq, a);
				Delete(rq, num1);
			}
			p->num = a[i]; p->next = NULL;
			EnQueue(rq, p);
			Print(*rq);
			cout << endl;
			count++;
		}
		i++;
	}
	cout << "缺页次数" << count << "缺页率" << count * 1.0 / j << endl;
}
void ChangeV(struct PageQueue* rq, int a, int i) {
	Page* q = rq->head;
	while (q->num != a)
		q = q->next;
	q->visit = i;
}
void LRU(struct PageQueue* rq, int a[]) {
	int i = 0, count = 0,num;
	while (a[i] != 0) {
		Page* p = new page;
		if (!Find(a[i], *rq)) {
			cout << "在" << a[i] << "处产生缺页中断";
			if (count >= n) {
				num = Getleastr(rq);
				Delete(rq, num);
			}
			p->num = a[i]; p->next = NULL; p->visit = i;
			EnQueue(rq, p);
			Print(*rq);
			cout << endl;
			count++;
		}
		else {
			ChangeV(rq, a[i], i);
		}
		i++;
	}
	cout << "缺页次数" << count << "缺页率" << count * 1.0 / j << endl;
}
int main()
{
	int a[30] = { 0 },t,i=0;
	cout << "主存块数" << endl;
	cin >> n;
	cout << "页面号" << endl;
	while (cin.get() != '\n'||j==0) {
		cin >> a[j];
		j++;
	}
	PageQueue pg;
	initQueue(&pg);
	//FIFO(&pg, a);
	//OPT(&pg, a);
	LRU(&pg, a);
}

内容演示

FIFO

最佳置换算法

LRU

实验总结

通过本次实验加深了我对页面置换算法的理解，本次实验中的页面置换算法有
FIFO（先进先出置换算法）、LRU（最近最少使用页面置换算法）、OPT（最佳置换算法）。

FIFO算法的核心思想是置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。

LRU算法的核心思想是置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。LRU算法普偏地适用于各种类型的程序，但是系统要时时刻刻对各页的访问历史情况加以记录和更新，开销太大，因此LRU算法必须要有硬件的支持。

OPT算法的核心思想是置换以后不再被访问，或者在将来最迟才回被访问的页面，缺页中断率最低。缺点：该算法需要依据以后各业的使用情况，而当一个进程还未运行完成是，很难估计哪一个页面是以后不再使用或在最长时间以后才会用到的页面。

这三种算法对比：OPT > LRU > FIFO 但是OPT算法是不能实现的，但该算法仍然有意义，可以作为其他算法优劣的一个标准。