進(jìn)程調(diào)度算法.doc

1 課程設(shè)計說明書 設(shè)計名稱 進(jìn)程調(diào)度算法設(shè)計 題 目 進(jìn)程調(diào)度算法設(shè)計 學(xué)生姓名 專 業(yè) 計算機(jī)應(yīng)用技術(shù) 班 級 09 計算機(jī)?？?學(xué) 號 309104 指導(dǎo)教師 日 期 2011 年 5 月 5 日 2 課程設(shè)計任務(wù)書 計算機(jī)應(yīng)用技術(shù) 專業(yè) 09 年級 ?？?班 一 一 設(shè)計題目設(shè)計題目 進(jìn)程調(diào)度算法的設(shè)計 二 二 主要內(nèi)容主要內(nèi)容 1 設(shè)計進(jìn)程控制塊 PCB 表結(jié)構(gòu) 分別適用于優(yōu)先數(shù)調(diào)度算法和循環(huán)輪轉(zhuǎn)調(diào) 度算法 2 建立進(jìn)程就緒隊列 對兩種不同算法編制入鏈子程序 3 編制兩種進(jìn)程調(diào)度算法 1 優(yōu)先數(shù)調(diào)度 2 循環(huán)輪轉(zhuǎn)調(diào)度 開發(fā)環(huán)境 VC 語言的編程環(huán)境 三 三 具體要求具體要求 1 本程序用兩種算法對五個進(jìn)程進(jìn)行調(diào)度 每個進(jìn)程可有三個狀態(tài) 并假 設(shè)初始狀態(tài)為就緒狀態(tài) 2 為了便于處理 程序中的某進(jìn)程運(yùn)行時間以時間片為單位計算 各進(jìn)程 的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進(jìn)程需運(yùn)行的時間片數(shù)的初始值均由用戶給 定 3 在優(yōu)先數(shù)算法中 優(yōu)先數(shù)的值為 50 與運(yùn)行時間的差值 即 P TIME process needtime 進(jìn)程每執(zhí)行一次 優(yōu)先數(shù)減 3 CPU 時間片數(shù)加 1 進(jìn)程還需要的時間片數(shù)減 1 在輪轉(zhuǎn)算法中 采用固定時間片 即 每執(zhí)行一次進(jìn)程 該進(jìn)程的執(zhí)行時間片數(shù)為已執(zhí)行了 2 個單位 這時 CPU 時間片數(shù)加 2 進(jìn)程還需要的時間片數(shù)減 2 并排列到就緒隊列的 尾上 4 對于遇到優(yōu)先數(shù)一致的情況 采用 FIFO 策略解決 開發(fā)環(huán)境 VC 語言的編程環(huán)境 四 進(jìn)度安排進(jìn)度安排 1 資料查找 系統(tǒng)分析 數(shù)據(jù)流程分析 概要設(shè)計 2 系統(tǒng)詳細(xì)設(shè)計 功能設(shè)計 3 3 算法實(shí)現(xiàn) 編程調(diào)試 4 資料整理 課程設(shè)計說明書編寫 五 五 完成后應(yīng)上交的材料完成后應(yīng)上交的材料 1 課程設(shè)計說明書 2 相關(guān)源程序文件 六 六 總評成績總評成績 指導(dǎo)教師 簽名日期 年 月 日 系 主 任 審核日期 年 月 日 4 目目 錄錄 一 設(shè)計目的 4 二 設(shè)計內(nèi)容 4 三 設(shè)計原理 5 3 1 優(yōu)先數(shù)調(diào)度算法 5 3 2 循環(huán)輪轉(zhuǎn)調(diào)度算法 5 四 設(shè)計步驟 5 4 1 任務(wù)分析 5 4 2 概要設(shè)計 6 4 3 詳細(xì)設(shè)計 6 4 4 流程圖 7 4 5 源程序 7 4 6 程序測試數(shù)據(jù)及結(jié)果 13 4 6 1 程序測試數(shù)據(jù) 13 4 6 2 運(yùn)用優(yōu)先數(shù)調(diào)度算法的執(zhí)行結(jié)果 如下圖 13 4 6 3 運(yùn)用循環(huán)輪轉(zhuǎn)調(diào)度算法的執(zhí)行結(jié)果 如下圖 14 五 設(shè)計總結(jié) 18 六 參考文獻(xiàn) 18 5 一一 設(shè)計目的設(shè)計目的 通過這次課程設(shè)計 加深理解有關(guān)進(jìn)程控制塊 進(jìn)程隊列的概念 并體會 和了解優(yōu)先數(shù)和循環(huán)輪轉(zhuǎn)調(diào)度算法的具體實(shí)施辦法 培養(yǎng)程序設(shè)計的方法和技 巧 提高編制清晰 合理 可讀性好的系統(tǒng)程序的能力 同時加深對操作系統(tǒng) 課程的理解 二二 設(shè)計內(nèi)容設(shè)計內(nèi)容 1 用語言來實(shí)現(xiàn)對 n 個進(jìn)程采用不同調(diào)度算法的進(jìn)程調(diào)度 2 每個用來標(biāo)識進(jìn)程的進(jìn)程控制塊 PCB 用結(jié)構(gòu)來描述 包括以下字段 1 進(jìn)程優(yōu)先數(shù) ID 其中 0 為閑逛進(jìn)程 用戶進(jìn)程的標(biāo)識數(shù)為 1 2 3 2 進(jìn)程優(yōu)先級 Priority 閑逛進(jìn)程 idle 的優(yōu)先級為 0 用戶進(jìn)程的 優(yōu)先級大于 0 且隨機(jī)產(chǎn)生 優(yōu)先數(shù)越大 優(yōu)先級越高 3 進(jìn)程占用的 CPU 時間 CPUtime 進(jìn)程每運(yùn)行一次 累計值等于 4 4 進(jìn)程總共需要運(yùn)行時間 Alltime 利用隨機(jī)函數(shù)產(chǎn)生 5 進(jìn)程狀態(tài) 0 就緒態(tài) 1 運(yùn)行態(tài) 2 阻塞態(tài) 6 隊列指針 next 用來將多個進(jìn)程控制塊 PCB 鏈接為隊列 3 優(yōu)先數(shù)改變的原則 1 進(jìn)程在就緒隊列中每呆一個時間片 優(yōu)先數(shù)增加 1 2 進(jìn)程每運(yùn)行一個時間片 優(yōu)先數(shù)減 3 4 在調(diào)度前 系統(tǒng)中擁有的進(jìn)程數(shù) PCB number 由鍵盤輸入 經(jīng)初始化后 所有的進(jìn)程控制塊 PCB 鏈接成就緒隊列 三三 設(shè)計原理設(shè)計原理 3 1 優(yōu)先數(shù)調(diào)度算法優(yōu)先數(shù)調(diào)度算法 對每個進(jìn)程確定一個優(yōu)先數(shù) 該算法總是讓優(yōu)先數(shù)最高的進(jìn)程先使用處理 器 對具有相同優(yōu)先數(shù)的進(jìn)程 再來采用先來先服務(wù)的次序分配處理器 系統(tǒng) 常與任務(wù)的緊迫性和系統(tǒng)效率等因素確定進(jìn)程的優(yōu)先數(shù) 進(jìn)程的優(yōu)先數(shù)可以固 定的 也可隨進(jìn)程執(zhí)行過程動態(tài)變化 一個高優(yōu)先數(shù)進(jìn)程占用處理器后 系統(tǒng) 處理該進(jìn)程時有兩種算法 一是 非搶占式 另一種是 可搶占式 前者是 次進(jìn)程占用處理器后一直運(yùn)行到結(jié)束 除非本身主動讓出處理器 后者則是嚴(yán) 格保證在任何時刻總是讓優(yōu)先數(shù)最高的進(jìn)程在處理器上運(yùn)行 3 2 循環(huán)輪轉(zhuǎn)調(diào)度算法循環(huán)輪轉(zhuǎn)調(diào)度算法 循環(huán)輪轉(zhuǎn)調(diào)度算法的具體原理是 每個進(jìn)程被分配一個時間片 即該進(jìn)程 允許運(yùn)行的時間 就緒的進(jìn)程都存放在一個就緒鏈表中 隊首的進(jìn)程將獲得時 6 間片 如果在時間片結(jié)束時進(jìn)程還在運(yùn)行 則 CPU 將剝奪并分配給下一個進(jìn)程 調(diào)度程序所要做的就是維護(hù)一張就緒進(jìn)程列表 當(dāng)進(jìn)程用完它的時間片后 它 被移到隊列的末尾 四 設(shè)計步驟四 設(shè)計步驟 4 1 任務(wù)分析任務(wù)分析 1 PCB 結(jié)構(gòu)通常包括以下信息 進(jìn)程名 進(jìn)程優(yōu)先數(shù) 輪轉(zhuǎn)時間片 進(jìn)程 已占用的 CPU 時間 進(jìn)程還需要的 CPU 時間 進(jìn)程的狀態(tài) 當(dāng)前隊列指針等 可根據(jù)實(shí)驗(yàn)的不同 PCB 結(jié)構(gòu)的內(nèi)容可以作適當(dāng)?shù)脑鰟h 2 本程序用兩種算法對五個進(jìn)程進(jìn)行調(diào)度 每個進(jìn)程可有三個狀態(tài) 就緒 執(zhí)行 完成 并假設(shè)初始狀態(tài)為就緒狀態(tài) 3 為了便于處理 程序中的某進(jìn)程運(yùn)行時間以時間片為單位計算 各進(jìn)程 的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進(jìn)程需運(yùn)行的時間片數(shù)的初始值均由用戶給定 4 在優(yōu)先數(shù)算法中 優(yōu)先數(shù)可以先取值為一個常數(shù)減去進(jìn)程所需要的時間 片數(shù)目 進(jìn)程每執(zhí)行一次 優(yōu)先數(shù)減 3 CPU 時間片數(shù)加 1 進(jìn)程還需要的時間 片數(shù)減 1 在輪轉(zhuǎn)算法中 采用固定時間片 即 每執(zhí)行一次進(jìn)程 該進(jìn)程的 執(zhí)行時間片數(shù)為已執(zhí)行了 2 個單位 這時 CPU 時間片數(shù)加 2 進(jìn)程還需要的 時間片數(shù)減 2 并排列到就緒隊列的尾上 5 對于遇到優(yōu)先數(shù)一致的情況 采用 FIFO 策略解決 4 2 概要設(shè)計概要設(shè)計 1 本程序用兩種算法對五個進(jìn)程進(jìn)行調(diào)度 每個進(jìn)程可有三個狀態(tài) 并假 設(shè)初始狀態(tài)為就緒狀態(tài) 2 為了便于處理 程序中的某進(jìn)程運(yùn)行時間以時間片為單位計算 各進(jìn)程 的優(yōu)先數(shù)或輪轉(zhuǎn)時間數(shù)以及進(jìn)程需運(yùn)行的時間片數(shù)的初始值均由用戶給定 3 在優(yōu)先數(shù)算法中 優(yōu)先數(shù)的值為 50 與運(yùn)行時間的差值 即 P TIME process needtime 進(jìn)程每執(zhí)行一次 優(yōu)先數(shù)減 3 CPU 時間片數(shù)加 1 進(jìn)程 還需要的時間片數(shù)減 1 在輪轉(zhuǎn)算法中 采用固定時間片 即 每執(zhí)行一次進(jìn) 程 該進(jìn)程的執(zhí)行時間片數(shù)為已執(zhí)行了 2 個單位 這時 CPU 時間片數(shù)加 2 進(jìn)程還需要的時間片數(shù)減 2 并排列到就緒隊列的尾上 4 對于遇到優(yōu)先數(shù)一致的情況 采用 FIFO 策略解決 4 3 詳細(xì)設(shè)計詳細(xì)設(shè)計 1 struct pcb 定義 pcb 塊 2 Void display 顯示結(jié)果信息函數(shù) 3 int process finish pcb q 進(jìn)程完成標(biāo)示 4 void display round 顯示循環(huán)輪轉(zhuǎn)調(diào)度算法運(yùn)行結(jié)果 5 priority cal 優(yōu)先數(shù)調(diào)度算法 7 6 void cpu round 處理器的工作狀態(tài) 4 4 流程圖流程圖 開始 生成并按生成次序 排列進(jìn)程控制塊鏈 鏈?zhǔn)走M(jìn)程投入運(yùn)行 時間片到 進(jìn)程時 間片減 1 優(yōu)先級減 3 撤銷該進(jìn)程 運(yùn)行進(jìn)程退出 取 鏈?zhǔn)走M(jìn)程投入運(yùn)行 時間片為 0 優(yōu)先級大于隊列中優(yōu)先 級最高的進(jìn)程 進(jìn)程隊列 為空 結(jié)束 4 5 源程序源程序 源程序如下 8 include include include include include include define P NUM 5 define P TIME 50 enum state ready execute block finish struct pcb char name 4 int priority int cputime int needtime int count int round state process pcb next pcb get process pcb get process pcb q pcb t pcb p int i 0 cout input name and time endl while i q name cin q needtime q cputime 0 q priority P TIME q needtime q process ready q next NULL if i 0 p q t q else t next q t q i while return p void display pcb p 9 cout name cputime needtime priority state endl while p cout name cout cout cputime cout cout needtime cout cout priority cout process case ready cout ready endl break case execute cout execute endl break case block cout block endl break case finish cout finish next int process finish pcb q int bl 1 while bl q q next return bl void cpuexe pcb q pcb t q int tp 0 while q if q process finish q process ready if q needtime 0 q process finish if tppriority t q q q next 10 if t needtime 0 t priority 3 t needtime t process execute t cputime void priority cal pcb p system cls p get process int cpu 0 system cls while process finish p cpu cout cputime cpu endl cpuexe p display p Sleep 100 getch system cls printf All processes have finished press any key to exit getch void display menu cout CHOOSE THE ALGORITHM endl cout 1 PRIORITY endl cout 2 ROUNDROBIN endl cout 3 EXIT endl pcb get process round pcb q pcb t pcb p int i 0 cout input name and time endl while i q name cin q needtime q cputime 0 q round 0 q count 0 11 q process ready q next NULL if i 0 p q t q else t next q t q i while return p void cpu round pcb q q cputime 2 q needtime 2 if q needtimeneedtime 0 q count q round q process execute pcb get next pcb k pcb head pcb t t k do t t next while t if t NULL t head while t next k return t void set state pcb p while p if p needtime 0 p process finish if p process execute p process ready 12 p p next void display round pcb p cout NAME CPUTIME NEEDTIME COUNT ROUND STATE endl while p cout name cout cout cputime cout cout needtime cout cout count cout cout round cout process case ready cout ready endl break case execute cout execute endl break case finish cout finish next void round cal pcb p pcb r system cls p get process round int cpu 0 system cls r p while process finish p cpu 2 cpu round r r get next r p cout cpu cpu endl display round p set state p Sleep 100 getch system cls void main 13 display menu int k scanf d switch k case 1 priority cal break case