覃毅操作系統(tǒng)實習(xí)報告

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