操作系統(tǒng)實(shí)習(xí)報(bào)告桂林理工大學(xué)信息科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)（應(yīng)用）專業(yè)-班覃毅頁(yè)面置換系統(tǒng)設(shè)計(jì)設(shè)計(jì)目的：加深對(duì)請(qǐng)求頁(yè)式存儲(chǔ)管理實(shí)現(xiàn)原理的理解，掌握最佳OPT置換算法、先進(jìn)先出FIFO頁(yè)面置換算法、近來(lái)最久未使用LRU頁(yè)面置換算法，并運(yùn)用程序設(shè)計(jì)語(yǔ)言模擬其過(guò)程。設(shè)計(jì)規(guī)定:1．顧客可覺(jué)得程序指定內(nèi)存塊數(shù)2．顧客能夠自由設(shè)立程序的頁(yè)面訪問(wèn)次序3.顧客可在OPT、FIFO和LRU算法選擇一種,并能觀看到頁(yè)面置換過(guò)程。設(shè)計(jì)內(nèi)容：設(shè)計(jì)一種由顧客輸入指定的鏈?zhǔn)疥?duì)列設(shè)計(jì)一種由顧客指定塊數(shù)的內(nèi)存塊鏈?zhǔn)疥?duì)列分別設(shè)計(jì)OPT、FIFO、LRU算法開(kāi)發(fā)環(huán)境：Windows環(huán)境，VC6.0平臺(tái)分析設(shè)計(jì)：<一>實(shí)驗(yàn)原理：在進(jìn)程運(yùn)行過(guò)程中，若其所要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，需要把它們調(diào)入內(nèi)存，但內(nèi)存已無(wú)空閑空間時(shí)，為了確保進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤(pán)的對(duì)換區(qū)中。OPT算法:每訪問(wèn)一種頁(yè)面都先掃描內(nèi)存塊鏈?zhǔn)疥?duì)列，若現(xiàn)在需訪問(wèn)頁(yè)面已被調(diào)入內(nèi)存則可訪問(wèn)下一種頁(yè)面；否則，從內(nèi)存塊隊(duì)列中選擇一種（將來(lái)）最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面并將其換出。具體實(shí)現(xiàn)：用現(xiàn)在需訪問(wèn)頁(yè)面掃描內(nèi)存塊隊(duì)列，若已被調(diào)入則停止，否則將其計(jì)數(shù)器count加1。最后選擇計(jì)數(shù)器值最大的內(nèi)存塊換出。FIFO算法：該算法在發(fā)生缺頁(yè)時(shí)總是裁減最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以裁減。具體實(shí)現(xiàn)：每個(gè)頁(yè)面調(diào)入內(nèi)存時(shí)總將其放在內(nèi)存塊隊(duì)列的隊(duì)尾，每當(dāng)發(fā)生缺頁(yè)時(shí)就將處在對(duì)頭的內(nèi)存塊頁(yè)面換出。LRU算法：該算法根據(jù)頁(yè)面調(diào)入內(nèi)存后近來(lái)最久未使用的頁(yè)面予以裁減。具體實(shí)現(xiàn)：每個(gè)頁(yè)面調(diào)入內(nèi)存時(shí)其時(shí)間計(jì)數(shù)器count開(kāi)始計(jì)時(shí)，每當(dāng)有頁(yè)面被調(diào)入時(shí)內(nèi)存中的頁(yè)面的時(shí)間計(jì)數(shù)器均加1；新被調(diào)入的頁(yè)面時(shí)間計(jì)數(shù)器初始化為1。發(fā)生缺頁(yè)時(shí)，尋找時(shí)間計(jì)數(shù)器值最大的內(nèi)存塊頁(yè)面換出。<二>程序構(gòu)造：組建顧客輸入的頁(yè)面訪問(wèn)隊(duì)列，q_new=newq_node;q_r->next=q_new;q_r=q_r->next;根據(jù)顧客輸入指定的內(nèi)存塊數(shù)目m,組織m_node類型結(jié)點(diǎn)的內(nèi)存隊(duì)列。m_cp=newm_node;rear->mp=m_cp;尋找換出頁(yè)面并換人新頁(yè)面 m_cp->mpage=temp->page;或者調(diào)節(jié)內(nèi)存塊隊(duì)列 for(m_temp=m_cp,m_cp=m_cp->mp;m_cp!=rear;m_cp=m_cp->mp) {m_temp->mpage=m_cp->mpage;m_temp=m_cp; } m_temp->mpage=m_cp->mpage; m_temp=m_cp; m_temp->mpage=new_mcp->mpage; rear=m_temp;<三>數(shù)據(jù)構(gòu)造：顧客指定的訪問(wèn)頁(yè)面序列構(gòu)造體結(jié)點(diǎn)：structq_node{intpage;//訪問(wèn)頁(yè)號(hào) q_node*next;//指向下一種節(jié)點(diǎn) q_node() {next=NULL;}};內(nèi)存塊構(gòu)造體結(jié)點(diǎn)：structm_node//內(nèi)存塊結(jié)點(diǎn){intmpage;//調(diào)入內(nèi)存中的頁(yè)面號(hào) intcount;//用于計(jì)數(shù) m_node*mp;//指向下一種結(jié)點(diǎn) m_node() { count=0; mp=NULL; }};初始化，將顧客指定的訪問(wèn)頁(yè)面組織成鏈?zhǔn)疥?duì)列，并提示顧客輸入內(nèi)存塊數(shù)目調(diào)用初始化，將顧客指定的訪問(wèn)頁(yè)面組織成鏈?zhǔn)疥?duì)列，并提示顧客輸入內(nèi)存塊數(shù)目調(diào)用LRU算法：LRU(q_h,n)調(diào)用FIFO算法：FIFO(q_h,n)調(diào)用OPT算法：OPT(q_h,n)程序退出，return0；顧客選擇退出，ch=q或者ch=Q判斷顧客選擇的是哪種算法，并調(diào)用對(duì)應(yīng)的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch)顧客選擇算法Cin>>ch 顧客選擇算法顧客選擇算法Cin>>ch顧客選擇算法Cin>>ch判斷顧客選擇的是哪種算法，并調(diào)用對(duì)應(yīng)的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;判斷顧客選擇的是哪種算法，并調(diào)用對(duì)應(yīng)的算法if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch) 運(yùn)行示例及成果分析:選用測(cè)試數(shù)據(jù)并調(diào)用對(duì)應(yīng)算法，頁(yè)面置模擬過(guò)程以下圖所示：1.測(cè)試數(shù)據(jù)為12302，以111作為結(jié)束標(biāo)志，運(yùn)行測(cè)試成功2.測(cè)試數(shù)據(jù)為123564213，測(cè)試成功，頁(yè)面置換模擬過(guò)程以下圖所示：實(shí)習(xí)心得體會(huì)：通過(guò)兩個(gè)星期的操作系統(tǒng)實(shí)習(xí)，我收獲了諸多，也學(xué)到了諸多。為了完畢實(shí)習(xí)任務(wù)，我需要一次又一次地研究頁(yè)面置換的有關(guān)算法，特別是本次需要使用程序設(shè)計(jì)語(yǔ)言模擬設(shè)計(jì)的OPT、FIFO、LRU三種算法。在分析理解透這三個(gè)算法的基礎(chǔ)上，我開(kāi)始著手開(kāi)始設(shè)計(jì)。我用了一天的時(shí)間完畢了程序設(shè)計(jì)，但實(shí)習(xí)任務(wù)絕不是僅此就結(jié)束的。我在調(diào)試程序過(guò)程中，碰到了諸多難題。在此期間我的情緒曾一度低落，甚至對(duì)自己能否獨(dú)立完畢實(shí)習(xí)任務(wù)失去了信心。但很快我懂得編寫(xiě)程序、調(diào)試程序都不是一件容易的事情，我不能太過(guò)于依賴別人的協(xié)助，而需要自己一步步地探索，一點(diǎn)點(diǎn)地積累，才干真正地學(xué)到東西，這這也是郭老師教會(huì)我的。因此，在操作系統(tǒng)實(shí)習(xí)過(guò)程中，我真正地理理解頁(yè)面置換算法的原理與調(diào)度過(guò)程，加深了對(duì)指針的理解，學(xué)會(huì)了如何靈活使用使用指針，同時(shí)也增強(qiáng)了自己的實(shí)踐動(dòng)手能力，達(dá)成了理論聯(lián)系實(shí)際的效果！附錄：源程序清單#include<iostream>usingnamespacestd;structq_node//顧客指定的訪問(wèn)頁(yè)面序列{intpage;//頁(yè)號(hào)q_node*next;//指向下一種節(jié)點(diǎn)q_node() {next=NULL;}};structm_node//內(nèi)存塊結(jié)點(diǎn){intmpage;//調(diào)入內(nèi)存中的頁(yè)面號(hào) intcount;//用于計(jì)數(shù) m_node*mp;//指向下一種結(jié)點(diǎn)m_node(){count=0;mp=NULL;}};intmain(){voidOPT(q_node*h,intx);voidFIFO(q_node*h,intx);voidLRU(q_node*h,intx);q_node*q_h,*q_r,*q_new; intn;charch; cout<<"***************歡迎使用頁(yè)面置換演示系統(tǒng)！***************"<<endl<<endl; cout<<"***************計(jì)算機(jī)（應(yīng)用）-1班********************"<<endl <<"****************學(xué)號(hào)：*********************"<<endl <<"****************覃毅*********************"<<endl<<endl; cout<<"請(qǐng)你輸入需要訪問(wèn)的頁(yè)面隊(duì)列:"<<endl;q_new=newq_node; cin>>q_new->page; q_h=q_new; q_r=q_h; while(q_r->page!=111)//創(chuàng)立顧客指定的訪問(wèn)隊(duì)列 { q_new=newq_node;cin>>q_new->page; q_r->next=q_new; q_r=q_r->next; }cout<<"請(qǐng)輸入你設(shè)立的內(nèi)存塊數(shù)：";cin>>n; cout<<endl<<"請(qǐng)您選擇頁(yè)面置換算法;"<<endl <<"O代表最佳置換算法;"<<endl <<"F代表先進(jìn)先出頁(yè)面置換算法;"<<endl <<"L代表近來(lái)最久未使用算法！"<<endl<<endl;while(1) { cout<<"請(qǐng)選擇你需要調(diào)用的算法：";cin>>ch;//顧客選擇頁(yè)面置換算法 if(ch=='q'||ch=='Q') { cout<<"退出演示系統(tǒng)！"<<endl; break; } if(ch=='o'||ch=='f'||ch=='l'||ch=='q') ch=ch-32;switch(ch) { case'O':OPT(q_h,n);break; case'F':FIFO(q_h,n);break; case'L':LRU(q_h,n);break; default:cout<<"輸入錯(cuò)誤。"<<endl; } }return0;}/****************OPT算法:1.裝入x個(gè)頁(yè)面到內(nèi)存塊數(shù)組；2.判斷待訪問(wèn)隊(duì)列中的首元素，并進(jìn)行對(duì)換或者訪問(wèn)下一頁(yè)******/voidOPT(q_node*h,intx){q_node*temp,*cp;//temp指向訪問(wèn)隊(duì)列中的對(duì)頭，cp作為活動(dòng)指針m_node*head,*rear,*m_cp;inti,max;boolfound;temp=h;head=newm_node;head->mpage=temp->page;//組建內(nèi)塊隊(duì)列rear=head;temp=temp->next;for(i=2;i<=x;i++){ m_cp=newm_node; m_cp->mpage=temp->page; rear->mp=m_cp; rear=rear->mp; temp=temp->next;}//此時(shí)temp指向現(xiàn)在待訪問(wèn)頁(yè)面while(temp->page!=111){ for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp)//**************掃描內(nèi)存數(shù)組，尋找將來(lái)最久不會(huì)被訪問(wèn)的頁(yè)面********************** { cp=temp; found=false; while(cp->page!=111) { if(m_cp->mpage==cp->page) { found=true; break; } else m_cp->count++; cp=cp->next; } }max=head->count;for(m_cp=head->mp;m_cp!=NULL;m_cp=m_cp->mp) if(m_cp->count>max) max=m_cp->count;cp=temp; for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) if(cp->page==m_cp->mpage) { temp=temp->next; found=true; cout<<""<<m_cp->mpage<<"頁(yè)已被調(diào)入內(nèi)存,接著訪問(wèn)下一種頁(yè)面！"<<endl; } if(found)//現(xiàn)在頁(yè)已被調(diào)入內(nèi)存，需訪問(wèn)下一種頁(yè)面 continue; for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) if(m_cp->count==max) { cout<<""<<m_cp->mpage<<"頁(yè)被換出；" <<temp->page<<"頁(yè)換人。"<<endl; m_cp->mpage=temp->page; m_cp->count=0;//****************** break; }temp=temp->next;for(m_cp=head;m_cp!=NULL;m_cp=m_cp->mp) m_cp->count=0;}cout<<"*****************OPT算法結(jié)束！******************"<<endl;}/******************FIFO算法：1.組織內(nèi)存塊隊(duì)列；2.若現(xiàn)在待訪問(wèn)頁(yè)面已存在內(nèi)存中，則將它取出并移動(dòng)到隊(duì)尾，訪問(wèn)下一種元素；否則，用現(xiàn)在待訪問(wèn)頁(yè)面置換對(duì)頭內(nèi)存塊3.訪問(wèn)下一種元素****************/voidFIFO(q_node*h,intx){m_node*head,*rear,*m_cp;intj; boolfound;//標(biāo)記現(xiàn)在待換人頁(yè)面與否已在內(nèi)存q_node*temp=h; head=newm_node; head->mpage=temp->page;//組織內(nèi)存塊隊(duì)列 rear=head; temp=temp->next;for(j=2;j<=x;j++) { m_cp=newm_node; m_cp->mpage=temp->page;rear->mp=m_cp; rear=rear->mp; temp=temp->next; }//跳出循環(huán)時(shí)temp指向現(xiàn)在待訪問(wèn)頁(yè)面while(temp->page!=111)//temp指向現(xiàn)在待訪問(wèn)的元素 { cout<<""<<temp->page<<"頁(yè)被訪問(wèn)！"<<endl; found=false; m_cp=head;//m_cp用于掃描內(nèi)存塊隊(duì)列for(j=1;j<=x;j++) { if(temp->page!=m_cp->mpage)//判斷現(xiàn)在待訪問(wèn)元素與否已經(jīng)調(diào)入內(nèi)存，若沒(méi)有調(diào)入則繼續(xù)掃描內(nèi)存塊隊(duì)列 m_cp=m_cp->mp; else//否則調(diào)節(jié)內(nèi)存塊隊(duì)列 { cout<<""<<temp->page<<"頁(yè)已被調(diào)入內(nèi)存，修改內(nèi)存塊隊(duì)列次序并訪問(wèn)下一種頁(yè)面！"<<endl;m_node*m_temp,*new_mcp=newm_node;//new_mcp結(jié)點(diǎn)用于保存已被調(diào)入的頁(yè)面信息new_mcp->mpage=m_cp->mpage;for(m_temp=m_cp,m_cp=m_cp->mp;m_cp!=rear;m_cp=m_cp->mp) {m_temp->mpage=m_cp->mpage; m_temp=m_cp; } m_temp->mpage=m_cp->mpage; m_temp=m_cp; m_temp->mpage=new_mcp->mpage; rear=m_temp; found=true; break; } } if(found) { temp=temp->next; continue; }//執(zhí)行頁(yè)面置換 m_node*m_temp,*new_mcp=head; cout<<""<<head->mpage<<"頁(yè)被換出，"<<temp->page<<"頁(yè)被換人！"<<endl; for(m_temp=head,new_mcp=head->mp;new_mcp!=rear;new_mcp=new_mcp->mp) { m_temp->mpage=new_mcp->mpage; m_temp=m_temp->mp; }m_temp->mpage=new_mcp->mpage; m_temp=m_temp->mp; m_temp->mpage=temp->page; rear=m_temp;temp=temp->next; }cout<<"*****************FIFO算法結(jié)束!*****************"<<endl;}/***************LRU算法：(備注：節(jié)點(diǎn)元素count用于內(nèi)存塊計(jì)算器)1.組織內(nèi)存隊(duì)列，每當(dāng)有一種新頁(yè)面從外存調(diào)入內(nèi)存，需將其內(nèi)存塊計(jì)算器置12.掃描、換頁(yè)。若現(xiàn)在待訪問(wèn)頁(yè)面已被調(diào)入內(nèi)存，則重新初始化其內(nèi)存塊計(jì)算器值；否則，尋找近來(lái)最久未被訪問(wèn)的內(nèi)存塊頁(yè)面將其換出并將其計(jì)算器置1，同時(shí)使其它內(nèi)存塊頁(yè)面計(jì)算器值加1***************/voidLRU(q_node*h,intx){m_node*head,*rear,*m_cp; intj,k,max; boolfound;//標(biāo)記現(xiàn)在待換人頁(yè)面與否已在內(nèi)存q_node*temp=h; head=newm_node;head->mpage=temp->page;//第一模塊：組織內(nèi)存塊隊(duì)列 rear=head; temp=temp->next;for(j=2;j<=x;j++) {m_cp=newm_node;//m_cp指向現(xiàn)在內(nèi)存塊 m_cp->mpage=temp->page;rear->mp=m_cp; rear=rear->mp; temp=temp->next; m_cp=head; for(k=1;k<=j;k++)//將已調(diào)入內(nèi)存的頁(yè)面計(jì)算器值加1 {m_cp->count++; m_cp=m_cp->mp; }}