操作系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告用C實(shí)現(xiàn)頁面調(diào)度算法

1、操 作 系 統(tǒng)實(shí)驗(yàn)報(bào)告(3)學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院班級：計(jì)091學(xué)號：姓名：時(shí)間：2011/12/31目 錄1. 實(shí)驗(yàn)名稱32. 實(shí)驗(yàn)?zāi)康?3. 實(shí)驗(yàn)內(nèi)容34. 實(shí)驗(yàn)要求35. 實(shí)驗(yàn)原理36. 實(shí)驗(yàn)環(huán)境47. 實(shí)驗(yàn)設(shè)計(jì)47.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)47.2算法設(shè)計(jì)57.3功能模塊設(shè)計(jì)98. 實(shí)驗(yàn)運(yùn)行結(jié)果99. 實(shí)驗(yàn)心得13附錄：源代碼（部分）13一、實(shí)驗(yàn)名稱：用c+實(shí)現(xiàn)頁面調(diào)度算法二、實(shí)驗(yàn)?zāi)康模和ㄟ^自己編程來實(shí)現(xiàn)頁面調(diào)度算法，進(jìn)一步理解頁面調(diào)度算法的概念及含義，提高對頁面調(diào)度算法的認(rèn)識，同時(shí)提高自己的動(dòng)手實(shí)踐能力。加深我們對主存與輔助存儲器統(tǒng)一管理、邏輯地址與物理地址轉(zhuǎn)換、部分裝入和部分替換問題的理

2、解，同時(shí)，有利于我們對虛擬存儲技術(shù)的理解。三、實(shí)驗(yàn)內(nèi)容：利用c+,實(shí)現(xiàn)頁面調(diào)度算法1. 最優(yōu)替換算法opt2. 先進(jìn)先出調(diào)度算法3. 最近最少調(diào)度算法四、實(shí)驗(yàn)要求：1.完成頁面調(diào)度算法的設(shè)計(jì)2.分別計(jì)算每種算法的缺頁次數(shù)和缺頁中斷率五、實(shí)驗(yàn)原理：不必裝入進(jìn)程的全部信息，僅將當(dāng)前使用部分先裝入主存，其余部分存放在磁盤中，待使用時(shí)由系統(tǒng)自動(dòng)將其裝起來。當(dāng)進(jìn)程所訪問的程序和數(shù)據(jù)在主存中時(shí)，可順利進(jìn)行；如果處理器所訪問的程序或數(shù)據(jù)不在主存中，為了繼續(xù)執(zhí)行，由系統(tǒng)自動(dòng)將這部分信息從磁盤裝入，叫做“部分裝入”；如若此刻沒有足夠的空閑物理空間，便把主存中暫時(shí)不用的信息移至磁盤，叫做“部分替換”。目前有許多頁

3、面調(diào)度算法，本實(shí)驗(yàn)主要涉及先進(jìn)先出調(diào)度算法、最近最少調(diào)度算法、最近最不常用調(diào)度算法。本實(shí)驗(yàn)使用頁面調(diào)度算法時(shí)作如下假設(shè)，進(jìn)程在創(chuàng)建時(shí)由操作系統(tǒng)為之分配一個(gè)固定數(shù)目物理頁，執(zhí)行過程中物理頁的數(shù)目和位置不會改變。也即進(jìn)程進(jìn)行頁面調(diào)度時(shí)只能在分到的幾個(gè)物理頁中進(jìn)行。 1.最優(yōu)替換算法opt選擇將來最久不被訪問的頁面作為被替換的頁面，它就是一種比較好的頁面替換算法。2. 先進(jìn)先出調(diào)度算法 先進(jìn)先出調(diào)度算法根據(jù)頁面進(jìn)入內(nèi)存的時(shí)間先后選擇淘汰頁面，先進(jìn)入內(nèi)存的頁面先淘汰，后進(jìn)入內(nèi)存的后淘汰。本算法實(shí)現(xiàn)時(shí)需要將頁面按進(jìn)入內(nèi)存的時(shí)間先后組成一個(gè)隊(duì)列，每次調(diào)度隊(duì)首頁面予以淘汰。 3.最近最少調(diào)度算法 先進(jìn)先出調(diào)

4、度算法沒有考慮頁面的使用情況，大多數(shù)情況下性能不佳。根據(jù)程序執(zhí)行的局部性特點(diǎn)，程序一旦訪問了某些代碼和數(shù)據(jù)，則在一段時(shí)間內(nèi)會經(jīng)常訪問他們，因此最近最少用調(diào)度在選擇淘汰頁面時(shí)會考慮頁面最近的使用，總是選擇在最近一段時(shí)間以來最少使用的頁面予以淘汰。算法實(shí)現(xiàn)時(shí)需要為每個(gè)頁面設(shè)置數(shù)據(jù)結(jié)構(gòu)記錄頁面自上次訪問以來所經(jīng)歷的時(shí)間。缺頁中斷次數(shù)是缺頁時(shí)發(fā)出缺頁中斷的次數(shù) 缺頁中斷率=缺頁中斷次數(shù)/總的頁面引用次數(shù)*100% 六、實(shí)驗(yàn)環(huán)境：win-7系統(tǒng)visual c+ 6.0七、實(shí)驗(yàn)設(shè)計(jì)：1.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)定義結(jié)構(gòu)體：struct pageframe/頁框結(jié)構(gòu)int id;/頁框號int pageid;/駐留的

5、頁號int visitedcount;/駐留頁計(jì)數(shù)器，訪問加1int unvisitedcount;/最近訪問，訪問清零，未訪問加1bool replace;/將被淘汰為trueint staytime;/駐留時(shí)間計(jì)數(shù)int nextsite;struct page/頁結(jié)構(gòu)int id;/頁號struct data/基本數(shù)據(jù)構(gòu)成pageframe *pf;/頁框指針，用于指定個(gè)數(shù)頁框申請int pflength;/頁框個(gè)數(shù)page *p;/頁指針，用于指定個(gè)數(shù)頁申請int plength;/頁個(gè)數(shù)int *pflogicruler;/邏輯標(biāo)尺，用于記錄淘汰序列int pagelackcount

6、;/缺頁計(jì)數(shù)器;定義類對象：class method/方法類private:public:method()bool findpage(data *db,int pid)bool flag=false;for(int i=0;ipflength;i+)if(db-pfi.pageid=pid)db-pfi.visitedcount+;db-pfi.unvisitedcount=1;db-pfi.replace=false;flag=true;elsedb-pfi.unvisitedcount+;db-pfi.staytime+;return flag;2.算法設(shè)計(jì) 2.1 fifo算法class

7、 fifo:public method/fifo算法private:public:void setpflogicruler(data *db)int *a2;a0=new intdb-pflength;a1=new intdb-pflength;for(int i = 0; ipflength;i+)a0i=db-pfi.pageid;a1i=db-pfi.staytime;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;

8、a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)db-pfi.replace=true;2.2 lru算法class lru:public method/lru算法private:public:void setpflogicruler(data *db)int *a2;a0=new intdb-pflength;a1=new intdb-pflength;for(int i = 0; ipflength;i+)a0i=d

9、b-pfi.pageid;a1i=db-pfi.unvisitedcount;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)db-pfi.replace=true;2.3 opt算法class opt

10、:public method/opt算法private:public:void setpflogicruler(data *db,int site)for(int i=0;ipflength;i+)if(db-pfi.pageid!=-1)db-pfi.nextsite=db-plength+1;elsedb-pfi.nextsite=db-plength+2;for(int j=site; jplength;j+)if(db-pfi.pageid=db-pj.id)db-pfi.nextsite=j+1;break;int *a2;a0=new intdb-pflength;a1=new i

11、ntdb-pflength;for( i = 0; ipflength;i+)a0i=db-pfi.pageid;a1i=db-pfi.nextsite;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)

12、db-pfi.replace=true;break;3.功能模塊設(shè)計(jì)class control/選擇所需算法struct data/基本數(shù)據(jù)構(gòu)成struct page/頁結(jié)構(gòu)struct pageframe/頁框結(jié)構(gòu)class display/輸出class fifo:public method/fifo算法class lru:public method/lru算法class opt:public method/opt算法class method/方法類void main() /主函數(shù)8、 實(shí)驗(yàn)運(yùn)行結(jié)果：1.選擇opt算法實(shí)現(xiàn)：2.選擇fifo算法實(shí)現(xiàn)3.選擇lru算法實(shí)現(xiàn)九、實(shí)驗(yàn)心得：通過此

13、次的實(shí)驗(yàn),我更加了解了全局替換策略,了解到先進(jìn)先出頁面替換算法總是淘汰最先調(diào)入主存的頁面,淘汰在主存中駐留時(shí)間最長的頁面。了解到最近最少使用頁面替換算法淘汰的頁面是在最近一段時(shí)間內(nèi)最久未被訪問的那一頁。在整體上加深了我對虛擬存儲管理的理解，構(gòu)件了一個(gè)系統(tǒng)的存儲管理的體系。當(dāng)然在實(shí)驗(yàn)過程中，我也遇到了一些困難，但是我通過及時(shí)請教同學(xué)，查詢相關(guān)資料，及時(shí)解決了問題，但仍有不足之處，我將會在今后學(xué)習(xí)中更加努力。附錄：源代碼（部分）#includeusing namespace std;struct pageframe/頁框結(jié)構(gòu)int id;/頁框號int pageid;/駐留的頁號int visit

14、edcount;/駐留頁計(jì)數(shù)器，訪問加1int unvisitedcount;/最近訪問，訪問清零，未訪問加1bool replace;/將被淘汰為trueint staytime;/駐留時(shí)間計(jì)數(shù)int nextsite;struct page/頁結(jié)構(gòu)int id;/頁號struct data/基本數(shù)據(jù)構(gòu)成pageframe *pf;/頁框指針，用于指定個(gè)數(shù)頁框申請int pflength;/頁框個(gè)數(shù)page *p;/頁指針，用于指定個(gè)數(shù)頁申請int plength;/頁個(gè)數(shù)int *pflogicruler;/邏輯標(biāo)尺，用于記錄淘汰序列int pagelackcount;/缺頁計(jì)數(shù)器;cla

15、ss methodprivate:public:method()bool findpage(data *db,int pid)bool flag=false;for(int i=0;ipflength;i+)if(db-pfi.pageid=pid)db-pfi.visitedcount+;db-pfi.unvisitedcount=1;db-pfi.replace=false;flag=true;elsedb-pfi.unvisitedcount+;db-pfi.staytime+;return flag;int replace(data *db,int pfid,int pid)int p

16、;p=db-pfpfid.pageid;db-pfpfid.pageid=pid;db-pfpfid.replace=false;db-pfpfid.unvisitedcount=1;db-pfpfid.visitedcount=1;db-pfpfid.staytime=1;db-pagelackcount+;return p;int longesttime(data *db)int lt,pfnum;pfnum=db-pf0.id;lt=db-pf0.staytime;for(int i=1; ipflength;i+)if(ltpfi.staytime)lt=db-pfi.staytime

17、;pfnum=db-pfi.id;return pfnum;int mostunvisited(data *db)int mu=0;mu=db-pf0.unvisitedcount;for(int i=0;ipflength;i+)if(mudb-pfi.unvisitedcount)mu=db-pfi.visitedcount;return mu;void setpflogicruler()int getdiepf(data *db)for(int i=0;ipflength;i+)if(db-pfi.replace=true)return db-pfi.id;class opt:publi

18、c methodprivate:public:void setpflogicruler(data *db,int site)for(int i=0;ipflength;i+)if(db-pfi.pageid!=-1)db-pfi.nextsite=db-plength+1;elsedb-pfi.nextsite=db-plength+2;for(int j=site; jplength;j+)if(db-pfi.pageid=db-pj.id)db-pfi.nextsite=j+1;break;int *a2;a0=new intdb-pflength;a1=new intdb-pflengt

19、h;for( i = 0; ipflength;i+)a0i=db-pfi.pageid;a1i=db-pfi.nextsite;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)db-pfi.repla

20、ce=true;break;class fifo:public methodprivate:public:void setpflogicruler(data *db)int *a2;a0=new intdb-pflength;a1=new intdb-pflength;for(int i = 0; ipflength;i+)a0i=db-pfi.pageid;a1i=db-pfi.staytime;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0

21、j+1;a1j+1=t;a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)db-pfi.replace=true;class lru:public methodprivate:public:void setpflogicruler(data *db)int *a2;a0=new intdb-pflength;a1=new intdb-pflength;for(int i = 0; ipflength;i+)a0i=db-p

22、fi.pageid;a1i=db-pfi.unvisitedcount;int t,h;for(i = 1; ipflength;i+)for(int j=0;jpflength-i;j+)if(a1ja1j+1)t=a1j;h=a0j;a1j=a1j+1;a0j=a0j+1;a1j+1=t;a0j+1=h;for( i = 0; ipflength;i+)db-pflogicruleri=a0i;for(i = 0; ipflength;i+)if(db-pfi.pageid=db-pflogicruler0)db-pfi.replace=true;class controlprivate:

23、public:opt opt;fifo fifo;lru lru;control();class setbaseinfoprivate:public:setbaseinfo()void setpageframe(data *db)for(int i=0;ipflength;i+)db-pfi.id=i;db-pfi.pageid=-1;db-pfi.replace=false;db-pfi.staytime=1;db-pfi.unvisitedcount=1;db-pfi.visitedcount=1;db-pflogicruleri=-1;db-pfi.nextsite=db-plength

24、+2;void setpage(data *db)int pid;cout設(shè)置頁面訪問順序.n;for(int i=0;iplength;i+)cout輸入第ipid;db-pi.id=pid;cout設(shè)置頁面訪問順序完畢n;class displayprivate:public:display()void displaypagelist(data*db)cout頁表順序: ;for(int i=0;iplength;i+)coutpi.id ;coutendl;void displaylogicruler(data*db)cout淘汰序列: ;for(int i=0;ipflength;i+

25、)if(db-pflogicruleri=-1)continue;coutpflogicruleri ;coutendl;void displaypagelack(data*db)cout缺頁數(shù): pagelackcount;cout 缺頁率: pagelackcount/(1.0*db-plength);coutendl;void displaypageframe(data*db)cout頁框 頁面 須淘汰 駐留時(shí)間 最少訪問 最多訪問 下一次出現(xiàn)位置n;for(int i=0;ipflength;i+)cout ;coutpfi.idpfi.pageid=-1)cout ;elsecout

26、pfi.pageid ;coutpfi.replace ;coutpfi.staytime ;coutpfi.unvisitedcount ;coutpfi.visitedcountpfi.nextsitedb-plength)elsecoutpfi.nextsite;coutendl;void main()cout-頁面調(diào)度算法模擬-n;cout-預(yù)置信息-n;int choice=1;data *db;db=new data;int plength=9;coutplength;int pflength=3;coutpflength;db-plength=plength;db-pflengt

27、h=pflength;db-p=new pageplength;db-pf=new pageframepflength;db-pagelackcount=0;db-pflogicruler=new intpflength;setbaseinfo setbaseinfo;setbaseinfo.setpage(db);setbaseinfo.setpageframe(db);display display;control control;coutn選擇頁面調(diào)度算法n;cout 1. 最佳頁面替換算法(opt)n;cout 2. 先進(jìn)先出頁面替換算法(fifo)n;cout 3. 最近最少使用頁面替換算法(lru)n;coutchoice;switch(choice)case 1:control.opt.setpflogicruler(db,-3);display.displaylogicruler(db);for(int i = 0; iplength;i+)