南通大學計算機科學與技術學院專南通大學計算機科學與技術學院專業：學生姓名：學號：時間：操作系統課程設計報告操作系統課程設計報告操作系統模擬算法課程設計報告設計要求將本學期三次的實驗集成實現：處理機管理；存儲器管理；虛擬存儲器的缺頁調度。設計流程圖主流程圖開始的圖形界面開始的圖形界面存儲器管理缺頁調度處理機管理存儲器管理缺頁調度處理機管理LRU算法先進先出最佳適應法首次適應法先來先服務 LRU算法先進先出最佳適應法首次適應法先來先服務時間片輪轉時間片輪轉A.處理機調度1)先來先服務FCFS開始開始初始化進程控制塊，讓進程控制塊按進程到達先后順序讓進程排隊初始化進程控制塊，讓進程控制塊按進程到達先后順序讓進程排隊調度數組中首個進程，并讓數組中的下一位移到首位調度數組中首個進程，并讓數組中的下一位移到首位計算并打印進程的完成時刻、周轉時間、帶權周轉時間計算并打印進程的完成時刻、周轉時間、帶權周轉時間其中：周轉時間=完成時間-到達時間帶權周轉時間=周轉時間/服務時間更改計時器的當前時間,即下一刻進程的開始時間更改計時器的當前時間,即下一刻進程的開始時間當前時間=前一進程的完成時間+其服務時間數組為空數組為空NY結束結束先來先服務算法流程2)時間片輪轉法時間片輪轉算法流程圖B.存儲器管理(可變式分區管理）1)首次適應法分配流程圖開始申請xkb內存開始申請xkb內存由鏈頭找到第一個空閑區分區大小≥xkb？大于分區大小=分區大小-xkb，修改下一個空閑區的后向指針內容為（后向指針）+xkb;修改上一個空閑區的前向指針為（前向指針）+xkb將該空閑區從鏈中摘除：修改下一個空閑區的后向地址=該空閑區后向地址，修改上一個空閑區的前向指針為該空閑區的前向指針等于小于延鏈查找下一個空閑區到鏈尾了？作業等待返回是否登記已分配表返回分配給進程的內存首地址首次適應算法回收流程圖開始開始輸入完成進程的標號在分配區表中查找釋放區p下鄰分區空閑區前一個空閑區的后向指針指向p的后一個分區，p的后一個分區的前向指針指向p的前一個分區，且p的前一個分區大小更改為加上p的大小，釋放p釋放區p上鄰分區空前一個分區的后向指針指向p的后一個空閑分區，p的后一個空閑分區的前向指針指向p的前一個分區，且p的后一個分區大小更改為加上p的大小釋放區p上下均鄰空閑區前一個空閑區的后向指針指向p的后一個空閑分區，p的后一個空閑分區的前向指針指向p的前一個空閑分區，且p的前一個空閑分區大小更改為加上p的大小再加上p的后一個空閑分區的大小，合并后的這個空閑區的后向指針指向p的下下個分區，如果p的下下個分區不為空，則其前向指針指向合并后的這個空閑區，釋放p和p的下一個分區釋放區p上下均不鄰空閑區將p放在鏈首，并修改其狀態位為空閑最佳適應法開始釋放分區與上空閑分區相鄰開始釋放分區與上空閑分區相鄰釋放分區與下空閑分區相鄰結束釋放分區與下空閑分區相鄰TFTFTF摘除鏈表中上分區。合并釋放分區與上分區，將上空閑區長度修改為這二分區的長度。摘除鏈表中上下分區。合并這三個分區，將上空閑區長度修改為三個分區的長度。摘除鏈表中下分區。合并釋放分區與下分區，將釋放分區中長度修改為這二分區的長度。將合并的或釋放的分區按長度升序重新插入到自由鏈表中。C.虛擬存儲器的缺頁調度1)先進先出FIFO開始FIFO的缺頁中斷處理開始FIFO的缺頁中斷處理查主存分塊表查主存分塊表有空閑塊可用？有空閑塊可用？Y分配一塊Y分配一塊NNJ=p[HEAD]J=p[HEAD]J的修改標志=1？J的修改標志=1？NNY輸出“Y輸出“將J頁復寫入交換區”輸出“輸出“裝入L頁”調整FIFO隊列，將L插入隊尾（HEAD=(HEAD+1)modM)調整FIFO隊列，將L插入隊尾（HEAD=(HEAD+1)modM)修改主存分塊表和頁表修改主存分塊表和頁表終止終止FIFO淘汰算法流程FIFO淘汰算法流程2）LRU開始LRU的缺頁中斷處理開始LRU的缺頁中斷處理查主存分塊表查主存分塊表有空閑塊可用？有空閑塊可用？Y分配一塊Y分配一塊NN找到棧底元素：J=p[M-1]找到棧底元素：J=p[M-1]J的修改標志=1？J的修改標志=1？NNY輸出“Y輸出“將J頁送到入交換區”輸出“輸出“裝入L頁”調整堆棧，使HEAD所指元素及以下的元素下移P[HEAD]=L調整堆棧，使HEAD所指元素及以下的元素下移P[HEAD]=L修改主存分塊表和頁表修改主存分塊表和頁表終止終止LRU淘汰算法流程LRU淘汰算法流程實現原理主界面設計一個框架分別去鏈接處理機管理、存儲器管理和缺頁調度相關的程序。A.處理機調度1)先來先服務FCFS任務先來先服務的調度算法實現處理機調度。要求實現對FCFS算法的模擬實現計算出該算法的平均作業周轉時間、平均帶權作業周轉時間。原理按作業到達CPU時間先后順序進行非剝奪式調度，先到達CPU的作業先被執行。數據結構structtask_struct{charname;/*進程名稱*/intnumber;/*進程編號*/floatcome_time;/*到達時間*/floatrun_begin_time;/*開始運行時間*/floatrun_time;/*運行時間*/floatrun_end_time;/*運行結束時間*/intpriority;/*優先級*/intorder;/*運行次序*/intrun_flag;/*調度標志*/}tasks[MAX];intfcfs()/*先來先服務算法*/進程名鏈接指針到達時間估計運行時間進程狀態進程控制塊結構實現方法建立一個鏈表按照到達CPU的時間從小到大排列，只需從第一個作業（頭結點）依次調度到最后一個作業（尾結點）。運行界面測試數據：作業名到達時間運行時間A028B09C03執行FCFS算法如下：2)時間片輪轉法任務只對進程的運行模擬，將其運行時間加一，判斷要求運行時間與已運行時間是否相等，若相等則表示進程結束，進程退出調度，釋放資源。要求實現對RR算法的模擬實現顯示執行完一個時間片的結果。原理時間片輪轉算法中，系統將所有的就程序按先來先服務的原則排成一個隊列，每次調度時，把CPU分配給隊首進程，并令其執行一個時間片。當執行的時間片用完時，調度程序停止該進程的執行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。數據結構temp->state='R';儲器管理(可變式分區管理）1)首次適應法任務通過采用首次適應算法實現內存的分配與回收，并可以查看和顯示當前內存現狀。要求1.實現對FF算法的模擬實現2.輸入要進行分配內存的進程ID和相應所需內存大小，回收內存時輸入已運行的進程ID。原理FF算法要求空閑鏈已地址遞增的次序連接。分配內存時，從鏈首開始順序查找，直到找到第一個滿足要求的空間并分配給進程，把分配后余下的空間仍然留在鏈表中。若從鏈首至鏈尾都不滿足要求，則分配失敗。該算法傾向于優先使用低地址的空間。數據結構intconstMEMO=256;現對BF算法的模擬實現2.輸入要進行分配內存的進程ID和相應所需內存大小，回收內存時輸入需要回收的內存塊。原理最佳適應算法掃描整個未分配表或鏈表，從空閑區中挑選一個能滿足用戶進程要求的最小分區進行分配。此算法保證不會分割一個更大的區域，使得裝入大作業的要求容易得到滿足，同時，通常把空閑區按長度遞增順序排列，查找時總是從最小的一個空閑區開始，直至找到滿足要求的分區為止，這時，最佳適應分配算法等同于首次適應算法。此算法的主存利用率好，所找出的分區如果最好滿足要求則是最合適的。數據結構intconstMEMO=256;擬存儲器的缺頁調度1)先進先出FIFO任務采用先進先出FIFO算法實現分頁管理的缺頁調度，并輸出每次調入調出的頁號和運行結果。要求1.實現對FIFO算法的模擬實現2.輸出每次執行的結果。原理基于程序總是按線性順序來訪問物理空間這一假設，總是淘汰最先調入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認為駐留時間最長的頁不再使用的可能性較大。數據結構voidFIFO(){ intlength; intfifo[100]={0}; intpageLength; intfifoPage[100]={0}; inti,j; cout<<"***********************先進先出算法**************************"<<endl; pageLength=3; length=9; for(i=1;i<=length;i++){ intflag=0; for(j=1;j<=pageLength;j++){ if(fifo[i]==fifoPage[j]){ flag=1; j=pageLength+1; }elseif(fifoPage[j]==0){ fifoPage[j]=fifo[i]; j=pageLength+1; flag=1; } }if(flag==1) { } else { cout<<"→淘汰"<<fifoPage[1]<<endl; for(j=1;j<=pageLength;j++){ fifoPage[j]=fifoPage[j+1]; } fifoPage[pageLength]=fifo[i]; }實現方法當采用先進先出算法時，用一個數組構成先進先出隊列，數組中各個元素為進程已在主存的頁號，其隊列頭指針初始化為0.假設分配給每個進程的內存塊數固定。當隊列滿需淘汰時，淘汰最先進入主存的一頁。若該頁修改過，還有存入磁盤。然后要把當前訪問的頁裝入該塊，并修改頁表和存儲分塊表的對應標志。運行界面測試數據：頁表長度：9；頁框長度：3；頁面請求數列：4,4,3,5,1,1,2,3,2執行先進先出FIFO算法結果如下：2）LRU任務采用先進先出LRU算法實現分頁管理的缺頁調度，并輸出每次調入調出的頁號和運行結果。要求1.實現對LRU算法的模擬實現2.輸出每次執行的結果。原理最近最少使用頁面替換算法淘汰的頁面是在最近一段時間內最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面可能還有立即被使用，而那些在較長時間內未被使用的頁面可能不會立即使用。在分頁虛擬存儲系統中，當硬件發出缺頁中斷后轉操作系統處理缺頁中斷。如果主存中已無空閑塊，可采用LRU算法進行缺頁處理。數據結構voidLRU(){ intlength; intlru[100]={0}; intpageLength; intlruPage[100]={0};inti,j; cout<<"***********************最近最少使用LRU算法***********************"<<endl; pageLength=3; length=9; for(i=1;i<=length;i++){ intflag=0; for(j=1;j<=pageLength;j++){ if(lru[i]==lruPage[j]){ for(intcc=j;cc>0;cc--){ lruPage[cc]=lruPage[cc-1]; } lruPage[1]=lru[i]; flag=1; j=pageLength+1; }elseif(lruPage[j]==0){ for(intvv=j;vv>0;vv--){ lruPage[vv]=lruPage[vv-1]; } lruPage[1]=lru[i]; j=pageLength+1; flag=1; } }if(flag==1) { } else { cout<<"→淘汰"<<lruPage[pageLength]<<endl; for(j=pageLength;j>0;j--){ lruPage[j]=lruPage[j-1]; } lruPage[1]=lru[i]; }實現方法當采用LRU算法時，用一個數組構成堆棧，堆棧中各個元素為進程已在主存的頁號，為了進行頁面置換，可設置一個棧指針，初始化為0.假定分配給每個進程的內存塊數固定不變。當隊列滿需淘汰時，操作系統選擇棧底元素淘汰，其他元素向下移一個位置，將新調入頁放棧指針指示的棧頂。當訪問的頁在棧中時，還應調整頁從當前位置到棧頂。運行界面測試數據：頁表長度：9；頁框長度：3；頁面請求數列：2,3,5,1,5,5,4,4,3執行最近最少使用LRU算法結果如下：總結與體會通過本次課程設計讓我對于圖形界面設計有了一定的思路和看法，同時我對先來先服務、時間片輪轉、首次適應算法、最佳適應算法、先進先出和最近最少使用算法有了更詳盡的認識。在編程的過程中發現會用到大量的指針，用指針來操作大量的數據比較方便，但最后應該記得釋放資源。從這次實驗中我發現我對于c++掌握也有所不足，程序經過了多次修改才得以完善，在以后應該注重編程方面的訓練。此外我還更深入的理解了各個進程調度算法，及實現過程。在編寫程序時查詢了很多資料，間接提高了我的搜索能力。在此次課程設計過程中，對進程的相關知識有了一定的加深。特別是對進程的進程控制塊的存在和價值有了更進一步的認識。在編寫程序的過程之中，對進程自身信息的設計和管理以及調度的算法都有助于對書本知識的理解和掌握。特別是設計先來先服務調度算法和時間片輪轉調度算法的時候，對進程的調度算法有了更好的深入理解。對進程管理中的等待隊列，就緒隊列，時間片等概念有了更深刻的印象。在設計此模擬操作系統的課設中，也加深了對c++知識的把握。解決了一些以往在編程中遇到了困難。通過此次的課程設計，不僅提高了對操作系統的認知，也在同時提高了編程的能力，加強了實踐。另外，我覺得此次課程設計雖然主要問題是在編程上，但是經過不斷的去調試，還是成功的調試了出來。但是這幾個程序用了多天的時間進行分析和修改，雖然出現了不少問題，但收獲頗多！源代碼：#include<iostream>#include<cstring>#include<cstddef>usingnamespacestd;intfcfsoutput();/*調度結果輸出*/intfcfsinput();un_begin_time=time_temp;tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;tasks[i].run_flag=1;time_temp=tasks[i].run_end_time;number_schedul=i;tasks[number_schedul].order=i+1;}fcfsoutput();return0;}intfcfsinput(){ task_structtt;inti,j;un_time=28;tasks[1].run_time=9;tasks[2].run_time=3;ame='A'; tasks[1].name='B'; tasks[2].name='C'; cout<<"************************先來先服務算法************************"<<endl<<endl;for(i=0;i<counter;i++){tasks[i].run_begin_time=0;tasks[i].run_end_time=0;tasks[i].order=0;tasks[i].run_flag=0;}return0;}intfcfsoutput()/*調度結果輸出*/{inti;floatturn_round_time=0,f1,w=0;cout<<"作業名到達時間運行時間開始時間停止時間運行次序周轉時間"<<endl;for(i=0;i<counter;i++){f1=tasks[i].run_end_time-tasks[i]e_time;turn_round_time+=f1;w+=(f1/tasks[i].run_time);cout<<""<<tasks[i].name<<'\t'<<""<<tasks[i]e_time<<'\t'<<""<<tasks[i].run_time<<'\t'<<""<<tasks[i].run_begin_time<<'\t'<<""<<tasks[i].run_end_time<<'\t'<<tasks[i].order<<'\t'<<f1<<'\t'<<endl;}cout<<"平均周轉時間："<<turn_round_time/counter<<endl;cout<<"平均帶權周轉時間："<<w/counter<<endl;cout<<"";return0;}/**/intrr(){intn=3,num=0;node*head=NULL;node*tail=NULL;cout<<"*********************時間片輪轉調度算法*********************"<<endl<<endl;for(inti=0;i<n;i++){node*temp=newnode; if(i==0)strcpy(temp->name,"A");