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

1、南通大學計算機科學與技術(shù)學院操作系統(tǒng)課程設計報告專 業(yè)：學生姓名：學號： 時間:操作系統(tǒng)模擬算法課程設計報告設計要求將本學期三次的實驗集成實現(xiàn):A. 處理機管理；B. 存儲器管理；C. 虛擬存儲器的缺頁調(diào)度。設計流程圖主流程圖先A.處理機時度來1）先來先服務間先片服輪務轉(zhuǎn)處理機管理FCFS次佳開始算并位移到首位先來先服束務算法流程廠進程到組中首個進程進程排陽組中 （計算的打印進程的首進應刻二組中 更改權(quán)周轉(zhuǎn)的當前時間，八 :初始化進程控制塊，適讓進程控制塊按適、7 f , 一一.一rvV刻、周轉(zhuǎn)時間、帶丿應，即下一刻進程的開始時間當前時間:=前一進程帶權(quán)周轉(zhuǎn)時間=數(shù)組為空/服務時間間法先缺頁調(diào)

2、曠L進R先U出算法2）時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)算法流程圖B.存儲器管理（可變式分區(qū)管理） 1）首次適應法 分配流程圖首次適應算法回收流程圖開始輸入完成進程的標號在分配區(qū)表中查找前一個分區(qū)的后向指釋放區(qū)p下鄰分區(qū)空釋放區(qū)p上鄰分區(qū)空前一個空閑區(qū)的后向 指針指向p的后一個 分區(qū)，p的后一個分 區(qū)的前向指針指向p 的前一個分區(qū)，且 p 的前一個分區(qū)大小更 改為加上p的大小， 釋放p 針指向p的后一個空 閑分區(qū)，p的后一個 空閑分區(qū)的前向指針 指向p的前一個分 區(qū)，且p的后一個分 區(qū)大小更改為加上 p 的大小前一個空閑區(qū)的后向指針指向p的后一個空閑分區(qū)，p的后一 個空閑分區(qū)的前向指針指向 p 的前一個空

3、閑分區(qū)，且 p的前 一個空閑分區(qū)大小更改為加上釋放區(qū)p上下均鄰空閑區(qū)釋放區(qū)p上下均不鄰空閑區(qū)p的大小再加上p的后一個空 閑分區(qū)的大小，合并后的這個 空閑區(qū)的后向指針指向 p的下 下個分區(qū)，如果p的下下個分 區(qū)不為空，則其前向指針指向 合并后的這個空閑區(qū)，釋放p和p的下一個分區(qū)將p放在鏈首， 并修改其狀態(tài)位 為空閑2）最佳適應法回收內(nèi)存流程C.虛擬存儲器的缺頁調(diào)度1）先進先出FIFO£開始T卜理開始FIFO的缺頁中斷釋放分區(qū)與上釋放分區(qū)與下空閑分區(qū)相鄰有空閑塊可用？T摘除鏈表中下分釋放分區(qū)與下配一塊閑分區(qū)相鄰摘除鏈表中上下分區(qū)。合并這三個分區(qū)，將上空閑區(qū)長 度修改為三個分區(qū) 的長度。2

4、)LRU摘除鏈表中上分 區(qū)。合并釋放分區(qū)與上分區(qū)，將上空 閑區(qū)長度修改為這 二分區(qū)的長度。區(qū)。合并釋放分區(qū)與下分區(qū)，將釋放 分區(qū)中長度修改為這二分區(qū)的長度。FIFO淘汰算法流程LRU淘汰算法流程實現(xiàn)原理主界面設計一個框架分別去鏈接處理機管理、存儲器管理和缺頁調(diào)度相關的程序。A. 處理機調(diào)度1）先來先服務FCFS（一）任務先來先服務的調(diào)度算法實現(xiàn)處理機調(diào)度。（二）要求1. 實現(xiàn)對FCFS算法的模擬實現(xiàn)2. 計算出該算法的平均作業(yè)周轉(zhuǎn)時間、平均帶權(quán)作業(yè)周轉(zhuǎn)時間。（三）原理按作業(yè)到達CPU寸間先后順序進行非剝奪式調(diào)度，先到達 CPU勺作業(yè)先被執(zhí)行（四）數(shù)據(jù)結(jié)構(gòu)structtask_structcha

5、rname;/* 進程名稱 */ intn umber;/* 進程編號 */ floatcome_time;/*到達時間 */floatru n_begin_time;/* 開始運行時間 */ floatrun_time;/*運行時間 */floatrun_end_time;/*運行結(jié)束時間 */in tpriority;/*優(yōu)先級 */intorder;/*運行次序 */intrun_flag;/*調(diào)度標志 */tasksMAX;intfcfs（）/*先來先服務算法*/進程名 鏈接指針 到達時間 估計運行時間 進程狀態(tài) 進程控制塊結(jié)構(gòu)（五）實現(xiàn)方法 建立一個鏈表按照到達CPU勺時間從小到大排

6、列，只需從第一個作業(yè)（頭結(jié)點） 依次調(diào)度到最后一個作業(yè)（尾結(jié)點）。（六）運行界面 測試數(shù)據(jù)：作業(yè)名到達時間運行時間A028B09C03執(zhí)行FCFS算法如下:2）時間片輪轉(zhuǎn)法（一）任務只對進程的運行模擬，將其運行時間加一，判斷要求運行時間與已運行時 間是否相等，若相等則表示進程結(jié)束，進程退出調(diào)度，釋放資源。（二）要求1. 實現(xiàn)對RR算法的模擬實現(xiàn)2. 顯示執(zhí)行完一個時間片的結(jié)果。（三）原理時間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就程序按先來先服務的原則排成一個隊 列，每次調(diào)度時，把CPU分配給隊首進程，并令其執(zhí)行一個時間片。當執(zhí)行 的時間片用完時，調(diào)度程序停止該進程的執(zhí)行，并將它送往就緒隊列的末 尾；然后

7、，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行 一個時間片。（四）數(shù)據(jù)結(jié)構(gòu)temp->state='R'初始狀態(tài)每個進程均為運行態(tài)temp->allocation=0;/初始時進程均不占用cpunum+=temp->need_time;用num來限制循環(huán)的次數(shù)（五）實現(xiàn)方法處理器調(diào)度總是選擇標志單元指示的進程運行。執(zhí)行：已運行時間+1來模擬進程的一次運行，表示進程已經(jīng)運行過一個單位的時間。當一個進 程被選中運行時，必須設置該進程可以運行的時間片值，以及恢復進程的現(xiàn) 場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行滿一個時間片進程運行一次后，應把該進程的

8、進程控制塊中的指針值送到標志單元，以 指示下一個輪到運行的進程。同時，應判斷該進程的要求運行時間與已運行時 間，若該進程的要求運行時間已運行時間，則表示它尚未執(zhí)行結(jié)束，應待到下一輪時再運行。若該進程的要求運行時間=已運行時間，則表示它已經(jīng)執(zhí)行結(jié) 束，應指導它的狀態(tài)修改成“結(jié)束”且退出隊列。此時，應把該進程的進程控 制塊中的指針值送到前面一個進程的指針位置。進程名 鏈接指針到達時間估計運行時間進程狀態(tài)進程控制塊結(jié)構(gòu)（六）運行界面測試數(shù)據(jù):作業(yè)號執(zhí)行時間/sA1B2C1執(zhí)行時間片輪轉(zhuǎn)算法RR如下:B.存儲器管理（可變式分區(qū)管理） 1）首次適應法（一）任務通過采用首次適應算法實現(xiàn)內(nèi)存的分配與回收，并

9、可以查看和顯示當前內(nèi)存現(xiàn) 狀。（二）要求1. 實現(xiàn)對FF算法的模擬實現(xiàn)2. 輸入要進行分配內(nèi)存的進程 ID 和相應所需內(nèi)存大小，回收內(nèi)存時輸入已運行 的進程 ID 。（三）原理FF算法要求空閑鏈已地址遞增的次序連接。分配內(nèi)存時，從鏈首開始順序查 找，直到找到第一個滿足要求的空間并分配給進程，把分配后余下的空間仍然 留在鏈表中。若從鏈首至鏈尾都不滿足要求，則分配失敗。該算法傾向于優(yōu)先 使用低地址的空間。（四）數(shù)據(jù)結(jié)構(gòu)intconstMEMO=256;初始化常類型MEMO用MEM表示內(nèi)存大?。ǔｎ愋偷淖?量或?qū)ο蟮闹凳遣荒鼙桓碌模﹕tructFreeMemoryintID;intStartAdd

10、;intSize;boolState;/ 定義state為布爾型變量，其值只有真（TRUE和假（FALSE） FreeMemory*Next;FreeMemory*AllocTable=newFreeMemory;/ 建立全局管理表用于內(nèi)與回收 FreeMemory*PtrforCycleFit=AllocTable;/ 為循環(huán)首次適應定義的指針，此指 針用于指向當前查找的起始地址 ;/ 初始化內(nèi)存函數(shù)voidMemoryInit（FreeMemory*&tempAdd）tempAdd->ID=0;/ 初始化當前進程為空 tempAdd->Size=MEMO;初始化可分配空

11、間為內(nèi)存大小 tempAdd->StartAdd=0;/ 初始化起始地址為 0 tempAdd->State=false;/ 初始化狀態(tài)為未分配 tempAdd->Next=NULL;/ 初始化下一個進程也為空/ 反饋內(nèi)存現(xiàn)態(tài)voidDispMemory（）FreeMemory*temp=AllocTable;/ 全局管理表反映內(nèi)存狀態(tài)cout<<" 系統(tǒng)總內(nèi)存 :"<<MEMO<<endl;for（;temp;temp=temp->Next）cout<<" 進程 ID："<&

12、lt;temp->ID<<""<<" 大?。?"<<temp->Size<<""<<" 起始地 址:"<<temp->StartAdd<<""<<"是否已分配:"<<temp->State<<endl;/ 輸出內(nèi)存的各個變量（五）實現(xiàn)方法 可變式分區(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的 需要，并且分區(qū)的個數(shù)是可以

13、調(diào)整的。當需要裝入一個作業(yè)時，根據(jù)作業(yè)需要 的貯存量，查看是否有足夠的空閑空間，若有，則按需求量分割一部分給作 業(yè)；若無，則作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大 小小的分區(qū)。有的分區(qū)被分配作業(yè)占用，有的分區(qū)空閑。在空閑區(qū)表中，按空 閑區(qū)首地址從低到高進行登記。當一個作業(yè)執(zhí)行完成時，作業(yè)所占用的分區(qū)應歸還給系統(tǒng)。在歸還時，要考慮 相鄰空間區(qū)合并問題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分以下 4 種情況考慮：A、釋放區(qū)下鄰空閑區(qū)；B、釋放區(qū)上鄰空閑區(qū)；C、釋放區(qū)上下都與空閑區(qū)鄰接；D釋放區(qū)上鄰空閑區(qū)不鄰接。（六）運行界面系統(tǒng)總內(nèi)存為 256 時，分別為進程 1、 2、 3 分配大小為

14、64、 128、 64 的內(nèi)存。 執(zhí)行首次適應算法分配內(nèi)存如下：若回收進程 2 的內(nèi)存，執(zhí)行結(jié)果如下：2）最佳適應法（一）任務 通過采用最佳適應算法實現(xiàn)內(nèi)存的分配與回收，并可以查看和顯示當前內(nèi)存現(xiàn) 狀。（二）要求1. 實現(xiàn)對BF算法的模擬實現(xiàn)2. 輸入要進行分配內(nèi)存的進程ID和相應所需內(nèi)存大小，回收內(nèi)存時輸入需要回 收的內(nèi)存塊。（三）原理 最佳適應算法掃描整個未分配表或鏈表，從空閑區(qū)中挑選一個能滿足用戶進程 要求的最小分區(qū)進行分配。此算法保證不會分割一個更大的區(qū)域，使得裝入大 作業(yè)的要求容易得到滿足，同時，通常把空閑區(qū)按長度遞增順序排列，查找時 總是從最小的一個空閑區(qū)開始，直至找到滿足要求的分

15、區(qū)為止，這時，最佳適 應分配算法等同于首次適應算法。此算法的主存利用率好，所找出的分區(qū)如果 最好滿足要求則是最合適的。（四） 數(shù)據(jù)結(jié)構(gòu)intconstMEMO=256;/ 初始化常類型 MEMO ，用 MEMO 表示內(nèi)存大小（常類型的變量或?qū)ο蟮?值是不能被更新的）structFreeMemory intID;intStartAdd;intSize;boolState;/定義state為布爾型變量，其值只有真（ TRUE）和假（FALSE）FreeMemory*Next;boolAlloc_BestFit（intid,intTrySize）/查找滿足此條件的 x1<=TrySize<

16、;=x2 的分區(qū) ,然后將其放置在 x2 中，并將 x2 拆分成兩個分區(qū) SortPartition（true）;/ 使用快速排序算法，升序排序for（;temp;temp=temp->Next）/*回收操作，回收過程中，要用到三個指針，上一個Last,當前temp,下一個temp->next當temp指向表頭或表尾時需要特殊考慮*/當要退岀工作時，就要回收/此退岀的工作由執(zhí)行函數(shù)調(diào)用voidE ndJob（i ntid）Free_Memory（id）;（五）實現(xiàn)方法空閑區(qū)設置為雙向鏈表，其雙向鏈的分區(qū)格式為:0 （狀態(tài)位）分區(qū)大小（N+2向前指針大小為N的已分配區(qū)或空閑區(qū)0 （狀

17、態(tài)位）分區(qū)大小（N+2）向后指針（六）運行界面 測試數(shù)據(jù)如下：進程123456所需內(nèi)存253445121310執(zhí)行最佳適應算法為其分配內(nèi)存如下:若回收進程4,執(zhí)行結(jié)果如下:C. 虛擬存儲器的缺頁調(diào)度1）先進先出FIFO（一）任務采用先進先出FIFO算法實現(xiàn)分頁管理的缺頁調(diào)度，并輸出每次調(diào)入調(diào)出的頁號 和運行結(jié)果。（二）要求1. 實現(xiàn)對FIFO算法的模擬實現(xiàn)2. 輸出每次執(zhí)行的結(jié)果。（三）原理基于程序總是按線性順序來訪問物理空間這一假設，總是淘汰最先調(diào)入主存的 頁面，即淘汰在主存中駐留時間最長的頁面，認為駐留時間最長的頁不再使用 的可能性較大。（四）數(shù)據(jù)結(jié)構(gòu)voidFIFO（）in tle ng

18、th;in tfifo100=0;in tpageLe ngth;in tfifoPage100=0;in ti,j;Coutvv"*先進先出算*"<<e ndrpageLe ngth=3;len gth=9;for(i=1;i<=le ngth;i+)in tflag=0;for(j=1;j<=pageLe ngth;j+) if(fifoi=fifoPagej)flag=1;j=pageLength+1;elseif（fifoPagej=0） fifoPagej=fifoi;j=pageLength+1;flag=1; if（flag=1）els

19、ecout«" t淘汰"vvfifoPage1v<endl;for（j=1;j<=pageLength;j+）fifoPagej=fifoPagej+1; fifoPagepageLength=fifoi;（五）實現(xiàn)方法 當采用先進先出算法時，用一個數(shù)組構(gòu)成先進先出隊列，數(shù)組中各個元素為進 程已在主存的頁號，其隊列頭指針初始化為 0. 假設分配給每個進程的內(nèi)存塊數(shù) 固定。當隊列滿需淘汰時，淘汰最先進入主存的一頁。若該頁修改過，還有存 入磁盤。然后要把當前訪問的頁裝入該塊，并修改頁表和存儲分塊表的對應標 志。（六）運行界面 測試數(shù)據(jù)： 頁表長度： 9；

20、頁框長度： 3；頁面請求數(shù)列： 4,4,3,5,1,1,2,3,2 執(zhí)行先進先出 FIFO 算法結(jié)果如下：2）LRU（一）任務采用先進先出LRU算法實現(xiàn)分頁管理的缺頁調(diào)度，并輸出每次調(diào)入調(diào)出的頁號 和運行結(jié)果。（二）要求1. 實現(xiàn)對LRU算法的模擬實現(xiàn)2. 輸出每次執(zhí)行的結(jié)果。（三）原理 最近最少使用頁面替換算法淘汰的頁面是在最近一段時間內(nèi)最久未被訪問的那 一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面可能還 有立即被使用，而那些在較長時間內(nèi)未被使用的頁面可能不會立即使用。在分頁虛擬存儲系統(tǒng)中，當硬件發(fā)出缺頁中斷后轉(zhuǎn)操作系統(tǒng)處理缺頁中斷。如果主存中已無空閑塊，可采用LRU算法進

21、行缺頁處理。(四) 數(shù)據(jù)結(jié)構(gòu)voidLRU()intlength; intlru100=0; intpageLength; intlruPage100=0; inti,j;cout<<"I *最近最少使用 LRU 算法<<endl;*11pageLength=3;length=9;for(i=1;i<=length;i+)intflag=0;for(j=1;j<=pageLength;j+)if(lrui=lruPagej)for(intcc=j;cc>0;cc-) lruPagecc=lruPagecc-1;lruPage1=lrui;fl

22、ag=1;j=pageLength+1;elseif(lruPagej=0) for(intvv=j;vv>0;vv-) lruPagevv=lruPagevv-1;lruPage1=lrui;j=pageLength+1;flag=1;if(flag=1)elsecout«" t淘汰"<<lruPagepageLength«endl;for(j=pageLength;j>0;j-)lruPagej=lruPagej-1;lruPage1=lrui;(五) 實現(xiàn)方法當采用LRU算法時，用一個數(shù)組構(gòu)成堆棧，堆棧中各個元素為進程已在主

23、存的 頁號，為了進行頁面置換，可設置一個棧指針，初始化為 0. 假定分配給每個進 程的內(nèi)存塊數(shù)固定不變。當隊列滿需淘汰時，操作系統(tǒng)選擇棧底元素淘汰，其 他元素向下移一個位置，將新調(diào)入頁放棧指針指示的棧頂。當訪問的頁在棧中 時，還應調(diào)整頁從當前位置到棧頂。(六) 運行界面測試數(shù)據(jù)：頁表長度： 9；頁框長度： 3；頁面請求數(shù)列： 2,3,5,1,5,5,4,4,3執(zhí)行最近最少使用LRU算法結(jié)果如下：總結(jié)與體會通過本次課程設計讓我對于圖形界面設計有了一定的思路和看法，同時我 對先來先服務、時間片輪轉(zhuǎn)、首次適應算法、最佳適應算法、先進先出和最近 最少使用算法有了更詳盡的認識。在編程的過程中發(fā)現(xiàn)會用到大

24、量的指針，用 指針來操作大量的數(shù)據(jù)比較方便，但最后應該記得釋放資源。從這次實驗中我 發(fā)現(xiàn)我對于C+掌握也有所不足，程序經(jīng)過了多次修改才得以完善，在以后應 該注重編程方面的訓練。此外我還更深入的理解了各個進程調(diào)度算法，及實現(xiàn)過程。在編寫程序時 查詢了很多資料，間接提高了我的搜索能力。在此次課程設計過程中，對進程 的相關知識有了一定的加深。特別是對進程的進程控制塊的存在和價值有了更 進一步的認識。在編寫程序的過程之中，對進程自身信息的設計和管理以及調(diào) 度的算法都有助于對書本知識的理解和掌握。特別是設計先來先服務調(diào)度算法 和時間片輪轉(zhuǎn)調(diào)度算法的時候，對進程的調(diào)度算法有了更好的深入理解。對進 程管理中

25、的等待隊列，就緒隊列，時間片等概念有了更深刻的印象。在設計此模擬操作系統(tǒng)的課設中，也加深了對 C+知識的把握。解決了一 些以往在編程中遇到了困難。通過此次的課程設計，不僅提高了對操作系統(tǒng)的 認知，也在同時提高了編程的能力，加強了實踐。另外，我覺得此次課程設計 雖然主要問題是在編程上，但是經(jīng)過不斷的去調(diào)試，還是成功的調(diào)試了出來。 但是這幾個程序用了多天的時間進行分析和修改，雖然出現(xiàn)了不少問題，但收 獲頗多！ 源代碼：#inClude<iostream>#inClude<Cstring>#inClude<Cstddef>usingnamespaCestd;int

26、fCfsoutput();/* 調(diào)度結(jié)果輸出 */intfCfsinput();/ 進程參數(shù)的初始化voidkaishi();#defineMAX10struct no de/建立鏈表來存放進程數(shù)據(jù)charname5;/ 進程名稱 intneed_time;/ 所需要的時間 intallocation;/ 占用 cpu 的情況charstate;/目前的狀態(tài) R為運行，E為運行完畢 node*next;/ 鏈表的尾結(jié)點;structtask_structcharname;/* 進程名稱 */ intnumber;/* 進程編號 */ floatcome_time;/* 到達時間 */ floa

27、trun_begin_time;/* 開始運行時間 */ floatrun_time;/* 運行時間 */ floatrun_end_time;/* 運行結(jié)束時間 */ intpriority;/* 優(yōu)先級 */ intorder;/* 運行次序 */ intrun_flag;/* 調(diào)度標志 */tasksMAX;intcounter;/* 實際進程個數(shù) */ intfcfs()/* 先來先服務算法 */ fcfsinput();floattime_temp=0;inti;intnumber_schedul; time_temp=e_time; for(i=0;i<c

28、ounter;i+) tasksi.run_begin_time=time_temp; tasksi.run_end_time=tasksi.run_begin_time+tasksi.run_time; tasksi.run_flag=1;time_temp=tasksi.run_end_time; number_schedul=i;tasksnumber_schedul.order=i+1; fcfsoutput();return0; intfcfsinput() task_structtt;inti,j;/初始化進程數(shù) counter=3;/初始化每個到達系統(tǒng)的時間為5、 7、 8tas

29、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(e_time>tasksj+1.come_time) tt=tasksj; tasksj=tasksj+1;tasksj+1=tt;/初始化每個進程估計運行的時間 tasks0.run_time=28;tasks1.run_time=9;tasks2.run_time=3; /初始化每個進程的名字 ='A&

30、#39;='B'='C'cout<<"I*先來先服務算法"<<endl<<endl;for(i=0;i<counter;i+)tasksi.run_begin_time=0; tasksi.run_end_time=0;tasksi.order=0;tasksi.run_flag=0; return0;intfcfsoutput()/* 調(diào)度結(jié)果輸出 */ inti; floatturn_round_time=0,f1,w=0;cout<<&qu

31、ot; 作業(yè)名到達時間運行時間開始時間停止時間運行次序周轉(zhuǎn)時間"<<endl;for(i=0;i<counter;i+)f1=tasksi.run_end_e_time;turn_round_time+=f1;w+=(f1/tasksi.run_time);cout<<""<<<<'t'<<""<<e_time<<'t'<<"&qu

32、ot;<<tasksi.run_time<<'t'<<""<<tasksi.run_begin_time<<'t'<<""<<tasksi.run_end_time<<'t'<<tasksi.order<<'t'<<f1<<'t'<<endl;cout<<" 平均周轉(zhuǎn)時間： "<<

33、;turn_round_time/counter<<endl;cout<<" 平均帶權(quán)周轉(zhuǎn)時間： "<<w/counter<<endl;cout<<""return0;/*/intrr()intn=3,num=0; node*head=NULL;node*tail=NULL;cout<<"I*時間片輪轉(zhuǎn)調(diào)度算法 *"<<endl<<endl;for(inti=0;i<n;i+)node*temp=newnode;if(i=0)strc

34、py(temp->name,"A");if(i=1)strcpy(temp->name,"B");if(i=2)strcpy(temp->name,"C"); temp->need_time=rand()%4+1; temp->state='R'/ 初始狀態(tài)每個進程均為運行態(tài) temp->allocation=0;/初始時進程均不占用 cpunum+=temp->need_time;/ 用 num 來限制循環(huán)的次數(shù) if(!head)tail=head=temp;elsetai

35、l->next=temp; tail=temp;tail->next=head;node*p;p=head;cout<<endl<<" 初始時刻： "<<endl;cout<<" 進程 "<<'t'<<" 剩余時間 "<<'t'<<" 占用 cpu 時間 "<<endl; while(p!=tail)cout<<""<<p

36、->name<<'t'<<""<<p->need_time<<'t'<<'t'<<p->allocation<<'s'<<endl; p=p->next; cout<<""<<tail->name<<'t'<<""<<tail->need_time<<&#

37、39;t'<<'t'<<p->allocation<<'s'<<endl; node*q;intlabel=1;intm=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

38、9;label=1;p=p->next;cout<<" 執(zhí)行 "<<m<<" 秒后： "<<endl;q=head;cout<<" 進程 "<<'t'<<" 剩余時間 "<<'t'<<" 占用 cpu 時間 "<<endl;while(q!=tail) cout<<""<<q->name&l

39、t;<'t'<<""<<q->need_time<<'t'<<'t'<<q->allocation<<'s'<<endl;q=q->next; cout<<""<<tail->name<<'t'<<""<<tail->need_time<<'t'<

40、;<'t'<<q->allocation<<'s'<<endl; m+;cout<<endl<<""return0;/*/intconstMEMO=256;/ 初始化常類型 MEMO ，用 MEMO 表示內(nèi)存大小(常類型的變量或?qū)ο蟮?值是不能被更新的) structFreeMemoryintID;intStartAdd;intSize;boolState;/定義state為布爾型變量，其值只有真( TRUE)和假(FALSE)FreeMemory*Next;FreeMe

41、mory*AllocTable=newFreeMemory;/ 建立全局管理表用于內(nèi)存分配與回收 FreeMemory*PtrforCycleFit=AllocTable;/ 為循環(huán)首次適應定義的指針，此指針用于指向當前查找 的起始地址 ;/初始化內(nèi)存函數(shù) voidMemoryInit(FreeMemory*&tempAdd) tempAdd->ID=0;/ 初始化當前進程為空 tempAdd->Size=MEMO;/ 初始化可分配空間為內(nèi)存大小 tempAdd->StartAdd=0;/ 初始化起始地址為 0 tempAdd->State=false;/ 初始

42、化狀態(tài)為未分配 tempAdd->Next=NULL;/ 初始化下一個進程也為空 /反饋內(nèi)存現(xiàn)態(tài) voidDispMemory() FreeMemory*temp=AllocTable;/ 全局管理表反映內(nèi)存狀態(tài)cout<<" 系統(tǒng)總內(nèi)存 :"<<MEMO<<endl; for(;temp;temp=temp->Next) cout<<" 進程 ID ："<<temp->ID<<""<<" 大小： "<<

43、;temp->Size<<""<<" 起始地 址:"v<temp->StartAddvv""vv"是否已分配:"<<temp->State<<endl;/輸出內(nèi)存的各個變量/分區(qū)排序voidSortPartition(boolorder)/ 在此使用的是快速排序算法FreeMemory*temp1=AllocTable;FreeMemory*temp2=AllocTable;FreeMemory*Last1=temp1;FreeMemory*L

44、ast2=temp2; if(temp2->Next) temp2=temp2->Next;switch(order)case1:升序部分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=t

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

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

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

48、; NewItem->Size=temp->Size-TrySize;NewItem->StartAdd=temp->StartAdd+TrySize;NewItem->State=false;temp->ID=id; temp->Size=TrySize;temp->State=true; temp->Next=NewItem;returntrue;/endforreturnfalse; boolAlloc_BestFit(intid,intTrySize)/查找滿足此條件的 x1<=TrySize<=x2 的分區(qū) ,然后將其

49、放置在 x2 中，并將 x2 拆分成兩個分區(qū) SortPartition(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,St

50、artAdd 都不用變 temp->State=true;/ 值為真表示已分配else/比所找到的要小，則需要將其拆分 FreeMemory*NewItem=newFreeMemory;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->

51、;State=true; temp->Next=NewItem;returntrue;/endforreturnfalse;boolAlloc_Memory(intid,intAlgorithm,intTrySize)/ 對算法進行選擇switch(Algorithm)case1:returnAlloc_FirstFit(id,TrySize);break;case2:returnAlloc_BestFit(id,TrySize);break;default:cout<<" 你沒有指定算法 ,系統(tǒng)將默認為首次適應算法 !"<<endl; ret

52、urnAlloc_FirstFit(id,TrySize);/*EndMemoryAlloc 內(nèi)存分配區(qū)操作定義完成 */*RecycleMemory 回收內(nèi)存 */ boolFree_Memory(intid)FreeMemory*temp=AllocTable;FreeMemory*Last=temp; if(temp->ID=id)/考慮第一條記錄的特殊情況if(temp->Next&&!temp->Next->State)/ 下一分區(qū)沒有被占用，將與本條合并 temp->ID=0; temp->Size=temp->Size+t

53、emp->Next->Size;temp->State=0;/ 回收Last=temp->Next;temp->Next=temp->Next->Next;deleteLast;else/只有第一分區(qū)為空，則清除相關表項的數(shù)據(jù)temp->ID=0;temp->State=false;/ 改為沒有使用狀態(tài)returntrue;/特殊情況第一條if(temp->Next)temp=temp->Next;for(;temp;temp=temp->Next)/*回收操作，回收過程中，要用到三個指針，上一個 Last,當前temp,

54、下一個temp->next 當 temp 指向表頭或表尾時需要特殊考慮 */ if(temp->ID=id)/begin 找到該 ID 表項if(temp->Next)/ 沒有到最后一條if(!Last->State&&!temp->Next->State)/ 回收區(qū)與插入點的前、后兩個分區(qū)鄰接優(yōu)先級為 1 Last->Next=temp->Next->Next;Last->Size=Last->Size+temp->Size+temp->Next->Size;deletetemp->Ne

55、xt;deletetemp;elseif(!Last->State)/ 回收區(qū)與插入點的前一個分區(qū)相鄰接優(yōu)先級為 2Last->Next=temp->Next;Last->Size=Last->Size+temp->Size;deletetemp;elseif(!(temp->Next->State)/ 回收區(qū)與插入點的后一個分區(qū)相鄰接優(yōu)先級為 3/if(temp->Next->Next)Last=temp->Next->Next;/else/Last=NULL;temp->Size=temp->Size+te

56、mp->Next->Size;temp->State=false;temp->ID=0;FreeMemory*tempfor=temp->Next;temp->Next=Last;deletetempfor;else/回收區(qū)為獨立單位.優(yōu)先級為4temp->ID=0;temp->State=false;/ 最后一條elseif(!Last->State)/ 最后一條的前一條為空Last->Size=Last->Size+temp->Size;Last->Next=NULL;deletetemp;else/最后一條的前

57、一條不為空temp->ID=0;temp->State=0;returntrue;/end 找到該 ID 表項此類情況處理完畢Last=temp;/endforreturnfalse;/*MemoryRecycled 內(nèi)存分配完畢 Alldone,thejobreferedwillleavesystem*/ /當進程開始時 ,就應該為之分配內(nèi)存 voidBeginJob(intid,intAlgorithm,intTrySize)Alloc_Memory(id,Algorithm,TrySize);/當要退出工作時 ,就要回收 /此退出的工作由執(zhí)行函數(shù)調(diào)用 voidEndJob(i

58、ntid)Free_Memory(id);/*/voidFIFO()intlength;intfifo100=0;intpageLength; intfifoPage100=0;inti,j;cout<<"I*"<<endl;pageLength=3;length=9;cout<<" 時刻 t"<<'t'for(i=0;i<length;i+)cout<<i<<'t'cout<<endl<<" 引用串 "

59、;<<'t'for(i=1;i<=length;i+)fifoi=rand()%5+1;cout<<fifoi<<'t'for(i=1;i<=length;i+)intflag=0;for(j=1;j<=pageLength;j+)if(fifoi=fifoPagej)flag=1; j=pageLength+1; elseif(fifoPagej=0) fifoPagej=fifoi; j=pageLength+1;flag=1;if(flag=1)elsecout«" t淘汰"vvfifoPage1v<endl;for(j=1;j<=pageLength;j+)fifoPagej=fifoPagej+1;fifoPagepageLength=fifoi;cout«e ndlvv"t="vvi-1<v"時"<v't： for(intjk=1;jk<=pageLength;jk+)cout<<"P"<<jk<<'t'cout&l