操作系统：用C语言模拟先进先出的算法(FIFO)、最久未使用算法(LRU)、改进的Clock置换算法的命中率。-Toy模板网

这篇具有很好参考价值的文章主要介绍了操作系统：用C语言模拟先进先出的算法(FIFO)、最久未使用算法(LRU)、改进的Clock置换算法的命中率。。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2.1 实验目的

通过请求页面式存储管理中页面置换算法设计，了解存储技术的特点，掌握请求页式存储管理的页面置换算法。

2.2 实验内容

用程序实现生产者——消费者问题，将指令序列转换为用户虚存中的请求调用页面流。

具体要求：

l页面大小为1K

l用户内存容量为4页到40页

l用户外存的容量为40k

在用户外存中，按每K存放10条指令，400条指令在外存中的存放方式为：

l0-9条指令为第0页

l10-19条指令为第1页

。。。。。

l390-399条指令为第39页

按以上方式，用户指令可组成40页，通过随机数产生一个指令序列，共400个指令（0-399）。模拟请求页式存储管理中页面置换算法，执行一条指令，首先在外存中查找所对应的页面和页面号，然后将此页面调入内存中，模拟并计算下列三种算法在不同内存容量下的命中率(页面有效次数/页面流的个数):

1.先进先出的算法(FIFO)

2.最久未使用算法(LRU)

3.改进的Clock置换算法

提示

·随机指令的产生：rand() 或srand()

·用户内存中页面控制结构采用链表

struct p_str{

int pagenum; /* 页号 */

int count; /* 访问页面的次数 */

struct p_str next; /* 下一指针 */

}p_str;

2.3算法描述

FIFO先入先出算法采用队列思想，先调入内存的页放在最前面，当内存存满时新的不同的页需要调入内存时，旧的页要进行依次出队，然后将新的页放入队列最后。

LRU最久未使用算法在使用时增加了一个时间time参数，当一个内存的页刚被调入或者访问时，time会归零，当在一次时间片内未使用时时间参数time++。当内存存满且有新的页调入内存时时，会在内存中挑选time最大的页进行删除，并将新的页填入。

改进Clock置换算法一共分四步，当内存存满且有新页调入时，先寻找A=0且M=0的进行替换，如果没有则寻找A=0且M=1进行替换，如果没有将所有内存中的页的A便为0，在重复以上两步进行内存中的新旧页替换。

2.4 实验结果（Linux虚拟机运行）

编译指令：g++ -o page page.cpp

运行指令：./page

根据数学计算可知，当内存页为40时，三种算法的命中率均为90及以上。

c lru算法模拟实现,一些小算法的学习,算法,c语言,linux

当内存页小于40时，三种算法在随机生成页时命中率是离散的

c lru算法模拟实现,一些小算法的学习,算法,c语言,linux

2.5 实验小结

本代码中FIFO采用队列并没有太大难度，而LRU相对FIFO仅是增加了一个时间变量用来选择置换的页，也就是说每次置换相对于FIFO要多出一个遍历求最大值的过程，也不能忘了在对链表进行增删的时候应该在遍历时遍历到length-1以此到达要删除结点的前一个结点，这样直接令前一结点的next=next->next，十分方便。代码中最难的就是改进Clock算法，其难就难在于多次进行链表遍历和增删所导致的结点为NULL或者爆内存的情况，因此最应该注意的是一共需要每次增删最多会遍历四次，所以在引用游标指针pp时应该在每次遍历完的时候重新让其等于begin也就是队首，这样才能保证代码不报错或者得出的测试概率错误。文章来源地址https://www.toymoban.com/news/detail-775817.html

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define maxsize 400	/*400访问次数*/
typedef struct p_str {
	int pagenum; /* 页号 */
	int count; /* 访问页面的次数 */
	int aa;/*访问位(Clock)*/
	int mm;/*修改位(Clock)*/
	int longtime;/*未使用的时间(LRU)*/
	struct p_str* next; /* 下一指针 */
}p_str;
int n;
void FIFO();
void LRU();
void Improve_Clock();

int main() {
	int m;
	srand((unsigned)time(NULL));
	scanf("%d %d", &n, &m); //输入内存容量和测试次数
	int i = m;
	while (m--) {
		printf("\n第%d次测试\n", i - m);
		//cout << endl << "第" << i - m << "次测试" << endl;
		FIFO();
		LRU();
		Improve_Clock();
	}
}

void FIFO() {
	double effective = 0;	/*有效访问次数*/
	int length = 0;		/*队列长度*/
	p_str* begin = (p_str*)malloc(sizeof(p_str));		/*创建头结点*/
	p_str* end = begin;		/*创建尾结点*/
	begin->count = -1; begin->pagenum = -1; begin->next = NULL;
	for (int i = 0; i < maxsize; i++) {	/*400次随机数测试*/
		int t = 0;
		int page = rand() % 400 / 10;
		p_str* pp = begin;
		for (int j = 0; j < length; j++) {		/*先遍历看内存是否有相同的页*/
			pp = pp->next;
			if (pp->pagenum == page) {		/*有则有效次数加一*/
				pp->count++;
				t = 1;
				effective++;
				break;
			}
		}
		if (t == 0) {		/*进行无效访问，即添加结点或替换节点*/
			if (length < n) {		/*内存未满，添加结点*/
				p_str* q = (p_str*)malloc(sizeof(p_str));
				q->count = 1; q->pagenum = page; q->next = NULL;
				end->next = q;
				end = q;
				length++;
			}
			else {		/*内存已满，删除表头结点，新结点加到表尾*/
				begin->next = begin->next->next;
				p_str* q = (p_str*)malloc(sizeof(p_str));
				q->count = 1; q->pagenum = page; q->next = NULL;
				end->next = q;
				end = q;
			}
		}
	}
	printf("在页面流个数为%d，内存容量为%d页的条件下，FIFO命中率为：%f %%\n", maxsize, n, (effective / 400) * 100);
	//cout << "在页面流个数为" << maxsize << "，内存容量为" << n << "页的情况下，FIFO命中率为:" << (effective / 400) * 100 << "%" << endl;
}

void LRU() {
	double effective = 0;	/*有效访问次数*/
	int length = 0;		/*队列长度*/
	p_str* begin = (p_str*)malloc(sizeof(p_str));	/*创建头尾结点*/
	p_str* end = begin;
	begin->count = -1; begin->pagenum = -1; begin->longtime = -1; begin->next = NULL;
	for (int i = 0; i < maxsize; i++) {		/*400次随机数测试*/
		int t = 0;
		int page = rand() % 400 / 10;
		p_str* pp = begin;
		for (int j = 0; j < length; j++) {		/*遍历内存看是否可以有效访问*/
			pp = pp->next;
			if (pp->pagenum == page) {
				pp->count++; pp->longtime = -1; t++; effective++; break;
			}
		}
		if (!t) {		/*无效访问*/
			if (length < n) {		/*添加结点*/
				p_str* q = (p_str*)malloc(sizeof(p_str));
				q->count = 1; q->pagenum = page; q->next = NULL; q->longtime = -1;
				end->next = q;
				end = q;
				length++;
			}
			else {
				int max, maxtime = -1;		/*最久未访问结点位置，最久未访问时间*/
				pp = begin;
				for (int j = 0; j < length; j++) {		/*寻找最久未访问的结点*/
					pp = pp->next;
					if (pp->longtime > maxtime) {
						maxtime = pp->longtime;
						max = j;
					}
				}
				pp = begin;
				for (int j = 0; j < max - 1; j++) {		/*删除该结点*/
					pp = pp->next;
				}
				pp->next = pp->next->next;
				p_str* q = (p_str*)malloc(sizeof(p_str));	/*添加新结点*/
				q->count = 1; q->pagenum = page; q->next = NULL; q->longtime = -1;
				end->next = q;
				end = q;
			}
		}
		pp = begin;
		for (int j = 0; j < length; j++) {		/*所有未被访问节点时间加一*/
			pp = pp->next;
			pp->longtime++;
		}
	}
	printf("在页面流个数为%d，内存容量为%d页的条件下，LRU命中率为：%f %%\n", maxsize, n, (effective / 400) * 100);
	//cout << "在页面流个数为" << maxsize << "，内存容量为" << n << "页的情况下，LRU命中率为:" << (effective / maxsize) * 100 << "%" << endl;
}

void  Improve_Clock() {
	double effective = 0;	/*有效访问次数*/
	int length = 0;		/*队列长度*/
	p_str* begin = (p_str*)malloc(sizeof(p_str));		/*创建头尾结点*/
	p_str* end = begin;
	begin->count = -1; begin->pagenum = -1; begin->aa = -1; begin->mm = -1; begin->next = NULL;
	for (int i = 0; i < maxsize; i++) {
		int t = 0;
		int page = rand() % 400 / 10;
		int  m = rand() % 2;
		p_str* pp = begin;
		for (int j = 0; j < length; j++) {		/*尝试有效访问*/
			pp = pp->next;
			if (pp == NULL) {
				pp = end;
			}
			if (pp->pagenum == page) {
				pp->aa = 1; t++; effective++; break;
			}
		}
		if (!t) {
			if (length < n) {		/*添加结点*/
				p_str* q = (p_str*)malloc(sizeof(p_str));
				q->count = 1; q->pagenum = page; q->next = NULL; q->longtime = -1; q->aa = 1; q->mm = m;
				end->next = q;
				end = q;
				length++;
			}
			else {
				int f = 0;
				p_str* q = (p_str*)malloc(sizeof(p_str));
				q->count = 1; q->pagenum = page; q->next = NULL; q->longtime = -1; q->aa = 1; q->mm = m;
				p_str* pp = begin;
				for (int j = 0; j < length-1; j++) {
					if (pp->next->aa == 0 && pp->next->mm == 0) {		/*寻找A=0，M=0替换*/
						pp->next = pp->next->next;
						end->next = q;
						end = q;
						f = 1; break;
					}
					else {
						pp = pp->next;
					}
				}
				if (f)continue;
				else {
					pp = begin;
					for (int j = 0; j < length-1; j++) {
						if (pp->next->aa == 0 && pp->next->mm == 1) {		/*寻找A=0,M=1替换*/
							pp->next = pp->next->next;
							end->next = q;
							end = q;
							f = 1; break;
						}
						else {
							pp = pp->next;
						}
					}
				}
				if (f)continue;
				else {
					pp = begin;
					for (int j = 0; j < length; j++) {		/*所有结点A归零*/
						pp = pp->next;
						pp->aa = 0;
					}
				}
				pp = begin;
				for (int j = 0; j < length-1; j++) {
					if (pp->next->aa == 0 && pp->next->mm == 0) {	/*寻找A=0，M=0替换*/
						pp->next = pp->next->next;
						end->next = q;
						end = q;
						f = 1; break;
					}
					else {
						pp = pp->next;
					}
				}
				if (f)continue;
				else {
					pp = begin;
					for (int j = 0; j < length-1; j++) {
						if (pp->next->aa == 0 && pp->next->mm == 1) {	/*寻找A=0,M=1替换*/
							pp->next = pp->next->next;
							end->next = q;
							end = q;
							f = 1; break;
						}
						else {
							pp = pp->next;
						}
					}
				}
			}
		}
	}
	//cout << "在页面流个数为" << maxsize << "，内存容量为" << n << "页的情况下，优化Clock命中率为:" << (effective / maxsize) * 100 << "%" << endl;
	printf("在页面流个数为%d，内存容量为%d页的条件下，优化Clock命中率为：%f %%\n", maxsize, n, (effective / 400) * 100);
}

到了这里，关于操作系统：用C语言模拟先进先出的算法(FIFO)、最久未使用算法(LRU)、改进的Clock置换算法的命中率。的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！