1、學 號： 課 程 設 計題 目進程調度模擬設計時間片輪轉、強占式短進程優先算法學 院計算機科學與技術學院專 業班 級姓 名指導教師吳利軍2013年1月16日課程設計任務書學生姓名： 指導教師：吳利軍 工作單位： 計算機科學與技術學院 題 目: 進程調度模擬設計時間片輪轉、強占式短進程優先算法 初始條件：1預備內容：閱讀操作系統的處理機管理章節內容，對進程調度的功能以及進程調度算法有深入的理解。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）1模擬進程調度，能夠處理以下的情形： 能夠選擇不同的調度算法（要求中給出的調度算

2、法）； 能夠輸入進程的基本信息，如進程名、到達時間和運行時間等； 根據選擇的調度算法顯示進程調度隊列； 根據選擇的調度算法計算平均周轉時間和平均帶權周轉時間。2設計報告內容應說明： 需求分析； 功能設計（數據結構及模塊說明）； 開發平臺及源程序的主要部分； 測試用例，運行結果與運行情況分析； 自我評價與總結：i）你認為你完成的設計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設計得到的收獲（在編寫，調試，執行過程中的經驗和教訓）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；時間安排：設計安排一周：周1、周2：完成程序分析及設計。周2、周3：完成程

3、序調試及測試。周4、周5：驗收、撰寫課程設計報告。（注意事項：嚴禁抄襲，一旦發現，一律按0分記）指導教師簽名： 年 月 日系主任（或責任教師）簽名： 年 月 日進程調度模擬設計時間片輪轉、強占式短進程優先算法一、需求分析本次課程設計需要通過設計一個模擬進程調度的系統，來實現進程調度過程的模擬，對進程調度的功能以及進程調度的算法有更加深層次的理解。時間片輪轉法的基本思路是每個進程被分配一個時間段，稱作它的時間片，即該進程允許運行的時間。如果在時間片結束時進程還在運行，則CPU將被剝奪并分配給另一個進程。如果進程在時間片結束前阻塞或結束，則CPU當即進行切換。調度程序所要做的就是維護一張就緒進程列

4、表，當進程用完它的時間片后，它被移到隊列的末尾。這樣讓每個進程在就緒隊列中的等待時間與享受服務的時間成正比例。在批處理為主的系統中，如果采用FCFS方式進程作業調度，雖然系統開銷小，算法簡單，但是，如果估計執行時間很短的作業時在那些長作業的后面到達系統的話，則必須等待長作業執行完成之后才有機會獲得執行。這將造成不必要的等待和不公平，最短作業優先法就是選擇那些估計需要執行時間最短的作業投入執行，為它們創建進程和分配資源。直觀上說，采用最短作業優先的調度算法，可使得系統在同一時間內處理的作業個數最多，從而吞吐量也就大于其它調度方式。按照需求有以下條件：進程PCB（包含進程名、到達時間、預計運行時間

5、等）調度算法（時間片輪轉、強占式短進程優先）為完成這兩種算法的調度模擬，需要用高級語言編程完成模擬操作，能夠處理以下的情形：（1）能夠選擇不同的調度算法（要求中給出的調度算法）（2）能夠輸入進程的基本信息，如進程名、到達時間和運行時間等（3）根據選擇的調度算法顯示進程調度隊列（4）根據選擇的調度算法計算平均周轉時間和平均帶權周轉時間該設計中的進程調度模擬系統在使用時，用戶可以輸入各進程信息（包含進程名、到達時間、估計運行時間）；輸入完畢確認后，可選擇兩種調度算法中的一種執行，查看結果可得到相應算法的調度序列，每個進程的到達時間、預計運行時間、開始時間、結束時間和周轉時間、帶權周轉時間，以及平均

6、周轉時間和平均帶權周轉時間。二、功能設計2.1 進程信息的描述和實現此次課程設計中，進程作為基本數據處理單元，需要對進程的基本信息進行相關的描述。進程的基本信息包括進程進程名、到達的時間、預計的進程運行時間、進程開始運行時間、進程仍需運行的時間、進程完成的時間、進程運行的次數等。在此，定義一個類來抽象進程。并在此基礎上進行其他操作。數據結構方案聲明如下： class ProcePcb public :ProcePcb (string name,int sub,int exe,int id) : pro_name(name),time_submit(sub),time_exe(exe),pro_

7、id(id), time_start(0),time_end(0),time_wait(0),pro_state(READY),time_left(exe), time_turn(0),time_aver(0.0)/默認構造函數ProcePcb () : pro_name (string( ), time_submit(0),time_exe(0),pro_id(-1), time_end(0),time_start(0),time_wait(0),pro_state(READY),time_left(0), time_turn(0),time_aver(0.0) /Getters and S

8、ettersstring getPro_name () return pro_name ;int getTime_submit () return time_submit ;int getTime_exe () return time_exe ;int getPro_id () return pro_id ;int getTime_start () return time_start ; int getTime_wait () return time_start ; int getPro_state () return pro_state ;int getTime_left () return

9、 time_left ;int getTime_turn () return time_turn ;int getTime_aver () return time_aver ;void setTime_start (int start) time_start = start ; /設置開始時間void setTime_left (int left) time_left = left ;void setTime_end (int end) time_end = end ; /設置結束時間void setPro_state (int state) pro_state = state ; /設置進程

10、的狀態/.打印進程的信息void PrintPcbInfo () ; / /.進程執行模擬bool ProceExe(int) ; /參數為時間單位,返回CPU是否執行完畢/內部邏輯計算 包括周轉時間以及帶權周轉時間的計算void CalTimeLogic() ;protected:/進程的名字string pro_name ;/提交時間-用十進制封裝int time_submit ; /從時間的1開始計時/進程所需的運行時間 int time_exe ;/進程ID - 系統生成int pro_id ;/開始執行的時間int time_start ;/結束的時間int time_end ;/等

11、待的時間int time_wait ;/進程的狀態 (就緒，執行，完成)int pro_state ; /.上下文封裝int time_left ; /還需多少時間單位,初始化為所需的執行時間/周轉時間int time_turn ;/帶權周轉時間float time_aver ; ; 2.2 調度算法的描述和實現進程基本信息所構成的模塊作為基本單元，并且相關調度算法的側重進程基本信息點不同，所以要根據其調度算法的特點來結合基本信息進行對應的設計。此次課程設計要求的調度算法描述如下：2.2.1 時間片輪轉調度算法時間片輪轉法的中心思想在于將CPU的運行劃分為一個個時間片，然后將這些時間片平均分配

12、給已經準備就緒的進程，在一個時間片內只允許一個進程占用處理器。如果當前進程運行結束則時間片終止。這樣可以較公平的分配處理器運行時間，使每個進程都可以得到處理。2.2.2 強占式短進程優先調度算法對強占式短進程優先調度算法而言，其本質特征便是按進程的預計運行時間長短進行排序，先執行短進程。若內存中運行的進程優先級比就緒隊列中的某進程優先級低（即運行的進程預計運行時間比就緒隊列中的某進程長），此運行的進程讓出內存并進入就緒隊列，優先級更高的短進程強占內存資源并運行直到結束或者遇到優先級更高的進程強占為止。2.2.3 模塊說明：class CPUModel /CPU功能模塊的封裝public :CP

13、UModel () :pcbnum(0),idCount(0),allturn(0),allaver(0.0) /從用戶界面獲取進程void GetPcb (pcbList &) ;/.CPU開始執行程序void ExeProce(pcbList &) ;/時間片輪轉法模擬程序void RRModel(pcbList&) ; /不能改變原隊列/搶占式短進程優先void SJF_Grab(sjfList) ;/.獲取當前時刻之前的最短進程在隊列中的標號int GetTheSP(sjfList ,int) ; /隊列為排序之后的隊列/.獲取下一個進程IDint GetNextId() ;/打印就緒

14、隊列中的進程的信息void PrintList(pcbList) ;int getPcbnum () return pcbnum ; /.bool IsProComing(int) ; /.當前時刻時是否有新的進程到達/.將就緒隊列按提交時間排序void SortTheList(sjfList) ;bool IsOver(sjfList) ; /是否所有的進程都執行完畢private :/進程數量int pcbnum ;int idCount ; /進程ID計數int allturn ; /總周轉時間float allaver ; /總帶權周轉時間 ;下面為較為重要的幾個函數：void Pro

15、cePcb:PrintPcbInfo () /打印信息void ProcePcb:CalTimeLogic() /內部邏輯計算bool ProcePcb:ProceExe(int time) /進程執行模擬void CPUModel:GetPcb (pcbList & list) /獲取用戶需要建立的進程，入就緒隊列void CPUModel:PrintList(pcbList list) /打印就緒隊列中的進程的信息void CPUModel:ExeProce (pcbList & list) 進程調度主過程void CPUModel:RRModel(pcbList & list) /時間片

16、輪轉法模擬void CPUModel:SJF_Grab(sjfList list) /強占式短進程優先模擬程序的主程序流程如下：int main () CPUModel cpu ;cpu.GetPcb(pcblist) ;cpu.PrintList(pcblist) ;cpu.ExeProce(pcblist) ;return 0 ;三、開發平臺Microsoft Windows 7操作系統；Microsoft Visual 2010。四、源程序的主要部分4.1. 時間片輪轉法模擬部分：void CPUModel:RRModel(pcbList & list) static int rtime

17、 = 1 ; /表示時鐘if(list.size() = 0)return ;/.不斷的從就緒隊列中取進程執行/*時間片輪轉的模型是：時間片為1秒 進程各個時間都以十進制來簡化進程正在執行時打印其信息并讓主CPU停頓1秒以表示執行進程一個時間單位*/ ProcePcb pcb ; /每次執行的進程/設置一個輪轉隊列pcbList rrlist ;while (1) /查找當前時間下已經提交的進程入輪轉隊列if(IsProComing(rtime)while(readylist.size() != 0 & IsProComing(rtime + 1) /先對隊列判空是必須的ProcePcb pc

18、b = readylist.front() ;rrlist.push(pcb) ;readylist.pop() ;/下面的程序操作輪轉隊列if(rrlist.size() = 0 ) /查看最早提交的進程cout TIME: 第 rtime 秒：endl ;cout 沒有進程提交！endl ;+rtime ; Sleep(1000) ; /消耗CPU時間1秒continue ; /./.每次從隊列中取第一個進程pcb = rrlist.front() ;rrlist.pop() ; /先進行進程邏輯維護pcb.setPro_state(EXECUTE) ; /設置執行狀態if(pcb.get

19、Time_start() = 0)pcb.setTime_start(rtime) ; /設置開始時間bool result = false ;result = pcb.ProceExe(1) ; /進程執行一個時間單位cout TIME: 第 rtime 秒：endl ;cout正在調度執行的進程：endl;pcb.PrintPcbInfo() ; /打印正在執行的進程的信息if(result)/進程執行完畢pcb.setPro_state(END) ;pcb.setTime_end(rtime) ; /結束的時間/CPU調度統計計算pcb.CalTimeLogic() ;allturn +

20、= pcb.getTime_turn() ;allaver += pcb.getTime_aver() ;/.cout進程:endl ;pcb.PrintPcbInfo() ;cout執行完畢endl ;else/執行完一個時間片后進程仍然沒有完畢/則要查看下一個進程是否已經提交. 現在設置了輪轉隊列不要進行這個判斷pcb.setPro_state(READY) ;/設置進程的狀態為就緒rrlist.push(pcb) ; /入輪轉隊列if(rrlist.size() = 0 & readylist.size() = 0)/所有進程調度執行完畢cout TIME: 第 rtime 秒：endl

21、 ;cout所有的進程執行完畢，退出時間片輪轉法模擬模塊程序！endl ;cout輪轉法調度結果統計:endl ;cout總進程數：pcbnum 個 endl ;cout平均周轉時間 : (float)allturn/pcbnumendl ;cout平均帶權周轉時間 : allaver/pcbnumendl ;coutendl ;break ;+rtime ; Sleep(2000) ; /消耗CPU時間1秒4.2強占式短進程優先法部分：void CPUModel:SJF_Grab(sjfList list) if(list = NULL )return ;static int time =

22、1 ; /控制CPU的時鐘從1開始計時int pid = -1; /選取占有CPU的進程在隊列中的位置/.while(1) pid = GetTheSP(list,time) ;/獲取已經提交的進程中最短進程/進程尚未結束但是返回-1則說明當前時間還沒有提交任何進程if(!IsOver(list) & pid = -1)cout TIME: 第 time 秒：endl ;cout 沒有進程提交！endl ;+time ;Sleep(1000) ; /消耗CPU時間1秒continue ;else if(!IsOver(list) & pid != -1)/執行進程/先進行進程邏輯維護listp

23、id.setPro_state(EXECUTE) ; /設置執行狀態if(listpid.getTime_start() = 0)listpid.setTime_start(time) ; /設置開始時間bool result = false ;result = listpid.ProceExe(1) ; /進程執行一個時間單位cout TIME: 第 time 秒：endl ;cout正在調度執行的進程：endl;listpid.PrintPcbInfo() ; /打印正在執行的進程的信息if(result)/進程執行完畢listpid.setPro_state(END) ;listpid.

24、setTime_end(time) ; /結束的時間/CPU調度統計計算listpid.CalTimeLogic() ;allturn += listpid.getTime_turn() ;allaver += listpid.getTime_aver() ;/.cout進程:endl ;listpid.PrintPcbInfo() ;cout執行完畢endl ;+time ;Sleep(1000) ; /消耗CPU時間1秒else if(IsOver(list)/所有的進程執行完畢cout TIME: 第 time 秒：endl ;cout所有的進程執行完畢，退出強占式短進程優先法模擬程序！

25、endl ;cout強占式短進程優先法調度結果統計:endl ;cout總進程數：pcbnum 個 endl ;cout平均周轉時間 : (float)allturn/pcbnumendl ;cout平均帶權周轉時間 : allaver/pcbnumendl ;coutendl ;break ;五、測試用例進程名：a 到達時間：1 預測運行時間：3進程名：b 到達時間：3 預測運行時間：5進程名：c 到達時間：5 預測運行時間：2依次輸入進程信息。輸入完畢后可顯示出所有進程信息，并可開始選擇使用哪種算法進行模擬調度，下面選擇1，時間片輪轉法，模擬開始。3秒末進程a 執行完畢，顯示其周轉時間和帶權周轉時間。10秒末進程c執行完畢，顯示其周轉時間和帶權周轉時間。11秒末進程b執行完畢，顯示其周轉時間和帶權周轉時間。所有調度完畢，顯示