1、調(diào)度算法，實(shí)現(xiàn)處理器調(diào)度。一、實(shí)驗(yàn)?zāi)康脑诓捎枚嗟莱绦蛟O(shè)計(jì)的系統(tǒng)中，往往有若干個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)。當(dāng)就緒狀態(tài)進(jìn)程個(gè)數(shù)大于處理器數(shù)時(shí)，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用處理器。本實(shí)驗(yàn)?zāi)M在單處理器情況下處理器調(diào)度，幫助自己加深了解處理器調(diào)度的工作。二、實(shí)驗(yàn)題目選擇一個(gè)調(diào)度算法，實(shí)現(xiàn)處理器調(diào)度。三、背景材料（一）設(shè)計(jì)一個(gè)按優(yōu)先數(shù)調(diào)度算法實(shí)現(xiàn)處理器調(diào)度的程序提示：1、假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程控制塊的格式為：進(jìn)程名指針要求運(yùn)行時(shí)間優(yōu)先數(shù)狀態(tài)進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為Pl,P2,P3,P4,P5。指針按優(yōu)先數(shù)的大小把五個(gè)進(jìn)程連成隊(duì)列，

2、用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址,最后一個(gè)進(jìn)程中的指針為“0”。要求運(yùn)行時(shí)間假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)間數(shù)。優(yōu)先數(shù)賦予進(jìn)程的優(yōu)先數(shù),調(diào)度時(shí)總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。狀態(tài)可假設(shè)有兩種狀態(tài),“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個(gè)進(jìn)程的初始狀態(tài)都為“就緒”,用“R”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。2、在每次運(yùn)行你所設(shè)計(jì)的處理器調(diào)度程序之前,為每個(gè)進(jìn)程任意確定它的“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”。本實(shí)驗(yàn)由于為了檢查的方便，優(yōu)先數(shù)和運(yùn)行時(shí)間采用下表中的數(shù)值。3、為了調(diào)度方便，把五個(gè)進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊(duì)列。用一單元指出隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例如：隊(duì)首

3、標(biāo)志K2K1P1K2P2K3P3K4P4K5P50K4K5K3K12312415342RRRRRPCB1PCB2PCB3PCB4PCB54、處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)就減“1”。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：優(yōu)先數(shù)-1要求運(yùn)行時(shí)間-1來模擬進(jìn)程的一次運(yùn)行。提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作。5、進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間10,則再將它加入隊(duì)列(按優(yōu)先數(shù)大小插入，且置隊(duì)首標(biāo)志)；若要求運(yùn)行

4、時(shí)間=0,貝I把它的狀態(tài)修改成“結(jié)束”(E),且退出隊(duì)列。6、若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面(4)和(5)的步驟，直到所有進(jìn)程都成為“結(jié)束”狀態(tài)。7、在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化?？梢詾槲鍌€(gè)進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。#include#includeusingnamespacestd;/struct_proccharname32;struct_proc*next;intrun_time;intpriorit

5、y;intstate;/就緒為;_proc*root;/向就緒隊(duì)列中插入進(jìn)程,按照降序voidInsert(_proc*pr)_proc*q=root;方便插入,記錄插入位置的前面的進(jìn)程_proc*p=root-next;if(root-state!=0)while(p!=NULL)找插入位置if(p-prioritypr-priority)優(yōu)先級(jí)小于時(shí)，繼續(xù)遍歷q=p;p=p-next;else/找到插入break;pr-next=p;插入q-next=pr;+root-state;進(jìn)程個(gè)數(shù)加一/創(chuàng)建進(jìn)程_procCreat(charname,intpriority,intrun_time)

6、_procpr;strcpy(,name);pr.priority=priority;pr.run_time=run_time;pr.state=0;pr.next=NULL;returnpr;/刪除就緒隊(duì)列中對(duì)首進(jìn)程_proc*Delete()_proc*pr=root-next;root-next=root-next-next;-root-state;returnpr;/對(duì)就緒隊(duì)列排序,按照降序voidSort()if(root-next-run_time=0)要執(zhí)行時(shí)間為時(shí)，從就緒隊(duì)列中刪除該進(jìn)程Delete();root-next-state=1;else/不為時(shí)，先刪除

7、，再根據(jù)變化后的優(yōu)先級(jí)，插入到相應(yīng)位置_proc*pr=Delete();Insert(pr);/輸出執(zhí)行進(jìn)程號(hào)voidOutPut()coutvvroot-next-namevvendl;輸出，模擬進(jìn)程執(zhí)行-root-next-priority;修改進(jìn)程的優(yōu)先級(jí)和運(yùn)行時(shí)間，狀態(tài)-root-next-run_time;voidSolve()/根結(jié)點(diǎn)root=new_proc;root-state=0;/state記錄就緒隊(duì)列中的進(jìn)程個(gè)數(shù)root-next=NULL;指向第一個(gè)進(jìn)程/創(chuàng)建幾個(gè)進(jìn)程，并插入就緒隊(duì)列_procpr1=Creat(p1，2，1);Insert(&pr1);_procpr

8、2=Creat(p2，3，5);Insert(&pr2);_procpr3=Creat(p3，1，3);Insert(&pr3);_procpr4=Creat(p4，2，4);Insert(&pr4);_procpr5=Creat(p5，4，2);Insert(&pr5);coutvv調(diào)度序列：vvendl;while(root-state!=0)OutPut();Sort();intmain()Solve();getchar();getchar();return0;（二）設(shè)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序。1、假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。進(jìn)程控制塊的格

9、式為：進(jìn)程名指針要求運(yùn)行時(shí)間已運(yùn)行時(shí)間狀態(tài)進(jìn)程名作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為QI,Q2,Q3,Q4,Q5。指針進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制塊的首地址，最后一個(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)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。2、每次運(yùn)行所設(shè)計(jì)的處理器調(diào)度程序前，為每個(gè)進(jìn)程任意確定它的“要求運(yùn)行時(shí)間”。3、把五個(gè)進(jìn)程按順序排成循環(huán)隊(duì)列，用指針指出隊(duì)列連接情

10、況。另用一標(biāo)志單元記錄輪到運(yùn)行的進(jìn)程。例如，當(dāng)前輪到P2執(zhí)行，則有：標(biāo)志單元K2K1Q1K2Q2K3Q3K4Q4K5Q5K2K3K4K5K12312410000RRRRRPCB1PCB2PCB3PCB4PCB54、處理器調(diào)度總是選擇標(biāo)志單元指示的進(jìn)程運(yùn)行。由于本實(shí)驗(yàn)是模擬處理器調(diào)度的功能，所以，對(duì)被選中的進(jìn)程并不實(shí)際的啟動(dòng)運(yùn)行，而是執(zhí)行：已運(yùn)行時(shí)間+1來模擬進(jìn)程的一次運(yùn)行，表示進(jìn)程已經(jīng)運(yùn)行過一個(gè)單位的時(shí)間。請(qǐng)同學(xué)注意：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí)，必須置上該進(jìn)程可以運(yùn)行的時(shí)間片值，以及恢復(fù)進(jìn)程的現(xiàn)場(chǎng)，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行滿一個(gè)時(shí)間片。在這時(shí)省去了這些工作，僅用“

11、已運(yùn)行時(shí)間+1”來表示進(jìn)程已經(jīng)運(yùn)行滿一個(gè)時(shí)間片。5、進(jìn)程運(yùn)行一次后，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到標(biāo)志單元，以指示下一個(gè)輪到運(yùn)行的進(jìn)程。同時(shí)，應(yīng)判斷該進(jìn)程的要求運(yùn)行時(shí)間與已運(yùn)行時(shí)間，若該進(jìn)程的要求運(yùn)行時(shí)間1已運(yùn)行時(shí)間，則表示它尚未執(zhí)行結(jié)束，應(yīng)待到下一輪時(shí)再運(yùn)行。若該進(jìn)程的要求運(yùn)行時(shí)間=已運(yùn)行時(shí)間，則表示它已經(jīng)執(zhí)行結(jié)束，應(yīng)指導(dǎo)它的狀態(tài)修改成“結(jié)束”（E）且退出隊(duì)列。此時(shí)，應(yīng)把該進(jìn)程的進(jìn)程控制塊中的指針值送到前面一個(gè)進(jìn)程的指針位置。6、若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面的4和5的步驟，直到所有的進(jìn)程都成為“結(jié)束”狀態(tài)。7、在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次選中進(jìn)程的

12、進(jìn)程名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化?？梢詾槲鍌€(gè)進(jìn)程任意確定一組“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理器調(diào)度程序，顯示或打印逐次被選中的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。#include#includeusingnamespacestd;/struct_proccharname32;struct_proc*next;intrun_time;intalloc_time;intstate;/就緒為;_proc*root;/向就緒隊(duì)列中插入進(jìn)程,按照降序voidInsert(_proc*pr)if(root-next=NULL)root=pr;pr-next=pr;return;pr-next=root

13、-next;插入root-next=pr;root=pr;/創(chuàng)建進(jìn)程_procCreat(charname,intrun_time,intalloc_time)_procpr;strcpy(,name);pr.run_time=run_time;pr.alloc_time=alloc_time;pr.state=0;pr.next=NULL;returnpr;/刪除就緒隊(duì)列中對(duì)首進(jìn)程voidDelete()if(root-next=root)root=NULL;return;root-next=root-next-next;/輸出進(jìn)程號(hào),模擬進(jìn)程執(zhí)行voidOutPut()cou

14、tvvroot-next-namevvendl;輸出，模擬進(jìn)程執(zhí)行+root-next-alloc_time;修改進(jìn)程voidSolve()/根結(jié)點(diǎn)root=new_proc;root-state=0;/state記錄就緒隊(duì)列中的進(jìn)程個(gè)數(shù)root-next=NULL;空循環(huán)鏈表，指向自身/創(chuàng)建幾個(gè)進(jìn)程,并插入就緒隊(duì)列_procpr1=Creat(Q1,2,1);Insert(&pr1);_procpr2=Creat(Q2,3,0);Insert(&pr2);_procpr3=Creat(Q3,1,0);Insert(&pr3);_procpr4=Creat(Q4,2,0);Insert(&pr

15、4);_procpr5=Creat(Q5,4,0);Insert(&pr5);coutvv調(diào)度序列：vvendl;while(root!=NULL)一直循環(huán)遍歷OutPut();執(zhí)行root指向的進(jìn)程執(zhí)行完畢即：run_time=alloc_time，從隊(duì)列中刪除該進(jìn)程if(root-next-alloc_time=root-next-run_time)執(zhí)行完畢Delete();從就緒隊(duì)列中，刪除該進(jìn)程continue;root=root-next;/root指針后移，執(zhí)行下一個(gè)進(jìn)程做準(zhǔn)備intmain()Solve();getchar();getchar();return0;四、實(shí)驗(yàn)內(nèi)容1、

16、設(shè)計(jì)一個(gè)按背景材料中指定優(yōu)先數(shù)的優(yōu)先數(shù)調(diào)度算法實(shí)現(xiàn)處理器調(diào)度的程序2、設(shè)計(jì)一個(gè)按時(shí)間片輪轉(zhuǎn)法實(shí)現(xiàn)處理器調(diào)度的程序。#includestdio.h#include#include#definegetpch(type)(type*)malloc(sizeof(type)#defineNULL0structpcb/*定義進(jìn)程控制塊PCB*/charname10;charstate;intsuper;intntime;intrtime;structpcb*link;*ready=NULL,*p;typedefstructpcbPCB;sort()/*建立對(duì)進(jìn)程進(jìn)行優(yōu)先級(jí)排列函數(shù)*/PCB*first,

17、*second;intinsert=0;if(ready=NULL)p-link=ready;ready=p;else/*進(jìn)程比較優(yōu)先級(jí),插入適當(dāng)?shù)奈恢弥?/first=ready;second=first-link;while(second!=NULL)first=first-link;second=second-link;/*插尾*/if(insert=0)first-link=p;input()/*建立進(jìn)程控制塊函數(shù)*/inti,num;system(cls);/*清屏*/printf(n請(qǐng)輸入進(jìn)程號(hào)?);scanf(%d,&num);for(i=0;iname);printf(n輸入進(jìn)

18、程運(yùn)行時(shí)間:);scanf(%d,&p-ntime);printf(n);p-rtime=0;p-state=w;p-link=NULL;sort();/*調(diào)用sort函數(shù)*/intspace()intl=0;PCB*pr=ready;while(pr!=NULL)l+;pr=pr-link;return(l);disp(PCB*pr)/*建立進(jìn)程顯示函數(shù),用于顯示當(dāng)前進(jìn)程*/printf(nqnametstatetsupertndtimetruntimen);printf(|%st,pr-name);printf(|%ct,pr-state);printf(|%dt,pr-super);printf(|%dt,pr-ntime);printf(|%dt,pr-rtime)