首页 / 算法 / 操作系统——页面调度算法
操作系统——页面调度算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了操作系统——页面调度算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3385字，纯文字阅读大概需要5分钟。
内容图文
在之前系列的博客中介绍了页面调度算法的原理：
https://www.cnblogs.com/wkfvawl/p/11700301.html#_label2_3
这里编写代码模拟一些页面调度算法的实现。
（1）最佳淘汰算法——OPT(Optimal)
这是Belady贝莱迪于1966年提出的一种理论上的算法。该算法每次都淘汰以后
永不使用的，或者过最长的时间后才会被访问的页面。显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。
（2）先进先出淘汰算法——FIFO
这是最早出现的淘汰算法。
总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。
（3） 最近最久未使用算法——(LRU, Least Recently Used）
根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。
OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向前看的，而LRU是向后看的。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N;//进程虚页数
int M;//内存块个数
int page[100];//进程虚页
int block[100];//内存块
int weight[100];//当前内存块在后面出现的次数
int success;//命中次数
int fail;//未命中次数
void FIFO()
{
int i,j;
int flag;
int pos=0;
int success=0;
int fail=0;
for(i=0; i<N; i++)
{
flag =0;
for(j=1; j<=M; j++)
{
if(page[i]==block[j])//命中
{
flag=1;
success++;
pos--;
break;
}
}
if(flag==0)
{
fail++;
block[pos%M+1]=page[i];
}
pos++;
for(j=1; j<=M; j++)
{
printf("%d ",block[j]);
}
printf("\n");
}
printf("命中次数为：%d\n",success);
printf("未命中次数为：%d\n",fail);
}
void OPT()
{
int i,j,k;
int flag;
int success=0;
int fail=0;
int needReplace;
for(i=0; i<N; i++)
{
flag=0;
for(j=1; j<=M; j++)
{
if(page[i]==block[j])//命中
{
flag=1;
success++;
}
}
if(flag==0)//未命中
{
fail++;
for(j=1; j<=M; j++) //若内存块未满，先将内存块填满
{
if(block[j]==0)
{
block[j]=page[i];
break;
}
}
int minCnt=100;
memset(weight,0,sizeof(weight));
if(j>M)//若内存块已满，需要进行调度
{
for(k=i+1; k<N; k++) //向后
{
for(j=1; j<=M; j++)
{
if(block[j]==page[k])
{
weight[j]=N-k;//越靠近，权值越大
break;
}
}
}
for(j=1; j<=M; j++) //找权值最小的那一个
{
if(weight[j]<=minCnt)
{
minCnt=weight[j];
needReplace=j;
}
}
block[needReplace]=page[i];//替换掉权值最小的
}
}
for(j=1; j<=M; j++)
{
printf("%d ",block[j]);
}
printf("\n");
}
printf("命中次数为：%d\n",success);
printf("未命中次数为：%d\n",fail);
}
void LRU()
{
int i,j;
int flag;
int success=0;
int fail=0;
int needReplace;
for(i=0; i<N; i++)
{
flag=0;
for(j=1; j<=M; j++)
{
if(page[i]==block[j])//命中
{
flag=1;
success++;
}
}
if(flag==0)//未命中
{
fail++;
for(j=1; j<=M; j++) //现将内存块填满
{
if(block[j]==0)
{
block[j]=page[i];
break;
}
}
if(j>M)//内存块已满，需要进行调度
{
//向前找,需要替换的页面为i-M
needReplace=page[i-M];
for(j=1; j<=M; j++)
{
if(block[j]==needReplace)//找到后替换掉
{
block[j]=page[i];
break;
}
}
}
}
for(j=1; j<=M; j++)
{
printf("%d ",block[j]);
}
printf("\n");
}
printf("命中次数为：%d\n",success);
printf("未命中次数为：%d\n",fail);
}
int main()
{
printf("请输入进程执行时页面访问个数：\n");
scanf("%d",&N);
printf("请输入空闲内存块的个数：\n");
scanf("%d",&M);
printf("请输入进程执行时页面访问次序：\n");
memset(page,0,sizeof(page));
memset(block,0,sizeof(block));
int i;
int needReplace;
for(i=0; i<N; i++)
{
scanf("%d",&page[i]);
}
printf("采用最佳淘汰算法OPT:\n");
OPT();
memset(block,0,sizeof(block));
printf("采用先进先出淘汰算法FIFO:\n");
FIFO();
memset(block,0,sizeof(block));
printf("采用最近最久未使用淘汰算法LRU:\n");
LRU();
return 0;
}
/*
12
3
2
3
2
1
5
2
4
5
3
2
5
2
*/
内容总结
以上是互联网集市为您收集整理的操作系统——页面调度算法全部内容，希望文章能够帮你解决操作系统——页面调度算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。