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

一、實(shí)驗(yàn)?zāi)康模?）在單辦理器狀況下準(zhǔn)時(shí)間片輪轉(zhuǎn)算法實(shí)現(xiàn)辦理器調(diào)動(dòng)，輸出運(yùn)轉(zhuǎn)動(dòng)向變化過程。（2）經(jīng)過算法的實(shí)現(xiàn)加深認(rèn)識(shí)辦理器調(diào)動(dòng)的工作。二、實(shí)驗(yàn)內(nèi)容輸入實(shí)現(xiàn)辦理器調(diào)動(dòng)的幾個(gè)進(jìn)度信息，隨意確立一組“要求運(yùn)轉(zhuǎn)時(shí)間”，啟動(dòng)所設(shè)計(jì)的辦理器調(diào)動(dòng)程序，顯示逐次被選中進(jìn)度的進(jìn)度名以及進(jìn)度控制塊的動(dòng)向變化過程。三、實(shí)驗(yàn)步驟1、任務(wù)剖析：時(shí)間片輪轉(zhuǎn)的主要思想就是按次序?yàn)槊恳粋€(gè)進(jìn)度一次只分派一個(gè)時(shí)間片的時(shí)間。算法要達(dá)成的功能就是將各個(gè)進(jìn)度依據(jù)時(shí)間片輪轉(zhuǎn)運(yùn)轉(zhuǎn)的動(dòng)向過程顯示出來。時(shí)間片輪轉(zhuǎn)算法的主要實(shí)現(xiàn)過程是第一為每一個(gè)進(jìn)度創(chuàng)立一個(gè)進(jìn)度控制塊，定義數(shù)據(jù)構(gòu)造，說明進(jìn)度控制塊所包含的內(nèi)容，有進(jìn)度名、進(jìn)度所需運(yùn)轉(zhuǎn)時(shí)間、已運(yùn)轉(zhuǎn)時(shí)間和進(jìn)度的狀態(tài)以及指針的信息。實(shí)現(xiàn)的過程即運(yùn)用指針指向某一個(gè)進(jìn)度，判斷目前的進(jìn)度是不是就緒狀態(tài)“r”，假如是，則為該進(jìn)度分派一個(gè)時(shí)間片，同時(shí)，已運(yùn)轉(zhuǎn)時(shí)間加一且要求運(yùn)轉(zhuǎn)的時(shí)間減一，這樣循環(huán)履行，當(dāng)某一個(gè)進(jìn)度的所需要運(yùn)轉(zhuǎn)的時(shí)間減少至0時(shí)，則將該進(jìn)度的狀態(tài)設(shè)置為“e”。而后，將指針指向下一個(gè)未運(yùn)轉(zhuǎn)達(dá)成的進(jìn)度，重復(fù)判斷，直至所有的進(jìn)度都運(yùn)轉(zhuǎn)結(jié)束。2、綱要設(shè)計(jì)：（1）所用數(shù)據(jù)構(gòu)造及符號(hào)說明typedefstructPCB{charname[10];//進(jìn)度名structPCB*next;//循環(huán)鏈指針intneed_time;//要求運(yùn)轉(zhuǎn)時(shí)間intworked_time;//已運(yùn)轉(zhuǎn)時(shí)間，初始為0charcondition;//進(jìn)度狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)intflag;//進(jìn)度結(jié)束標(biāo)記，用于輸出}PCB;PCB*front,*rear;//循環(huán)鏈行列的頭指針和尾指針intN;//N為進(jìn)度數(shù)（2）主程序的流程圖：開始輸入進(jìn)度數(shù)N輸入各進(jìn)度信息為每個(gè)進(jìn)度創(chuàng)立PCB并初始化形成一個(gè)循環(huán)鏈行列指針指向循環(huán)鏈隊(duì)Y列第一個(gè)進(jìn)度進(jìn)度能否’r’運(yùn)轉(zhuǎn)時(shí)間+1且節(jié)余時(shí)間-1Y節(jié)余時(shí)間=0？將進(jìn)度狀態(tài)置為’e’（達(dá)成）指針指向行列中下個(gè)進(jìn)度N所有進(jìn)度能否達(dá)成Y（3）程序說明：辦理器調(diào)動(dòng)老是選擇結(jié)指束針指示的進(jìn)度運(yùn)轉(zhuǎn)。因?yàn)楸緦?shí)驗(yàn)是模擬辦理器調(diào)動(dòng)的功能，因此，對(duì)被選中的進(jìn)度其實(shí)不實(shí)質(zhì)的啟動(dòng)運(yùn)轉(zhuǎn)，而是履行：已運(yùn)轉(zhuǎn)時(shí)間+1來模擬進(jìn)度的一次運(yùn)轉(zhuǎn)，表示進(jìn)度已經(jīng)運(yùn)轉(zhuǎn)過一個(gè)單位的時(shí)間。3、詳盡設(shè)計(jì)（1）第一每一個(gè)進(jìn)度用一個(gè)進(jìn)度控制塊PCB來代表。進(jìn)度控制塊的格式為：進(jìn)度名指針要求運(yùn)轉(zhuǎn)時(shí)間已運(yùn)轉(zhuǎn)時(shí)間狀態(tài)此中，進(jìn)度名——作為進(jìn)度的表記，如Q1、Q2等。指針——進(jìn)度按次序排成循環(huán)鏈行列，用指針指出下一個(gè)進(jìn)度的進(jìn)度控制塊的首地點(diǎn)，最后一個(gè)進(jìn)度的指針指出第一個(gè)進(jìn)度的進(jìn)度控制塊首地點(diǎn)。要求運(yùn)轉(zhuǎn)時(shí)間——假定進(jìn)度需要運(yùn)轉(zhuǎn)的單位時(shí)間數(shù)。已運(yùn)轉(zhuǎn)時(shí)間——假定進(jìn)度已經(jīng)運(yùn)轉(zhuǎn)的單位時(shí)間數(shù)，初始值為“0”。狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個(gè)進(jìn)度運(yùn)轉(zhuǎn)結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。（2）每次運(yùn)轉(zhuǎn)所設(shè)計(jì)的辦理器調(diào)動(dòng)程序前，為每個(gè)進(jìn)度隨意確立它的“要求運(yùn)轉(zhuǎn)時(shí)間”。把五個(gè)進(jìn)度按次序排成循環(huán)鏈行列，用指針指出行列連結(jié)狀況。用指針表示輪到運(yùn)轉(zhuǎn)的進(jìn)度，以下列圖描繪所示：K1

Q1

K2

Q2

K3

Q3

K4

Q4

K5

Q5K2

K3

K4

K5

K12

4

3

1

20

0

0

0

0R

R

R

R

RPCB1PCB2PCB3PCB4PCB5（3）程序詳盡設(shè)計(jì)步驟：a.第一成立PCB的數(shù)據(jù)構(gòu)造，為了便于正確輸出，加上了進(jìn)度結(jié)束標(biāo)記flag。輸入進(jìn)程信息（包含進(jìn)度名和要求運(yùn)轉(zhuǎn)的時(shí)間），并為每個(gè)進(jìn)度創(chuàng)立一個(gè)PCB并初始化形成一個(gè)循環(huán)鏈行列，用函數(shù)

creatPCB( )

來實(shí)現(xiàn)。b.成立函數(shù)

judge( )

用來判斷進(jìn)度所有運(yùn)轉(zhuǎn)結(jié)束標(biāo)記，即當(dāng)所有進(jìn)度的狀態(tài)變成’

e’（即達(dá)成狀態(tài)）后，循環(huán)結(jié)束，表示所有進(jìn)度都已運(yùn)轉(zhuǎn)成功。c.成即刻間片輪轉(zhuǎn)算法creatProcess（）對(duì)進(jìn)度進(jìn)行輪轉(zhuǎn)運(yùn)轉(zhuǎn)，第一指針s指向第一個(gè)進(jìn)度PCB，即s=front，判斷該進(jìn)度的狀態(tài)能否為’r’（就緒狀態(tài)），即if(s->condition=='r')，假如則表示此進(jìn)度還沒有履行結(jié)束，則履行s->worked_time++且s->need_time--if(s->need_time==0)，則表示此進(jìn)度已運(yùn)轉(zhuǎn)結(jié)束，將其狀態(tài)置為結(jié)束，即s->condition='e'并依據(jù)狀態(tài)位輸出達(dá)成信息，且此后不會(huì)再運(yùn)轉(zhuǎn)此進(jìn)度。將指針指向下個(gè)進(jìn)度，s=s->next并判斷所有進(jìn)度能否已所有運(yùn)轉(zhuǎn)結(jié)束，沒有則重復(fù)上邊算法。當(dāng)所有進(jìn)度的狀態(tài)位都變成’e’表示所有進(jìn)度運(yùn)轉(zhuǎn)達(dá)成，則循環(huán)結(jié)束。

，，，d.成立主函數(shù)main( ),輸入進(jìn)度數(shù)N，調(diào)用初始化循環(huán)鏈行列函數(shù)creatPCB( )和時(shí)間片輪轉(zhuǎn)算法creatProcess(N)，每次選中進(jìn)度的進(jìn)度名以及運(yùn)轉(zhuǎn)一次后進(jìn)度行列的變化，實(shí)現(xiàn)辦理器的調(diào)動(dòng)。4、調(diào)試剖析：a．調(diào)試過程中碰到的問題及解決方案開始運(yùn)轉(zhuǎn)到Q5運(yùn)轉(zhuǎn)達(dá)成后顯示錯(cuò)誤，以下列圖所示：原由：經(jīng)檢查程序發(fā)現(xiàn)語句if(s->condition=='e'){printf("進(jìn)度%s已經(jīng)運(yùn)轉(zhuǎn)達(dá)成！\n\n",s->name);}有錯(cuò)誤，因?yàn)楫?dāng)某個(gè)進(jìn)度運(yùn)轉(zhuǎn)達(dá)成后，其狀態(tài)標(biāo)記已改正為’e’，因此再次循環(huán)運(yùn)轉(zhuǎn)未達(dá)成的進(jìn)度時(shí)，當(dāng)運(yùn)轉(zhuǎn)到此句時(shí)仍會(huì)將前面已達(dá)成的進(jìn)度從頭輸出一遍達(dá)成信息，致使輸犯錯(cuò)誤。flag

解決方案：為每個(gè)進(jìn)度加上一個(gè)結(jié)束標(biāo)記flag，并賦初值為0，當(dāng)進(jìn)度運(yùn)轉(zhuǎn)達(dá)成后，將改為1，再將后邊輸出改為if(s->condition=='e'||s->flag==0){printf("進(jìn)度%s已經(jīng)運(yùn)轉(zhuǎn)達(dá)成！\n\n",s->name);s->flag==0;}循環(huán)時(shí)就不會(huì)從頭輸出一遍了。

，這樣在前面進(jìn)度運(yùn)轉(zhuǎn)達(dá)成輸出后，后邊再b．改良假想：本實(shí)驗(yàn)較簡單，但還不夠完美，如未實(shí)現(xiàn)插入進(jìn)度功能，即進(jìn)度在運(yùn)轉(zhuǎn)過程中能夠插入其余的進(jìn)度再運(yùn)轉(zhuǎ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．開始從進(jìn)度Q1開始準(zhǔn)時(shí)間片輪轉(zhuǎn)運(yùn)轉(zhuǎn)進(jìn)度，Q4先運(yùn)轉(zhuǎn)達(dá)成c.接著Q1運(yùn)轉(zhuǎn)達(dá)成d.接著Q5運(yùn)轉(zhuǎn)達(dá)成e.再Q(mào)3運(yùn)轉(zhuǎn)達(dá)成最后Q2運(yùn)轉(zhuǎn)達(dá)成四、實(shí)驗(yàn)總結(jié)因在初期的時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)度依據(jù)先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)動(dòng)是，把CPU分派給隊(duì)首進(jìn)度，并令其履行一個(gè)時(shí)間片。當(dāng)履行的時(shí)間片用完時(shí)，調(diào)動(dòng)程序停止該進(jìn)度的履行，并將它送往就緒行列的末端；而后，再把辦理機(jī)分派給就緒隊(duì)列中新的隊(duì)首進(jìn)度，同時(shí)也讓它履行一個(gè)時(shí)間片。在時(shí)間片輪轉(zhuǎn)算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響。假如選擇很小的時(shí)間片將有益于短作業(yè)，因?yàn)樗茌^快地達(dá)成，但會(huì)屢次的發(fā)生中止、進(jìn)度上下文的切換，進(jìn)而增添系統(tǒng)的開支；反之，假如選擇太長時(shí)間片，使得每個(gè)進(jìn)度都能在一個(gè)時(shí)間片內(nèi)達(dá)成，因此，一般定為時(shí)間片略大于一次典型地交互所需要的時(shí)間。在達(dá)成時(shí)間片輪轉(zhuǎn)算法的實(shí)現(xiàn)過程中，我們碰到了一些問題，比方如何運(yùn)用循環(huán)行列，如何設(shè)計(jì)構(gòu)造體等等，也踴躍配歸并思慮進(jìn)行解決。整體來說，我們的算法固然實(shí)現(xiàn)了表現(xiàn)進(jìn)度動(dòng)向運(yùn)轉(zhuǎn)變化的過程，但是相對(duì)而言比較簡單。實(shí)驗(yàn)中，我們小組不停議論對(duì)算法進(jìn)行優(yōu)化，使得運(yùn)轉(zhuǎn)結(jié)果看起來更簡單理解，也達(dá)到了辦理機(jī)調(diào)動(dòng)的功能。做實(shí)驗(yàn)讓我們關(guān)于時(shí)間片輪轉(zhuǎn)的思想理解的更為透辟，穩(wěn)固了理論知識(shí)的學(xué)習(xí)。實(shí)驗(yàn)心得領(lǐng)會(huì)：第一，我們以為此次課程設(shè)計(jì)是對(duì)學(xué)習(xí)《操作系統(tǒng)》的一次綜合觀察，鍛煉我們綜合剖析問題、解決問題的能力。首次獲得課程設(shè)計(jì)的題目時(shí)，為程序自己的簡單而竊喜過；實(shí)驗(yàn)過程中也出現(xiàn)了一些難題需要解決，為此去苦苦探究過。課程設(shè)計(jì)時(shí)期，幾乎有幾日我們完整投入進(jìn)去了，就像是在做一個(gè)相當(dāng)重要的項(xiàng)目同樣的感覺。以前跑過圖書室?guī)状危贿^為了一種新的想法獲得實(shí)現(xiàn)，也曾多次登錄網(wǎng)站閱讀網(wǎng)頁，為了填補(bǔ)一些知識(shí)上的疏漏，為此曾灑下了真切的汗水。當(dāng)我們的想法獲得實(shí)現(xiàn)，又學(xué)會(huì)了新的知識(shí)的時(shí)候，心中盡是驚喜，也許這是實(shí)踐出真知的真切考證，有付出就有回報(bào)的真切寫照吧。其次，我們感覺了真摯的友情。在實(shí)驗(yàn)中，碰到的問題是多方面的，并且有那么一部分是從前學(xué)過的C問題，但是已經(jīng)忘掉或是從前沒有真切的理解過。但是你會(huì)發(fā)現(xiàn)就在你的身旁，會(huì)有那么一批人在背后熱情的幫助你，讓你身處窘境卻感覺無窮希望。這仿佛是人生的一種歷程，風(fēng)風(fēng)雨雨中我們一同走過，而后為了一些坑坑洼洼相互真摯的幫助過和無私的付出過。團(tuán)隊(duì)的協(xié)作和相互心的溝通讓我們相互豐厚起來，這也是我們成長中必不行失的重要部分。最后，我認(rèn)識(shí)到了自己的不足。平心而談，從前真的沒有認(rèn)真的學(xué)習(xí)過，即便是在聽課，但是此后卻沒有對(duì)學(xué)習(xí)中出現(xiàn)的問題而認(rèn)真剖析過。茍且偷生，迷失了我行進(jìn)的方向，而現(xiàn)在卻又從頭敞開了。無論是此后的學(xué)習(xí)仍是工作，我想這都是很重要的，我們需要不停進(jìn)步的動(dòng)力?？偟恼f來知識(shí)上的收獲特別重要，精神上的豐產(chǎn)也是更為可喜的，讓我知道了學(xué)無止境的道理。我們每個(gè)人永久不可以知足于現(xiàn)有的成就，人生就像在登山，一座山岳的后邊還有更高的山岳在等著你。挫折是一份財(cái)產(chǎn)，經(jīng)歷是一份擁有。此次課程設(shè)計(jì)勢(shì)必成為我人生旅途上一個(gè)特別美好的回想。五、附錄實(shí)驗(yàn)源程序以下：#include"stdio.h"#include"conio.h"#include"malloc.h"#include"string.h"#defineNULL0typedefstructPCB{charname[10];//進(jìn)度名structPCB*next;//鏈指針intneed_time;//要求運(yùn)轉(zhuǎn)時(shí)間intworked_time;//已運(yùn)轉(zhuǎn)時(shí)間charcondition;//進(jìn)度狀態(tài)，只有“就緒”和“結(jié)束”兩種狀態(tài)intflag;//進(jìn)度結(jié)束標(biāo)記}PCB;PCB*front,*rear;intN;//N為進(jìn)度數(shù)voidcreatPCB( ){//為每個(gè)進(jìn)度創(chuàng)立一個(gè)PCB并初始化形成一個(gè)循環(huán)鏈行列PCB*p,*l;l=(PCB*)malloc(sizeof(PCB));printf("Pleaseenterprocessnameandtime\n");scanf("%s%d",l->name,&l->need_time);l->condition='r';//進(jìn)度初始狀態(tài)為就緒l->worked_time=0;l->next=NULL;l->flag=0;front=l;for(inti=1;i<N;i++){p=(PCB*)malloc(sizeof(PCB));scanf("%s%d",p->name,&p->need_time);p->condition='r';p->worked_time=0;p->flag=0;l->next=p;l=l->next;}rear=l;rear->next=front;}voidoutput( ){//進(jìn)度輸出函數(shù)printf("nameruntimeneedtimestate\n");for(intj=1;j<=N;j++){printf("%-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front->condition);front=front->next;}printf("\n");}intjudge(PCB*p){//判斷所有進(jìn)度運(yùn)轉(zhuǎn)結(jié)束intflag=1;for(inti=0;i<N;i++){if(p->condition!='e'){flag=0;break;}p=p->next;}returnflag;}voidcreatProcess(intn){//時(shí)間片輪轉(zhuǎn)算法PCB*s,*p;inti,j,flag1=0;s=(PCB*)malloc(sizeof(PCB));s=front;printf("\n--------------------------------------------\n");output( );printf("Pressanykeytocontinue...\n\n");getch( );//按隨意鍵持續(xù)s=front;while(flag1!=1){if(s->condition=='r'){s->worked_time++;s->need_time--;if(s->need_time==0)s->condition='e';output( );printf("Pressanykeytocontinue...\n\