操作系統(tǒng)模擬算法課程設(shè)計(jì)報(bào)告

...wd......wd......wd...南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專(zhuān)南通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專(zhuān)業(yè)：學(xué)生姓名：學(xué)號(hào)：時(shí)間：操作系統(tǒng)課程設(shè)計(jì)報(bào)告操作系統(tǒng)課程設(shè)計(jì)報(bào)告操作系統(tǒng)模擬算法課程設(shè)計(jì)報(bào)告設(shè)計(jì)要求將本學(xué)期三次的實(shí)驗(yàn)集成實(shí)現(xiàn)：處理機(jī)管理；存儲(chǔ)器管理；虛擬存儲(chǔ)器的缺頁(yè)調(diào)度。設(shè)計(jì)流程圖主流程圖開(kāi)場(chǎng)的圖形界面開(kāi)場(chǎng)的圖形界面存儲(chǔ)器管理缺頁(yè)調(diào)度處理機(jī)管理存儲(chǔ)器管理缺頁(yè)調(diào)度處理機(jī)管理LRU算法先進(jìn)先出最正確適應(yīng)法首次適應(yīng)法先來(lái)先服務(wù)LRU算法先進(jìn)先出最正確適應(yīng)法首次適應(yīng)法先來(lái)先服務(wù)時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)A.處理機(jī)調(diào)度1)先來(lái)先服務(wù)FCFS開(kāi)場(chǎng)開(kāi)場(chǎng)初始化進(jìn)程控制塊，讓進(jìn)程控制塊按進(jìn)程到達(dá)先后順序讓進(jìn)程排隊(duì)初始化進(jìn)程控制塊，讓進(jìn)程控制塊按進(jìn)程到達(dá)先后順序讓進(jìn)程排隊(duì)調(diào)度數(shù)組中首個(gè)進(jìn)程，并讓數(shù)組中的下一位移到首位調(diào)度數(shù)組中首個(gè)進(jìn)程，并讓數(shù)組中的下一位移到首位計(jì)算并打印進(jìn)程的完成時(shí)刻、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間計(jì)算并打印進(jìn)程的完成時(shí)刻、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間其中：周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間更改計(jì)時(shí)器的當(dāng)前時(shí)間,即下一刻進(jìn)程的開(kāi)場(chǎng)時(shí)間更改計(jì)時(shí)器的當(dāng)前時(shí)間,即下一刻進(jìn)程的開(kāi)場(chǎng)時(shí)間當(dāng)前時(shí)間=前一進(jìn)程的完成時(shí)間+其服務(wù)時(shí)間數(shù)組為空數(shù)組為空NY完畢完畢先來(lái)先服務(wù)算法流程2)時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)算法流程圖B.存儲(chǔ)器管理(可變式分區(qū)管理〕1)首次適應(yīng)法分配流程圖開(kāi)場(chǎng)申請(qǐng)xkb內(nèi)存開(kāi)場(chǎng)申請(qǐng)xkb內(nèi)存由鏈頭找到第一個(gè)空閑區(qū)分區(qū)大小≥xkb大于分區(qū)大小=分區(qū)大小-xkb，修改下一個(gè)空閑區(qū)的后向指針內(nèi)容為〔后向指針〕+xkb;修改上一個(gè)空閑區(qū)的前向指針為〔前向指針〕+xkb將該空閑區(qū)從鏈中摘除：修改下一個(gè)空閑區(qū)的后向地址=該空閑區(qū)后向地址，修改上一個(gè)空閑區(qū)的前向指針為該空閑區(qū)的前向指針等于小于延鏈查找下一個(gè)空閑區(qū)到鏈尾了作業(yè)等待返回是否登記已分配表返回分配給進(jìn)程的內(nèi)存首地址首次適應(yīng)算法回收流程圖開(kāi)場(chǎng)開(kāi)場(chǎng)輸入完成進(jìn)程的標(biāo)號(hào)在分配區(qū)表中查找釋放區(qū)p下鄰分區(qū)空閑區(qū)前一個(gè)空閑區(qū)的后向指針指向p的后一個(gè)分區(qū)，p的后一個(gè)分區(qū)的前向指針指向p的前一個(gè)分區(qū)，且p的前一個(gè)分區(qū)大小更改為加上p的大小，釋放p釋放區(qū)p上鄰分區(qū)空前一個(gè)分區(qū)的后向指針指向p的后一個(gè)空閑分區(qū)，p的后一個(gè)空閑分區(qū)的前向指針指向p的前一個(gè)分區(qū)，且p的后一個(gè)分區(qū)大小更改為加上p的大小釋放區(qū)p上下均鄰空閑區(qū)前一個(gè)空閑區(qū)的后向指針指向p的后一個(gè)空閑分區(qū)，p的后一個(gè)空閑分區(qū)的前向指針指向p的前一個(gè)空閑分區(qū)，且p的前一個(gè)空閑分區(qū)大小更改為加上p的大小再加上p的后一個(gè)空閑分區(qū)的大小，合并后的這個(gè)空閑區(qū)的后向指針指向p的下下個(gè)分區(qū)，如果p的下下個(gè)分區(qū)不為空，那么其前向指針指向合并后的這個(gè)空閑區(qū)，釋放p和p的下一個(gè)分區(qū)釋放區(qū)p上下均不鄰空閑區(qū)將p放在鏈?zhǔn)?，并修改其狀態(tài)位為空閑最正確適應(yīng)法開(kāi)場(chǎng)釋放分區(qū)與上空閑分區(qū)相鄰開(kāi)場(chǎng)釋放分區(qū)與上空閑分區(qū)相鄰釋放分區(qū)與下空閑分區(qū)相鄰?fù)戤呩尫欧謪^(qū)與下空閑分區(qū)相鄰TFTFTF摘除鏈表中上分區(qū)。合并釋放分區(qū)與上分區(qū)，將上空閑區(qū)長(zhǎng)度修改為這二分區(qū)的長(zhǎng)度。摘除鏈表中上下分區(qū)。合并這三個(gè)分區(qū)，將上空閑區(qū)長(zhǎng)度修改為三個(gè)分區(qū)的長(zhǎng)度。摘除鏈表中下分區(qū)。合并釋放分區(qū)與下分區(qū)，將釋放分區(qū)中長(zhǎng)度修改為這二分區(qū)的長(zhǎng)度。將合并的或釋放的分區(qū)按長(zhǎng)度升序重新插入到自由鏈表中。C.虛擬存儲(chǔ)器的缺頁(yè)調(diào)度1)先進(jìn)先出FIFO開(kāi)場(chǎng)FIFO的缺頁(yè)中斷處理開(kāi)場(chǎng)FIFO的缺頁(yè)中斷處理查主存分塊表查主存分塊表有空閑塊可用有空閑塊可用Y分配一塊Y分配一塊NNJ=p[HEAD]J=p[HEAD]J的修改標(biāo)志=1J的修改標(biāo)志=1NNY輸出“Y輸出“將J頁(yè)復(fù)寫(xiě)入交換區(qū)〞輸出“輸出“裝入L頁(yè)〞調(diào)整FIFO隊(duì)列，將L插入隊(duì)尾〔HEAD=(HEAD+1)modM)調(diào)整FIFO隊(duì)列，將L插入隊(duì)尾〔HEAD=(HEAD+1)modM)修改主存分塊表和頁(yè)表修改主存分塊表和頁(yè)表終止終止FIFO淘汰算法流程FIFO淘汰算法流程2〕LRU開(kāi)場(chǎng)LRU的缺頁(yè)中斷處理開(kāi)場(chǎng)LRU的缺頁(yè)中斷處理查主存分塊表查主存分塊表有空閑塊可用有空閑塊可用Y分配一塊Y分配一塊NN找到棧底元素：J=p[M-1]找到棧底元素：J=p[M-1]J的修改標(biāo)志=1J的修改標(biāo)志=1NNY輸出“Y輸出“將J頁(yè)送到入交換區(qū)〞輸出“輸出“裝入L頁(yè)〞調(diào)整堆棧，使HEAD所指元素及以下的元素下移P[HEAD]=L調(diào)整堆棧，使HEAD所指元素及以下的元素下移P[HEAD]=L修改主存分塊表和頁(yè)表修改主存分塊表和頁(yè)表終止終止LRU淘汰算法流程LRU淘汰算法流程實(shí)現(xiàn)原理主界面設(shè)計(jì)一個(gè)框架分別去鏈接處理機(jī)管理、存儲(chǔ)器管理和缺頁(yè)調(diào)度相關(guān)的程序。A.處理機(jī)調(diào)度1)先來(lái)先服務(wù)FCFS任務(wù)先來(lái)先服務(wù)的調(diào)度算法實(shí)現(xiàn)處理機(jī)調(diào)度。要求實(shí)現(xiàn)對(duì)FCFS算法的模擬實(shí)現(xiàn)計(jì)算出該算法的平均作業(yè)周轉(zhuǎn)時(shí)間、平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間。原理按作業(yè)到達(dá)CPU時(shí)間先后順序進(jìn)展非剝奪式調(diào)度，先到達(dá)CPU的作業(yè)先被執(zhí)行。數(shù)據(jù)構(gòu)造structtask_struct{charname;/*進(jìn)程名稱*/intnumber;/*進(jìn)程編號(hào)*/floatcome_time;/*到達(dá)時(shí)間*/floatrun_begin_time;/*開(kāi)場(chǎng)運(yùn)行時(shí)間*/floatrun_time;/*運(yùn)行時(shí)間*/floatrun_end_time;/*運(yùn)行完畢時(shí)間*/intpriority;/*優(yōu)先級(jí)*/intorder;/*運(yùn)行次序*/intrun_flag;/*調(diào)度標(biāo)志*/}tasks[MAX];intfcfs()/*先來(lái)先服務(wù)算法*/進(jìn)程名鏈接指針到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間進(jìn)程狀態(tài)進(jìn)程控制塊構(gòu)造實(shí)現(xiàn)方法建設(shè)一個(gè)鏈表按照到達(dá)CPU的時(shí)間從小到大排列，只需從第一個(gè)作業(yè)〔頭結(jié)點(diǎn)〕依次調(diào)度到最后一個(gè)作業(yè)〔尾結(jié)點(diǎn)〕。運(yùn)行界面測(cè)試數(shù)據(jù)：作業(yè)名到達(dá)時(shí)間運(yùn)行時(shí)間A028B09C03執(zhí)行FCFS算法如下：2)時(shí)間片輪轉(zhuǎn)法任務(wù)只對(duì)進(jìn)程的運(yùn)行模擬，將其運(yùn)行時(shí)間加一，判斷要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間是否相等，假設(shè)相等那么表示進(jìn)程完畢，進(jìn)程退出調(diào)度，釋放資源。要求實(shí)現(xiàn)對(duì)RR算法的模擬實(shí)現(xiàn)顯示執(zhí)行完一個(gè)時(shí)間片的結(jié)果。原理時(shí)間片輪轉(zhuǎn)算法中，系統(tǒng)將所有的就程序按先來(lái)先服務(wù)的原那么排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序停頓該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。數(shù)據(jù)構(gòu)造temp->state='R';//初始狀態(tài)每個(gè)進(jìn)程均為運(yùn)行態(tài)temp->allocation=0; //初始時(shí)進(jìn)程均不占用cpunum+=temp->need_time;//用num來(lái)限制循環(huán)的次數(shù)實(shí)現(xiàn)方法處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。執(zhí)行：已運(yùn)行時(shí)間+1來(lái)模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過(guò)一個(gè)單位的時(shí)間。當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須設(shè)置該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個(gè)輪到運(yùn)行的進(jìn)程。同時(shí)，應(yīng)判斷該進(jìn)程的要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間，假設(shè)該進(jìn)程的要求運(yùn)行時(shí)間已運(yùn)行時(shí)間，那么表示它尚未執(zhí)行完畢，應(yīng)待到下一輪時(shí)再運(yùn)行。假設(shè)該進(jìn)程的要求運(yùn)行時(shí)間=已運(yùn)行時(shí)間，那么表示它已經(jīng)執(zhí)行完畢，應(yīng)指導(dǎo)它的狀態(tài)修改成“完畢〞且退出隊(duì)列。此時(shí)，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個(gè)進(jìn)程的指針位置。進(jìn)程名鏈接指針到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間進(jìn)程狀態(tài)進(jìn)程控制塊構(gòu)造運(yùn)行界面測(cè)試數(shù)據(jù)：作業(yè)號(hào)執(zhí)行時(shí)間/sA1B2C1執(zhí)行時(shí)間片輪轉(zhuǎn)算法RR如下：B.存儲(chǔ)器管理(可變式分區(qū)管理〕1)首次適應(yīng)法任務(wù)通過(guò)采用首次適應(yīng)算法實(shí)現(xiàn)內(nèi)存的分配與回收，并可以查看和顯示當(dāng)前內(nèi)存現(xiàn)狀。要求1.實(shí)現(xiàn)對(duì)FF算法的模擬實(shí)現(xiàn)2.輸入要進(jìn)展分配內(nèi)存的進(jìn)程ID和相應(yīng)所需內(nèi)存大小，回收內(nèi)存時(shí)輸入已運(yùn)行的進(jìn)程ID。原理FF算法要求空閑鏈已地址遞增的次序連接。分配內(nèi)存時(shí)，從鏈?zhǔn)组_(kāi)場(chǎng)順序查找，直到找到第一個(gè)滿足要求的空間并分配給進(jìn)程，把分配后余下的空間仍然留在鏈表中。假設(shè)從鏈?zhǔn)字伶溛捕疾粷M足要求，那么分配失敗。該算法傾向于優(yōu)先使用低地址的空間。數(shù)據(jù)構(gòu)造intconstMEMO=256;//初始化常類(lèi)型MEMO，用MEMO表示內(nèi)存大小〔常類(lèi)型的變量或?qū)ο蟮闹凳遣荒鼙桓碌摹硈tructFreeMemory{intID;intStartAdd;intSize;boolState;//定義state為布爾型變量，其值只有真〔TRUE)和假〔FALSE)FreeMemory*Next;};FreeMemory*AllocTable=newFreeMemory;//建設(shè)全局管理表用于內(nèi)與回收FreeMemory*PtrforCycleFit=AllocTable;//為循環(huán)首次適應(yīng)定義的指針，此指針用于指向當(dāng)前查找的起始地址;//初始化內(nèi)存函數(shù)voidMemoryInit(FreeMemory*&tempAdd){tempAdd->ID=0;//初始化當(dāng)前進(jìn)程為空tempAdd->Size=MEMO;//初始化可分配空間為內(nèi)存大小tempAdd->StartAdd=0;//初始化起始地址為0tempAdd->State=false;//初始化狀態(tài)為未分配tempAdd->Next=NULL;//初始化下一個(gè)進(jìn)程也為空}//反響內(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<<"進(jìn)程ID："<<temp->ID<<""<<"大?。?<<temp->Size<<""<<"起始地址:"<<temp->StartAdd<<""<<"是否已分配:"<<temp->State<<endl;}//輸出內(nèi)存的各個(gè)變量實(shí)現(xiàn)方法可變式分區(qū)管理是指在處理作業(yè)過(guò)程中建設(shè)分區(qū)，使分區(qū)大小正好適合作業(yè)的需要，并且分區(qū)的個(gè)數(shù)是可以調(diào)整的。當(dāng)需要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的貯存量，查看是否有足夠的空閑空間，假設(shè)有，那么按需求量分割一局部給作業(yè)；假設(shè)無(wú)，那么作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大小小的分區(qū)。有的分區(qū)被分配作業(yè)占用，有的分區(qū)空閑。在空閑區(qū)表中，按空閑區(qū)首地址從低到高進(jìn)展登記。當(dāng)一個(gè)作業(yè)執(zhí)行完成時(shí)，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時(shí)，要考慮相鄰空間區(qū)合并問(wèn)題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分以下4種情況考慮：A、釋放區(qū)下鄰空閑區(qū)；B、釋放區(qū)上鄰空閑區(qū)；C、釋放區(qū)上下都與空閑區(qū)鄰接；D、釋放區(qū)上鄰空閑區(qū)不鄰接。運(yùn)行界面系統(tǒng)總內(nèi)存為256時(shí)，分別為進(jìn)程1、2、3分配大小為64、128、64的內(nèi)存。執(zhí)行首次適應(yīng)算法分配內(nèi)存如下：假設(shè)回收進(jìn)程2的內(nèi)存，執(zhí)行結(jié)果如下：2〕最正確適應(yīng)法任務(wù)通過(guò)采用最正確適應(yīng)算法實(shí)現(xiàn)內(nèi)存的分配與回收，并可以查看和顯示當(dāng)前內(nèi)存現(xiàn)狀。要求1.實(shí)現(xiàn)對(duì)BF算法的模擬實(shí)現(xiàn)2.輸入要進(jìn)展分配內(nèi)存的進(jìn)程ID和相應(yīng)所需內(nèi)存大小，回收內(nèi)存時(shí)輸入需要回收的內(nèi)存塊。原理最正確適應(yīng)算法掃描整個(gè)未分配表或鏈表，從空閑區(qū)中挑選一個(gè)能滿足用戶進(jìn)程要求的最小分區(qū)進(jìn)展分配。此算法保證不會(huì)分割一個(gè)更大的區(qū)域，使得裝入大作業(yè)的要求容易得到滿足，同時(shí)，通常把空閑區(qū)按長(zhǎng)度遞增順序排列，查找時(shí)總是從最小的一個(gè)空閑區(qū)開(kāi)場(chǎng)，直至找到滿足要求的分區(qū)為止，這時(shí)，最正確適應(yīng)分配算法等同于首次適應(yīng)算法。此算法的主存利用率好，所找出的分區(qū)如果最好滿足要求那么是最適宜的。數(shù)據(jù)構(gòu)造intconstMEMO=256;//初始化常類(lèi)型MEMO，用MEMO表示內(nèi)存大小〔常類(lèi)型的變量或?qū)ο蟮闹凳遣荒鼙桓碌摹硈tructFreeMemory{intID;intStartAdd;intSize;boolState;//定義state為布爾型變量，其值只有真〔TRUE)和假〔FALSE)FreeMemory*Next;};boolAlloc_BestFit(intid,intTrySize){//查找滿足此條件的x1<=TrySize<=x2的分區(qū),然后將其放置在x2中，并將x2拆分成兩個(gè)分區(qū)SortPartition(true);//使用快速排序算法，升序排序for(;temp;temp=temp->Next){/*回收操作,回收過(guò)程中，要用到三個(gè)指針，上一個(gè)Last,當(dāng)前temp,下一個(gè)temp->next當(dāng)temp指向表頭或表尾時(shí)需要特殊考慮*///當(dāng)要退出工作時(shí),就要回收//此退出的工作由執(zhí)行函數(shù)調(diào)用voidEndJob(intid){Free_Memory(id);}實(shí)現(xiàn)方法空閑區(qū)設(shè)置為雙向鏈表，其雙向鏈的分區(qū)格式為：0〔狀態(tài)位〕分區(qū)大小〔N+2〕向前指針大小為N的已分配區(qū)或空閑區(qū)0〔狀態(tài)位〕分區(qū)大小〔N+2)向后指針運(yùn)行界面測(cè)試數(shù)據(jù)如下：進(jìn)程123456所需內(nèi)存253445121310執(zhí)行最正確適應(yīng)算法為其分配內(nèi)存如下：假設(shè)回收進(jìn)程4，執(zhí)行結(jié)果如下：C.虛擬存儲(chǔ)器的缺頁(yè)調(diào)度1)先進(jìn)先出FIFO任務(wù)采用先進(jìn)先出FIFO算法實(shí)現(xiàn)分頁(yè)管理的缺頁(yè)調(diào)度，并輸出每次調(diào)入調(diào)出的頁(yè)號(hào)和運(yùn)行結(jié)果。要求1.實(shí)現(xiàn)對(duì)FIFO算法的模擬實(shí)現(xiàn)2.輸出每次執(zhí)行的結(jié)果。原理基于程序總是按線性順序來(lái)訪問(wèn)物理空間這一假設(shè)，總是淘汰最先調(diào)入主存的頁(yè)面，即淘汰在主存中駐留時(shí)間最長(zhǎng)的頁(yè)面，認(rèn)為駐留時(shí)間最長(zhǎng)的頁(yè)不再使用的可能性較大。數(shù)據(jù)構(gòu)造voidFIFO(){ intlength; intfifo[100]={0}; intpageLength; intfifoPage[100]={0}; inti,j; cout<<"***********************先進(jìn)先出算法**************************"<<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]; }實(shí)現(xiàn)方法當(dāng)采用先進(jìn)先出算法時(shí)，用一個(gè)數(shù)組構(gòu)成先進(jìn)先出隊(duì)列，數(shù)組中各個(gè)元素為進(jìn)程已在主存的頁(yè)號(hào)，其隊(duì)列頭指針初始化為0.假設(shè)分配給每個(gè)進(jìn)程的內(nèi)存塊數(shù)固定。當(dāng)隊(duì)列滿需淘汰時(shí)，淘汰最先進(jìn)入主存的一頁(yè)。假設(shè)該頁(yè)修改正，還有存入磁盤(pán)。然后要把當(dāng)前訪問(wèn)的頁(yè)裝入該塊，并修改頁(yè)表和存儲(chǔ)分塊表的對(duì)應(yīng)標(biāo)志。運(yùn)行界面測(cè)試數(shù)據(jù)：頁(yè)表長(zhǎng)度：9；頁(yè)框長(zhǎng)度：3；頁(yè)面請(qǐng)求數(shù)列：4,4,3,5,1,1,2,3,2執(zhí)行先進(jìn)先出FIFO算法結(jié)果如下：2〕LRU任務(wù)采用先進(jìn)先出LRU算法實(shí)現(xiàn)分頁(yè)管理的缺頁(yè)調(diào)度，并輸出每次調(diào)入調(diào)出的頁(yè)號(hào)和運(yùn)行結(jié)果。要求1.實(shí)現(xiàn)對(duì)LRU算法的模擬實(shí)現(xiàn)2.輸出每次執(zhí)行的結(jié)果。原理最近最少使用頁(yè)面替換算法淘汰的頁(yè)面是在最近一段時(shí)間內(nèi)最久未被訪問(wèn)的那一頁(yè)，它是基于程序局部性原理來(lái)考慮的，認(rèn)為那些剛被使用過(guò)的頁(yè)面可能還有立即被使用，而那些在較長(zhǎng)時(shí)間內(nèi)未被使用的頁(yè)面可能不會(huì)立即使用。在分頁(yè)虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出缺頁(yè)中斷后轉(zhuǎn)操作系統(tǒng)處理缺頁(yè)中斷。如果主存中已無(wú)空閑塊，可采用LRU算法進(jìn)展缺頁(yè)處理。數(shù)據(jù)構(gòu)造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]; }實(shí)現(xiàn)方法當(dāng)采用LRU算法時(shí)，用一個(gè)數(shù)組構(gòu)成堆棧，堆棧中各個(gè)元素為進(jìn)程已在主存的頁(yè)號(hào)，為了進(jìn)展頁(yè)面置換，可設(shè)置一個(gè)棧指針，初始化為0.假定分配給每個(gè)進(jìn)程的內(nèi)存塊數(shù)固定不變。當(dāng)隊(duì)列滿需淘汰時(shí)，操作系統(tǒng)選擇棧底元素淘汰，其他元素向下移一個(gè)位置，將新調(diào)入頁(yè)放棧指針指示的棧頂。當(dāng)訪問(wèn)的頁(yè)在棧中時(shí)，還應(yīng)調(diào)整頁(yè)從當(dāng)前位置到棧頂。運(yùn)行界面測(cè)試數(shù)據(jù)：頁(yè)表長(zhǎng)度：9；頁(yè)框長(zhǎng)度：3；頁(yè)面請(qǐng)求數(shù)列：2,3,5,1,5,5,4,4,3執(zhí)行最近最少使用LRU算法結(jié)果如下：總結(jié)與體會(huì)通過(guò)本次課程設(shè)計(jì)讓我對(duì)于圖形界面設(shè)計(jì)有了一定的思路和看法，同時(shí)我對(duì)先來(lái)先服務(wù)、時(shí)間片輪轉(zhuǎn)、首次適應(yīng)算法、最正確適應(yīng)算法、先進(jìn)先出和最近最少使用算法有了更詳盡的認(rèn)識(shí)。在編程的過(guò)程中發(fā)現(xiàn)會(huì)用到大量的指針，用指針來(lái)操作大量的數(shù)據(jù)比較方便，但最后應(yīng)該記得釋放資源。從這次實(shí)驗(yàn)中我發(fā)現(xiàn)我對(duì)于c++掌握也有所缺乏，程序經(jīng)過(guò)了屢次修改才得以完善，在以后應(yīng)該注重編程方面的訓(xùn)練。此外我還更深入的理解了各個(gè)進(jìn)程調(diào)度算法，及實(shí)現(xiàn)過(guò)程。在編寫(xiě)程序時(shí)查詢了很多資料，間接提高了我的搜索能力。在此次課程設(shè)計(jì)過(guò)程中，對(duì)進(jìn)程的相關(guān)知識(shí)有了一定的加深。特別是對(duì)進(jìn)程的進(jìn)程控制塊的存在和價(jià)值有了更進(jìn)一步的認(rèn)識(shí)。在編寫(xiě)程序的過(guò)程之中，對(duì)進(jìn)程自身信息的設(shè)計(jì)和管理以及調(diào)度的算法都有助于對(duì)書(shū)本知識(shí)的理解和掌握。特別是設(shè)計(jì)先來(lái)先服務(wù)調(diào)度算法和時(shí)間片輪轉(zhuǎn)調(diào)度算法的時(shí)候，對(duì)進(jìn)程的調(diào)度算法有了更好的深入理解。對(duì)進(jìn)程管理中的等待隊(duì)列，就緒隊(duì)列，時(shí)間片等概念有了更深刻的印象。在設(shè)計(jì)此模擬操作系統(tǒng)的課設(shè)中，也加深了對(duì)c++知識(shí)的把握。解決了一些以往在編程中遇到了困難。通過(guò)此次的課程設(shè)計(jì)，不僅提高了對(duì)操作系統(tǒng)的認(rèn)知，也在同時(shí)提高了編程的能力，加強(qiáng)了實(shí)踐。另外，我覺(jué)得此次課程設(shè)計(jì)雖然主要問(wèn)題是在編程上，但是經(jīng)過(guò)不斷的去調(diào)試，還是成功的調(diào)試了出來(lái)。但是這幾個(gè)程序用了多天的時(shí)間進(jìn)展分析和修改，雖然出現(xiàn)了不少問(wèn)題，但收獲頗多！源代碼：#include<iostream>#include<cstring>#include<cstddef>usingnamespacestd;intfcfsoutput();/*調(diào)度結(jié)果輸出*/intfcfsinput();//進(jìn)程參數(shù)的初始化voidkaishi();#defineMAX10structnode//建設(shè)鏈表來(lái)存放進(jìn)程數(shù)據(jù){charname[5];//進(jìn)程名稱intneed_time;//所需要的時(shí)間intallocation;//占用cpu的情況charstate;//目前的狀態(tài)R為運(yùn)行，E為運(yùn)行完畢node*next;//鏈表的尾結(jié)點(diǎn)};structtask_struct{charname;/*進(jìn)程名稱*/intnumber;/*進(jìn)程編號(hào)*/floatcome_time;/*到達(dá)時(shí)間*/floatrun_begin_time;/*開(kāi)場(chǎng)運(yùn)行時(shí)間*/floatrun_time;/*運(yùn)行時(shí)間*/floatrun_end_time;/*運(yùn)行完畢時(shí)間*/intpriority;/*優(yōu)先級(jí)*/intorder;/*運(yùn)行次序*/intrun_flag; /*調(diào)度標(biāo)志*/}tasks[MAX];intcounter;/*實(shí)際進(jìn)程個(gè)數(shù)*/intfcfs()/*先來(lái)先服務(wù)算法*/{fcfsinput();floattime_temp=0;inti;intnumber_schedul;time_temp=tasks[0]e_time;for(i=0;i<counter;i++){tasks[i].run_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;//初始化進(jìn)程數(shù)counter=3;//初始化每個(gè)到達(dá)系統(tǒng)的時(shí)間為5、7、8tasks[0]e_time=rand()%9;tasks[1]e_time=rand()%9;tasks[2]e_time=rand()%9;for(i=1;i<3;i++){ for(j=0;j<3-i;j++) { if(tasks[j]e_time>tasks[j+1]e_time) { tt=tasks[j]; tasks[j]=tasks[j+1]; tasks[j+1]=tt; } }}//初始化每個(gè)進(jìn)程估計(jì)運(yùn)行的時(shí)間tasks[0].run_time=28;tasks[1].run_time=9;tasks[2].run_time=3;//初始化每個(gè)進(jìn)程的名字 tasks[0].name='A'; tasks[1].name='B'; tasks[2].name='C'; cout<<"************************先來(lái)先服務(wù)算法************************"<<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()/*調(diào)度結(jié)果輸出*/{inti;floatturn_round_time=0,f1,w=0;cout<<"作業(yè)名到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)場(chǎng)時(shí)間停頓時(shí)間運(yùn)行次序周轉(zhuǎn)時(shí)間"<<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<<"平均周轉(zhuǎn)時(shí)間："<<turn_round_time/counter<<endl;cout<<"平均帶權(quán)周轉(zhuǎn)時(shí)間："<<w/counter<<endl;cout<<"";return0;}/**/intrr(){intn=3,num=0;node*head=NULL;node*tail=NULL;cout<<"*********************時(shí)間片輪轉(zhuǎn)調(diào)度算法*********************"<<endl<<endl;for(inti=0;i<n;i++){node*temp=newnode; if(i==0)strcpy(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)每個(gè)進(jìn)程均為運(yùn)行態(tài)temp->allocation=0; //初始時(shí)進(jìn)程均不占用cpunum+=temp->need_time;//用num來(lái)限制循環(huán)的次數(shù)if(!head){tail=head=temp;}else{tail->next=temp;tail=temp;tail->next=head;}}node*p;p=head;cout<<endl<<"初始時(shí)刻："<<endl;cout<<"進(jìn)程"<<'\t'<<"剩余時(shí)間"<<'\t'<<"占用cpu時(shí)間"<<endl;while(p!=tail){ cout<<""<<p->name<<'\t'<<""<<p->need_time<<'\t'<<'\t'<<p->allocation<<'s'<<endl; p=p->next;}cout<<""<<tail->name<<'\t'<<""<<tail->need_time<<'\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'; } label=1; p=p->next;}cout<<"執(zhí)行"<<m<<"秒后："<<endl;q=head;cout<<"進(jìn)程"<<'\t'<<"剩余時(shí)間"<<'\t'<<"占用cpu時(shí)間"<<endl;while(q!=tail){ cout<<""<<q->name<<'\t'<<""<<q->need_time<<'\t'<<'\t'<<q->allocation<<'s'<<endl; q=q->next;}cout<<""<<tail->name<<'\t'<<""<<tail->need_time<<'\t'<<'\t'<<q->allocation<<'s'<<endl;m++;}cout<<endl<<"";return0;}/**/intconstMEMO=256;//初始化常類(lèi)型MEMO，用MEMO表示內(nèi)存大小〔常類(lèi)型的變量或?qū)ο蟮闹凳遣荒鼙桓碌摹硈tructFreeMemory{intID;intStartAdd;intSize;boolState;//定義state為布爾型變量，其值只有真〔TRUE)和假〔FALSE)FreeMemory*Next;};FreeMemory*AllocTable=newFreeMemory;//建設(shè)全局管理表用于內(nèi)存分配與回收FreeMemory*PtrforCycleFit=AllocTable;//為循環(huán)首次適應(yīng)定義的指針，此指針用于指向當(dāng)前查找的起始地址;//初始化內(nèi)存函數(shù)voidMemoryInit(FreeMemory*&tempAdd){tempAdd->ID=0;//初始化當(dāng)前進(jìn)程為空tempAdd->Size=MEMO;//初始化可分配空間為內(nèi)存大小tempAdd->StartAdd=0;//初始化起始地址為0tempAdd->State=false;//初始化狀態(tài)為未分配tempAdd->Next=NULL;//初始化下一個(gè)進(jìn)程也為空}//反響內(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<<"進(jìn)程ID："<<temp->ID<<""<<"大?。?<<temp->Size<<""<<"起始地址:"<<temp->StartAdd<<""<<"是否已分配:"<<temp->State<<endl;}//輸出內(nèi)存的各個(gè)變量//分區(qū)排序voidSortPartition(boolorder)//在此使用的是快速排序算法{FreeMemory*temp1=AllocTable;FreeMemory*temp2=AllocTable;FreeMemory*Last1=temp1;FreeMemory*Last2=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=temp2->Next;temp2->Next=temp1->Next;temp1->Next=temp->Next;}Last2=temp2;}Last1=temp1;}}break;case0://降序局部{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->Next;}Last2=temp2;}Last1=temp1;}}}}/*內(nèi)存分配*/boolAlloc_FirstFit(intid,intTrySize)//定義布爾型函數(shù)Alloc_FirstFit(){//查找一個(gè)可用第一個(gè)滿足分配請(qǐng)求的分區(qū)，如果滿足將其寫(xiě)入內(nèi)存分配表//否那么分配失敗，返回FreeMemory*temp=AllocTable;for(;temp;temp=temp->Next){if(TrySize<=temp->Size&&!temp->State)//第一個(gè)滿足條件的分區(qū)已找到{if(TrySize==temp->Size)//剛好和申請(qǐng)的大小一致{temp->ID=id;//保持不變temp->Next,Size,StartAdd都不用變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->State=true;temp->Next=NewItem;}returntrue;}}//endforreturnfalse;}boolAlloc_BestFit(intid,intTrySize){//查找滿足此條件的x1<=TrySize<=x2的分區(qū),然后將其放置在x2中，并將x2拆分成兩個(gè)分區(qū)SortPartition(true);//使用快速排序算法，升序排序FreeMemory*temp=AllocTable;if(temp->Next)temp=temp->Next;for(;temp;temp=temp->Next){if(TrySize<=temp->Size&&!temp->State)//第一個(gè)滿足條件的分區(qū)已找到{if(TrySize==temp->Size)//剛好和申請(qǐng)的大小一致{temp->ID=id;//保持不變temp->Next,Size,StartAdd都不用變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->State=true;temp->Next=NewItem;}returntrue;}}//endforreturnfalse;}boolAlloc_Memory(intid,intAlgorithm,intTrySize)//對(duì)算法進(jìn)展選擇{switch(Algorithm){case1:returnAlloc_FirstFit(id,TrySize);break;case2:returnAlloc_BestFit(id,TrySize);break;default:cout<<"你沒(méi)有指定算法,系統(tǒng)將默認(rèn)為首次適應(yīng)算法!!!"<<endl;returnAlloc_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ū)沒(méi)有被占用，將與本條合并{temp->ID=0;temp->Size=temp->Size+temp->Next->Size;temp->State=0;//回收Last=temp->Next;temp->Next=temp->Next->Next;deleteLast;}else//只有第一分區(qū)為空，那么去除相關(guān)表項(xiàng)的數(shù)據(jù){temp->ID=0;temp->State=false;//改為沒(méi)有使用狀態(tài)}returntrue;}//特殊情況第一條if(temp->Next)temp=temp->Next;for(;temp;temp=temp->Next){/*回收操作,回收過(guò)程中，要用到三個(gè)指針，上一個(gè)Last,當(dāng)前temp,下一個(gè)temp->next當(dāng)temp指向表頭或表尾時(shí)需要特殊考慮*/if(temp->ID==id)//begin找到該ID表項(xiàng){if(temp->Next)//沒(méi)有到最后一條{if(!Last->State&&!temp->Next->State)//回收區(qū)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接優(yōu)先級(jí)為1{Last->Next=temp->Next->Next;Last->Size=Last->Size+temp->Size+temp->Next->Size;deletetemp->Next;deletetemp;}elseif(!Last->State)//回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)相鄰接優(yōu)先級(jí)為2{Last->Next=temp->Next;Last->Size=Last->Size+temp->Size;deletetemp;}elseif(!(temp->Next->State))//回收區(qū)與插入點(diǎn)的后一個(gè)分區(qū)相鄰接優(yōu)先級(jí)為3{//if(temp->Next->Next)Last=temp->Next->Next;//else//Last=NULL;temp->Size=temp->Size+temp->Next->Size;temp->State=false;temp->ID=0;FreeMemory*tempfor=temp->Next;temp->Next=Last;deletetempfor;}else//回收區(qū)為獨(dú)立單位.優(yōu)先級(jí)為4{temp->ID=0;temp->State=false;}}//最后一條else{if(!Last->State)//最后一條的前一條為空{(diào)Last->Size=Last->Size+temp->Size;Last->Next=NULL;deletetemp;}else//最后一條的前一條不為空{(diào)temp->ID=0;temp->State=0;}}returntrue;}//end找到該ID表項(xiàng)此類(lèi)情況處理完畢Last=temp;}//endforreturnfalse;}/*MemoryRecycled內(nèi)存分配完畢Alldone,thejobreferedwillleavesystem*///當(dāng)進(jìn)程開(kāi)場(chǎng)時(shí),就應(yīng)該為之分配內(nèi)存voidBeginJob(intid,intAlgorithm,intTrySize){Alloc_Memory(id,Algorithm,TrySize);}//當(dāng)要退出工作時(shí),就要回收//此退出的工作由執(zhí)行函數(shù)調(diào)用voidEndJob(intid){Free_Memory(id);}/**/voidFIFO(){ intlength; intfifo[100]={0}; intpageLength; intfifoPage[100]={0}; inti,j; cout<<"***********************先進(jìn)先出算法**************************"<<endl; pageLength=3; length=9; cout<<"時(shí)刻t"<<'\t'; for(i=0;i<length;i++) { cout<<i<<'\t'; }cout<<endl<<"引用串"<<'\t'; for(i=1;i<=length;i++) { fifo[i]=rand()%5+1; cout<<fifo[i]<<'\t'; } 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]; } cout<<endl<<"t="<<i-1<<"時(shí)"<<'\t'; for(intjk=1;jk<=pageLength;jk++) { cout<<"P"<<jk<<'\t'; } cout<<endl<<'\t'; for(ints=1;s<=pageLength;s++){ cout<<fifoPage[s]<<'\t'; } cout<<endl; }}/**/voidLRU(){ intlength; intlru[100]={0}; intpageLength; intlruPage[100]={0}; inti,j; cout<<"***********************最近最少使用LRU算法***********************"<<endl; pageLength=3; length=9; cout<<"時(shí)刻t"<<'\t'; for(i=0;i<length;i++) { cout<<i<<'\t'; }cout<<endl<<"引用串"<<'\t'; for(i=1;i<=length;i++) { lru[i]=rand()%5+1; cout<<lru[i]<<'\t'; } for(i=1;i<=length;i++){ intflag=0; for(j=1;j<=pageLength;j++){ if(lru[i]==lruPage[j]){