操作系統(tǒng)一個小型操作系統(tǒng)的設(shè)計與實現(xiàn)課程設(shè)計

1、南通大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：學(xué)生姓名：學(xué)號：時間：操作系統(tǒng)課程設(shè)計報告操作系統(tǒng)模擬算法課程設(shè)計報告設(shè)計要求將本學(xué)期三次的實驗集成實現(xiàn)：A. 處理機(jī)管理；B. 存儲器管理；C. 虛擬存儲器的缺頁調(diào)度。設(shè)計流程圖主流程圖開始的圖形界面 存儲器管理缺頁調(diào)度處理機(jī)管理LRU算法先進(jìn)先出最佳適應(yīng)法首次適應(yīng)法先來先服務(wù)時間片輪轉(zhuǎn)A.處理機(jī)調(diào)度 1)先來先服務(wù)FCFS開始初始化進(jìn)程控制塊，讓進(jìn)程控制塊按進(jìn)程到達(dá)先后順序讓進(jìn)程排隊調(diào)度數(shù)組中首個進(jìn)程，并讓數(shù)組中的下一位移到首位計算并打印進(jìn)程的完成時刻、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間其中：周轉(zhuǎn)時間 = 完成時間 - 到達(dá)時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間更改計時

2、器的當(dāng)前時間,即下一刻進(jìn)程的開始時間當(dāng)前時間=前一進(jìn)程的完成時間+其服務(wù)時間數(shù)組為空NY結(jié)束 先來先服務(wù)算法流程2)時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)算法流程圖B.存儲器管理(可變式分區(qū)管理） 1)首次適應(yīng)法 分配流程圖開始申請xkb內(nèi)存由鏈頭找到第一個空閑區(qū)分區(qū)大小xkb？大于分區(qū)大小=分區(qū)大小-xkb，修改下一個空閑區(qū)的后向指針內(nèi)容為（后向指針）+xkb;修改上一個空閑區(qū)的前向指針為（前向指針）+xkb將該空閑區(qū)從鏈中摘除：修改下一個空閑區(qū)的后向地址=該空閑區(qū)后向地址，修改上一個空閑區(qū)的前向指針為該空閑區(qū)的前向指針等于小于延鏈查找下一個空閑區(qū)到鏈尾了？作業(yè)等待返回是否登記已分配表返回分配給進(jìn)程的內(nèi)存首

3、地址首次適應(yīng)算法回收流程圖 開始輸入完成進(jìn)程的標(biāo)號在分配區(qū)表中查找釋放區(qū)p下鄰分區(qū)空閑區(qū)前一個空閑區(qū)的后向指針指向p的后一個分區(qū)，p的后一個分區(qū)的前向指針指向p的前一個分區(qū)，且p的前一個分區(qū)大小更改為加上p的大小，釋放p釋放區(qū)p上鄰分區(qū)空前一個分區(qū)的后向指針指向p的后一個空閑分區(qū)，p的后一個空閑分區(qū)的前向指針指向p的前一個分區(qū)，且p的后一個分區(qū)大小更改為加上p的大小釋放區(qū)p上下均鄰空閑區(qū)前一個空閑區(qū)的后向指針指向p的后一個空閑分區(qū)，p的后一個空閑分區(qū)的前向指針指向p的前一個空閑分區(qū)，且p的前一個空閑分區(qū)大小更改為加上p的大小再加上p的后一個空閑分區(qū)的大小，合并后的這個空閑區(qū)的后向指針指向p的下

4、下個分區(qū)，如果p的下下個分區(qū)不為空，則其前向指針指向合并后的這個空閑區(qū)，釋放p和p的下一個分區(qū)釋放區(qū)p上下均不鄰空閑區(qū)將p放在鏈?zhǔn)?，并修改其狀態(tài)位為空閑2） 最佳適應(yīng)法開始釋放分區(qū)與上空閑分區(qū)相鄰釋放分區(qū)與下空閑分區(qū)相鄰 結(jié)束釋放分區(qū)與下空閑分區(qū)相鄰TFTFTF摘除鏈表中上分區(qū)。合并釋放分區(qū)與上分區(qū)，將上空閑區(qū)長度修改為這二分區(qū)的長度。摘除鏈表中上下分區(qū)。合并這三個分區(qū)，將上空閑區(qū)長度修改為三個分區(qū)的長度。摘除鏈表中下分區(qū)。合并釋放分區(qū)與下分區(qū)，將釋放分區(qū)中長度修改為這二分區(qū)的長度。將合并的或釋放的分區(qū)按長度升序重新插入到自由鏈表中?；厥諆?nèi)存流程C.虛擬存儲器的缺頁調(diào)度 1)先進(jìn)先出FIFO開

5、始FIFO的缺頁中斷處理查主存分塊表有空閑塊可用？Y分配一塊NJ=pHEADJ的修改標(biāo)志=1？NY輸出“將J頁復(fù)寫入交換區(qū)”輸出“裝入L頁”調(diào)整FIFO隊列，將L插入隊尾（HEAD=(HEAD+1)modM)修改主存分塊表和頁表終止FIFO淘汰算法流程 2）LRU開始LRU的缺頁中斷處理查主存分塊表有空閑塊可用？Y分配一塊N找到棧底元素：J=pM-1J的修改標(biāo)志=1？NY輸出“將J頁送到入交換區(qū)”輸出“裝入L頁”調(diào)整堆棧，使HEAD所指元素及以下的元素下移PHEAD=L修改主存分塊表和頁表終止LRU淘汰算法流程實現(xiàn)原理主界面設(shè)計一個框架分別去鏈接處理機(jī)管理、存儲器管理和缺頁調(diào)度相關(guān)的程序。A.

6、處理機(jī)調(diào)度 1)先來先服務(wù)FCFS（1） 任務(wù)先來先服務(wù)的調(diào)度算法實現(xiàn)處理機(jī)調(diào)度。（2） 要求1. 實現(xiàn)對FCFS算法的模擬實現(xiàn)2. 計算出該算法的平均作業(yè)周轉(zhuǎn)時間、平均帶權(quán)作業(yè)周轉(zhuǎn)時間。（3） 原理按作業(yè)到達(dá)CPU時間先后順序進(jìn)行非剝奪式調(diào)度，先到達(dá)CPU的作業(yè)先被執(zhí)行。（4） 數(shù)據(jù)結(jié)構(gòu) struct task_struct char name; /*進(jìn)程名稱*/ int number; /*進(jìn)程編號*/ float come_time; /*到達(dá)時間*/ float run_begin_time; /*開始運(yùn)行時間*/ float run_time; /*運(yùn)行時間*/ float run_

7、end_time; /*運(yùn)行結(jié)束時間*/ int priority; /*優(yōu)先級*/ int order; /*運(yùn)行次序*/ int run_flag; /*調(diào)度標(biāo)志*/ tasksMAX;int fcfs()/*先來先服務(wù)算法*/進(jìn)程名鏈接指針到達(dá)時間估計運(yùn)行時間進(jìn)程狀態(tài)進(jìn)程控制塊結(jié)構(gòu)（5） 實現(xiàn)方法建立一個鏈表按照到達(dá)CPU的時間從小到大排列，只需從第一個作業(yè)（頭結(jié)點）依次調(diào)度到最后一個作業(yè)（尾結(jié)點）。（6） 運(yùn)行界面測試數(shù)據(jù)：作業(yè)名到達(dá)時間運(yùn)行時間A028B09C03執(zhí)行FCFS算法如下： 2)時間片輪轉(zhuǎn)法（1） 任務(wù)只對進(jìn)程的運(yùn)行模擬，將其運(yùn)行時間加一，判斷要求運(yùn)行時間與已運(yùn)行時間是否

8、相等，若相等則表示進(jìn)程結(jié)束，進(jìn)程退出調(diào)度，釋放資源。（2） 要求1. 實現(xiàn)對RR算法的模擬實現(xiàn)2. 顯示執(zhí)行完一個時間片的結(jié)果。（3） 原理時間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就程序按先來先服務(wù)的原則排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。當(dāng)執(zhí)行的時間片用完時，調(diào)度程序停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機(jī)分配給就緒隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。（4） 數(shù)據(jù)結(jié)構(gòu) temp->state='R' /初始狀態(tài)每個進(jìn)程均為運(yùn)行態(tài) temp->allocation=0;/初始時進(jìn)程均不占用cpu num+=te

9、mp->need_time; /用num來限制循環(huán)的次數(shù)（5） 實現(xiàn)方法處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。執(zhí)行：已運(yùn)行時間+1來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個單位的時間。當(dāng)一個進(jìn)程被選中運(yùn)行時，必須設(shè)置該進(jìn)程可以運(yùn)行的時間片值，以及恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個時間片 進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個輪到運(yùn)行的進(jìn)程。同時，應(yīng)判斷該進(jìn)程的要求運(yùn)行時間與已運(yùn)行時間，若該進(jìn)程的要求運(yùn)行時間¹已運(yùn)行時間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時再運(yùn)行。若該進(jìn)程的要求運(yùn)行時間=已運(yùn)行時間，則表示它

10、已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”且退出隊列。此時，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個進(jìn)程的指針位置。進(jìn)程名鏈接指針到達(dá)時間估計運(yùn)行時間進(jìn)程狀態(tài)進(jìn)程控制塊結(jié)構(gòu)（6） 運(yùn)行界面測試數(shù)據(jù)：作業(yè)號執(zhí)行時間/sA1B2C1執(zhí)行時間片輪轉(zhuǎn)算法RR如下：B.存儲器管理(可變式分區(qū)管理） 1)首次適應(yīng)法（1） 任務(wù)通過采用首次適應(yīng)算法實現(xiàn)內(nèi)存的分配與回收，并可以查看和顯示當(dāng)前內(nèi)存現(xiàn)狀。（2） 要求1.實現(xiàn)對FF算法的模擬實現(xiàn)2.輸入要進(jìn)行分配內(nèi)存的進(jìn)程ID和相應(yīng)所需內(nèi)存大小，回收內(nèi)存時輸入已運(yùn)行的進(jìn)程ID。（3） 原理FF算法要求空閑鏈已地址遞增的次序連接。分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，

11、直到找到第一個滿足要求的空間并分配給進(jìn)程，把分配后余下的空間仍然留在鏈表中。若從鏈?zhǔn)字伶溛捕疾粷M足要求，則分配失敗。該算法傾向于優(yōu)先使用低地址的空間。（4） 數(shù)據(jù)結(jié)構(gòu)int const MEMO=256;/初始化常類型MEMO，用MEMO表示內(nèi)存大小（常類型的變量或?qū)ο蟮闹凳遣荒鼙桓碌模﹕truct FreeMemory int ID;int StartAdd;int Size; bool State;/定義state 為布爾型變量，其值只有 真 （TRUE) 和假 （FALSE) FreeMemory* Next;FreeMemory* AllocTable=new FreeMemory;

12、/建立全局管理表用于內(nèi)與回收FreeMemory* PtrforCycleFit=AllocTable;/為循環(huán)首次適應(yīng)定義的指針，此指針用于指向當(dāng)前查找的起始地址;/初始化內(nèi)存函數(shù)void MemoryInit(FreeMemory* &tempAdd) tempAdd->ID=0;/初始化當(dāng)前進(jìn)程為空 tempAdd->Size=MEMO;/初始化可分配空間為內(nèi)存大小 tempAdd->StartAdd=0;/初始化起始地址為0 tempAdd->State=false;/ 初始化狀態(tài)為未分配 tempAdd->Next=NULL;/初始化下一個進(jìn)程也

13、為空/反饋內(nèi)存現(xiàn)態(tài)void DispMemory() FreeMemory* temp=AllocTable;/全局管理表反映內(nèi)存狀態(tài) cout<<"系統(tǒng)總內(nèi)存: "<<MEMO<<endl; for(;temp;temp=temp->Next) cout<<"進(jìn)程ID："<<temp->ID<<" "<<"大?。?quot;<<temp->Size<<" "<<&qu

14、ot;起始地址:"<<temp->StartAdd<<" "<<"是否已分配:"<<temp->State<<endl;/ 輸出內(nèi)存的各個變量（5） 實現(xiàn)方法可變式分區(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需要，并且分區(qū)的個數(shù)是可以調(diào)整的。當(dāng)需要裝入一個作業(yè)時，根據(jù)作業(yè)需要的貯存量，查看是否有足夠的空閑空間，若有，則按需求量分割一部分給作業(yè)；若無，則作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大小小的分區(qū)。有的分區(qū)被分配作業(yè)占用，有的分區(qū)空閑。

15、在空閑區(qū)表中，按空閑區(qū)首地址從低到高進(jìn)行登記。當(dāng)一個作業(yè)執(zhí)行完成時，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時，要考慮相鄰空間區(qū)合并問題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分以下4種情況考慮：A、釋放區(qū)下鄰空閑區(qū)；B、釋放區(qū)上鄰空閑區(qū)；C、釋放區(qū)上下都與空閑區(qū)鄰接；D、釋放區(qū)上鄰空閑區(qū)不鄰接。（6） 運(yùn)行界面系統(tǒng)總內(nèi)存為256時，分別為進(jìn)程1、2、3分配大小為64、128、64的內(nèi)存。執(zhí)行首次適應(yīng)算法分配內(nèi)存如下：若回收進(jìn)程2的內(nèi)存，執(zhí)行結(jié)果如下： 2）最佳適應(yīng)法（1） 任務(wù)通過采用最佳適應(yīng)算法實現(xiàn)內(nèi)存的分配與回收，并可以查看和顯示當(dāng)前內(nèi)存現(xiàn)狀。（2） 要求1.實現(xiàn)對BF算法的模擬實現(xiàn)2.輸入要進(jìn)行分配內(nèi)

16、存的進(jìn)程ID和相應(yīng)所需內(nèi)存大小，回收內(nèi)存時輸入需要回收的內(nèi)存塊。（3） 原理最佳適應(yīng)算法掃描整個未分配表或鏈表，從空閑區(qū)中挑選一個能滿足用戶進(jìn)程要求的最小分區(qū)進(jìn)行分配。此算法保證不會分割一個更大的區(qū)域，使得裝入大作業(yè)的要求容易得到滿足，同時，通常把空閑區(qū)按長度遞增順序排列，查找時總是從最小的一個空閑區(qū)開始，直至找到滿足要求的分區(qū)為止，這時，最佳適應(yīng)分配算法等同于首次適應(yīng)算法。此算法的主存利用率好，所找出的分區(qū)如果最好滿足要求則是最合適的。（4） 數(shù)據(jù)結(jié)構(gòu)int const MEMO=256;/初始化常類型MEMO，用MEMO表示內(nèi)存大?。ǔｎ愋偷淖兞炕?qū)ο蟮闹凳遣荒鼙桓碌模﹕truct Fr

17、eeMemory int ID;int StartAdd;int Size; bool State;/定義state 為布爾型變量，其值只有 真 （TRUE) 和假 （FALSE) FreeMemory* Next;bool Alloc_BestFit(int id,int TrySize)/查找滿足此條件的 x1<=TrySize<=x2 的分區(qū),然后將其放置在x2中，并將x2拆分成兩個分區(qū) SortPartition(true);/使用快速排序算法，升序排序for(;temp;temp=temp->Next) /*回收操作,回收過程中，要用到三個指針，上一個Last,當(dāng)前

18、temp,下一個temp->next 當(dāng)temp指向表頭或表尾時需要特殊考慮*/當(dāng)要退出工作時,就要回收/此退出的工作由執(zhí)行函數(shù)調(diào)用void EndJob(int id) Free_Memory(id);（5） 實現(xiàn)方法空閑區(qū)設(shè)置為雙向鏈表，其雙向鏈的分區(qū)格式為：0（狀態(tài)位）分區(qū)大小（N+2）向前指針大小為N的已分配區(qū)或空閑區(qū)0（狀態(tài)位）分區(qū)大?。∟+2)向后指針（6） 運(yùn)行界面測試數(shù)據(jù)如下：進(jìn)程123456所需內(nèi)存253445121310執(zhí)行最佳適應(yīng)算法為其分配內(nèi)存如下：若回收進(jìn)程4，執(zhí)行結(jié)果如下：C.虛擬存儲器的缺頁調(diào)度 1)先進(jìn)先出FIFO（1） 任務(wù)采用先進(jìn)先出FIFO算法實現(xiàn)分

19、頁管理的缺頁調(diào)度，并輸出每次調(diào)入調(diào)出的頁號和運(yùn)行結(jié)果。（2） 要求1.實現(xiàn)對FIFO算法的模擬實現(xiàn)2.輸出每次執(zhí)行的結(jié)果。（3） 原理基于程序總是按線性順序來訪問物理空間這一假設(shè)，總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認(rèn)為駐留時間最長的頁不再使用的可能性較大。（4） 數(shù)據(jù)結(jié)構(gòu)void FIFO()int length;int fifo100=0;int pageLength;int fifoPage100=0;int i,j;cout<<" *先進(jìn)先出算法*"<<endl;pageLength=3;length=9; for(

20、i=1;i<=length;i+)int flag=0;for(j=1;j<=pageLength;j+)if(fifoi=fifoPagej)flag=1;j=pageLength+1;else if(fifoPagej=0)fifoPagej=fifoi;j=pageLength+1;flag=1; if(flag=1)elsecout<<" 淘汰"<<fifoPage1<<endl;for(j=1;j<=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=f

21、ifoi;（5） 實現(xiàn)方法當(dāng)采用先進(jìn)先出算法時，用一個數(shù)組構(gòu)成先進(jìn)先出隊列，數(shù)組中各個元素為進(jìn)程已在主存的頁號，其隊列頭指針初始化為0.假設(shè)分配給每個進(jìn)程的內(nèi)存塊數(shù)固定。當(dāng)隊列滿需淘汰時，淘汰最先進(jìn)入主存的一頁。若該頁修改過，還有存入磁盤。然后要把當(dāng)前訪問的頁裝入該塊，并修改頁表和存儲分塊表的對應(yīng)標(biāo)志。（6） 運(yùn)行界面測試數(shù)據(jù)：頁表長度：9；頁框長度：3；頁面請求數(shù)列：4,4,3,5,1,1,2,3,2執(zhí)行先進(jìn)先出FIFO算法結(jié)果如下： 2）LRU（1） 任務(wù)采用先進(jìn)先出LRU算法實現(xiàn)分頁管理的缺頁調(diào)度，并輸出每次調(diào)入調(diào)出的頁號和運(yùn)行結(jié)果。（2） 要求1.實現(xiàn)對LRU算法的模擬實現(xiàn)2.輸出每次

22、執(zhí)行的結(jié)果。（3） 原理最近最少使用頁面替換算法淘汰的頁面是在最近一段時間內(nèi)最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認(rèn)為那些剛被使用過的頁面可能還有立即被使用，而那些在較長時間內(nèi)未被使用的頁面可能不會立即使用。在分頁虛擬存儲系統(tǒng)中，當(dāng)硬件發(fā)出缺頁中斷后轉(zhuǎn)操作系統(tǒng)處理缺頁中斷。如果主存中已無空閑塊，可采用LRU算法進(jìn)行缺頁處理。（4） 數(shù)據(jù)結(jié)構(gòu)void LRU()int length;int lru100=0;int pageLength;int lruPage100=0; int i,j;cout<<" *最近最少使用LRU算法*"<<

23、endl;pageLength=3;length=9; for(i=1;i<=length;i+)int flag=0;for(j=1;j<=pageLength;j+)if(lrui=lruPagej)for(int cc=j;cc>0;cc-)lruPagecc=lruPagecc-1;lruPage1=lrui;flag=1;j=pageLength+1;else if(lruPagej=0)for(int vv=j;vv>0;vv-)lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1; if(fla

24、g=1)elsecout<<" 淘汰"<<lruPagepageLength<<endl;for(j=pageLength;j>0;j-)lruPagej=lruPagej-1;lruPage1=lrui;（5） 實現(xiàn)方法當(dāng)采用LRU算法時，用一個數(shù)組構(gòu)成堆棧，堆棧中各個元素為進(jìn)程已在主存的頁號，為了進(jìn)行頁面置換，可設(shè)置一個棧指針，初始化為0.假定分配給每個進(jìn)程的內(nèi)存塊數(shù)固定不變。當(dāng)隊列滿需淘汰時，操作系統(tǒng)選擇棧底元素淘汰，其他元素向下移一個位置，將新調(diào)入頁放棧指針指示的棧頂。當(dāng)訪問的頁在棧中時，還應(yīng)調(diào)整頁從當(dāng)前位置到棧頂。（6）

25、運(yùn)行界面測試數(shù)據(jù)：頁表長度：9；頁框長度：3；頁面請求數(shù)列：2,3,5,1,5,5,4,4,3執(zhí)行最近最少使用LRU算法結(jié)果如下：總結(jié)與體會通過本次課程設(shè)計讓我對于圖形界面設(shè)計有了一定的思路和看法，同時我對先來先服務(wù)、時間片輪轉(zhuǎn)、首次適應(yīng)算法、最佳適應(yīng)算法、先進(jìn)先出和最近最少使用算法有了更詳盡的認(rèn)識。在編程的過程中發(fā)現(xiàn)會用到大量的指針，用指針來操作大量的數(shù)據(jù)比較方便，但最后應(yīng)該記得釋放資源。從這次實驗中我發(fā)現(xiàn)我對于c+掌握也有所不足，程序經(jīng)過了多次修改才得以完善，在以后應(yīng)該注重編程方面的訓(xùn)練。此外我還更深入的理解了各個進(jìn)程調(diào)度算法，及實現(xiàn)過程。在編寫程序時查詢了很多資料，間接提高了我的搜索能力

26、。在此次課程設(shè)計過程中，對進(jìn)程的相關(guān)知識有了一定的加深。特別是對進(jìn)程的進(jìn)程控制塊的存在和價值有了更進(jìn)一步的認(rèn)識。在編寫程序的過程之中，對進(jìn)程自身信息的設(shè)計和管理以及調(diào)度的算法都有助于對書本知識的理解和掌握。特別是設(shè)計先來先服務(wù)調(diào)度算法和時間片輪轉(zhuǎn)調(diào)度算法的時候，對進(jìn)程的調(diào)度算法有了更好的深入理解。對進(jìn)程管理中的等待隊列，就緒隊列，時間片等概念有了更深刻的印象。在設(shè)計此模擬操作系統(tǒng)的課設(shè)中，也加深了對c+知識的把握。解決了一些以往在編程中遇到了困難。通過此次的課程設(shè)計，不僅提高了對操作系統(tǒng)的認(rèn)知，也在同時提高了編程的能力，加強(qiáng)了實踐。另外，我覺得此次課程設(shè)計雖然主要問題是在編程上，但是經(jīng)過不斷的

27、去調(diào)試，還是成功的調(diào)試了出來。但是這幾個程序用了多天的時間進(jìn)行分析和修改，雖然出現(xiàn)了不少問題，但收獲頗多！源代碼：#include<iostream>#include<cstring>#include <cstddef>using namespace std;int fcfsoutput(); /*調(diào)度結(jié)果輸出*/int fcfsinput(); /進(jìn)程參數(shù)的初始化void kaishi();#define MAX 10struct node /建立鏈表來存放進(jìn)程數(shù)據(jù) char name5; /進(jìn)程名稱 int need_time; /所需要的時間 int

28、allocation; /占用cpu的情況 char state; /目前的狀態(tài) R為運(yùn)行，E為運(yùn)行完畢 node *next; /鏈表的尾結(jié)點 ;struct task_struct char name; /*進(jìn)程名稱*/ int number; /*進(jìn)程編號*/ float come_time; /*到達(dá)時間*/ float run_begin_time; /*開始運(yùn)行時間*/ float run_time; /*運(yùn)行時間*/ float run_end_time; /*運(yùn)行結(jié)束時間*/ int priority; /*優(yōu)先級*/ int order; /*運(yùn)行次序*/ int run_f

29、lag; /*調(diào)度標(biāo)志*/ tasksMAX;int counter; /*實際進(jìn)程個數(shù)*/int fcfs()/*先來先服務(wù)算法*/fcfsinput();float time_temp=0;int i;int number_schedul;time_temp=e_time;for(i=0;i<counter;i+) tasksi.run_begin_time=time_temp; tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time; tasksi.run_flag=1; time_temp=tasks

30、i.run_end_time; number_schedul=i; tasksnumber_schedul.order=i+1;fcfsoutput();return 0;int fcfsinput() task_struct tt; int i,j; /初始化進(jìn)程數(shù) counter=3; /初始化每個到達(dá)系統(tǒng)的時間為5、7、8 e_time=rand()%9; e_time=rand()%9; e_time=rand()%9; for(i=1;i<3;i+) for(j=0;j<3-i;j+) if(

31、e_time>tasksj+1.come_time) tt=tasksj; tasksj=tasksj+1; tasksj+1=tt; /初始化每個進(jìn)程估計運(yùn)行的時間 tasks0.run_time=28; tasks1.run_time=9; tasks2.run_time=3; /初始化每個進(jìn)程的名字='A'='B'='C'cout<<"*先來先服務(wù)算法*"<<endl<<endl;for(i=0;i<coun

32、ter;i+) tasksi.run_begin_time=0; tasksi.run_end_time=0; tasksi.order=0; tasksi.run_flag=0;return 0;int fcfsoutput() /*調(diào)度結(jié)果輸出*/int i;float turn_round_time=0,f1,w=0;cout<<"作業(yè)名 到達(dá)時間 運(yùn)行時間 開始時間 停止時間 運(yùn)行次序 周轉(zhuǎn)時間"<<endl;for(i=0;i<counter;i+) f1=tasksi.run_end_e_time; t

33、urn_round_time+=f1; w+=(f1/tasksi.run_time); cout<<" "<<<<'t'<<" "<<e_time<<'t'<<" " <<tasksi.run_time<<'t'<<" "<<tasksi.run_begin_time<<'t

34、'<<" " <<tasksi.run_end_time<<'t'<<tasksi.order<<'t'<<f1<<'t'<<endl;cout<<"平均周轉(zhuǎn)時間："<<turn_round_time/counter<<endl;cout<<"平均帶權(quán)周轉(zhuǎn)時間："<<w/counter<<endl;cout<

35、<" "return 0;/*-*/int rr()int n=3,num=0;node *head=NULL;node *tail=NULL;cout<<"*時間片輪轉(zhuǎn)調(diào)度算法*"<<endl<<endl;for(int i=0;i<n;i+) node *temp=new node;if(i=0)strcpy(temp->name,"A");if(i=1)strcpy(temp->name,"B");if(i=2)strcpy(temp->nam

36、e,"C"); temp->need_time=rand()%4+1; temp->state='R' /初始狀態(tài)每個進(jìn)程均為運(yùn)行態(tài) temp->allocation=0;/初始時進(jìn)程均不占用cpu num+=temp->need_time; /用num來限制循環(huán)的次數(shù) if(!head) tail=head=temp; else tail->next=temp; tail=temp; tail->next=head; node *p;p=head;cout<<endl<<"初始時刻：&q

37、uot;<<endl;cout<<"進(jìn)程"<<'t'<<"剩余時間"<<'t'<<"占用cpu時間"<<endl;while(p!=tail)cout<<" "<<p->name<<'t'<<" "<<p->need_time<<'t'<<'t&#

38、39;<<p->allocation<<'s'<<endl;p=p->next;cout<<" "<<tail->name<<'t'<<" "<<tail->need_time<<'t'<<'t'<<p->allocation<<'s'<<endl;node *q;int label=1;in

39、t m=1;while(label=1&&m<=num)cout<<endl;label=0; while(!p->need_time) p=p->next; if(p->need_time) p->need_time-;p->allocation+; if(p->need_time=0) p->state='E' label=1;p=p->next; cout<<"執(zhí)行"<<m<<"秒后："<<endl; q

40、=head; cout<<"進(jìn)程"<<'t'<<"剩余時間"<<'t'<<"占用cpu時間"<<endl; while(q!=tail) cout<<" "<<q->name<<'t'<<" "<<q->need_time<<'t'<<'t'<&

41、lt;q->allocation<<'s'<<endl; q=q->next; cout<<" "<<tail->name<<'t'<<" "<<tail->need_time<<'t'<<'t'<<q->allocation<<'s'<<endl; m+;cout<<endl<<

42、" "return 0;/*-*/int const MEMO=256;/初始化常類型MEMO，用MEMO表示內(nèi)存大?。ǔｎ愋偷淖兞炕?qū)ο蟮闹凳遣荒鼙桓碌模﹕truct FreeMemory int ID;int StartAdd;int Size; bool State;/定義state 為布爾型變量，其值只有 真 （TRUE) 和假 （FALSE) FreeMemory* Next;FreeMemory* AllocTable=new FreeMemory;/建立全局管理表用于內(nèi)存分配與回收FreeMemory* PtrforCycleFit=AllocTable;/

43、為循環(huán)首次適應(yīng)定義的指針，此指針用于指向當(dāng)前查找的起始地址;/初始化內(nèi)存函數(shù)void MemoryInit(FreeMemory* &tempAdd) tempAdd->ID=0;/初始化當(dāng)前進(jìn)程為空 tempAdd->Size=MEMO;/初始化可分配空間為內(nèi)存大小 tempAdd->StartAdd=0;/初始化起始地址為0 tempAdd->State=false;/ 初始化狀態(tài)為未分配 tempAdd->Next=NULL;/初始化下一個進(jìn)程也為空/反饋內(nèi)存現(xiàn)態(tài)void DispMemory() FreeMemory* temp=AllocTabl

44、e;/全局管理表反映內(nèi)存狀態(tài) cout<<"系統(tǒng)總內(nèi)存: "<<MEMO<<endl; for(;temp;temp=temp->Next) cout<<"進(jìn)程ID："<<temp->ID<<" "<<"大?。?quot;<<temp->Size<<" "<<"起始地址:"<<temp->StartAdd<<"

45、 "<<"是否已分配:"<<temp->State<<endl;/ 輸出內(nèi)存的各個變量/分區(qū)排序void SortPartition(bool order)/在此使用的是快速排序算法FreeMemory* temp1=AllocTable;FreeMemory* temp2=AllocTable;FreeMemory* Last1=temp1;FreeMemory* Last2=temp2;if(temp2->Next)temp2=temp2->Next; switch(order) case 1:/升序部分

46、for(;temp1;temp1=temp1->Next) for(;temp2;temp2=temp2->Next) if(temp1->Size> temp2->Size)&&!temp1->State&&!temp2->State)/找到符合條件的，則交換 Last1->Next=temp2; Last2->Next=temp1; FreeMemory* temp=temp2->Next; temp2->Next=temp1->Next; temp1->Next=temp->

47、;Next; Last2=temp2; Last1=temp1; break; case 0:/降序部分 for(;temp1;temp1=temp1->Next) for(;temp2;temp2=temp2->Next) if(temp1->Size < temp2->Size)&&!temp1->State&&!temp2->State)/找到符合條件的，則交換 Last1->Next=temp2; Last2->Next=temp1; FreeMemory* temp=temp2->Next;

48、temp2->Next=temp1->Next; temp1->Next=temp->Next; Last2=temp2; Last1=temp1; /*內(nèi)存分配*/bool Alloc_FirstFit(int id, int TrySize)/ 定義布爾型函數(shù)Alloc_FirstFit()/查找一個可用第一個滿足分配請求的分區(qū)，如果滿足將其寫入內(nèi)存分配表/否則分配失敗，返回 FreeMemory* temp=AllocTable;for(;temp;temp=temp->Next) if(TrySize<=temp->Size &&

49、; !temp->State)/第一個滿足條件的分區(qū)已找到 if(TrySize=temp->Size)/剛好和申請的大小一致 temp->ID=id; /保持不變temp->Next,Size,StartAdd都不用變 temp->State=true; /值為真表示已分配 else/比所找到的要小，則需要將其拆分 FreeMemory* NewItem=new FreeMemory; NewItem->Next=temp->Next; NewItem->ID=0; NewItem->Size=temp->Size-TrySize;

50、 NewItem->StartAdd=temp->StartAdd+TrySize; NewItem->State=false; temp->ID=id; temp->Size=TrySize; temp->State=true; temp->Next=NewItem; return true; /end forreturn false;bool Alloc_BestFit(int id,int TrySize)/查找滿足此條件的 x1<=TrySize<=x2 的分區(qū),然后將其放置在x2中，并將x2拆分成兩個分區(qū) SortPartitio

51、n(true);/使用快速排序算法，升序排序FreeMemory* temp=AllocTable;if(temp->Next)temp=temp->Next;for(;temp;temp=temp->Next) if(TrySize<=temp->Size && !temp->State)/第一個滿足條件的分區(qū)已找到 if(TrySize=temp->Size)/剛好和申請的大小一致 temp->ID=id; /保持不變temp->Next,Size,StartAdd都不用變 temp->State=true; /值

52、為真表示已分配 else/比所找到的要小，則需要將其拆分 FreeMemory* NewItem=new FreeMemory; NewItem->Next=temp->Next; NewItem->ID=0; NewItem->Size=temp->Size-TrySize; NewItem->StartAdd=temp->StartAdd+TrySize; NewItem->State=false; temp->ID=id; temp->Size=TrySize; temp->State=true; temp->Nex

53、t=NewItem; return true; /end for return false; bool Alloc_Memory(int id, int Algorithm,int TrySize)/對算法進(jìn)行選擇 switch(Algorithm) case 1 : return Alloc_FirstFit(id,TrySize); break; case 2: return Alloc_BestFit(id,TrySize); break; default: cout<<"你沒有指定算法,系統(tǒng)將默認(rèn)為首次適應(yīng)算法!"<<endl; return Alloc_FirstFit(id,TrySize); /*End Memory Alloc 內(nèi)存分配區(qū)操作定義完成*/ /*Recycle Memory 回收內(nèi)存*/bool Free_Memory(int id) FreeMemory* temp=AllocTable; FreeMemory* Last=temp; if(temp-