可變時間片輪轉(zhuǎn)+先來先服務(wù)實驗報告

1、目的要求：用高級語言編寫一個程序，先用可變時間片輪轉(zhuǎn)法將輸入的任意個進(jìn)程進(jìn)行調(diào)度，再用先來先服務(wù)法對它們進(jìn)行作業(yè)調(diào)度，以加深對進(jìn)程調(diào)度和作業(yè)調(diào)度算法的理解。數(shù)據(jù)結(jié)構(gòu)設(shè)計：進(jìn)程屬性結(jié)構(gòu)：struct pcbnodeint pid;/進(jìn)程id int priority;/優(yōu)先數(shù) int trtime;/總運行時間 int rtime;/剩余運行時間 int atime;/從開始到全部進(jìn)入就緒隊列所需的時間 int stime;/開始運行時間 int ftime;/完成運行時間 int ttime;/周轉(zhuǎn)時間 float wttime;/帶權(quán)周轉(zhuǎn)時間;隊列屬性結(jié)構(gòu)：struct qnode/進(jìn)程隊列

2、 int id; struct qnode* next;/隊列中下一個進(jìn)程指針;隊列頭結(jié)構(gòu)：struct lqqnode* head;/隊列首部;進(jìn)程輸入類：void input(pcbnode* pt,int pn);進(jìn)程初始化類：void initialqueue(lq& q,pcbnode* pt,int pn);時間片輪轉(zhuǎn)類void roundrobin(lq& q,int piece,int& ttimesum,int& wttimesum,pcbnode* pt);時間片分配類：bool deal(lq& q,qnode* q,qnode* p,int piece,int& cti

3、me,pcbnode* pt);先來先服務(wù)類：void fcfs(lq& q,int& ttimesum,int& wttimesum,pcbnode* pt);實驗環(huán)境：c+語言程序設(shè)計平臺算法流程設(shè)計：開始在input文件中輸入各個進(jìn)程的從開始到全部進(jìn)入就緒隊列所需時間、剩余運行時間、優(yōu)先數(shù)，一行一進(jìn)程輸入進(jìn)程數(shù)和時間片大小初始化就緒隊列，將文件中進(jìn)程投入運行等待隊列為空為隊列首進(jìn)程分配時間片進(jìn)程在時間片內(nèi)做完計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間將該進(jìn)程退出隊列，計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間將文件中的作業(yè)（進(jìn)程）投入隊列運行并確定其開始和完成時間運行隊首作業(yè)，計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間，退出隊列計算時

4、間片輪轉(zhuǎn)調(diào)度的平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間并打印將其后一作業(yè)移至隊首計算先來先服務(wù)的平均周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間并打印結(jié)束ynyn下一進(jìn)程到來將該進(jìn)程移至隊末，將其后一進(jìn)程移至隊首yn將其后一進(jìn)程移至隊首其后有進(jìn)程yn等待隊列為空其后有作業(yè)yynn運行事例演示：input文本中輸入： 運行結(jié)果： 在input文本中所輸入的三列數(shù)據(jù)分別為：各進(jìn)程的從開始到全部進(jìn)入就緒隊列所需的時間、剩余運行時間、優(yōu)先數(shù)，而真正在輪轉(zhuǎn)與服務(wù)中起到作用的只有前兩者。上述程序0到4的編號是按每行進(jìn)程的輸入順序分配的，在時間片輪轉(zhuǎn)調(diào)度中，其執(zhí)行順序起初也按編號的從小到大排序，但當(dāng)它們由于一次使用完時間片后為完成其所有工作量

5、而需再次被調(diào)用時，其運行順序就與input文本中第一列數(shù)據(jù)相關(guān)了，例如進(jìn)程2和3，由于進(jìn)程3全部進(jìn)入隊列的時間為11，而當(dāng)進(jìn)程2第一次運行后所過去的時間只有9（執(zhí)行了三次大小為3的時間片），于是接下來仍運行一次進(jìn)程2，之后才輪到進(jìn)程3（此時過去時間為12），接著就是剩余進(jìn)程輪轉(zhuǎn)運行直到結(jié)束。其后就是先來先服務(wù)，按進(jìn)程編號由小到大運行，各個進(jìn)程所占的時刻數(shù)就是它們input文本中第二列的數(shù)據(jù)，也就是運行時間。源程序：#include#include#include#includeusing namespace std;struct pcbnodeint pid;/進(jìn)程id int priorit

6、y;/優(yōu)先數(shù) int trtime;/總運行時間 int rtime;/剩余運行時間 int atime;/從開始到全部進(jìn)入就緒隊列所需的時間 int stime;/開始運行時間 int ftime;/完成運行時間 int ttime;/周轉(zhuǎn)時間 float wttime;/帶權(quán)周轉(zhuǎn)時間;struct qnode/進(jìn)程隊列 int id; struct qnode* next;/隊列中下一個進(jìn)程指針;struct lqqnode* head;/隊列首部;void input(pcbnode* pt,int pn);void initialqueue(lq& q,pcbnode* pt,int

7、pn);void roundrobin(lq& q,int piece,int& ttimesum,int& wttimesum,pcbnode* pt);bool deal(lq& q,qnode* q,qnode* p,int piece,int& ctime,pcbnode* pt);void fcfs(lq& q,int& ttimesum,int& wttimesum,pcbnode* pt);int main()lq q;/就緒隊列 q.head=null; int pn;/進(jìn)程數(shù) int piece;/時間片大小 int ttimesum=0;/周轉(zhuǎn)時間 int wttimesu

8、m=0;/帶權(quán)周轉(zhuǎn)時間 pcbnode* pt=new pcbnodepn;/進(jìn)程表 coutpn;/輸入在input文件中所輸入的進(jìn)程的個數(shù)（每行一個進(jìn)程） coutpiece;/輸入所需時間片的大小 input(pt,pn);/調(diào)用input.txt文件中進(jìn)程數(shù)據(jù) initialqueue(q,pt,pn);/初始化就緒隊列 roundrobin(q,piece,ttimesum,wttimesum,pt);/可變時間片輪轉(zhuǎn)進(jìn)程調(diào)度，調(diào)用deal()，piece為時間片大小 cout可變時間片輪的平均周轉(zhuǎn)時間為：ttimesum/pnendl; cout可變時間片輪的平均帶權(quán)周轉(zhuǎn)時間為：w

9、ttimesum/pnendl; input(pt,pn); initialqueue(q,pt,pn); fcfs(q,ttimesum,wttimesum,pt);/先來先服務(wù)作業(yè)調(diào)度 cout先來先服務(wù)的平均周轉(zhuǎn)時間為：ttimesum/pnendl; cout先來先服務(wù)的平均帶權(quán)周轉(zhuǎn)時間為：wttimesum/pnendl; delete pt; return 0;void input(pcbnode* pt,int pn)file* fp;/讀入進(jìn)程相關(guān)內(nèi)容 if(fp=fopen(input.txt,r)=null)/若無法訪問input文件 coutcan not open fi

10、le!endl; exit(0); for(int i=0;ipn;i+) fscanf(fp,%d %d %d,&pti.atime,&pti.rtime,&pti.priority);/輸入各進(jìn)程從開始到全部進(jìn)入就緒隊列所需的時間、剩余運行時間、優(yōu)先數(shù) fclose(fp);void initialqueue(lq& q,pcbnode* pt,int pn)for(int i=0;inext=null; qnode* p; qnode* q; for(i=0;iid=pti.pid; p-next=null; if(i=0) q.head-next=p; else q-next=p; q

11、=p; void roundrobin(lq& q,int piece,int& ttimesum,int& wttimesum,pcbnode* pt)ttimesum=0;/總的周轉(zhuǎn)時間 wttimesum=0;/平均周轉(zhuǎn)時間 int ctime=0;/當(dāng)前時間 qnode* p; qnode* q; qnode* r; bool finish=false;/調(diào)用deal()后，該進(jìn)程是否已經(jīng)做完退出 p=q.head; q=p-next; while(q!=null)/從隊列首部開始依次分配時間片 do cout*endl; cout在時間片(ctime+1)/piece+1內(nèi)，活動進(jìn)程

12、為：idendl; cout進(jìn)程id 現(xiàn)在需要的時間片為：id.rtimeendl; finish=deal(q,q,p,piece,ctime,pt);/分配時間片給q進(jìn)程 coutnext=null) r=q.head-next; else r=q-next; else /若未做完，計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間 ttimesum+=ptq-id.ttime; wttimesum+=ptq-id.wttime; delete q;/刪除q進(jìn)程 q=p; while(!finish&(ptr-id.atimectime+piece); p=q;/若下個進(jìn)程不來，則繼續(xù)給當(dāng)前進(jìn)程分配時間片 q=q

13、-next; if(q=null&q.head-next!=null) p=q.head; q=p-next; delete q.head; q.head=null;bool deal(lq& q,qnode* q,qnode* p,int piece,int& ctime,pcbnode* pt)/分配時間片給q所指進(jìn)程，p為剛退出的進(jìn)程if (ptq-id.rtimeid.ftime=ctime+ptq-id.rtime; ptq-id.ttime+=ptq-id.rtime; ptq-id.wttime=ptq-id.ttime/ptq-id.trtime; ctime=ptq-id.f

14、time; p-next=q-next; coutendl; cout進(jìn)程id完成！id.rtime=ptq-id.rtime-piece; ptq-id.ttime+=piece; ctime+=piece; return false; void fcfs(lq& q,int& ttimesum,int& wttimesum,pcbnode* pt)ttimesum=0;/平均周轉(zhuǎn)時間 wttimesum=0;/平均帶權(quán)周轉(zhuǎn)時間 qnode* p; qnode* q; p=q.head-next; if(p!=null)/確定開始和完成時間 ptp-id.stime=ptp-id.atime

15、; ptp-id.ftime=ptp-id.atime+ptp-id.trtime; for(q=p-next;q!=null;q=q-next) if(ptq-id.atimeid.ftime) ptq-id.stime=ptp-id.ftime; ptq-id.ftime=ptp-id.ftime+ptq-id.trtime; else/若下個進(jìn)程到達(dá)時間較晚 ptq-id.stime=ptq-id.atime; ptq-id.ftime=ptq-id.atime+ptq-id.trtime; p=q; for(q=q.head-next;q!=null;q=q-next)/計算平均周轉(zhuǎn)時

16、間和平均帶權(quán)周轉(zhuǎn)時間 ptq-id.ttime=ptq-id.ftime-ptq-id.atime; ptq-id.wttime=ptq-id.ttime/ptq-id.trtime; ttimesum+=ptq-id.ttime; wttimesum+=ptq-id.wttime; int t=0; for(q=q.head-next;q!=null;q=q-next) cout*endl; while(tid.ftime) cout時刻t：進(jìn)程id活動next!=null) cout時刻t：進(jìn)程id結(jié)束活動，開始下一個進(jìn)程。endl; cout進(jìn)程id的周轉(zhuǎn)時間為：id.ttimeendl; cout進(jìn)程id的帶權(quán)周轉(zhuǎn)時間為：id.wttimeendlendl; else cout時刻t：進(jìn)程id結(jié)束活動。endlendl; cout進(jìn)程id的周轉(zhuǎn)時間為：id.ttimeendl; cout進(jìn)程id的帶權(quán)周轉(zhuǎn)時間為：id.wttimeendlendl; cout所有進(jìn)程