可變時間片輪轉+先來先服務實驗報告

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

2、 int id; struct qnode* next;/隊列中下一個進程指針;隊列頭結構：struct lqqnode* head;/隊列首部;進程輸入類：void input(pcbnode* pt,int pn);進程初始化類：void initialqueue(lq& q,pcbnode* pt,int pn);時間片輪轉類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);先來先服務類：void fcfs(lq& q,int& ttimesum,int& wttimesum,pcbnode* pt);實驗環(huán)境：c+語言程序設計平臺算法流程設計：開始在input文件中輸入各個進程的從開始到全部進入就緒隊列所需時間、剩余運行時間、優(yōu)先數(shù)，一行一進程輸入進程數(shù)和時間片大小初始化就緒隊列，將文件中進程投入運行等待隊列為空為隊列首進程分配時間片進程在時間片內做完計算周轉時間和帶權周轉時間將該進程退出隊列，計算周轉時間和帶權周轉時間將文件中的作業(yè)（進程）投入隊列運行并確定其開始和完成時間運行隊首作業(yè)，計算周轉時間和帶權周轉時間，退出隊列計算時

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

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

6、y;/優(yōu)先數(shù) int trtime;/總運行時間 int rtime;/剩余運行時間 int atime;/從開始到全部進入就緒隊列所需的時間 int stime;/開始運行時間 int ftime;/完成運行時間 int ttime;/周轉時間 float wttime;/帶權周轉時間;struct qnode/進程隊列 int id; struct qnode* next;/隊列中下一個進程指針;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;/進程數(shù) int piece;/時間片大小 int ttimesum=0;/周轉時間 int wttimesu

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

9、ttimesum/pnendl; input(pt,pn); initialqueue(q,pt,pn); fcfs(q,ttimesum,wttimesum,pt);/先來先服務作業(yè)調度 cout先來先服務的平均周轉時間為：ttimesum/pnendl; cout先來先服務的平均帶權周轉時間為：wttimesum/pnendl; delete pt; return 0;void input(pcbnode* pt,int pn)file* fp;/讀入進程相關內容 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);/輸入各進程從開始到全部進入就緒隊列所需的時間、剩余運行時間、優(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;/總的周轉時間 wttimesum=0;/平均周轉時間 int ctime=0;/當前時間 qnode* p; qnode* q; qnode* r; bool finish=false;/調用deal()后，該進程是否已經做完退出 p=q.head; q=p-next; while(q!=null)/從隊列首部開始依次分配時間片 do cout*endl; cout在時間片(ctime+1)/piece+1內，活動進程

12、為：idendl; cout進程id 現(xiàn)在需要的時間片為：id.rtimeendl; finish=deal(q,q,p,piece,ctime,pt);/分配時間片給q進程 coutnext=null) r=q.head-next; else r=q-next; else /若未做完，計算周轉時間和帶權周轉時間 ttimesum+=ptq-id.ttime; wttimesum+=ptq-id.wttime; delete q;/刪除q進程 q=p; while(!finish&(ptr-id.atimectime+piece); p=q;/若下個進程不來，則繼續(xù)給當前進程分配時間片 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所指進程，p為剛退出的進程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進程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;/平均周轉時間 wttimesum=0;/平均帶權周轉時間 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/若下個進程到達時間較晚 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)/計算平均周轉時

16、間和平均帶權周轉時間 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：進程id活動next!=null) cout時刻t：進程id結束活動，開始下一個進程。endl; cout進程id的周轉時間為：id.ttimeendl; cout進程id的帶權周轉時間為：id.wttimeendlendl; else cout時刻t：進程id結束活動。endlendl; cout進程id的周轉時間為：id.ttimeendl; cout進程id的帶權周轉時間為：id.wttimeendlendl; cout所有進程