操作系统的页面调度算法

❶ 页面调度算法的实现和分析源码

dev c++

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct mem
{
int num;
int v;
}meme;
static int process[1024],L,M;
void LRU();
void FIFO();
void get();
int menu();

int main()
{
menu();
system("pause");
}

int menu()
{
int x;
while(1)
{
printf("************************************************\n\n");
printf("*************1.输入页面地址流长度***************\n");
printf("*************2.输入存储块数目 ***************\n");
printf("*************3.获得页面地址流 ***************\n");
printf("*************4.FIFO算法 ***************\n");
printf("*************5.LRU算法 ***************\n");
printf("*************6.退出 ***************\n\n");
printf("************************************************\n\n");
printf("请选择：");
scanf("%d",&x);
switch(x)
{
case 1:printf("\n请输入页面地址流长度L(10<L<100)：");scanf("%d",&L);break;
case 2:printf("\n请输入输入存储块数目M(3<=M<=5)：");scanf("%d",&M);break;
case 3:printf("\n获得页面地址流为：");get();break;
case 4:printf("\n算法：FIFO L=%d M=%d",L,M);FIFO();break;
case 5:printf("\n算法：LRU L=%d M=%d",L,M);LRU();break;
case 6:exit(0);break;
default:printf("\n输入错误！");break;
}
printf("\n\n");
}
}

void get()
{
srand((unsigned)time(NULL));
for(int i=0;i<L;i++)
{
process[i]=rand()%10;
printf("%d ",process[i]);
}
}

void FIFO()
{
int i = 0, j = 0,k=0,x,y;
int replace,count=0;
meme memery[M];
printf("\n页号");
for(k=0;k<M;k++){printf("\t块%d",k+1);memery[k].num=-1;}
printf("\t淘汰\t缺页统计");

for(i = 0; i<L; i++) //对输入序列进行循环
{
x=0;y=0; //置x，y初值为0
for(j = 0; j <M; j++) //对三个内存块进行循环，先查找有没有与即将访问页号相同的
if(memery[j].num == process[i])
{ x=1;//有相同的则置x为1
replace=-2;
break;//跳出此次内存块循环
}

if(x==0)//没有与即将访问页号相同的内存块
{
for(j = 0; j <M; j++)//对内存块循环，查找有没有空内存块
if(memery[j].num==-1)
{
y=1;//有则置y为1
replace=-1;count++;
memery[j].num=process[i];// 置此内存块为访问页号
if(j!=0) memery[j-1].v=0;//置上一个访问块v为0
memery[j].v=1;//置此块v为1
break;//跳出此次内存块循环
}
}

if(x==0&&y==0)//既没有与即将访问页号相同的内存块也没有空内存块
{
for(j=0;j<M;j++)//对内存块循环，查找出v=1的内存块
{
if(memery[j].v==1)
{
memery[j].v=0;//置此块v为0
count++;
if(j!=M-1)
{
replace=memery[j+1].num;
memery[j+1].num=process[i]; //置下个内存块为访问页号块
memery[j+1].v=1;//置下个内存块v为1
}
else
{
replace=memery[0].num;
memery[0].num=process[i]; //置下个内存块为访问页号块
memery[0].v=1;//置下个内存块v为1
}
break;
}
}
}

printf("\n%d",process[i]);
for(j = 0 ;j <M; j++) //打印每次访问后的情况
printf("\t%d",memery[j].num);
if(replace!=-2)
printf("\t%d",replace);
else printf("\t");
printf("\t%d",count);
}
}

void LRU()
{
int i = 0, j = 0,k=0,x,y;
int replace,count=0;
meme memery[M];
printf("\n页号");
for(k=0;k<M;k++){printf("\t块%d",k+1);memery[k].num=-1;}
printf("\t淘汰\t缺页统计");

for(i = 0; i<L; i++) //对输入序列进行循环
{
x=0;y=0; //置x，y初值为0
for(j = 0; j<M; j++) //对三个内存块进行循环，先查找有没有与即将访问页号相同的
if(memery[j].num == process[i])
{ x=1;//有相同的则置x为1
replace=-2;
memery[j].v=0;//置此块v为0
for(k=0;k<M;k++)
if(k!=j&&memery[k].num!=-1)memery[k].v++;//其他不为-1页v++
break;//跳出此次内存块循环
}

if(x==0)//没有与即将访问页号相同的内存块
{
for(j = 0; j <M; j++)//对内存块循环，查找有没有空内存块
if(memery[j].num==-1)
{
y=1;//有则置y为1
replace=-1; count++;
memery[j].num=process[i];// 置此内存块为访问页号
memery[j].v=0;//置此块v为0
for(k=0;k<M;k++)
if(k!=j&&memery[k].num!=-1)memery[k].v++;//其他不为-1页v++
break;//跳出此次内存块循环
}
}

if(x==0&&y==0)//既没有与即将访问页号相同的内存块也没有空内存块
{
int m=memery[0].v;
for(j = 0; j < M; j++)
{
if(memery[j].v>m)
m=memery[j].v;
}//查找出v最大的内存块m
for(j=0;j<M;j++)//对内存块循环，v=m的内存块
{
if(memery[j].v==m)
{
replace=memery[j].num;
count++;
memery[j].num=process[i]; //置此内存块为访问页号块
memery[j].v=0;//置此块v为0
}
else memery[j].v++;//其他块v++
}
}

printf("\n%d",process[i]);
for(j = 0 ;j <M; j++) //打印每次访问后的情况
printf("\t%d",memery[j].num);
if(replace!=-2)
printf("\t%d",replace);
else printf("\t");
printf("\t%d",count);
}
}

❷ 操作系统概论的LRU调度算法

LUR是最近最少使用调度算法。
刚开始三个内存单元都是空的，7,0,1直接装入内存；
当2要装入内存时，由于3个内存单元都已被暂用，必须先有一个页让出内存，根据最近最少使用调度算法的原则，最少使用的页号为7（最长时间未使用），所以7出去，2进来，形成0,1,2的布局（2取代了7的位置，所以实际的顺序是2,0,1，但是将其按照最长时间未使用的顺序排列便于理解和后面的运算）
0页面要装入内存，但是其实它本来已经就在内存中，所以无需调度，内存中页面不变，将其按照最长时间未使用的顺序排列为1,2,0（实际顺序还是2,0,1）；
3要进入内存，将最长时间未用到的1替换出去，所以又变成了2,0,3（3替换原来1的位置，所以实际顺序为2,0,3）
依次类推可得结果。

❸ k：=（k+1）mod n页面调度FIFO算法公式怎么解释

条件：
a^k = n (mod k+1)
b^k = m (mod k+1)
m*n = 1 (mod k+1)
所以(ab)^k = 1 (mod k+1) (1)

记k+1的欧拉函数为ψ(k+1)，那么在(1,ψ(k+1))内，有且仅有
a^ψ(k+1) = 1 (mod k+1)
b^ψ(k+1) = 1 (mod k+1)
相乘得(ab)^ψ(k+1) = 1 (mod k+1) (2)
由于k >=ψ(k+1)
由(1)(2)可以得到k = p * ψ(k+1)
所以m = a^k = (a^ψ(k+1))^p = 1 (mod k+1)
n = b^k = (b^ψ(k+1))^p = 1 (mod k+1)

❹ 页面调度算法的实验内容

（1）设计程序实现以上三种页面调度算法，要求：
①.可以选择页面调度算法类型；
②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，可以从键盘输入页面序列，也可从文件中读取；
③.随时计算当前的页面调度次数的缺页中断率；
④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝；
⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上；
⑥.存盘及读盘功能，可以随时将数据存入磁盘文件，供以后重复实验时使用。
（2）假定进程分配到3个物理块，对于下面的页面引用序列：
7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1
请分别用先进和先出调度算法，最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。
再假定进程分配到4、5个物理块，重复本实验。
（3）假定进程分配到3个物理块，对于下面的页面引用序列：
4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9
请分别用先进先出调度算法、最近最少用调度算法，最近最不常用调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。
再假定进程分配到4、5个物理块，重复本实验。
（4）假定进程分配到3个物理块，使用程序的动态页面序列生成算法，生成一个页面序列，将此序列存入磁盘文件。再从磁盘文件读入该序列，用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。

❺ 求高手教教我"虚拟内存页面调度算法"

其实我不懂你这个问题下面是我复制别人的 哈 不知道是不是
#include <iostream>
#include <deque>
#include <ctime>
using namespace std;

typedef struct
{
int id; //页面ID
int stayTime; //内存中驻留时间
int unUseTime; //已经多久未被使用
}CPage;
deque<int> RunQueue;
deque<CPage> interPage; //内存中的四个页面
deque<CPage> exterPage; //外存中的N个页面
int presentSeat; //目前运行到了队列的第几个？
int lackNum[3] ={0};
int getRandNum(int range) //返回[0,range)范围内的整数
{
return static_cast<int>(rand()%range);
}
int findPageIdByCmdId(int cmdId) //通过强制转换成整数的形式判断指令属于哪个页面
{
return static_cast<int>(cmdId/10);
}
void InitDevice() //初始化运行队列 按照25% 50% 25%的标准生成
{
srand(static_cast<int>(time(NULL)));
int t_cmdNum = getRandNum(320); //随机选择第一条指令
RunQueue.push_back(t_cmdNum); //将其插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //顺序执行下一条指令

while(RunQueue.size() <= 320)
{
t_cmdNum = getRandNum(t_cmdNum); //跳转到m1属于[0,m-1]
RunQueue.push_back(t_cmdNum); //将m1插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m1+1插入队列
int temp = 320 - (t_cmdNum + 2);
t_cmdNum = t_cmdNum+2+getRandNum(temp);//跳转到m2属于[m+2,319]
RunQueue.push_back(t_cmdNum); //插入队列
if(t_cmdNum < 319)
RunQueue.push_back(t_cmdNum+1); //将m2+1插入队列
}
while(RunQueue.size() > 320)
RunQueue.pop_back();
}
void InitMemoryQueue() //初始化运行标志、内存外存页面队列
{
presentSeat = 0;
exterPage.clear();
interPage.clear();
for(int i=0;i<32;i++)
{
CPage temp;
temp.id = i;
temp.stayTime = 0;
temp.unUseTime = 0;
exterPage.push_back(temp);
}
}
int searchStatusOfPage(int t_PageId,bool sign) //分别在内外存中查找页面 存在返回位置 不存在返回-1
{
if(sign)
for(unsigned i=0;i<interPage.size();i++)
{
if(t_PageId == interPage[i].id)
return i;
} //这里的括号不能删除，否则if else的匹配会出问题
else
for(unsigned j=0;j<exterPage.size();j++)
if(t_PageId == exterPage[j].id)
return j;
return -1;
}
int searchNextStatusOfInterPage(int start, int id) //OPT算法中查找内存页面中的页面下次需要用到它的时候的队列下标
{ //找到就返回下标 没找到就返回-1
for(int i=start;i < 320;i++)
if(static_cast<int>(RunQueue[i]/10) == id)
return i;
return -1;
}
int findLongestStayTimePage() //FIFO算法中查找在内存中呆了最久的页面
{
int max = 0;
for(unsigned i=1;i<interPage.size();i++)
if(interPage[i].stayTime>interPage[max].stayTime)
max = i;
return max;
}
int findLongestUnUseTimePage() //LRU算法中查找最久未使用的页面
{
int max = 0;
for(unsigned j=0;j<interPage.size();j++)
if(interPage[j].unUseTime>interPage[max].unUseTime)
max = j;
return max;
}
int findNeedLongestTimePage() //OPT算法中查找最长时间不会用到的页面
{
deque<int> temp;
for(unsigned i=0;i < interPage.size();i++)
{
int it = searchNextStatusOfInterPage(presentSeat,interPage[i].id);
if(it == -1)
return i;
temp.push_back(it);
}
int max = -1,status = 0;
for(unsigned j=1;j < temp.size();j++)
{
if(max < temp[j])
{
max = temp[j];
status = j;
}
}
return status; //返回需要最长时间才执行的页面在内存中的位置
}
void directFlod(int t_PageId) //当内存空间还有剩余时直接调入
{
int status = searchStatusOfPage(t_PageId,false);
if(status == -1) return;
interPage.push_back(exterPage[status]); //先插入节点到内存，再从外存中将其删除
exterPage.erase(exterPage.begin()+status);
}
bool Manage(int count,int t_PageId) //当内存已经满了需要按照三种算法调度时
{
int status = searchStatusOfPage(t_PageId,false); //获取执行页面在外存中的索引地址
if(status == -1)
return false;
int targetStatus = 0;
if(count == 0)
targetStatus = findNeedLongestTimePage();
else if(count == 1)
targetStatus = findLongestStayTimePage();
else if(count == 2)
targetStatus = findLongestUnUseTimePage();
interPage[targetStatus].stayTime = 0;
interPage[targetStatus].unUseTime = 0;
swap(exterPage[status],interPage[targetStatus]);
return true;
}
void Run(int count) //运行，通过count来决定使用什么算法
{
while(presentSeat < 320)
{
for(unsigned i=0;i<interPage.size();i++)
{
interPage[i].stayTime++;
interPage[i].unUseTime++;
}
int t_PageId = findPageIdByCmdId(RunQueue[presentSeat++]),status = -1; //找到当前将要执行的指令的页面号
if((status =searchStatusOfPage(t_PageId,true)) != -1)
{
interPage[status].unUseTime = 0;
continue;
}
lackNum[count]++;
if(interPage.size()<4)
directFlod(t_PageId);
else
Manage(count,t_PageId);
}
}
void main(void) //主函数
{
InitDevice();
int count = 0;
while(count<3)
{
InitMemoryQueue();
Run(count);
cout<<(double)lackNum[count++]/320*100<<"%"<<endl;
}
}

❻ 最佳页面淘汰算法是怎样计算的

<1> 先进先出调度算法
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
<2>最近最少调度算法
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
<3>最近最不常用调度算法
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（2）缺页调度次数和缺页中断率、缺页置换率计算
缺页中断次数是缺页时发出缺页中断的次数。
缺页中断率=缺页中断次数/总的页面引用次数*100%
缺页调度次数是调入新页时需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数*100%

❼ 操作系统原理与应用之 页面调度算法问题

FIFO：即先进先出算法，就是先进去的页在位置不够时先淘汰。所以具体如下：
主存开始为空
访问1，1不在主存中，产生缺页中断，添加，主存里现在是：1
访问2，2不在主存中，产生缺页中断，添加，主存里现在是：1,2
以此类推，
1,2,3（缺页中断）
1,2,3,6（缺页中断）
访问4，4不在主存中，缺页中断，主存满了，最早的1淘汰，主存里现在是：2,3,6,4
然后3,6,4,7（缺页中断，2淘汰）
然后3，3在主存中，不产生中断
然后6,4,7,2（缺页中断，3淘汰）
4,7,2,1（缺页中断，6淘汰）
4在主存中，不中断
7在主存中，不中断
7,2,1,5（缺页中断，4淘汰）
2,1,5,6（缺页中断，7淘汰）
5在主存中，不中断
2在主存中，不中断
1在主存中，不中断
整个FIFO过程就是这样。

LRU是最近最久未使用的先淘汰，具体如下：
1（缺页中断）
1,2（缺页中断）
1,2,3（缺页中断）
1,2,3,6（缺页中断）
2,3,6,4（缺页中断，1最久没用过，淘汰）
3,6,4,7（缺页中断，2最久没用过，淘汰）
3在主存中，不中断，3最近使用过，主存中顺序调整为6,4,7,3
4,7,3,2（缺页中断，6最久没用过，淘汰）
7,3,2,1（缺页中断，4最久没用过，淘汰）
3,2,1,4（缺页中断，7最久没用过，淘汰）
2,1,4,7（缺页中断，3最久没用过，淘汰）
1,4,7,5（缺页中断，2最久没用过，淘汰）
4,7,5,6（缺页中断，1最久没用过，淘汰）
5在主存中，调整顺序为4,7,6,5
7,6,5,2（缺页中断，4最久没用过，淘汰）
6,5,2,1（缺页中断，7最久没用过，淘汰）
整个LRU过程就是这样。

全手打求采纳谢谢~！如有问题请追问~

❽ 操作系统的主要算法都有哪些

一、进程(作业)调度算法
l 先来先服务调度算法（FCFS）：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。特点：利于长进程，而不利于短进程。

l 短进程（作业）优先调度算法(SPF)：它是从就绪队列中选择一个估计运行时间最短的进程，将处理器分配给该进程，使之占有处理器并执行，直到该进程完成或因发生事件而阻塞，然后退出处理器，再重新调度。

l 时间片轮转调度算法 ：系统将所有的就绪进程按进入就绪队列的先后次序排列。每次调度时把CPU分配给队首进程，让其执行一个时间片，当时间片用完，由计时器发出时钟中断，调度程序则暂停该进程的执行，使其退出处理器，并将它送到就绪队列的末尾，等待下一轮调度执行。

l 优先数调度算法 ：它是从就绪队列中选择一个优先权最高的进程，让其获得处理器并执行。

l 响应比高者优先调度算法：它是从就绪队列中选择一个响应比最高的进程，让其获得处理器执行，直到该进程完成或因等待事件而退出处理器为止。特点：既照顾了短进程，又考虑了进程到达的先后次序，也不会使长进程长期得不到服务，因此是一个比较全面考虑的算法，但每次进行调度时，都需要对各个进程计算响应比。所以系统开销很大，比较复杂。

l 多级队列调度算法

基本概念：

作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

作业平均周转时间(T)＝周转时间/作业个数

作业带权周转时间（Wi）＝周转时间/运行时间

响应比＝（等待时间＋运行时间）/运行时间

二、存储器连续分配方式中分区分配算法
n 首次适应分配算法（FF）：对空闲分区表记录的要求是按地址递增的顺序排列的，每次分配时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区，一部分分配给作业，另一部分仍为空闲区。

n 循环首次适应算法：每次分配均从上次分配的位置之后开始查找。

n 最佳适应分配算法(BF)：是按作业要求从所有的空闲分区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲区表中，分配时，顺序查找。

三、页面置换算法
l 最佳置换算法（OPT) ：选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

l 先进先出置换算法（FIFO）：选择最先进入内存的页面予以淘汰。

l 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

l 最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

四、磁盘调度
n 先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

n 最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

n 扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

n 循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。