時間片輪轉(zhuǎn)算法

1、一、實驗?zāi)康模?）在單處理器情況下按時間片輪轉(zhuǎn)算法實現(xiàn)處理器調(diào)度，輸出運行動態(tài)變化過程。（2）通過算法的實現(xiàn)加深了解處理器調(diào)度的工作。二、實驗內(nèi)容輸入實現(xiàn)現(xiàn)處理器器調(diào)度的的幾個進進程信息息，任意意確定一一組“要求運運行時間間”，啟動動所設(shè)計計的處理理器調(diào)度度程序，顯示逐逐次被選選中進程程的進程程名以及及進程控控制塊的的動態(tài)變變化過程程。實驗步驟驟1、任務(wù)務(wù)分析：時間片片輪轉(zhuǎn)的的主要思思想就是是按順序序為每一一個進程程一次只只分配一一個時間間片的時時間。算算法要完完成的功功能就是是將各個個進程按按照時間間片輪轉(zhuǎn)轉(zhuǎn)運行的的動態(tài)過過程顯示示出來。時間片片輪轉(zhuǎn)算算法的主主要實現(xiàn)現(xiàn)過程是是首先為為每一個

2、個進程創(chuàng)創(chuàng)建一個個進程控控制塊，定義數(shù)據(jù)據(jù)結(jié)構(gòu)，說明進進程控制制塊所包包含的內(nèi)內(nèi)容，有有進程名名、進程程所需運運行時間間、已運運行時間間和進程程的狀態(tài)態(tài)以及指指針的信信息。實實現(xiàn)的過過程即運運用指針針指向某某一個進進程，判判斷當(dāng)前前的進程程是否是是就緒狀狀態(tài)“r”，如果果是，則則為該進進程分配配一個時時間片，同時，已運行行時間加加一且要要求運行行的時間間減一，如此循循環(huán)執(zhí)行行，當(dāng)某某一個進進程的所所需要運運行的時時間減少少至0時時，則將將該進程程的狀態(tài)態(tài)設(shè)置為為“e”。然后，將指針針指向下下一個未未運行完完成的進進程，重重復(fù)判斷斷，直至至所有的的進程都都運行結(jié)結(jié)束。2、概要要設(shè)計：（1）所所用

3、數(shù)據(jù)據(jù)結(jié)構(gòu)及及符號說說明typeedeff sttrucct PPCBchaar nnamee100; /進進程名strructt PCCB *nexxt; /循循環(huán)鏈指指針intt neeed_timme; /要要求運行行時間intt woorkeed_ttimee; /已已運行時時間，初初始為00chaar ccondditiion; /進進程狀態(tài)態(tài)，只有有“就緒”和“結(jié)束”兩種狀狀態(tài)intt fllag; /進進程結(jié)束束標(biāo)志，用于輸輸出PCBB;PCB *frrontt,*rrearr; /循環(huán)環(huán)鏈隊列列的頭指指針和尾尾指針int N; /N為進程程數(shù)（2）主主程序的的流程圖圖：開始輸入

4、進程數(shù)N輸入各進程信息為每個進程創(chuàng)建PCB并初始化形成一個循環(huán)鏈隊列指針指向循環(huán)鏈隊列第一個進程進程是否r運行時間+1且剩余時間-1 Y剩余時間=0？ Y將進程狀態(tài)置為e（完成）指針指向隊列中下個進程所有進程是否完成 N 結(jié)束 Y（3）程程序說明明：處理理器調(diào)度度總是選選擇指針針指示的的進程運運行。由由于本實實驗是模模擬處理理器調(diào)度度的功能能，所以以，對被被選中的的進程并并不實際際的啟動動運行，而是執(zhí)執(zhí)行：已已運行時時間+11來模擬擬進程的的一次運運行，表表示進程程已經(jīng)運運行過一一個單位位的時間間。3、詳細(xì)細(xì)設(shè)計（1）首首先每一一個進程程用一個個進程控控制塊PPCB來來代表。進程控控制塊的的格

5、式為為：進程名指針要求運行行時間已運行時時間狀態(tài)其中，進進程名作為為進程的的標(biāo)識，如Q11、Q2等。指針進程按按順序排排成循環(huán)環(huán)鏈隊列，用指針針指出下下一個進進程的進進程控制制塊的首首地址，最后一一個進程程的指針針指出第第一個進進程的進進程控制制塊首地地址。要求運行行時間假設(shè)設(shè)進程需需要運行行的單位位時間數(shù)數(shù)。已運行時時間假設(shè)進進程已經(jīng)經(jīng)運行的的單位時時間數(shù)，初始值值為“0”。狀態(tài)有兩種種狀態(tài)，“就緒”和“結(jié)束”，初始始狀態(tài)都都為“就緒”，用“R”表示。當(dāng)一個個進程運運行結(jié)束束后，它它的狀態(tài)態(tài)為“結(jié)束”，用“E”表示。（2）每每次運行行所設(shè)計計的處理理器調(diào)度度程序前前，為每每個進程程任意確確定

6、它的的“要求運運行時間間”。把五個進進程按順順序排成成循環(huán)鏈鏈隊列，用指針針指出隊隊列連接接情況。用指針針表示輪輪到運行行的進程程，如下下圖描述述所示：K1Q1K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12431200000RRRRRPCB11PCB22PCB33PCB44PCB55（3）程程序詳細(xì)細(xì)設(shè)計步步驟：a.首先先建立PPCB的的數(shù)據(jù)結(jié)結(jié)構(gòu)，為為了便于于正確輸輸出，加加上了進進程結(jié)束束標(biāo)志fflagg。輸入入進程信信息（包包括進程程名和要要求運行行的時間間），并并為每個個進程創(chuàng)創(chuàng)建一個個PCBB并初始始化形成成一個循循環(huán)鏈隊隊列，用用函數(shù)ccreaatPCCB()來實現(xiàn)現(xiàn)

7、。b.建立立函數(shù)jjudgge()用來判判斷進程程全部運運行結(jié)束束標(biāo)志，即當(dāng)所所有進程程的狀態(tài)態(tài)變?yōu)閑（即完完成狀態(tài)態(tài)）后，循環(huán)結(jié)結(jié)束，表表示所有有進程都都已運行行成功。c.建立立時間片片輪轉(zhuǎn)算算法crreattProocesss（）對進程程進行輪輪轉(zhuǎn)運行行，首先先指針ss指向第第一個進進程PCCB，即即s=ffronnt，判判斷該進進程的狀狀態(tài)是否否為r（就緒緒狀態(tài)），即if(s-conndittionn = rr)，若是則表表示此進進程尚未未執(zhí)行結(jié)結(jié)束，則則執(zhí)行ss-wworkked_timme+且s-neeed_ttimee-，if(s-neeed_ttimee=00)，則則表示此此進程

8、已已運行結(jié)結(jié)束，將將其狀態(tài)態(tài)置為結(jié)結(jié)束，即即s-conndittionn=ee，并并根據(jù)狀狀態(tài)位輸輸出完成成信息，且以后后不會再再運行此此進程。將指針針指向下下個進程程，s=s-nexxt，并并判斷所所有進程程是否已已全部運運行結(jié)束束，沒有有則重復(fù)復(fù)上面算算法。當(dāng)當(dāng)所有進進程的狀狀態(tài)位都都變成e表示所所有進程程運行完完成，則則循環(huán)結(jié)結(jié)束。d.建立立主函數(shù)數(shù)maiin(),輸入入進程數(shù)數(shù)N，調(diào)調(diào)用初始始化循環(huán)環(huán)鏈隊列列函數(shù)ccreaatPCCB()和時間間片輪轉(zhuǎn)轉(zhuǎn)算法ccreaatPrroceess(N)，每次選選中進程程的進程程名以及及運行一一次后進進程隊列列的變化化，實現(xiàn)現(xiàn)處理器器的調(diào)度度。

9、4、調(diào)試試分析：a調(diào)試試過程中中遇到的的問題及及解決方方案開始運行行到Q55運行完完成后顯顯示錯誤誤，如下下圖所示示：原因：經(jīng)經(jīng)檢查程程序發(fā)現(xiàn)現(xiàn)語句iif(ss-ccondditiion=ee )prrinttf(進程%ss已經(jīng)運運行完成成！nnn,s-naame);有有錯誤，因為當(dāng)當(dāng)某個進進程運行行完成后后，其狀狀態(tài)標(biāo)志志已修改改為ee，所所以再次次循環(huán)運運行未完完成的進進程時，當(dāng)運行行到此句句時仍會會將前面面已完成成的進程程重新輸輸出一遍遍完成信信息，導(dǎo)導(dǎo)致輸出出錯誤。解決方案案：為每每個進程程加上一一個結(jié)束束標(biāo)志fflagg，并賦賦初值為為0，當(dāng)進進程運行行完成后后，將fflagg改為1

10、，再將將后面輸輸出改為為if(s-conndittionn=e | s-flaag=0 )prrinttf(進程%ss已經(jīng)運運行完成成！nnn,s-naame);s-fllag=0;，這這樣在前前面進程程運行完完成輸出出后，后后面再循循環(huán)時就就不會重重新輸出出一遍了了。b改進進設(shè)想：本實驗驗較簡單單，但還還不夠完完善，如如未實現(xiàn)現(xiàn)插入進進程功能能，即進進程在運運行過程程中可以以插入其其他的進進程再運運行。還還有未進進行進程程優(yōu)先級級判別，本實驗驗?zāi)J(rèn)進進程的優(yōu)優(yōu)先級按按輸入的的先后順順序從大大到小排排列的，還有其其他功能能等，希希望在以以后的實實驗中逐逐步完善善。5、測試試結(jié)果：a首先先輸出五

11、五個進程程的初始始狀態(tài)b開始始從進程程Q1開始始按時間間片輪轉(zhuǎn)轉(zhuǎn)運行進進程，QQ4先運運行完成成c.接著著Q1運行行完成d.接著著Q5運行行完成e.再Q(mào)Q3運行行完成f.最后后Q2運行行完成四、實驗驗總結(jié)因在早期期的時間間片輪轉(zhuǎn)轉(zhuǎn)法中，系統(tǒng)將將所有的的就緒進進程按照照先來先先服務(wù)的的原則排排成一個個隊列，每次調(diào)調(diào)度是，把CPPU分配配給隊首首進程，并令其其執(zhí)行一一個時間間片。當(dāng)當(dāng)執(zhí)行的的時間片片用完時時，調(diào)度度程序停停止該進進程的執(zhí)執(zhí)行，并并將它送送往就緒緒隊列的的末尾；然后，再把處處理機分分配給就就緒隊列列中新的的隊首進進程，同同時也讓讓它執(zhí)行行一個時時間片。在時間間片輪轉(zhuǎn)轉(zhuǎn)算法中中，時間間

12、片的大大小對系系統(tǒng)性能能有很大大的影響響。如果果選擇很很小的時時間片將將有利于于短作業(yè)業(yè)，因為為它能較較快地完完成，但但會頻繁繁的發(fā)生生中斷、進程上上下文的的切換，從而增增加系統(tǒng)統(tǒng)的開銷銷；反之之，如果果選擇太太長時間間片，使使得每個個進程都都能在一一個時間間片內(nèi)完完成，所所以，一一般定為為時間片片略大于于一次典典型地交交互所需需要的時時間。在完成時時間片輪輪轉(zhuǎn)算法法的實現(xiàn)現(xiàn)過程中中，我們們遇到了了一些問問題，比比如怎樣樣運用循循環(huán)隊列列，如何何設(shè)計結(jié)結(jié)構(gòu)體等等等，也也積極配配合并思思考進行行解決。整體來來說，我我們的算算法雖然然實現(xiàn)了了體現(xiàn)進進程動態(tài)態(tài)運行變變化的過過程，但但是相對對而言比比

13、較簡單單。實驗驗中，我我們小組組不斷討討論對算算法進行行優(yōu)化，使得運運行結(jié)果果看起來來更容易易理解，也達(dá)到到了處理理機調(diào)度度的功能能。做實實驗讓我我們對于于時間片片輪轉(zhuǎn)的的思想理理解的更更加透徹徹，鞏固固了理論論知識的的學(xué)習(xí)。實驗心得得體會：首先，我們認(rèn)為這這次課程程設(shè)計是是對學(xué)習(xí)習(xí)操作作系統(tǒng)的一次次綜合考考察，鍛鍛煉我們們綜合分分析問題題、解決決問題的的能力。初次得到到課程設(shè)設(shè)計的題題目時，為程序序本身的的簡單而而竊喜過過；實驗驗過程中中也出現(xiàn)現(xiàn)了一些些難題需需要解決決，為此此去苦苦苦探索過過。課程程設(shè)計期期間，幾幾乎有幾幾天我們們完全投投入進去去了，就就像是在在做一個個相當(dāng)重重要的項項目一

14、樣樣的感覺覺。曾經(jīng)經(jīng)跑過圖圖書館幾幾次，只只是為了了一種新新的想法法得到實實現(xiàn)，也也曾多次次登錄網(wǎng)網(wǎng)站瀏覽覽網(wǎng)頁，為了彌彌補一些些知識上上的紕漏漏，為此此曾灑下下了真實實的汗水水。當(dāng)我我們的想想法得到到實現(xiàn)，又學(xué)會會了新的的知識的的時候，心中滿滿是欣喜喜，或許許這是實實踐出真真知的真真實驗證證，有付付出就有有回報的的真實寫寫照吧。其次，我我們感受受了真誠誠的友誼誼。在實實驗中，遇到的的問題是是多方面面的，而而且有那那么一部部分是以以前學(xué)過過的C問問題，但但是已經(jīng)經(jīng)忘卻或或是以前前沒有真真正的理理解過。但是你你會發(fā)現(xiàn)現(xiàn)就在你你的身邊邊，會有有那么一一批人在在背后熱熱心的幫幫助你，讓你身身處困境境

15、卻感到到無限希希望。這這好像是是人生的的一種歷歷程，風(fēng)風(fēng)風(fēng)雨雨雨中我們們一起走走過，然然后為了了一些坑坑坑洼洼洼彼此真真誠的幫幫助過和和無私的的付出過過。團隊隊的協(xié)作作和彼此此心的交交流讓我我們彼此此豐厚起起來，這這也是我我們成長長中必不不可失的的重要部部分。最后，我我認(rèn)識到到了自己己的不足足。平心心而論，以前真真的沒有有認(rèn)真的的學(xué)習(xí)過過，即使使是在聽聽課，可可是后來來卻沒有有對學(xué)習(xí)習(xí)中出現(xiàn)現(xiàn)的問題題而仔細(xì)細(xì)分析過過。得過過且過，迷失了了我前進進的方向向，而現(xiàn)現(xiàn)在卻又又重新敞敞開了。不論是是以后的的學(xué)習(xí)還還是工作作，我想想這都是是很重要要的，我我們需要要不斷進進步的動動力?？偟恼f來來知識上上的

16、收獲獲很是重重要，精精神上的的豐收也也是更加加可喜的的，讓我我知道了了學(xué)無止止境的道道理。我我們每一一個人永永遠(yuǎn)不能能滿足于于現(xiàn)有的的成就，人生就就像在爬爬山，一一座山峰峰的后面面還有更更高的山山峰在等等著你。挫折是是一份財財富，經(jīng)經(jīng)歷是一一份擁有有。這次次課程設(shè)設(shè)計必將將成為我我人生旅旅途上一一個非常常美好的的回憶。五、附錄錄實驗源程程序如下下：#inccluddesstdiio.hh#inccluddecconiio.hh#inccluddemmallloc.h#inccluddesstriing.h#deffinee NUULL 0typeedeff sttrucct PPCBchaar

17、 nnamee100; /進進程名strructt PCCB *nexxt; /鏈鏈指針intt neeed_timme; /要要求運行行時間intt woorkeed_ttimee; /已已運行時時間chaar ccondditiion; /進進程狀態(tài)態(tài)，只有有“就緒”和“結(jié)束”兩種狀狀態(tài)intt fllag; /進進程結(jié)束束標(biāo)志PCBB;PCB *frrontt,*rrearr; int N; /N為進進程數(shù)voidd crreattPCBB()/為每每個進程程創(chuàng)建一一個PCCB并初初始化形形成一個個循環(huán)鏈鏈隊列PCBB *pp,*ll;l = (PPCB *)mmallloc(sizze

18、off(PCCB);priintff(PPleaase entter proocesss nnamee annd ttimeen);scaanf(%ss%d,l-naame,&l-neeed_timme);l-conndittionn = r; /進程程初始狀狀態(tài)為就就緒l-worrkedd_tiime = 00;l-nexxt=NNULLL;l-flaag=00;froont=l;forr(innt ii = 1;ii nnamee,&pp-nneedd_tiime);p-coondiitioon = rr;p-woorkeed_ttimee = 0;p-fllag=0; l-neext =

19、 pp;l=l-nexxt;reaar=ll;reear-neext=froont;voidd ouutpuut() /進程輸輸出函數(shù)數(shù) priintff(nnamee ruuntiime neeedtiime staaten);for(intt j=1;jjnamme,ffronnt-worrkedd_tiime,froont-neeed_timme,ffronnt-conndittionn); frrontt=frrontt-nnextt;priintff(n);int juddge(PCBB *pp) /判斷所所有進程程運行結(jié)結(jié)束intt fllag = 11;forr(innt ii=0;icoondiitioon != e)fflagg = 0;bbreaak;p=p-nexxt;retturnn fllag;