页式虚拟存储管理：页面调度算法
1.实验名称：页式虚拟存储管理：页面调度算法
2.实验目的
页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。
3.实验原理
（1）页面调度算法
目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。
下面对各调度算法的思想作一介绍。
<1> 先进先出调度算法
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
<2>最近最少调度算法
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
<3>最近最不常用调度算法
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（2）缺页调度次数和缺页中断率、缺页置换率计算
缺页中断次数是缺页时发出缺页中断的次数。
缺页中断率=缺页中断次数/总的页面引用次数*100%
缺页调度次数是调入新页时需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数*100%
4.实验内容
（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个物理块，使用程序的动态页面序列生成算法，生成一个页面序列，将此序列存入磁盘文件。再从磁盘文件读入该序列，用程序分别计算三种算法下的缺页中断次数、缺页中断率和缺页调度次数、缺页置换率。
5.实验步骤
#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();}
