操作系統(tǒng)課程設(shè)計-進程調(diào)度模擬設(shè)計--先來先服務(wù)-優(yōu)先級法

1、武漢理工大學(xué)系統(tǒng)軟件開發(fā)實訓(xùn)A課程設(shè)計說明書學(xué) 號： 課 程 設(shè) 計課程名字系統(tǒng)軟件開發(fā)實訓(xùn)A題 目進程調(diào)度模擬設(shè)計先來先服務(wù)、優(yōu)先級法學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)計算機科學(xué)與技術(shù)專業(yè)班 級姓 名指導(dǎo)教師李玉強2014年01月13日課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級： 指導(dǎo)教師： 李玉強 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題 目: 進程調(diào)度模擬設(shè)計先來先服務(wù)、優(yōu)先級法 初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求

2、）1模擬進程調(diào)度，能夠處理以下的情形： 能夠選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）； 能夠輸入進程的基本信息，如進程名、優(yōu)先級、到達時間和運行時間等； 根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列； 根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2設(shè)計報告內(nèi)容應(yīng)說明： 課程設(shè)計目的與功能； 需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)； 源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)。時間安排：設(shè)計安排3周：查閱、分析資料 1天系統(tǒng)軟件的分析與建模 4天系統(tǒng)軟件的設(shè)計 5天系統(tǒng)軟件的實現(xiàn) 3天撰寫文檔 1天課程設(shè)計驗收答辯 1天設(shè)計驗收安排：設(shè)計周的第三周的指定時間到實

3、驗室進行上機驗收。設(shè)計報告書收取時間：課程設(shè)計驗收答辯完結(jié)時。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記）指導(dǎo)教師簽名： 2013 年 12 月 10日系主任（或責(zé)任教師）簽名： 2013 年 12 月 10日課程設(shè)計報告書1.需求分析 1.1設(shè)計目的(1)閱讀操作系統(tǒng)的處理機管理章節(jié)內(nèi)容，對進程調(diào)度的功能以及進程調(diào)度算法有深入的理解。(2)掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求） 1.2程序流程圖開 始選擇調(diào)度算法先來先服務(wù)法輸入進程隊列信息優(yōu)先級法結(jié)束？Y/N結(jié) 束YN切 換 算 法1.3設(shè)計要求(1)能夠

4、選擇不同的調(diào)度算法（要求中給出的調(diào)度算法）；(2)能夠輸入進程的基本信息，如進程名、優(yōu)先級、到達時間和運行時間等；(3)根據(jù)選擇的調(diào)度算法顯示進程調(diào)度隊列；(4)根據(jù)選擇的調(diào)度算法計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。2.功能設(shè)計 2.1數(shù)據(jù)結(jié)構(gòu)1. 進程的結(jié)構(gòu)定義：struct processchar name10; /進程名int no; /進程序號double arrivetime; /進程達到時間double needtime; /進程運行時間 double starttime; /進程開始時間double endtime; /進程結(jié)束時間int state; /進程狀態(tài)，0表示未執(zhí)行，

5、1表示已執(zhí)行int priority; /進程優(yōu)先級process *next; process *head=Null;int count; ；2.使用鏈表存儲進程并按照到達時間排序、開始鏈表空？只有一節(jié)點比較當前節(jié)點的到達時間與連續(xù)兩個節(jié)點（p1,p1-next）的到達時間至少兩個節(jié)點結(jié) 束YN插 到 鏈 頭比較當前節(jié)點與已存在節(jié)點的到達時間在兩節(jié)點之間？插入它們之間插 入p1=p1-nextvoid insert(process *current) if (head!=Null)if(head-next=Null) /如果只有一個節(jié)點if(current-arrivetimearrivet

6、ime) /如果比鏈頭到達時間早，則插入鏈頭current-next=head;head=current;elsecurrent-next=Null;head-next=current; else /如果至少兩個節(jié)點 process *p1=head; if(head-arrivetime current-arrivetime ) current-next=head; head=current; else int flag=1; while(p1-next!=Null) /當head后面不為空時一直做 /如果在兩個節(jié)點間 if(p1-arrivetime arrivetime & p1-nex

7、t-arrivetime current-arrivetime) current-next=p1-next; p1-next=current; flag=0; break; else p1=p1-next; /如果到達時間最大，則插到鏈尾 if (flag=1) p1-next=current; current-next=Null; else head=current;2.2先來先服務(wù)算法設(shè)計 1.FCFS算法說明將用戶作業(yè)和就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進行調(diào)度處理，是一種最普遍和最簡單的方法。在該算法中，每個作業(yè)或進程按照它們在隊列中等待時間長短來決

8、定它們是否優(yōu)先享受服務(wù)。在沒有特殊理由要優(yōu)先調(diào)度某類作業(yè)或進程時，從處理的角度來看，F(xiàn)CFS方式是一種最合適的方法，因為無論是追加還是取出一個隊列元素在操作上都是最簡單的。2.創(chuàng)建進程void createFCFS() process *q1=new process ; coutcount; coutendl; int number=1; while(numberno=number; cout進程序號numberendl; coutq1-name; coutq1-arrivetime; coutq1-needtime; q1-next=NULL; insert(q1); number+; co

9、utendlnextP=null結(jié) 束YN前一個結(jié)束，后一個進程是否到達p節(jié)點：開始時間=到達時間 結(jié)束時間=開始時間+執(zhí)行時間 系統(tǒng)時間=結(jié)束時間并計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間P=head-nextNp節(jié)點：開始時間=系統(tǒng)時間 結(jié)束時間=開始時間+執(zhí)行時間 系統(tǒng)時間=結(jié)束時間并計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間P=head-nextYvoid printFCFS() process *p=new process; double systime=0; /記錄系統(tǒng)時間 double turn=0; /平均周轉(zhuǎn)時間 double turnw=0; /平均帶權(quán)周轉(zhuǎn)時間 if(head=NULL) cout沒有

10、進程調(diào)度starttime=head-arriveTime; head-endtime=head-arrivetime+head-needtime; systime=head-endtime; turn=turn+(head-endtime - head-arrivetime); turnw=turnw+(head-endtime - head-arrivetime) / head-needtime; p=head-next; while(p!=NULL) if(p-arrivetimesystime) /如果前一個結(jié)束后一個還沒到達 p-starttime=p-arrivetime; p-e

11、ndtime=p-starttime+p-needtime; systime=p-endTime; turn=turn+(p-endtime-p-arrivetime); turnw=turnw+(p-endtime-p-arrivetime)/p-needtime; p=p-next; else /如果前一個未結(jié)束時后一個已經(jīng)到達 p-starttime=systime; p-endtime=p-starttime+p-needtime; systime=p-endtime; turn=turn+(p-endtime-p-arrivetime); turnw=turnw+(p-endtime

12、-p-arrivetime)/p-needtime; p=p-next; cout.setf(ios:left); /設(shè)置對齊方式為left coutsetw(10)進程序號setw(10)進程名setw(10)到達時間setw(10)開始時間setw(10)執(zhí)行時間setw(10)結(jié)束時間endl; process *temp=head; while(temp!=NULL) cout.setf(ios:left); coutsetw(10)nosetw(10)namesetw(10)arriveTimesetw(10)startTimesetw(10)needTimesetw(10)endT

13、imenext; cout平均周轉(zhuǎn)時間turn/countendl平均帶權(quán)周轉(zhuǎn)時間turnw/countnext!=NULL) /回收空間 process *t=new process; t=head-next; head-next=t-next; delete t; head=NULL; 2.3 優(yōu)先級算法的設(shè)計1.PIRO算法及說明 優(yōu)先級法可被用作作業(yè)或進程的調(diào)度策略。首先，系統(tǒng)或用戶按某種原則為作業(yè)或進程指定一個優(yōu)先級來表示該作業(yè)或進程所享有的調(diào)度優(yōu)先權(quán)。該算法的核心是確定進程或作業(yè)的優(yōu)先級。 確定優(yōu)先級的方法可分為兩類。即動態(tài)法和靜態(tài)法靜態(tài)法根據(jù)作業(yè)或進程的靜態(tài)特性，在作業(yè)或進程開始

14、執(zhí)行之前就確定它們的優(yōu)先級，一旦開始執(zhí)行之后就不能改變。動態(tài)法則不然，它把作業(yè)或進程的靜態(tài)特性和動態(tài)特性結(jié)合起來確定作業(yè)或進程的優(yōu)先級，隨著作業(yè)或進程的執(zhí)行過程，其優(yōu)先級不斷變化。 靜態(tài)優(yōu)先級中，可以由用戶自己根據(jù)作業(yè)的緊急程度輸入一個適當?shù)膬?yōu)先級，為防止各用戶都將自己的作業(yè)冠以高優(yōu)先級，系統(tǒng)應(yīng)對高優(yōu)先級用戶收取較高的費用；也可以由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級。動態(tài)優(yōu)先級中，基于靜態(tài)優(yōu)先級的調(diào)度算法實現(xiàn)簡單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變，從而系統(tǒng)效率較低，調(diào)度性能不高?，F(xiàn)在的操作系統(tǒng)中，如果使用優(yōu)先級調(diào)度的話，則大多采用動態(tài)優(yōu)先級的調(diào)度策略。2.

15、創(chuàng)建進程void createPRIO() process *q1=new process; coutcount; coutendl; int number=1; while(numberno=number; cout進程序號numberendl; coutq1-name; coutq1-priority; coutq1-arriveTime; coutq1-needTime; q1-next=NULL; insert(q1); number+; coutendl2) process *n0=head; process *n1=n0-next; process *n2=n1-next; for

16、(int i=0;iarrivetime arrivetime priority priority) n1-next=n2-next; n0-next=n2; n2-next=n1; n1=n0-next; n2=n0-next-next; n0=n1; n1=n2; n2=n2-next; 4.輸出調(diào)度結(jié)果開 始鏈表空？Head節(jié)點：開始時間=到達時間 結(jié)束時間=開始時間+執(zhí)行時間 系統(tǒng)時間=結(jié)束時間并計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間P=head-nextP=null結(jié) 束N到達&未執(zhí)行p節(jié)點：開始時間=系統(tǒng)時間 結(jié)束時間=開始時間+執(zhí)行時間 系統(tǒng)時間=結(jié)束時間標記為已執(zhí)行并計算周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)

17、時間P=head-nextYvoid printPRIO() process *p=new process; double sysTime=0; /記錄系統(tǒng)時間 double turn=0; /平均周轉(zhuǎn)時間 double turnw=0; /平均帶權(quán)周轉(zhuǎn)時間 if(head=NULL) cout沒有進程調(diào)度！starttime=head-arrivetime; head-endtime=head-arrivetime+head-needtime; head-state=1; systime=head-endtime; turn=turn+(head-endtime - head-arrivet

18、ime); turnw=turnw+(head-endtime - head-arrivetime) / head-needtime; /判斷后面的 for(int i=0;inext; while(p!=NULL) changePRIO(double systime); /如果優(yōu)先級最大的進程已經(jīng)到達，則執(zhí)行 if(p-arrivetime state=0) p-starttime=systime; p-endtime=p-arrivetime+p-needtime; systime=p-endtime; p-state=1; turn=turn+(p-endtime-p-arrivetim

19、e); turnw=turnw+(p-endtime-p-arrivetime)/p-needtime; p=p-next; else p=p-next; process *temp=head; cout.setf(ios:left); coutsetw(10)進程序號setw(10)進程名setw(10)優(yōu)先級setw(10)到達時間setw(10)開始時間setw(10)執(zhí)行時間setw(10)結(jié)束時間endl; while(temp!=NULL) coutsetw(10)nosetw(10)namesetw(10)prioritysetw(10)arriveTimesetw(10)sta

20、rtTimesetw(10)needTimesetw(10)endTimenext; cout平均周轉(zhuǎn)時間：turn/countendl平均帶權(quán)周轉(zhuǎn)時間：turnw/countnext!=NULL) process *t=new process; t=head-next; head-next=t-next; delete t; head=NULL; 3. 源程序的主要部分 主程序主要完成調(diào)用各個函數(shù)完成相應(yīng)的功能，以及選擇調(diào)度算法的輸出提示，根據(jù)提示并完成相應(yīng)的算法實現(xiàn)過程。/程序主要部分int main()int choice; /選擇服務(wù)int go=1;while (go)coutend

21、lendl-進程調(diào)度模擬設(shè)計-endlendl; cout1.先來先服務(wù)算法endl2.優(yōu)先級法endl3.退出endlendl;coutchoice；switch(choice) case 1:FCFS();break; /調(diào)用先來先服務(wù)算法 case 2:PRIO();break; /調(diào)用優(yōu)先計算法 case 3:cout退出endl; go=0;break; /退出，返回首頁 default:cout選擇有誤，請重新輸入選擇！endl;break;system(pause);return 0;void FCFS() createFCFS(); printFCFS(); void PRIO

22、() createPRIO(); /changePRIO(); printPRIO(); 4.程序測試4.1先來先服務(wù)測試用例進程序號進程名稱到達時間執(zhí)行時間1a042b133c224d334.2先來先服務(wù)運行結(jié)果進程序號進程名稱優(yōu)先級到達時間執(zhí)行時間1a1042b4163c2244d3354.3先來先服務(wù)測試用例4.4優(yōu)先級算法運行結(jié)果5.自我評價與總結(jié)本次課程設(shè)計的內(nèi)容基本上是老師在課堂上所講的，所以我還是比較熟悉先來先服務(wù)算法和優(yōu)先級算法?？吹竭@個題目時，我還是感覺相當輕松的，因為我還是比較熟悉該內(nèi)容，比較熟悉算法思想。設(shè)計過程中要注意流程的條理清晰，易于讀懂和規(guī)劃，程序編寫完成以后，實

23、現(xiàn)了預(yù)期的效果，達到了設(shè)計的要求。界面設(shè)計比較清晰明了，易于閱讀和理解。本程序中，有些地方有重復(fù)，可以通過設(shè)計函數(shù)來簡化程序，例如程序的創(chuàng)建，可以通過函數(shù)調(diào)用來實現(xiàn)，從而不必在兩個算法中分別編寫。編寫程序時要先畫出程序的流程圖是非常有必要的，根據(jù)流程圖的順序來實現(xiàn)程序，并要注意合理的使用函數(shù)調(diào)用來使程序得到簡化，并且易讀易懂。編寫程序的時候一定要先畫流程圖，對應(yīng)流程圖設(shè)計函數(shù)來簡化程序。這次課程設(shè)計中比較失敗的地方就是優(yōu)先級算法的輸出開始時間和結(jié)束時間出了點問題。 這次課程設(shè)計使得我受益匪淺，尤其是對優(yōu)先級調(diào)度分析方法有了更深的理解和掌握。通過這次課程設(shè)計，我的編程能力又得到了進一步的提高，同

24、時也培養(yǎng)了我的思維能力?？偟恼f來，這次課程設(shè)計不僅豐富了我的理論知識，也加強了我的動手能力，還鍛煉了我的思維能力。在實驗程序編寫和調(diào)試過程中我學(xué)會了很多，也認識到了自己的不足，我還需要進一步的努力，以致取得更大的進步。我需要的就是要對自己有信心，腳踏實地，持之以恒，遇到困難時要冷靜思考，勇敢面對，直到得出結(jié)果。在實驗設(shè)計過程中，我也養(yǎng)成了較好地習(xí)慣，先有框架，然后跟著框架發(fā)展，最后就是要注重細節(jié)，要做到嚴謹和縝密。不可否認這種好習(xí)慣讓我受益無限，我也必須擁有它，以致我獲得更多。6.源程序#include#include#includestruct processchar name10; /進程

25、名int no; /進程序號double arrivetime; /進程達到時間double needtime; /進程運行時間 double starttime; /進程開始時間double endtime; /進程結(jié)束時間int state; /進程狀態(tài)int priority; /進程優(yōu)先級process *next; process *head=Null;int count; ；void FCFS();void PRIO();void createFCFS();void insert(process *current); void printFCFS();void createPRIO

26、();void changePRIO(double systime); void printPRIO() ;/程序主要部分int main()int choice; /選擇服務(wù)int go=1;while (go)coutendlendl-進程調(diào)度模擬設(shè)計-endlendl; cout1.先來先服務(wù)算法endl2.優(yōu)先級法endl3.退出endlendl;coutchoice；switch(choice) case 1:FCFS();break; /調(diào)用先來先服務(wù)算法 case 2:PRIO();break; /調(diào)用優(yōu)先計算法 case 3:cout退出endl; go=0;break; /退

27、出，返回首頁 default:cout選擇有誤，請重新輸入選擇！next=Null) /如果只有一個節(jié)點if(current-arrivetimearrivetime) /如果比鏈頭到達時間早，則插入鏈頭current-next=head;head=current;elsecurrent-next=Null;head-next=current; else /如果至少兩個節(jié)點 process *p1=head; if(head-arrivetime current-arrivetime ) current-next=head; head=current; else int flag=1; whi

28、le(p1-next!=Null) /當head后面不為空時一直做 /如果在兩個節(jié)點間 if(p1-arrivetime arrivetime & p1-next-arrivetime current-arrivetime) current-next=p1-next; p1-next=current; flag=0; break; else p1=p1-next; /如果到達時間最大，則插到鏈尾 if (flag=1) p1-next=current; current-next=Null; else head=current;void createFCFS() process *q1=new

29、process ; coutcount; coutendl; int number=1; while(numberno=number; cout進程序號numberendl; coutq1-name; coutq1-arrivetime; coutq1-needtime; q1-next=NULL; insert(q1); number+; coutendlendl; void printFCFS() process *p=new process; double systime=0; /記錄系統(tǒng)時間 double turn=0; /平均周轉(zhuǎn)時間 double turnw=0; /平均帶權(quán)周轉(zhuǎn)時

30、間 if(head=NULL) cout沒有進程調(diào)度starttime=head-arriveTime; head-endtime=head-arrivetime+head-needtime; systime=head-endtime; turn=turn+(head-endtime - head-arrivetime); turnw=turnw+(head-endtime - head-arrivetime) / head-needtime; p=head-next; while(p!=NULL) if(p-arrivetimesystime) /如果前一個結(jié)束后一個還沒到達 p-start

31、time=p-arrivetime; p-endtime=p-starttime+p-needtime; systime=p-endTime; turn=turn+(p-endtime-p-arrivetime); turnw=turnw+(p-endtime-p-arrivetime)/p-needtime; p=p-next; else /如果前一個未結(jié)束時后一個已經(jīng)到達 p-starttime=systime; p-endtime=p-starttime+p-needtime; systime=p-endtime; turn=turn+(p-endtime-p-arrivetime);

32、turnw=turnw+(p-endtime-p-arrivetime)/p-needtime; p=p-next; cout.setf(ios:left); /設(shè)置對齊方式為left coutsetw(10)進程序號setw(10)進程名setw(10)到達時間setw(10)開始時間setw(10)執(zhí)行時間setw(10)結(jié)束時間endl; process *temp=head; while(temp!=NULL) cout.setf(ios:left); coutsetw(10)nosetw(10)namesetw(10)arriveTimesetw(10)startTimesetw(1

33、0)needTimesetw(10)endTimenext; cout平均周轉(zhuǎn)時間turn/countendl平均帶權(quán)周轉(zhuǎn)時間turnw/countnext!=NULL) /回收空間 process *t=new process; t=head-next; head-next=t-next; delete t; head=NULL; void createPRIO() process *q1=new process; coutcount; coutendl; int number=1; while(numberno=number; cout進程序號numberendl; coutq1-name; coutq1-priority; coutq1-arriveTime; coutq1-needTime; q1-next=NULL; insert(q1); number+; coutendl2) process *n0=head; process *n1=n0-next; process *n2=n1-next; for(int i=0;iarri