devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

页面置换算法（OPT，FIFO，LRU，CLOCK）_(1)最佳淘汰算法(opt):选择永不使用或在未来最长时间内不再被访问的页面予以替换

作者：Gausst松鼠会 | 2024-06-07 23:35:18

赞

踩

(1)最佳淘汰算法(opt):选择永不使用或在未来最长时间内不再被访问的页面予以替换

文章目录


1、最佳淘汰算法（OPT）   
2、先进先出的算法（FIFO）
3、最近最久未使用算法（LRU）  
4、简单时钟(钟表)算法（CLOCK）  
命中率＝１－页面失效次数／页地址流(序列)长度
缺页率=缺页次数/（缺页次数+访问成功次数）

1、最佳淘汰算法（Optimal）

其所选择的被淘汰页面将是以后永不使用的， 或许是在最长（未来）时间内不再被访问的页面。 采用最佳置换算法通常可保证获得最低的缺页率。但由千人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的， 但可以利用该算法去评价其它算法。

举例

假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时，先将7, 0, l三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需调入。七次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面l被淘汰；因为，它在现有的1, 2, 0三个页面中，将是以后最晚才被访问的。 图示采用最佳置换算法时的置换图。由图可看出，采用最佳置换算法发生了6次页面置换。
在这里插入图片描述

代码

#include <stdio.h>
#include<iostream>
#include <string>
#include<stdlib.h>
#include <ctype.h>
#include<algorithm>
using namespace std;
#define ERROR -1 
int page[1000];//内存
int toppage;
int MAXSIZE;
int F, ch;//缺页次数,置换次数
void watch(){//查看当前内存中存有的页面号
	printf("当前内存序列：");
	for (int i = toppage; i >= 0; i--)
		printf("%d ", page[i]);
	//printf("\t置换次数：%d\t缺页率：%d%%\n", ch, F * 100 / (S+F));
	printf("\t置换次数：%d\t缺页次数：%d\n", ch, F);
	return;
}
int locatetime(int queue[], int num, int t, int w){//num是页面序列总长，t是当前queue页面序列号,w是当前内存号
	for (int i = t; i <= num; i++){
		if (queue[i] == page[w])return i;
	}
	return num + 1;
}
int Popbase(int queue[], int num, int t){//最久未使用被淘汰,t是queue序列号
	int max=-1,maxid=-1,h;
	for (int i = 0; i <= toppage; i++){
		h=locatetime(queue, num, t,i);
		if (max < h){
			maxid = i;
			max = h;
		}
	}
	return maxid;
}
int search(int a){
	for (int i = toppage; i >= 0; i--){
		if (a == page[i]) return i;
	}
	return ERROR;
}
int scan(char str[], int queue[]){

	int n = strlen(str), j = -1;
	for (int i = 0; i < n; i++){
		if (isdigit(str[i])){
			sscanf(str + i, "%d", &queue[++j]);
			while (isdigit(str[++i]));
			i--;
		}
	}
	return j;//总长度
}
void Optimal(){
	F = 0; ch = 0;
	toppage = -1;
	char str[1000];//输入字符串
	int t, queue[100];//是否重新出现过,页地址流
	printf("页地址流序列：");
	scanf("%s", str);
	int num = scan(str, queue)+1;//页地址流(序列)长度(0~num,所以长度+1）
	for (int i = 0; i < num; i++){
		t = search(queue[i]);
		if (t != ERROR){//在物理块中
			printf("不缺页，无需置换\n");
			continue;
		}
		else{//不在物理块中
			F++;//物理块中无，所以缺页次数+1
			if ((toppage + 1) >= MAXSIZE){//物理块满，最佳置换
				//最久未使用被淘汰，被淘汰位置换为当前序列号
				page[Popbase(queue, num, i)] = queue[i];//i是当前queue序列号
				ch++;//置换次数+1
			}
			else
				page[++toppage] = queue[i];
			
		}
		watch();
	}
	printf("页地址流长度：%d\t命中率：%d%%\t缺页率：%d%%\n\n", num, (num - ch) * 100 / num, F * 100 / num);
	fill(page, page + num-1, 0);
}

int main(){
	printf("分配给物理块的数量:");
	scanf("%d", &MAXSIZE);
	while (MAXSIZE != 0){
		while (MAXSIZE > 1000){
			printf("分配给的物理块过多,重新分配\n");
			printf("分配给物理块的数量:");
			scanf("%d", &MAXSIZE);
		}
		Optimal();
		printf("分配给物理块的数量:");
		scanf("%d", &MAXSIZE);
	}
	system("PAUSE");
	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

流程图

在这里插入图片描述
在这里插入图片描述

2、先进先出的算法（FIFO）

其所选择的被淘汰页面将是以后永不使用的， 或许是在最长（未来）时间内不再被访问的页面。 采用最佳置换算法通常可保证获得最低的缺页率。但由千人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的， 但可以利用该算法去评价其它算法。

举例

假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
进程运行时，先将7, 0, l三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需调入。七次访问页面0时，因它已在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面l被淘汰；因为，它在现有的1, 2, 0三个页面中，将是以后最晚才被访问的。 图示采用最佳置换算法时的置换图。由图可看出，采用最佳置换算法发生了6次页面置换。
在这里插入图片描述

代码

#include <stdio.h>
#include<iostream>
#include <string>
#include<stdlib.h>
#include <ctype.h>
#include<algorithm>
using namespace std;
#define ERROR -1 
int page[1000];//内存
int toppage;
int MAXSIZE;
int time;//最长驻留的page的序号
int F, ch;//缺页次数,置换次数
void watch(){//查看当前内存中存有的页面号
	printf("当前内存序列：");
	for (int i = toppage; i >= 0; i--)
		printf("%d ", page[i]);
	printf("\t置换次数：%d\t缺页次数：%d\n", ch, F);
	return;
}
int search(int a){
	for (int i = toppage; i >= 0; i--){
		if (a == page[i]) return i;
	}
	return ERROR;
}
int scan(char str[], int queue[]){

	int n = strlen(str), j = -1;
	for (int i = 0; i < n; i++){
		if (isdigit(str[i])){
			sscanf(str + i, "%d", &queue[++j]);
			while (isdigit(str[++i]));
			i--;
		}
	}
	return j;//总长度
}
void FIFO(){
	F = 0; ch = 0;
	toppage = -1;
	time = 0;
	char str[1000];//输入字符串
	int t, queue[100];//是否重新出现过,页地址流
	printf("页地址流序列：");
	scanf("%s", str);
	int num = scan(str, queue);//页地址流(序列)长度
	for (int i = 0; i <= num; i++){
		t = search(queue[i]);
		if (t != ERROR){//重复出现过，不缺页
			printf("不缺页，无需置换\n");
			continue;
		}
		else{//缺页
			F++;
			if ((toppage + 1) >= MAXSIZE){//物理块满，最先进入的页面出栈
				page[time] = queue[i];
				time = (time + 1) % MAXSIZE;
				ch++;//置换次数+1
			}
			else//物理块没满，直接置换进内存
				page[++toppage] = queue[i];
			watch();
		}
			
	}
	num++;
	printf("页地址流长度：%d\t命中率：%d%%\t缺页率：%d%%\n\n", num, (num - ch) * 100 / num, F * 100 / num);
	fill(page, page + num-1, 0);
}

int main(){
	printf("分配给物理块的数量:");
	scanf("%d", &MAXSIZE);
	while (MAXSIZE != 0){
		while (MAXSIZE > 1000){
			printf("分配给的物理块过多,重新分配\n");
			printf("分配给物理块的数量:");
			scanf("%d", &MAXSIZE);
		}
		FIFO();
		printf("分配给物理块的数量:");
		scanf("%d", &MAXSIZE);
	}
	system("PAUSE");
	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

流程图

在这里插入图片描述

3、最近最久未使用算法（LRU）

最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用清况，只能利用 “最近的过去” 作为 “最近的将来” 的近似， 因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。 当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

举例

当进程第一次对页面2进行访问时，由于页面7是最近最久未被访问的，故将它置换出去。当进程第一次对页面3进行访间时，第1页成为最近最久未使用的页，将它换出。由图可以看出， 前5个时间的图像与最佳置换算法时的相同， 但这并非是必然的结果。 因为最佳置换算法是从 “向后看” 的观点出发的，即它是依据以后各页的使用情况进行判断；而LRU算法则是 “ 向前看” 的，即根据各页以前的使用情况来判断， 而页面过去和未来的走向之间并无必然的联系。
在这里插入图片描述

代码

#include <stdio.h>
#include<iostream>
#include <string>
#include<stdlib.h>
#include <ctype.h>
#include<algorithm>
using namespace std;
#define ERROR -1 
int page[1000];//LRU栈
int toppage;
int MAXSIZE;
int F,ch;//缺页次数,置换次数
void watch(){//查看当前内存中存有的页面号
	printf("当前内存序列：");
	for (int i = toppage; i >= 0; i--)
		printf("%d ", page[i]);
	printf("\t置换次数：%d\t缺页次数：%d\n",ch,F);
	return;
}
void Popbase(int a){//page[a]出栈
	for (int i = (a+1); i <= toppage; i++){
		page[i - 1] = page[i];
	}
	toppage--;
	return;
}
int search(int a){
	for (int i = toppage; i >= 0; i--){
		if (a == page[i]) return i;
	}
	return ERROR;
}
int scan(char str[],int queue[]){
	
	int n = strlen(str),j=-1;
	for (int i = 0; i < n; i++){
		if (isdigit(str[i])){
			sscanf(str + i, "%d", &queue[++j]);
			while (isdigit(str[++i]));
			i--;
		}
	}
	return j;//总长度
}
void LRU(){
	F = 0; ch = 0;
	toppage = -1;
	char str[1000];//输入字符串
	int t,queue[100];//是否重新出现过,页地址流
	printf("页地址流序列：");
	scanf("%s", str);
	int num=scan(str, queue);//页地址流(序列)长度
	for(int i=0;i<=num;i++){
		t = search(queue[i]);
		if (t != ERROR){//重复出现过，不缺页
			Popbase(t);//重复出现的page[t]先出栈
		}
		else{//缺页
			F++;//缺页次数+1
			if ((toppage + 1) >= MAXSIZE){//物理块满，最近最久未使用的页面出栈
				Popbase(0);//最近最久未使用的页面是page[0],出栈
				ch++;//置换次数+1
			}
		}
		page[++toppage] = queue[i];
		watch();
	}
	num++;
	printf("页地址流长度：%d\t命中率：%d%%\t缺页率：%d%%\n\n", num, (num - ch) * 100 / num, F * 100 / num);
	fill(page, page + num - 1,0);
}

int main(){
	printf("分配给物理块的数量:");
	scanf("%d", &MAXSIZE);
	while (MAXSIZE != 0){
		while (MAXSIZE > 1000){
			printf("分配给的物理块过多,重新分配\n");
			printf("分配给物理块的数量:");
			scanf("%d", &MAXSIZE);
		}
		LRU();
		printf("分配给物理块的数量:");
		scanf("%d", &MAXSIZE);
	}
	system("PAUSE");
	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

流程图

在这里插入图片描述

4、简单时钟(钟表)算法（CLOCK）

我们把页面排成一个时钟的形状，该时针有一个针臂。每次需要更换页面的时候，我们从针臂所指的页面开始 检查。如果当前页面的访问位为0，即从上次检查到这次，若该页面没有被访问过，将该页面替换；如果当前页面的访问位为1，即当前页面被访问过，那就将其访问位清零，并顺时针移动指针到下一个页面。

代码

#include <stdio.h>
#include<iostream>
#include <string>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
using namespace std;
#define ERROR -1 
typedef struct CLOCK{
	int data;
	bool fw;
}CLOCK;

int toppage;
int MAXSIZE;
int time;//针臂
int F, ch;//缺页次数,置换次数
void watch(CLOCK page[]){//查看当前内存中存有的页面号
	printf("当前内存序列：");
	for (int i = toppage; i >= 0; i--)
		printf("%d ", page[i].data);
	printf("\t置换次数：%d\t缺页次数：%d\n", ch, F);
	return;
}
int search(int a, CLOCK page[]){
	for (int i = toppage; i >= 0; i--){
		if (a == page[i].data) return i;
	}
	return ERROR;
}
int scan(char str[], int queue[]){

	int n = strlen(str), j = -1;
	for (int i = 0; i < n; i++){
		if (isdigit(str[i])){
			sscanf(str + i, "%d", &queue[++j]);
			while (isdigit(str[++i]));
			i--;
		}
	}
	return j;//总长度
}
void FIFO(){
	CLOCK page[1000];//内存
	F = 0; ch = 0;
	toppage = -1;
	time = 0;//针臂指为0
	char str[1000];//输入字符串
	int t, queue[100];//是否重新出现过,页地址流
	printf("页地址流序列：");
	scanf("%s", str);
	int num = scan(str, queue);//页地址流(序列)长度
	for (int i = 0; i <= num; i++){
		t = search(queue[i],page);
		if (t != ERROR){//重复出现过，不缺页
			printf("不缺页，无需置换\n");
			continue;
		}
		else{//缺页
			F++;
			if ((toppage + 1) >= MAXSIZE){//物理块满，访问位为0的页面出队，访问位为1的页面置为0并访问下一个直到队尾
				while (page[time].fw){//访问位为1的页面都赋为访问位为0直到遇到访问位为0的
					page[time].fw = false;
					time = (time+1)%MAXSIZE;
				}
				page[time].data = queue[i];
				page[time].fw = true;//访问位置1
				time = (time + 1) % MAXSIZE;
				ch++;//置换次数+1
			}
			else{//物理块没满，直接置换进内存
				toppage++;
				page[toppage].data = queue[i];
				page[toppage].fw = true;
			}
			watch(page);
		}

	}
	num++;
	printf("页地址流长度：%d\t命中率：%d%%\t缺页率：%d%%\n\n", num, (num - ch) * 100 / num, F * 100 / num);

}

int main(){
	printf("分配给物理块的数量:");
	scanf("%d", &MAXSIZE);
	while (MAXSIZE != 0){
		while (MAXSIZE > 1000){
			printf("分配给的物理块过多,重新分配\n");
			printf("分配给物理块的数量:");
			scanf("%d", &MAXSIZE);
		}
		FIFO();
		printf("分配给物理块的数量:");
		scanf("%d", &MAXSIZE);
	}
	system("PAUSE");
	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

流程图

在这里插入图片描述

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号