页面调度算法

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

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过程就是这样。

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

② 页面调度算法

- 后的答案，你知道
打字不易，如满意，望采纳。

③ 页面调度先进先出算法（FIFO） 用C语言描述 欢迎高手前来挑战

c语言实现的页面调度算法,用三种算法实现调度1.先进先出2.OPT3.LRU 2.页面序列从指定的文本文件（TXT文件）中取出3.输出：第一行：每次淘汰的页面号 第二行：显示缺页的总次数(上机已经运行通过!!)-pages scheling algorithm, a three-Scheling Algorithm 1. FIFO 2.OPT3.LRU 2. Pages from the designated sequence of text files (TXT) out of three. Output : the first line : each of the pages out of the second line : show na the total number of pages (on the plane had run through! !)

④ 页面调度算法的实验目的

页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。

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

（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个物理块，使用程序的动态页面序列生成算法，生成一个页面序列，将此序列存入磁盘文件。再从磁盘文件读入该序列，用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。

⑥ 如何利用FIFO页面调度算法计算！

4 2 3 0 0 0 1 2 2 2
4 2 3 3 3 0 1 1 1
4 2 2 2 3 0 0 0
FT T F F T T
F：中断 前面三个已装入了不算中断。希望对你有帮助。

⑦ 页面调度算法的实验步骤

#include stdafx.h
#include conio.h
#include iostream.h
#include fstream.h
//-------------------------------Menu----------------------#define KEY_EXIT '-'
typedef struct{
char ch;
char *label;
void (*pfunc)();
}MenuItemDef;
Void clearscr() {cout<< ;}
int waitakey(){return getch();}
class MenuDef
{public:
int nCount;
MenuItemDef menu[24];
public:
MenuDef(){nCount=0;}
public:
void display()
{ for(int i=0; i<nCount;i++)
cout<< <<menu.ch<<.<<menu.label<<endl;
cout<< <<KEY_EXIT<<.<<EXIT<<endl; }
void run()
{int ch;
do{clearscr();
display();
ch=waitakey();
for(int i=0;i<nCount;i++)
if(menu.ch==ch)
menu.pfunc();
}while(ch!=KEY_EXIT); }
void add (char ch0,char *plabel,void(*func)())
{ menu[nCount].ch=ch0;
menu[nCount].label=plabel;
menu[nCount].pfunc=func;
nCount++;}};
//--------------------------------------page-----------------------
class Page{
public:
Page(){SetNull();}
public:
enum{kLFU=0,kFCFS,kLRU};
int nCurPage;
int nAlgID;
int nCountPage;
int pages[128];
int nCountFrame;
int nEmpty;
int frames[32];
int counters[32];
int nCount1;
int nCount2;
public:
void Input();
void Run();
int IsFinish(){return nCurPage>=nCountPage;}
void SetAlgorithm(int kAlgId){nAlgID=kAlgId;}
void SetNull()
{nCurPage=nCountPage=nCountFrame=nCount1=nCount2=nEmpty=0 ; nAlgID=kLRU;}
double IPercent(){return nCount1*1.0/nCurPage;}//缺页中断率
double EPercent(){return nCount2*1.0/nCurPage;}//缺页转换率
//functions should be implemented......
void FCFS() {} //先来先服务调度算法
void LRU() {} //LRU调度算法
void LFU() {} //LFU调度算法
void Display() {} //系统状态
void DisplayAlg() {} //算法执行状态
public:
friend istream& operator>>(istream&stream,Page&p)
{return stream;}
friend ostream& operator>>(ostream&stream,Page&p)
{return stream;} };
void Page::Input()
{ cout<<Count of page-frames:;
cin>>nCountFrame;
nEmpty=nCountFrame;
cout<<Count of page:;
cin>>nCountPage;
for (int i=0;i<nCountPage;i++)
cin>>pages;
nCurPage=0;
}
void Page::Run()
{ while(!IsFinish()){
waitakey(); //wait for a key pressed
if(nAlgID==kLFU)
LFU();
else if(nAlgID==kFCFS)
FCFS();
else
LRU();
DisplayAlg();
nCurPage++;}}
//------------global variables-----------------
MenuDef menu;
Page page;
//------------call-back functions for menu-------
void input()
{ clearscr();
page.SetNull();
page.Display();}
void display()
{ clearscr();
page.Display();}
void setalg1()
{ page.SetAlgorithm(Page::kLFU); }
void setalg2()
{ page.SetAlgorithm(Page::kFCFS); }
void setalg3()
{ page.SetAlgorithm(Page::kLRU); }
void run()
{ clearscr();
page.Run();}
void load()
{ char fname[128];
cout<< Load From file:;
cin>>fname;
ifstream inFile;
inFile.open(fname);
page.SetNull();
inFile>>page; }
void save()
{ char fname[128];
cout<< Save to file:;
cin>>fname;
ofstream outFile;
outFile.open(fname);
outFile>>page; }
void main(int args,char *argv[])
{ menu.add('1',Input from keyboard, input);
menu.add('3',Set Algorithm1:LFU,setalg1);
menu.add('4',Set Algorithm2:FCFS, setalg2);
menu.add('5',Set Algorithm3:LRU, setalg3);
menu.add('6',Display, display);
menu.add('7',Run, run);
menu.add('8',Load from file, load);
menu.add('9',Save to file, save);
menu.run();}

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

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);
}
}

⑨ 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)

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

其实我不懂你这个问题下面是我复制别人的 哈 不知道是不是
#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;
}
}