作業(yè)調(diào)度設(shè)計(jì)報告(多道)

1、作業(yè)調(diào)度( 多通道 ) 課程設(shè)計(jì)報告目的要求：用高級語言編寫和調(diào)試一個或多個作業(yè)調(diào)度的模擬程序，以加深對作業(yè)調(diào)度算法的理解。 詳細(xì)設(shè)計(jì)：在多通道批處理系統(tǒng)中，作業(yè)的運(yùn)行除了考慮作業(yè)之間的優(yōu)先關(guān)系之外，還必須考慮系統(tǒng)能否為其所需的資源分配資源。因?yàn)樵诙嗤ǖ琅幚硐到y(tǒng)中同時有不只一道作業(yè)在CPU 中運(yùn)行，這樣就會導(dǎo)致某個作業(yè)需要的資源正在被另一個作業(yè)占用，這樣就會導(dǎo)致無法分配資源的作業(yè)進(jìn)入等待狀態(tài)，直到該資源被其它作業(yè)釋放后才能重新激活。 、作業(yè)調(diào)度算法該作業(yè)調(diào)度系統(tǒng)的調(diào)度算法是基于優(yōu)先級的調(diào)度算法。在作業(yè)提交后按預(yù)先設(shè)定的優(yōu)先級的高低依次插入到就緒隊(duì)列(ready), 但在系統(tǒng)運(yùn)行過程中，除了考

2、慮優(yōu)先級外 ( 即優(yōu)先級高只是表明該作業(yè)能較先運(yùn)行 ) ，同時還應(yīng)該考慮該作業(yè)所需的資源是否能夠被分配到。 、為作業(yè)分配資源在這里采用這樣的方法判斷資源能否分配：查看該作業(yè)運(yùn)行所需的第一個資源，然后在系統(tǒng)資源中查看該資源是否還有空閑的，有則表示該資源可以插入到運(yùn)行隊(duì)列(run) 中，準(zhǔn)備在下一個時間片中運(yùn)行。 、設(shè)置同時運(yùn)行的最大并行度這里設(shè)置一個量maxrun ，這個量是系統(tǒng)允許同時并行運(yùn)行的作業(yè)數(shù)量，當(dāng)運(yùn)行隊(duì)列中的作業(yè)數(shù)目達(dá)到最大值maxrun 后，即使某作業(yè)所需的資源系統(tǒng)還有空閑的，也不再允許繼續(xù)分配。 、作業(yè)模塊每個作業(yè)由一個作業(yè)控制塊JCB 控制，相關(guān)信息將在代碼中將詳細(xì)給出。 、所

3、需資源模塊每個作業(yè)的JCB 模塊中有個所需資源的鏈，其結(jié)構(gòu)用needsource 表示，相關(guān)信息將在代碼中將詳細(xì)給出。 、系統(tǒng)資源模塊( systemsource )將系統(tǒng)擁有的各個資源及其的數(shù)目鏈成鏈，在系統(tǒng)運(yùn)行過程過這個鏈就可以查詢某作業(yè)需要的資源系統(tǒng)是否可以分配。每當(dāng)為某作業(yè)分配了某個資源后，該資源的數(shù)目減 1 ，而當(dāng)某作業(yè)釋放了某個資源后，該資源的數(shù)目又將加1 。相關(guān)信息將在代碼中將詳細(xì)給出。調(diào)度算法流程圖如下：開始初始化系統(tǒng)資源（將系統(tǒng)資源及數(shù)目鏈成鏈，以便查詢）初始化所有JCB ,使JCB按預(yù)定的優(yōu)先級排成隊(duì)列（systemtime=O )fch-r-i r作業(yè)調(diào)度（函數(shù)為： at

4、temper 。詳細(xì)過程見下圖查看調(diào)度情況（函數(shù)為：check （）;打印就緒隊(duì)列，運(yùn)行隊(duì)列，等待隊(duì)列中各個作業(yè)的信 息）作業(yè)運(yùn)行，將運(yùn)行隊(duì)列中的各個作業(yè)的所需的第一個資源撤消，查看等 待隊(duì)列，看是否有作業(yè)需要該資 源，有則激活該作業(yè)，同時所需資源鏈needsource * source 指針指向下一個資源。Systemtime力口1息，并從run隊(duì)列中撤消計(jì)算并打印該組作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間結(jié)束作業(yè)調(diào)度的詳細(xì)過程如下t作'通度（函數(shù)為：attemperO）數(shù) runjcb 力口 1)四、程序代碼如下：#in elude <iostream.h># i ncl

5、ude <stdlib.h>空間分配函數(shù)# i nclude "con io.h"#defi ne GetSpace(type) (type*)malloc(sizeof(type) /# defi ne NULL 0# defi ne source num 8 II系統(tǒng)擁有的各種同類資源數(shù)目# define maxrun 3 II定義在CPU中能同時運(yùn)行的作業(yè)總數(shù)系統(tǒng)資源名稱char syssourcenamesourcenum = 'A','B',C,'D','E','F',&#

6、39;G','H'int sournumsource num = 1,1,1,1,1,1,1,1; II對應(yīng)的系統(tǒng)資源數(shù)量int systemtime = 0; II系統(tǒng)時間，開始為零int runjcb = 0;/在運(yùn)行隊(duì)列中的作業(yè)數(shù)量，開始為零int JCBNum = 0; / 總的作業(yè)數(shù)int JCBTime = 0; / 總的周轉(zhuǎn)時間float JCBTime_1 = 0; / 總的帶權(quán)周轉(zhuǎn)時間struct systemsource /系統(tǒng)資源，包括名稱和數(shù)量char name; intnumber;systemsource * link;*systemsor;

7、struct needsource / char name; needsource *link;*sourcelink;struct jcb / char name10; int ptime;/ int rtime; / int ftime; / int super; /int needtime; /作業(yè)所需資源鏈表結(jié)構(gòu)作業(yè)結(jié)構(gòu)/ 作業(yè)名稱提交時間開始運(yùn)行時間完成時間優(yōu)先級所需運(yùn)行時間needsource * source; / 所需資源鏈表char state; / 作業(yè)狀態(tài)bool runflag; / 標(biāo)識該作業(yè)運(yùn)行與否jcb * link;*wait=NULL,*ready=NULL,

8、*run=NULL,*p;typedef struct systemsource SYSTEM; typedef struct needsource NEED;typedef struct jcb JCB;/ void init() / 將系統(tǒng)資源名稱和對應(yīng)的資源數(shù)目放到系統(tǒng)資源隊(duì)列中systemsource *fir,*sec;for(int i=0;i < sourcenum;i+)fir = GetSpace(SYSTEM);fir = new SYSTEM;fir->name = syssourcenamei; /fir->number = sournum i; /f

9、ir->link = NULL;系統(tǒng)資源名稱對應(yīng)的數(shù)量if(i=0)systemsor = fir; / 生成系統(tǒng)資源鏈表systemsor elsesec->link = fir;sec = fir; / void sort(bool BOOL) / 按作業(yè)的優(yōu)先級的高低依次插入到相關(guān)隊(duì)列/當(dāng) BOO 為 true 時表明要插入到就緒隊(duì)列，否則插入到等待隊(duì)列jcb *fir,*sec;bool ins = true;if(BOOL) / 插入就緒隊(duì)列fir = ready;elsefir = wait;if(fir=NULL) | (p->super) > (fir-

10、>super) p->link = fir; fir = p;if(BOOL)ready = fir;elsewait = fir; else sec = fir->link ; while(sec != NULL) if(p->super) > (sec->super) p->link = sec; fir->link = p; sec = NULL; ins = false;else fir=fir->link; sec=sec->link; if(ins) fir->link = p;/ void input()int n

11、um;cout<<"n 輸入作業(yè)個數(shù)："cin>>num;JCBNum += num; / 將新加的作業(yè)個數(shù)加到總的作業(yè)數(shù)中 for(int i=0; i<num; i+) p = GetSpace(JCB); p = new JCB;cout<<"nn 輸入作業(yè)"<<i+1<<" 的名稱："cin>>p->name ;cout<<"n 輸入該作業(yè)的優(yōu)先級："cin>>p->super;cout<

12、<"n 輸入該作業(yè)所需的資源數(shù)目："cin>>p->needtime;needsource *fir,*sec;systemsource *cur;sec = p->source;for(int j=0; j<p->needtime ; j+) bool BOOL=true;fir = GetSpace(NEED);while(BOOL) cur = systemsor; / 指向系統(tǒng)資源鏈表cout<<"n 輸入第 "<<j+1<<" 個資源的名稱：" c

13、in>>fir->name;fir->link = NULL;while(cur != NULL) / 保證輸入的資源是系統(tǒng)有的 if(fir->name = cur->name ) /輸入的是合法資源BOOL = false;break; elsecur = cur->link ;if(cur = NULL) / 輸入的是非法資源cout<<"n 該資源不是系統(tǒng)資源，請重新輸入.nn" if(j=0) p->source = fir;else sec->link = fir;sec = fir;p->

14、ptime = systemtime; /提交時間為當(dāng)前系統(tǒng)時間p->ftime = p->rtime = 0;p->runflag = false; / 開始時運(yùn)行狀態(tài)為否p->state = 'O' / 狀態(tài)為就緒Order p->link =NULL;sort(true);/ 參數(shù)為 true 表示插入就緒鏈表，當(dāng)參數(shù)為false 是表示要插入等待鏈表/ int space() / 查看就緒隊(duì)列是否為空，返回其長度int len=0; jcb *fir;fir = ready;while(fir != NULL)len+; fir=fir-&

15、gt;link ;return len;/ void attemper() / 為作業(yè)分配資源函數(shù)jcb *fir,*sec,*thr; systemsource *res;if(run != NULL) / 如果有作業(yè)正在運(yùn)行的話，優(yōu)先為它們分配資源 sec = fir = run; while(fir != NULL)res = systemsor; /while(res != NULL) 指向系統(tǒng)資源鏈表if(fir->source->name = res->name) / 找到運(yùn)行隊(duì)列中所有作業(yè)需要的資源查看系統(tǒng)能否為其分配資源if(res->number &g

16、t; 0) /res->number -; /sec = fir; / fir = fir->link;else / 并可以為該作業(yè)分配資源資源數(shù)減1繼續(xù)分配隊(duì)列中其它作業(yè)需要的資源不能分配，插入等待隊(duì)列if(fir = run) /如果的運(yùn)行隊(duì)列的隊(duì)首run = run->link ;p= fir;sec = fir = run; elsesec->link = fir->link;p=fir;fir = fir->link;p->link = NULL;p->state = 'W' / p->super -; / run

17、jcb -; / sort(false); / break; else res = res->link ;/ 為就緒隊(duì)列中的作業(yè)分配資源sec = fir = ready;jcb *cur;while(runjcb <= maxrun && fir != NULL) /作業(yè)狀態(tài)為等待Wait優(yōu)先級減1 ，從而保證其它作業(yè)能得到資源1插入等待隊(duì)列運(yùn)行運(yùn)行隊(duì)列中的總數(shù)小于允許同時運(yùn)行的總數(shù) res = systemsor; / 指向系統(tǒng)資源鏈表while(res != NULL)if(fir->source->name = res->name) 能夠?yàn)?/p>

18、該作業(yè)分配資源對應(yīng)資源數(shù)目減1 運(yùn)行隊(duì)列作業(yè)樹木加1if(fir = ready)if(res->number > 0) / res->number -; /runjcb +; / thr = fir;cur = run;/ 將該作業(yè)移出就緒隊(duì)列ready = ready->link ; sec = fir = ready;elsesec->link = fir->link ;fir = fir->link ; thr->link = NULL;thr->state = 'R' if(thr->runflag = fa

19、lse) / 該作業(yè)第一次運(yùn)行，開始運(yùn)行時間等于當(dāng)前系統(tǒng)時間thr->rtime = systemtime;thr->runflag = true; / 表示已經(jīng)運(yùn)行 / 插入到運(yùn)行隊(duì)列的隊(duì)尾if(run = NULL) run = thr;elsewhile(cur->link != NULL) /找到運(yùn)行隊(duì)列的隊(duì)尾cur = cur->link ;cur->link = thr; / 在隊(duì)尾插入該作業(yè)else/ 準(zhǔn)備為就緒隊(duì)列中的下一個作業(yè)分配資源sec = fir;fir = fir->link;break; / 跳處 while 循環(huán)res = re

20、s->link ; /指向系統(tǒng)資源鏈表的下一個資源，繼續(xù)查找/ void display(jcb *pr) needsource *res;cout<<"nt"<<pr->name<<"t"<<pr->ptime<<"t"<<pr->rtime<<"t"<<pr->ftime<<"t"<<pr->super<<"t&qu

21、ot;<<pr->state<<"t"<<pr->source->name<<endl;res = pr->source->link;while(res != NULL) / 將作業(yè)所需的資源列表逐一打印出來cout<<"ttttttt"<<res->name<<endl; res = res->link;cout<<endl;/ void check() / 打印在運(yùn)行隊(duì)列，就緒隊(duì)列和等待隊(duì)列中的作業(yè)的信息 jcb

22、*pr;if(run = NULL)cout<<"n 當(dāng)前在運(yùn)行隊(duì)列沒有任何作業(yè).n"elsecout<<"n 當(dāng)前在運(yùn)行隊(duì)列的作業(yè)參數(shù)如下.nn"cout<<"tnametptimetrtimrtftimetsupertstatetsource"<<endl; pr = run; while(pr != NULL) display(pr); / 打印作業(yè)信息函數(shù) pr = pr->link ; if(ready = NULL)cout<<"n 當(dāng)前在就緒隊(duì)列

23、沒有任何作業(yè).n"elsecout<<"n 當(dāng)前在就緒隊(duì)列的作業(yè)參數(shù)如下.nn"cout<<"tnametptimetrtimrtftimetsupertstatetsource"<<endl; pr = ready;while(pr != NULL) display(pr); / pr = 打印作業(yè)信息函數(shù) pr->link ; if(wait = NULL) cout<<"n 當(dāng)前在等待隊(duì)列沒有任何作業(yè).nn" elsecout<<"n 當(dāng)前在等

24、待隊(duì)列的作業(yè)參數(shù)如下.nn"cout<<"tnametptimetrtimrtftimetsupertstatetsource"<<endl; pr = wait;while(pr != NULL) display(pr); / 打印作業(yè)信息函數(shù)pr = pr->link ;cout<<endl;/ void activation(char ResName) /激活在等待隊(duì)列中的作業(yè)/ResName 為剛剛釋放的資源的名稱/ 在等待隊(duì)列中找到某作業(yè)所需資源隊(duì)列的第一個資源名稱跟其相同的，激活之jcb *fir,*sec;i

25、f(wait = NULL) / 等待隊(duì)列為空，返回return;if(wait->source->name = ResName) / 等待隊(duì)列中第一個作業(yè)就是需要該資源的作業(yè)/ 激活之p = wait;wait = wait->link ; p->state = 'O'/p->link = NULL; sort(true); 作業(yè)狀態(tài)為就緒Order/將該作業(yè)插入到就緒隊(duì)列中else/ 在等待隊(duì)列中查找需要該資源的作業(yè)fir = wait;sec=fir->link ;while(sec != NULL)if(sec->source-

26、>name = ResName) p = sec; fir->link = sec->link ; p->state = 'O'p->link = NULL; sort(true); /將該作業(yè)插入到就緒隊(duì)歹U中break;elsefir = sec;sec = sec->link ;/void destory(jcb *pr) / 打印運(yùn)行完成的作業(yè)信息，并撤消之pr->ftime = systemtime; cout<<"nnncout<<"cout<<"n 提交時間

27、：cout<<"n cout<<"ncout<<"ncout<<"ncout<<"ncout<<"ncout<<"n開始運(yùn)行時間：cout<<"n /開始運(yùn)行吩司作業(yè)"<<pr->name<<" 相關(guān)參數(shù)如已經(jīng)完成nn"下："<<endl; "<<pr->ptime;J"<<pr->r

28、time;J"<<pr->ftime;完成時刻：J"<<pr->needtime;所需運(yùn)行時間:J"<<pr->ftime-pr->rtime; /實(shí)際運(yùn)行時間:實(shí)際運(yùn)行時間等于完成時刻cout<<"n "cout<<"n周轉(zhuǎn)時間："<<pr->ftime-pr->ptime;周轉(zhuǎn)時間德育完成時刻-提交時刻cout<<"n "cout<<"n 帶權(quán)周轉(zhuǎn)時間"

29、;<<float(pr->ftime-pr->ptime)/float(pr->needtime);/帶權(quán)周轉(zhuǎn)時間等于周轉(zhuǎn)時間/所需的運(yùn)行時間cout<<"n "<<endl;JCBTime += systemtime-pr->ptime; /將該作業(yè)的周轉(zhuǎn)時間加入到作業(yè)總周轉(zhuǎn)時間更新總帶權(quán)周轉(zhuǎn)時間JCBTime_1 += float(JCBTime)/float(pr->needtime); / cout<<endl;delete pr;/void running() / 運(yùn)行函數(shù)/ 每運(yùn)行一次

30、相當(dāng)于把運(yùn)行隊(duì)列中所有作業(yè)所需的第一個資源從所需資源隊(duì)列中撤消掉jcb *fir;systemsource *res; / 系統(tǒng)資源 needsource *abandon; if(run = NULL) / 運(yùn)行隊(duì)列為空，沒有運(yùn)行作業(yè) return;fir = run;while(fir != NULL)res = systemsor; /res 指向系統(tǒng)資源鏈表的表頭 while(res != NULL)if(fir->source->name = res->name) / 運(yùn)行的結(jié)果是該作業(yè)取消所需的第一個資源abandon = fir->source; /aba

31、ndon 為需要釋放的資源fir->source =fir->source->link;res->number +; / 釋放該作業(yè)占用的但已經(jīng)完成的資源activation(res->name); /激活等待隊(duì)列中需要該資源的作業(yè)delete abandon;break;elseres = res->link ;fir = fir->link ;/void displayResult() /檢查是否有運(yùn)行完的作業(yè)jcb *fir,*sec,*thr;if(run = NULL) /運(yùn)行隊(duì)列為空，返回return;fir = sec = run; /在

32、運(yùn)行隊(duì)列中找到已經(jīng)完成的作業(yè)while(fir != NULL)if(run->source = NULL) /所需資源鏈表為空，該作業(yè)已經(jīng)完成thr = run; run = run->link ; fir = sec = run;destory(thr); /打印該作業(yè)的參數(shù)信息并撤消該作業(yè)runjcb -; /當(dāng)前運(yùn)行隊(duì)列的作業(yè)數(shù)減1cout<<"n 按任意鍵繼續(xù)."<<endl;getch();else if(fir->source = NULL) thr = fir; sec->link = fir->link ; fir = fir->link ;destory(thr); / 打印該作業(yè)的參數(shù)信息并撤消該作業(yè)runjcb -; / 當(dāng)前運(yùn)行隊(duì)列的作業(yè)數(shù)減 1 cout<<"n 按任意鍵繼續(xù)."