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

《操作系統(tǒng)A》課程綜合性實(shí)驗(yàn)報(bào)告開課實(shí)驗(yàn)室：基礎(chǔ)七 2011年5月29日實(shí)驗(yàn)題目| 進(jìn)程調(diào)度算法程序設(shè)計(jì)一、 實(shí)驗(yàn)?zāi)康耐ㄟ^對(duì)進(jìn)程調(diào)度算法的模擬，進(jìn)一步理解進(jìn)程的基本概念，加深對(duì)進(jìn)程運(yùn)行狀態(tài)和進(jìn)程調(diào)度過程、調(diào)度算法的理解。二、 設(shè)備與環(huán)境硬件設(shè)備：PC機(jī)一臺(tái)軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關(guān)的程序開發(fā)環(huán)境，如C\C++\Java等編程語言環(huán)境。三、 實(shí)驗(yàn)內(nèi)容（1） 用C語言（或其它語言，如Java）實(shí)現(xiàn)對(duì)N個(gè)進(jìn)程采用某種進(jìn)程調(diào)度算法（如動(dòng)態(tài)優(yōu)先權(quán)調(diào)度）的調(diào)度。（2） 每個(gè)用來標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊PCB可用結(jié)構(gòu)來描述，包括以下字段：進(jìn)程標(biāo)識(shí)數(shù)ID。進(jìn)程優(yōu)先數(shù)PRIORITY，并規(guī)定優(yōu)先數(shù)越大的進(jìn)程，其優(yōu)先權(quán)越高。進(jìn)程已占用CPU時(shí)間CPUTIME。進(jìn)程還需占用的CPU時(shí)間ALLTIME。當(dāng)進(jìn)程運(yùn)行完畢時(shí)，ALLTIME變?yōu)?。進(jìn)程的阻塞時(shí)間STARTBLOCK ，表示當(dāng)進(jìn)程再運(yùn)行STARTBLOCK 個(gè)時(shí)間片后，進(jìn)程將進(jìn)入阻塞狀態(tài)。進(jìn)程被阻塞的時(shí)間BLOCKTIME，表示已阻塞的進(jìn)程再等待BLOCKTIME 個(gè)時(shí)間片后，將轉(zhuǎn)換成就緒狀態(tài)。進(jìn)程狀態(tài)STATE。隊(duì)列指針NEXT，用來將PCB排成隊(duì)列。（3） 優(yōu)先數(shù)改變的原則：進(jìn)程在就緒隊(duì)列中呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1。進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減3。（4） 為了清楚地觀察每個(gè)進(jìn)程的調(diào)度過程，程序應(yīng)將每個(gè)時(shí)間片內(nèi)的進(jìn)程的情況顯示出來，包括正在運(yùn)行的進(jìn)程，處于就緒隊(duì)列中的進(jìn)程和處于阻塞隊(duì)列中的進(jìn)程。（5） 分析程序運(yùn)行的結(jié)果，談一下自己的認(rèn)識(shí)。四、實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)設(shè)計(jì)說明用時(shí)間片輪轉(zhuǎn)算法模擬單處理機(jī)調(diào)度。（1） 建立一個(gè)進(jìn)程控制塊PCB來代表。PCB包括：進(jìn)程名、到達(dá)時(shí)間、運(yùn)行時(shí)間和進(jìn)程后的狀態(tài)。進(jìn)程狀態(tài)分為就緒（R）和刪除（C）。（2） 為每個(gè)進(jìn)程任意確定一個(gè)要求運(yùn)行時(shí)間和到達(dá)時(shí)間。（3） 按照進(jìn)程到達(dá)的先后順序排成一個(gè)隊(duì)列。再設(shè)一個(gè)指針指向隊(duì)首和隊(duì)尾。（4） 執(zhí)行處理機(jī)調(diào)度時(shí)，開始選擇對(duì)首的第一個(gè)進(jìn)程運(yùn)行。（5） 執(zhí)行：a）輸出當(dāng)前運(yùn)行進(jìn)程的名字；b）運(yùn)行時(shí)間減去時(shí)間片的大小。（6） 進(jìn)程執(zhí)行一次后，若該進(jìn)程的剩余運(yùn)行時(shí)間為零，則刪除隊(duì)首，并將該進(jìn)程的狀態(tài)置為C；若不為空，則將向后找位置插入。繼續(xù)在運(yùn)行隊(duì)首的進(jìn)程。（7） 若進(jìn)程隊(duì)列不空，則重復(fù)上述的（5）和（6）步驟直到所有進(jìn)程都運(yùn)行完為止。在所設(shè)計(jì)的調(diào)度程序中，要求包含顯示或打印語句。以便顯示或打印每次選中進(jìn)程的名稱及運(yùn)行一次后隊(duì)列的變化情況。實(shí)驗(yàn)代碼/****************沏寸間片輪轉(zhuǎn)調(diào)度算法*******************/#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct?定義進(jìn)程控制塊{charpname[5];/進(jìn)程名intarrivetim（/到達(dá)時(shí)間intruntime;/運(yùn)行時(shí)間charstate; /運(yùn)行后的狀態(tài)structpcb*next;}PCB;typedefstruck裝頭結(jié)點(diǎn)，指針分別指向隊(duì)頭和隊(duì)尾{PCB*front,*rear;}queue;queue*init（進(jìn)程隊(duì)列置空{(diào)queue*head;head=（queue*）malloc（sizeof（queue））;head->front=NULL;head->rear=NULL;returnhead;}intempty(queue*head檢驗(yàn)進(jìn)程隊(duì)列是否為空{(diào)return(head->front?0:1);}queue*append(queue*head,charc[5],inta,int進(jìn)^程隊(duì)列入隊(duì)/往后插入{PCB*p;p=(PCB*)malloc(sizeof(PCB));strcpy(p->pname,c);p->arrivetime=a;p->runtime=r;p->state=s;p->next=NULL;if(empty(head))head->front=head->rear=p;else{head->rear->next=p;head->rear=p;}returnhead;}queue*creat(queue*hea創(chuàng)建進(jìn)程隊(duì)列{charc[5];chars='R';inta,r,i,n;printf請(qǐng)輸入進(jìn)程的數(shù)量:")；scanf("%d”,&n);for(i=1;i<=n;i++){ printf請(qǐng)輸入第%d個(gè)進(jìn)程的進(jìn)程名:〃，i);getchar();gets(c);printf(f輸入第%d個(gè)進(jìn)程的到達(dá)時(shí)間:〃，i);scanf("%d”,&a);printf請(qǐng)輸入第%d個(gè)進(jìn)程的服務(wù)時(shí)間:〃，i);scanf("%d”,&r);head=append(head,c,a,r,s);}returnhead;}voidprint(queue*hea輸出創(chuàng)J建的進(jìn)程隊(duì)列{PCB*p;p=head->front;if(!p)printf("間片輪轉(zhuǎn)調(diào)度隊(duì)列為空!\n”);while(p){printf("pname=%s arrivetime=%d runtime=%dstate=%c",p->pname,p->arrivetime,p->runtime,p->state);printf(〃\n〃)；p=p->next;}}voidRR(queue*head,int時(shí)間片輪轉(zhuǎn)調(diào)度算法的實(shí)現(xiàn){intt=head-〉front-〉arrivetime,lt=head-〉rear-〉arrivetime;if(head->front->runtime<q=t+head->front->runtime;elset=t+q;while(!empty(head)進(jìn)程隊(duì)列不為空才可調(diào)度{PCB*p1,*p2;printf("遠(yuǎn)行的時(shí)刻運(yùn)行的進(jìn)程運(yùn)行后的狀態(tài)\n");while(t<lt第一種情況:當(dāng)前運(yùn)行的時(shí)間小于最后一個(gè)進(jìn)程到達(dá)的時(shí)間做以下操作{p1=head->front;printf("%2d %s”,t,p1->pname);p1->runtime=p1->runtime-q;if(p1->runtime<=0)運(yùn)行時(shí)間小于0，刪除隊(duì)首{p1->state='C';printf("%c\n”,p1->state);head->front=p1->next;free(p1);}else/運(yùn).行時(shí)間大于0，向后找位置插入{printf("%c\n”,p1->state);p2=p1->next;while(p2->next&&p2->arrivetime!=t){ p2=p2->next;}/此時(shí)無新進(jìn)入隊(duì)列的進(jìn)程時(shí)，有兩種情況：1不用找位置往后插入，隊(duì)首不變，不做操作2.找位置往后插入if(p2->arrivetime!=t){PCB*p3=p1,*p4;while(p3->next&&p3->arrivetime<t){ p4=p3;p3=p3->next;}if(p3->arrivetime>t){ if(p4!=p1)/插在p4后，頭為p1->next{head->front=p1->next;p1->next=p4->next;p4->next=p1;}else不|故操作p4=p3=p2=NULL;}elsep4=p3=p2=NULL;}/此時(shí)有新進(jìn)入隊(duì)列的進(jìn)程時(shí):P1插在新進(jìn)入隊(duì)列的進(jìn)程P2后，隊(duì)首為p1->nextelse{head->front=p1->next;p1->next=p2->next;p2->next=p1;}}if(head->front->runtime<0J^燎化t=t+head->front->runtime;elset=t+q;}while(t>=lt第二種情況：當(dāng)前運(yùn)行的時(shí)間大于最后一個(gè)進(jìn)程到達(dá)的時(shí)間做以下操作{p1=head->front;printf("%2d %s”,t,p1->pname);p1->runtime=p1->runtime-q;if(p1->runtime<=0)運(yùn)行時(shí)間小于0，刪除隊(duì)首{p1->state='C';printf("%c\n”,p1->state);head->front=p1->next;free(p1);}else/運(yùn)行時(shí)間大于0，直接插在隊(duì)尾{printf("%c\n”,p1->state);if(!p1->next若原隊(duì)列只有一個(gè)進(jìn)程，不必往隊(duì)尾插head->front=p1;else若原隊(duì)列有多個(gè)進(jìn)程{head->front=p1->next;head->rear->next=p1;head->rear=p1;p1->next=NULL;}}if(empty(head))/時(shí)刻變化，隊(duì)列為空時(shí)不做時(shí)刻變化return;else{if(head->front->runtime<q=t+head->front->runtime;elset=t+q;}}}}voidmain(){queue*head;intq;head=init();head=creat(head);printf(〃您輸入的時(shí)間片輪轉(zhuǎn)進(jìn)程隊(duì)列為:\n〃)；print(head);printf("請(qǐng)輸入時(shí)間片輪轉(zhuǎn)調(diào)度的時(shí)間片為:")；scanf("%d”,&q);RR(head,q);時(shí)間片輪轉(zhuǎn)調(diào)度}

實(shí)驗(yàn)結(jié)果輸入進(jìn)程的數(shù)量，每個(gè)進(jìn)程的名稱、到達(dá)時(shí)間和服務(wù)時(shí)間，以及時(shí)間片：函 -|口|-Istate=Rstate=Rstate=Rstate=Rstate=R44

■■■■:E^J^名其名曹名曹名甚客甜程達(dá)塞達(dá)塞達(dá)畚達(dá)塞達(dá)務(wù)5進(jìn)船進(jìn)能進(jìn)能進(jìn)重進(jìn)船:勺勺勺.勺勺.勺勺.勺勺.勺勺.勺勺.勺勺?state=Rstate=Rstate=Rstate=Rstate=R44

■■■■:E^J^名其名曹名曹名甚客甜程達(dá)塞達(dá)塞達(dá)畚達(dá)塞達(dá)務(wù)5進(jìn)船進(jìn)能進(jìn)能進(jìn)重進(jìn)船:勺勺勺.勺勺.勺勺.勺勺.勺勺.勺勺.勺勺?3B---1,-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--ij—二..1二..1二..1二r二..1二..1二..1二..1二..1二..1二..1二..1二r二..1二..1建進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)進(jìn)射個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)個(gè)■屯111222333444555進(jìn)WWWWWWWWW1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)請(qǐng)04132532■■■■■■■■■■■■■■■■A可司?B可可?C可可?D司.可您輸入的時(shí)間片輪轉(zhuǎn)進(jìn)程隊(duì)燙為:runtime=4runtime=3runtime=5runtime=2runtime=4arriuetime=0arriuetime=1arriuetime=2arriuetime=3arriuetime=4pname=Apname=Bpname=Cpname=Dpname=E的時(shí)間片為H請(qǐng)輸入時(shí)恒得到的結(jié)果為:實(shí)驗(yàn)結(jié)果分析RR算法：每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并且令其執(zhí)行一個(gè)時(shí)間片，時(shí)間片的大小從幾個(gè)ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便依據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行；并且把它送往就緒隊(duì)列的隊(duì)尾；然后，再把處理劑分配給就緒隊(duì)列中的新隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一個(gè)給定時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)相應(yīng)所有用戶的請(qǐng)求。成功實(shí)現(xiàn)了RR輪轉(zhuǎn)調(diào)度算法，驗(yàn)證了算法實(shí)現(xiàn)程序的正確性。完成了實(shí)驗(yàn)要求的輸入。5.實(shí)驗(yàn)心得通過這次課程設(shè)計(jì)，我的收獲頗豐。課程設(shè)計(jì)之初我對(duì)時(shí)間片輪轉(zhuǎn)法基本上沒有什么深入的研究，只是通過課堂的講解大致了解其思想。經(jīng)過這將近兩周的學(xué)習(xí)后，我對(duì)時(shí)間片輪轉(zhuǎn)算法的理解有了更進(jìn)一步的提高，并通過自己設(shè)計(jì)程序，自己試驗(yàn)，自己調(diào)試對(duì)算法的內(nèi)容更進(jìn)一步的深刻認(rèn)識(shí)。老師讓我們?nèi)D書館自行查閱資料。在這期間，我不還在圖書館找到一些別