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

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

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