實驗二帶優(yōu)先級的時間片輪換的進程調(diào)度算法的實現(xiàn).ppt

帶優(yōu)先級的時間片輪換的進程調(diào)度算法的實現(xiàn),一、實驗?zāi)康?（1）掌握進程狀態(tài)轉(zhuǎn)換過程 （2）掌握時間片輪轉(zhuǎn)的進程調(diào)度算法； （3）掌握帶優(yōu)先級的進程調(diào)度算法,二、實驗內(nèi)容 （1）自定義PCB的數(shù)據(jù)結(jié)構(gòu)； （2）使用帶優(yōu)先級的時間片輪轉(zhuǎn)法調(diào)度進程，每運行一 個時間片，優(yōu)先級減半。 （3）命令集 A）create 隨機創(chuàng)建進程，進程的優(yōu)先級與所需要的時間片隨機決定； B）round 執(zhí)行1次時間片輪轉(zhuǎn)操作，其方法為運行高優(yōu)先級隊列的 第1個，再降低其優(yōu)先級，插入到相應(yīng)的隊列中。 C）ps 查看當(dāng)前進程狀態(tài) D）sleep 命令將進程掛起 E）awake 命令喚醒1個被掛起的進程 F）kill 命令殺死進程 G）quit命令退出 （4）選用面向?qū)ο蟮木幊谭椒ā?三、實驗原理或算法 本實驗結(jié)合了進程狀態(tài)轉(zhuǎn)換、優(yōu)先級調(diào)度、時間片輪轉(zhuǎn)調(diào)度三方面的內(nèi)容，根據(jù)進程狀態(tài)轉(zhuǎn)換圖，設(shè)置SLEEP命令，將1個進程掛起，AWAKE命令喚醒1個被掛起的進程（從阻塞狀態(tài)到就緒狀態(tài)）。 1) 優(yōu)先級 優(yōu)先級體現(xiàn)了進程的重要程度或緊迫程度，在大多數(shù)現(xiàn)代操作系統(tǒng)中，都采用了優(yōu)先級調(diào)度策略。優(yōu)先級從小到大（如 0-127） 優(yōu)先級最高，127 最低。在本實驗中按數(shù)值大小決定優(yōu)先級，數(shù)值大的優(yōu)先級高。 2) 基于時間片調(diào)度 將所有的就緒進程按照先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，將 cpu 分配給隊首進程，并令其執(zhí)行一個時間片。當(dāng)時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序把此進程終止，把該進程放到隊尾。 在該實驗中，時間片以 100ms 為單位（實際的要小得多）。在調(diào)度過程中，需要通過時間函數(shù)檢測進程的執(zhí)行時間，當(dāng)該進程執(zhí)行時間時間片大小時，進行調(diào)度。,3) 高優(yōu)先級調(diào)度 優(yōu)先級高的進程優(yōu)先得到 cpu，等該進程執(zhí)行完畢后，另外的進程才能執(zhí)行。 4) 基于時間片的高優(yōu)先級調(diào)度 在調(diào)度算法中，只有處于就緒狀態(tài)的進程才能被調(diào)度，調(diào)度算法結(jié)合了優(yōu)先級調(diào)度和時間片輪轉(zhuǎn)調(diào)度算法，約定：從最高優(yōu)先級隊列取第1個就緒狀態(tài)的進程進行調(diào)度，時間片到后降低其優(yōu)先級（降低一半），然后插入到低優(yōu)先級隊列的尾部，每次調(diào)度后，顯示進程的狀態(tài)。,四、數(shù)據(jù)結(jié)構(gòu)及符號說明 struct pcb /PCB int ident;/標(biāo)識符 int state;/狀態(tài) 0-就緒，1運行，2堵塞 int pior;/優(yōu)先級,MAXPIOR為最高優(yōu)先級*/ int life;/生命期*/ struct pcb *next;/*指針*/ void init()/ int create()/ void ps()/ void awake(int x)/ void kill(int x)/ void process()/對輸入命令的處理 void routine()/執(zhí)行一次調(diào)度運行，將最高優(yōu)先級隊列的進程運行1個時間片，并降低其優(yōu)先級,六、實驗源程序 #include #include #include #define getpch(type) (type*)malloc(sizeof(type) struct pcb /* 定義進程控制塊PCB */ char name10; char state; int super; int needtime; int runtime; struct pcb* link; *ready=NULL,*p; typedef struct pcb PCB; int ident;/標(biāo)識符 int state;/狀態(tài) 0-就緒，1運行，2堵塞 int pior;/優(yōu)先級,MAXPIOR為最高優(yōu)先級*/ int life;/生命期*/ struct pcb *next;/*指針*/, int create() int i=0,pior=0; struct pcb *p,*q,*s; while (idlisti!=0,void sleep(int x) int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0,p=arraypior;/建立同優(yōu)先級隊列（鏈表） if (p=NULL) arraypior=s; else while(p!=NULL) q=p; p=p-next; q-next=s; printf(“success create process id=%d, current process state disp below:n“,s-ident); ps(); /printf(“end displayn“); return 1; void ps() int i=0; struct pcb *p; for (i=0;iident,p-state,p-pior,p-life); p=p-next; ,if (i=MAXPIOR) printf(“Invaild process number.“); else if (p-state=2) printf(“the process %d has blocked,cannot sleep again!“,p-ident); else p-state=2; ps(); void awake(int x) int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0 while(p!=NULL) if (p-ident=x) ,test=1;killtest=1;break; else q=p;p=p-next; if (test=0) i+; /*找到X所在指針*/ if (i=MAXPIOR) printf(“Invaild process number.“); else if (p-state=0) printf(“the process %d is ready state,cannot awake again!“,p-ident); else p-state=0; ps(); void kill(int x) int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0 ,if (i!=MAXPIOR else, q-next=p-next; idlistx=0; life=life-(p-life); free(p); void process()/對輸入命令的處理 int i=0,ii=0; for (i=0;i7;i+) if (stricmp(str,commandi)=0) break; switch(i) case 0:printf(“thank you for using the program!n“);exit(0); break; case 1:ps(); break; case 2:create(); break; case 3: printf(“Which process you want to kill?n“);,scanf(“%d“, ,void routine()/執(zhí)行一次調(diào)度運行，將最高優(yōu)先級隊列的進程運行1個時間片，并降低其優(yōu)先級 int i=MAXPIOR-1,pior=0,t; struct pcb *pp,*qq,*pr,*r; do while (i=0 /進程處于就緒狀態(tài) if(r-life-QUANTUM0), r-life=r-life-QUANTUM; /時間減少Q(mào)UANTUM life=life-QUANTUM; else life=life-r-life; r-life=0; if (r-life=0)/進程運行完成，KILL它 printf(“the process %d is successful run,and release it!n“,r-ident); kill(r-ident); else if (pr=r) /將r結(jié)點從原隊列中刪除 arrayi+1=r-next; else pr-next=r-next; t=r-pior; /將r進程加入到相應(yīng)低優(yōu)先級隊列中的最后 pp=arrayt; qq=NULL; while (pp!=NULL), qq=pp;pp=pp-next; if(qq=NULL) /插入到隊尾 arrayt=r; else qq-next=r; r-next=NULL; printf(“after.n“); ps(); printf(“n 1 quantum successful run!n“); /* void main() init(); printf(“Welcome to the Process Scheduling system. This pr