時(shí)間片輪轉(zhuǎn)算法課程設(shè)計(jì)報(bào)告

1、-. z.一、實(shí)驗(yàn)?zāi)康谋菊n程設(shè)計(jì)以Windows操作系統(tǒng)為實(shí)驗(yàn)平臺(tái)，進(jìn)展源代碼分析和修改。通過(guò)該課程設(shè)計(jì)，使學(xué)生掌握Windows操作系統(tǒng)各局部構(gòu)造、實(shí)現(xiàn)機(jī)理和各種典型算法；系統(tǒng)地了解操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)思路，運(yùn)用內(nèi)核開(kāi)發(fā)環(huán)境實(shí)現(xiàn)對(duì)內(nèi)核的修改，培養(yǎng)學(xué)生的系統(tǒng)設(shè)計(jì)能力，并了解操作系統(tǒng)的開(kāi)展動(dòng)向和趨勢(shì)。二、實(shí)驗(yàn)內(nèi)容1分析設(shè)計(jì)內(nèi)容，給出解決方案要說(shuō)明設(shè)計(jì)實(shí)現(xiàn)的原理，采用的數(shù)據(jù)構(gòu)造。2畫(huà)出程序的根本構(gòu)造框圖和流程圖。3對(duì)程序的每一局部要有詳細(xì)的設(shè)計(jì)分析說(shuō)明。4源代碼格式要規(guī)*。5設(shè)計(jì)適宜的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析。6設(shè)計(jì)中遇到的問(wèn)題，設(shè)計(jì)的心得體會(huì)。7按期提交完整的程序代碼、可執(zhí)行程序和課程

2、設(shè)計(jì)報(bào)告。三、實(shí)驗(yàn)步驟1、任務(wù)分析： 時(shí)間片輪轉(zhuǎn)的主要思想就是按順序?yàn)槊恳粋€(gè)進(jìn)程一次只分配一個(gè)時(shí)間片的時(shí)間。算法要完成的功能就是將各個(gè)進(jìn)程按照時(shí)間片輪轉(zhuǎn)運(yùn)行的動(dòng)態(tài)過(guò)程顯示出來(lái)。時(shí)間片輪轉(zhuǎn)算法的主要實(shí)現(xiàn)過(guò)程是首先為每一個(gè)進(jìn)程創(chuàng)立一個(gè)進(jìn)程控制塊，定義數(shù)據(jù)構(gòu)造，說(shuō)明進(jìn)程控制塊所包含的內(nèi)容，有進(jìn)程名、進(jìn)程所需運(yùn)行時(shí)間、已運(yùn)行時(shí)間和進(jìn)程的狀態(tài)以及指針的信息。實(shí)現(xiàn)的過(guò)程即運(yùn)用指針指向*一個(gè)進(jìn)程，判斷當(dāng)前的進(jìn)程是否是就緒狀態(tài)r，如果是，則為該進(jìn)程分配一個(gè)時(shí)間片，同時(shí)，已運(yùn)行時(shí)間加一且要求運(yùn)行的時(shí)間減一，如此循環(huán)執(zhí)行，當(dāng)*一個(gè)進(jìn)程的所需要運(yùn)行的時(shí)間減少至0時(shí)，則將該進(jìn)程的狀態(tài)設(shè)置為e。然后，將指針指向下一個(gè)未

3、運(yùn)行完成的進(jìn)程，重復(fù)判斷，直至所有的進(jìn)程都運(yùn)行完畢。2、概要設(shè)計(jì)：1所用數(shù)據(jù)構(gòu)造及符號(hào)說(shuō)明typedef struct PCBchar name10; /進(jìn)程名struct PCB *ne*t; /循環(huán)鏈指針int need_time; /要求運(yùn)行時(shí)間int worked_time; /已運(yùn)行時(shí)間，初始為0char condition; /進(jìn)程狀態(tài)，只有就緒和完畢兩種狀態(tài)int flag; /進(jìn)程完畢標(biāo)志，用于輸出PCB;PCB *front,*rear; /循環(huán)鏈隊(duì)列的頭指針和尾指針int N; /N為進(jìn)程數(shù)2主程序的流程圖：進(jìn)程是否進(jìn)程是否r開(kāi)場(chǎng)輸入進(jìn)程數(shù)N輸入各進(jìn)程信息為每個(gè)進(jìn)程創(chuàng)立PC

4、B并初始化形成一個(gè)循環(huán)鏈隊(duì)列指針指向循環(huán)鏈隊(duì)列第一個(gè)進(jìn)程運(yùn)行時(shí)間+1且剩余時(shí)間-1剩余時(shí)間=0？將進(jìn)程狀態(tài)置為e完成所有進(jìn)程是否完成指針指向隊(duì)列中下個(gè)進(jìn)程完畢 Y Y N Y3程序說(shuō)明：處理器調(diào)度總是選擇指針指示的進(jìn)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)行時(shí)間+1來(lái)模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過(guò)一個(gè)單位的時(shí)間。3、詳細(xì)設(shè)計(jì)1首先每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來(lái)代表。進(jìn)程控制塊的格式為：進(jìn)程名指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)其中，進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，如Q1、Q2等。指針進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的

5、首地址，最后一個(gè)進(jìn)程的指針指出第一個(gè)進(jìn)程的進(jìn)程控制塊首地址。要求運(yùn)行時(shí)間假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。已運(yùn)行時(shí)間假設(shè)進(jìn)程已經(jīng)運(yùn)行的單位時(shí)間數(shù)，初始值為0。狀態(tài)有兩種狀態(tài)，就緒和完畢，初始狀態(tài)都為就緒，用R表示。當(dāng)一個(gè)進(jìn)程運(yùn)行完畢后，它的狀態(tài)為完畢，用E表示。2每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的要求運(yùn)行時(shí)間。把五個(gè)進(jìn)程按順序排成循環(huán)鏈隊(duì)列，用指針指出隊(duì)列連接情況。用指針表示輪到運(yùn)行的進(jìn)程，如下列圖描述所示：K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12431200000RRRRRPCB1PCB2PCB3PCB4PCB53程序詳細(xì)設(shè)計(jì)步驟：a.首先建立

6、PCB的數(shù)據(jù)構(gòu)造，為了便于正確輸出，加上了進(jìn)程完畢標(biāo)志flag。輸入進(jìn)程信息包括進(jìn)程名和要求運(yùn)行的時(shí)間，并為每個(gè)進(jìn)程創(chuàng)立一個(gè)PCB并初始化形成一個(gè)循環(huán)鏈隊(duì)列，用函數(shù)creatPCB()來(lái)實(shí)現(xiàn)。b.建立函數(shù)judge()用來(lái)判斷進(jìn)程全部運(yùn)行完畢標(biāo)志，即當(dāng)所有進(jìn)程的狀態(tài)變?yōu)閑即完成狀態(tài)后，循環(huán)完畢，表示所有進(jìn)程都已運(yùn)行成功。c.建立時(shí)間片輪轉(zhuǎn)算法creatProcess對(duì)進(jìn)程進(jìn)展輪轉(zhuǎn)運(yùn)行，首先指針s指向第一個(gè)進(jìn)程PCB，即s=front，判斷該進(jìn)程的狀態(tài)是否為r就緒狀態(tài)，即if(s-condition = r)，假設(shè)是則表示此進(jìn)程尚未執(zhí)行完畢，則執(zhí)行s-worked_time+且s-need_ti

7、me-，if(s-need_time=0)，則表示此進(jìn)程已運(yùn)行完畢，將其狀態(tài)置為完畢，即s-condition=e，并根據(jù)狀態(tài)位輸出完成信息，且以后不會(huì)再運(yùn)行此進(jìn)程。將指針指向下個(gè)進(jìn)程，s=s-ne*t，并判斷所有進(jìn)程是否已全部運(yùn)行完畢，沒(méi)有則重復(fù)上面算法。當(dāng)所有進(jìn)程的狀態(tài)位都變成e表示所有進(jìn)程運(yùn)行完成，則循環(huán)完畢。d.建立主函數(shù)main(),輸入進(jìn)程數(shù)N，調(diào)用初始化循環(huán)鏈隊(duì)列函數(shù)creatPCB()和時(shí)間片輪轉(zhuǎn)算法creatProcess(N)，每次選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化，實(shí)現(xiàn)處理器的調(diào)度。4、調(diào)試分析：a調(diào)試過(guò)程中遇到的問(wèn)題及解決方案開(kāi)場(chǎng)運(yùn)行到Q5運(yùn)行完成后顯示錯(cuò)誤，

8、如下列圖所示：原因：經(jīng)檢查程序發(fā)現(xiàn)語(yǔ)句if(s-condition=e )printf(進(jìn)程%s已經(jīng)運(yùn)行完成！nn,s-name);有錯(cuò)誤，因?yàn)楫?dāng)*個(gè)進(jìn)程運(yùn)行完成后，其狀態(tài)標(biāo)志已修改為e，所以再次循環(huán)運(yùn)行未完成的進(jìn)程時(shí)，當(dāng)運(yùn)行到此句時(shí)仍會(huì)將前面已完成的進(jìn)程重新輸出一遍完成信息，導(dǎo)致輸出錯(cuò)誤。解決方案：為每個(gè)進(jìn)程加上一個(gè)完畢標(biāo)志flag，并賦初值為0，當(dāng)進(jìn)程運(yùn)行完成后，將flag改為1，再將后面輸出改為if(s-condition=e | s-flag=0 )printf(進(jìn)程%s已經(jīng)運(yùn)行完成！nn,s-name);s-flag=0;，這樣在前面進(jìn)程運(yùn)行完成輸出后，后面再循環(huán)時(shí)就不會(huì)重新輸出一遍

9、了。b改良設(shè)想：本實(shí)驗(yàn)較簡(jiǎn)單，但還不夠完善，如未實(shí)現(xiàn)插入進(jìn)程功能，即進(jìn)程在運(yùn)行過(guò)程中可以插入其他的進(jìn)程再運(yùn)行。還有未進(jìn)展進(jìn)程優(yōu)先級(jí)判別，本實(shí)驗(yàn)?zāi)J(rèn)進(jìn)程的優(yōu)先級(jí)按輸入的先后順序從大到小排列的，還有其他功能等，希望在以后的實(shí)驗(yàn)中逐步完善。5、測(cè)試結(jié)果：a首先輸出五個(gè)進(jìn)程的初始狀態(tài)b開(kāi)場(chǎng)從進(jìn)程Q1開(kāi)場(chǎng)按時(shí)間片輪轉(zhuǎn)運(yùn)行進(jìn)程，Q4先運(yùn)行完成c.接著Q1運(yùn)行完成d.接著Q5運(yùn)行完成e.再Q(mào)3運(yùn)行完成f.最后Q2運(yùn)行完成四、實(shí)驗(yàn)總結(jié)因在早期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按照先來(lái)先效勞的原則排成一個(gè)隊(duì)列，每次調(diào)度是，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序停頓該進(jìn)程

10、的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響。如果選擇很小的時(shí)間片將有利于短作業(yè)，因?yàn)樗茌^快地完成，但會(huì)頻繁的發(fā)生中斷、進(jìn)程上下文的切換，從而增加系統(tǒng)的開(kāi)銷；反之，如果選擇太長(zhǎng)時(shí)間片，使得每個(gè)進(jìn)程都能在一個(gè)時(shí)間片內(nèi)完成，所以，一般定為時(shí)間片略大于一次典型地交互所需要的時(shí)間。在完成時(shí)間片輪轉(zhuǎn)算法的實(shí)現(xiàn)過(guò)程中，我們遇到了一些問(wèn)題，比方怎樣運(yùn)用循環(huán)隊(duì)列，如何設(shè)計(jì)構(gòu)造體等等，也積極配合并思考進(jìn)展解決。整體來(lái)說(shuō)，我們的算法雖然實(shí)現(xiàn)了表達(dá)進(jìn)程動(dòng)態(tài)運(yùn)行變化的過(guò)程，但是相對(duì)而言比擬簡(jiǎn)單。實(shí)驗(yàn)中

11、，我們小組不斷討論對(duì)算法進(jìn)展優(yōu)化，使得運(yùn)行結(jié)果看起來(lái)更容易理解，也到達(dá)了處理機(jī)調(diào)度的功能。做實(shí)驗(yàn)讓我們對(duì)于時(shí)間片輪轉(zhuǎn)的思想理解的更加透徹，穩(wěn)固了理論知識(shí)的學(xué)習(xí)。實(shí)驗(yàn)心得體會(huì)：首先，我們認(rèn)為這次課程設(shè)計(jì)是對(duì)學(xué)習(xí)操作系統(tǒng)的一次綜合考察，鍛煉我們綜合分析問(wèn)題、解決問(wèn)題的能力。初次得到課程設(shè)計(jì)的題目時(shí)，為程序本身的簡(jiǎn)單而竊喜過(guò)；實(shí)驗(yàn)過(guò)程中也出現(xiàn)了一些難題需要解決，為此去苦苦探索過(guò)。課程設(shè)計(jì)期間，幾乎有幾天我們完全投入進(jìn)去了，就像是在做一個(gè)相當(dāng)重要的工程一樣的感覺(jué)。曾經(jīng)跑過(guò)圖書(shū)館幾次，只是為了一種新的想法得到實(shí)現(xiàn)，也曾屢次登錄瀏覽網(wǎng)頁(yè)，為了彌補(bǔ)一些知識(shí)上的紕漏，為此曾灑下了真實(shí)的汗水。當(dāng)我們的想法得到實(shí)

12、現(xiàn)，又學(xué)會(huì)了新的知識(shí)的時(shí)候，心中滿是欣喜，或許這是實(shí)踐出真知的真實(shí)驗(yàn)證，有付出就有回報(bào)的真實(shí)寫(xiě)照吧。其次，我們感受了真誠(chéng)的友誼。在實(shí)驗(yàn)中，遇到的問(wèn)題是多方面的，而且有則一局部是以前學(xué)過(guò)的C問(wèn)題，但是已經(jīng)忘卻或是以前沒(méi)有真正的理解過(guò)。但是你會(huì)發(fā)現(xiàn)就在你的身邊，會(huì)有則一批人在背后熱心的幫助你，讓你身處困境卻感到無(wú)限希望。這好似是人生的一種歷程，風(fēng)風(fēng)雨雨中我們一起走過(guò)，然后為了一些坑坑洼洼彼此真誠(chéng)的幫助過(guò)和無(wú)私的付出過(guò)。團(tuán)隊(duì)的協(xié)作和彼此心的交流讓我們彼此豐厚起來(lái)，這也是我們成長(zhǎng)中必不可失的重要局部。最后，我認(rèn)識(shí)到了自己的缺乏。平心而論，以前真的沒(méi)有認(rèn)真的學(xué)習(xí)過(guò)，即使是在聽(tīng)課，可是后來(lái)卻沒(méi)有對(duì)學(xué)習(xí)中出

13、現(xiàn)的問(wèn)題而仔細(xì)分析過(guò)。得過(guò)且過(guò)，迷失了我前進(jìn)的方向，而現(xiàn)在卻又重新敞開(kāi)了。不管是以后的學(xué)習(xí)還是工作，我想這都是很重要的，我們需要不斷進(jìn)步的動(dòng)力?？偟恼f(shuō)來(lái)知識(shí)上的收獲很是重要，精神上的豐收也是更加可喜的，讓我知道了學(xué)無(wú)止境的道理。我們每一個(gè)人永遠(yuǎn)不能滿足于現(xiàn)有的成就，人生就像在爬山，一座山峰的后面還有更高的山峰在等著你。挫折是一份財(cái)富，經(jīng)歷是一份擁有。這次課程設(shè)計(jì)必將成為我人生旅途上一個(gè)非常美好的回憶。五、源程序?qū)嶒?yàn)源程序如下：#includestdio.h#includeconio.h#includemalloc.h#includestring.h#define NULL 0typedef s

14、truct PCBchar name10; /進(jìn)程名struct PCB *ne*t; /鏈指針int need_time; /要求運(yùn)行時(shí)間int worked_time; /已運(yùn)行時(shí)間char condition; /進(jìn)程狀態(tài)，只有就緒和完畢兩種狀態(tài)int flag; /進(jìn)程完畢標(biāo)志PCB;PCB *front,*rear; int N; /N為進(jìn)程數(shù)void creatPCB() /為每個(gè)進(jìn)程創(chuàng)立一個(gè)PCB并初始化形成一個(gè)循環(huán)鏈隊(duì)列PCB *p,*l;l = (PCB *)malloc(sizeof(PCB);printf(請(qǐng)輸入各進(jìn)程名和要求運(yùn)行時(shí)間n);scanf(%s%d,l-nam

15、e,&l-need_time);l-condition = r; /進(jìn)程初始狀態(tài)為就緒l-worked_time = 0;l-ne*t=NULL;l-flag=0;front=l;for(int i = 1;i name,&p-need_time);p-condition = r; p-worked_time = 0;p-flag=0; l-ne*t = p;l=l-ne*t;rear=l;rear-ne*t=front;void output() /進(jìn)程輸出函數(shù) printf(進(jìn)程名 已運(yùn)行時(shí)間 需要時(shí)間 狀態(tài)n);for(int j=1;jname, front-worked_time,

16、front-need_time, front-condition); front=front-ne*t;printf(n);int judge(PCB *p) /判斷所有進(jìn)程運(yùn)行完畢int flag = 1;for(int i=0;icondition != e)flag = 0;break;p=p-ne*t;return flag;void creatProcess(int n) /時(shí)間片輪轉(zhuǎn)算法PCB *s,*p;int i,j,flag1=0;s = (PCB *)malloc(sizeof(PCB);s=front;printf(n-n);output();printf(請(qǐng)按任意鍵繼續(xù)nn); getch(); /按任意鍵繼續(xù)s=front;while(flag1 != 1)if(s-condition = r)s-worked_