頁面調度算法

實驗名稱

頁式虛擬存儲管理：頁面調度算法

實驗目的

頁式虛擬存儲器實現的一個難點是設計頁面調度（置換）算法，即將新頁面調入記憶體時，如果記憶體中所有的物理頁都已經分配出去，就要按某種策略來廢棄某個頁面，將其所占據的物理頁釋放出來，供新頁面使用。本實驗的目的是通過編程實現幾種常見的頁面調度（置換）算法，加深讀者對頁面思想的理解。

實驗原理

頁面調度算法

目前有許多頁面調度算法，本實驗主要涉及先進先出調度算法、最近最少調度算法、最近最不常用調度算法。本實驗使用頁面調度算法時作如下假設，進程在創建時由作業系統為之分配一個固定數目物理頁，執行過程中物理頁的數目和位置不會改變。也即進程進行頁面調度時只能在分到的幾個物理頁中進行。

下面對各調度算法的思想作一介紹。

<1> 先進先出調度算法

先進先出調度算法根據頁面進入記憶體的時間先後選擇淘汰頁面，先進入記憶體的頁面先淘汰，後進入記憶體的後淘汰。本算法實現時需要將頁面按進入記憶體的時間先後組成一個佇列，每次調度隊首頁面予以淘汰。

<2>最近最少調度算法

先進先出調度算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程式執行的局部性特點，程式一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。算法實現時需要為每個頁面設定數據結構記錄頁面自上次訪問以來所經歷的時間。

<3>最近最不常用調度算法

由於程式設計中經常使用循環結構，根據程式執行的局部性特點，可以構想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。算法實現時需要為每個頁面設定計數器，記錄訪問次數。計數器由硬體或作業系統自動定時清零。

缺頁調度次數和缺頁中斷率、缺頁置換率計算

缺頁中斷次數是缺頁時發出缺頁中斷的次數。

缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%

缺頁調度次數是調入新頁時需要進行頁面調度的次數

缺頁置換率=缺頁調度次數/總的頁面引用次數*100%

實驗內容

（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 "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<<"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";}

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<<"\nLoad From file:";

cin>>fname;

ifstream inFile;

inFile.open(fname);

page.SetNull();

inFile>>page; }

void save()

{ char fname[128];

cout<<"\nSave 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();}