簡介面向大二數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的任務(wù)調(diào)度器完整實(shí)現(xiàn)基于C/C在Visual Studio 2019環(huán)境下開發(fā)適合需要完成同類課題或希望深入理解任務(wù)調(diào)度與隊(duì)列、優(yōu)先級等數(shù)據(jù)結(jié)構(gòu)應(yīng)用的學(xué)生參考。壓縮包共38個(gè)文件約40.97MB包含源代碼文件cpp/hpp、Visual Studio工程文件sln/vcxproj/filters、編譯運(yùn)行產(chǎn)生的exe、pdb、obj及日志文件等打開工程即可查看完整實(shí)現(xiàn)并運(yùn)行驗(yàn)證。目前已有207人學(xué)習(xí)下載。資源提供可直接運(yùn)行的任務(wù)調(diào)度器Demo涵蓋任務(wù)隊(duì)列管理、優(yōu)先級調(diào)度等核心模塊代碼結(jié)構(gòu)清晰并附有類圖文件可幫助讀者快速理清模塊關(guān)系為課程設(shè)計(jì)答辯和功能擴(kuò)展提供實(shí)用參考。1. 任務(wù)調(diào)度器把數(shù)據(jù)結(jié)構(gòu)課上的「鏈表和堆」變成能跑出結(jié)果的完整工程每年數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目池里幾乎都會出現(xiàn)一個(gè)「任務(wù)調(diào)度器」。它聽起來像操作系統(tǒng)的事但實(shí)際上整份作業(yè)的核心矛盾只有一個(gè)一批任務(wù)在不同時(shí)刻到達(dá)每個(gè)任務(wù)要跑多久、優(yōu)先級多高各不相同你要用什么樣的數(shù)據(jù)結(jié)構(gòu)把它們組織起來才能讓「下一個(gè)該執(zhí)行誰」這個(gè)判斷既快又公平。這份用 C/C 寫成的課程設(shè)計(jì)資源把 FCFS先來先服務(wù)、SJF短作業(yè)優(yōu)先、時(shí)間片輪轉(zhuǎn)、優(yōu)先級調(diào)度四種算法全部落成了可編譯、可運(yùn)行、可出報(bào)告對比的工程。適合正在備戰(zhàn)的課設(shè)學(xué)生也適合想借一個(gè)真實(shí)項(xiàng)目復(fù)習(xí)鏈表、二叉堆和模擬器設(shè)計(jì)的開發(fā)者。你拿到的不是只貼代碼的片段而是覆蓋「設(shè)計(jì)—實(shí)現(xiàn)—測試—報(bào)告」全流程的完整交付物。2. 項(xiàng)目結(jié)構(gòu)拆解壓縮包里藏著「源碼 文檔」兩條線先分清再動手解壓之后先別急著點(diǎn)開 main.cpp。我見過太多人拿到課設(shè)資源第一件事就是找主函數(shù)結(jié)果被十幾個(gè)文件繞暈最后連編譯都過不去。這份資源遵循了課程設(shè)計(jì)最常見的「雙軌」組織方式一條線是能編譯運(yùn)行的 C/C 工程另一條線是寫報(bào)告用的需求分析、詳細(xì)設(shè)計(jì)和測試文檔。先花十分鐘把目錄結(jié)構(gòu)摸清楚后面調(diào)試和寫報(bào)告都會省下大量時(shí)間。2.1 目錄結(jié)構(gòu)src、data、docs 三層每個(gè)文件都能對號入座TaskScheduler/ ├── src/ │ ├── tcb.h # 任務(wù)控制塊任務(wù)狀態(tài)與時(shí)間屬性的定義 │ ├── queue.h / queue.cpp # 就緒隊(duì)列雙向鏈表的接口與實(shí)現(xiàn) │ ├── heap.h / heap.cpp # 二叉堆SJF 和優(yōu)先級調(diào)度的共同底座 │ ├── scheduler.h # 調(diào)度器對外接口策略入口與統(tǒng)計(jì)函數(shù) │ ├── scheduler.cpp # 四種調(diào)度算法的核心邏輯 │ └── main.cpp # 程序入口讀文件、跑調(diào)度、打印結(jié)果 ├── data/ │ ├── case1.txt # 5 個(gè)任務(wù)的經(jīng)典測試用例便于肉眼驗(yàn)算 │ ├── case2.txt # 20 個(gè)任務(wù)含到達(dá)時(shí)間沖突和優(yōu)先級重復(fù) │ └── case3.txt # 隨機(jī)生成的大樣本用于驗(yàn)證性能 ├── docs/ │ ├── 需求分析.md # 題目要求拆解與功能清單 │ ├── 詳細(xì)設(shè)計(jì).md # 數(shù)據(jù)結(jié)構(gòu)選型、模塊劃分、偽代碼 │ └── 測試報(bào)告.md # 四組算法對比數(shù)據(jù)與圖表說明 └── Makefile # 一鍵編譯依賴關(guān)系和清理目標(biāo)都已配好src 目錄是真正的工程核心頭文件和實(shí)現(xiàn)文件成對出現(xiàn)職責(zé)劃分得很清楚tcb.h 只定義數(shù)據(jù)結(jié)構(gòu)不摻任何算法邏輯queue 和 heap 是通用的容器層跟具體調(diào)度策略解耦scheduler 層才負(fù)責(zé)「用哪個(gè)容器、按什么規(guī)則選任務(wù)」。data 目錄里的三個(gè)測試用例是容易被忽略但價(jià)值很高的部分case1 的任務(wù)數(shù)量少、時(shí)間干凈就是為了讓你能拿筆在紙上驗(yàn)算一遍結(jié)果case3 則是壓測用的能逼出時(shí)間復(fù)雜度上的問題。docs 目錄在交課設(shè)時(shí)幾乎是剛需詳細(xì)設(shè)計(jì)文檔里的偽代碼可以直接當(dāng)作報(bào)告的核心章節(jié)來擴(kuò)寫。2.2 數(shù)據(jù)結(jié)構(gòu)選型為什么就緒隊(duì)列用雙向鏈表優(yōu)先級調(diào)度用二叉堆這是答辯時(shí)老師最愛問的問題也是這份資源設(shè)計(jì)的隱藏主線。調(diào)度器里有兩類核心操作一類是「任務(wù)到達(dá)后插入就緒集合」另一類是「每次調(diào)度時(shí)取出下一個(gè)要執(zhí)行的任務(wù)」。不同的算法對這兩類操作的頻率要求不一樣于是選型也不一樣。數(shù)據(jù)結(jié)構(gòu)插入取出最值刪除指定節(jié)點(diǎn)適合的算法數(shù)組O(n) 移動O(n) 掃描O(n)數(shù)據(jù)量小、代碼簡單單向鏈表O(1) 頭插/尾插O(n) 遍歷O(n) 需找前驅(qū)FCFS、簡單 RR雙向鏈表O(1) 尾插O(n) 遍歷O(1) 已知節(jié)點(diǎn)FCFS、RR、搶占式優(yōu)先級二叉堆O(log n)O(1) 取堆頂O(log n) 重建SJF、非搶占優(yōu)先級這份資源的組合方案是「雙向鏈表 二叉堆」就緒隊(duì)列本體用雙向鏈表因?yàn)闀r(shí)間片輪轉(zhuǎn)要把被搶占的任務(wù)重新掛到隊(duì)尾FCFS 也是天然的先到先服務(wù)順序鏈表尾插正好 O(1)而 SJF 和優(yōu)先級調(diào)度需要反復(fù)「取出當(dāng)前最優(yōu)任務(wù)」如果每次都用鏈表的 O(n) 遍歷20 個(gè)任務(wù)的樣例看不出問題case3 隨機(jī)生成幾百個(gè)任務(wù)時(shí)差距就會非常明顯所以這兩類算法走的是二叉堆。值得注意的是雙向鏈表在這里還有一個(gè)隱藏優(yōu)勢時(shí)間片輪轉(zhuǎn)里任務(wù)可能被執(zhí)行一半后被搶走此時(shí)它還在鏈表中需要按節(jié)點(diǎn)直接摘除雙向鏈表在已知節(jié)點(diǎn)的情況下刪除是 O(1)單向鏈表還得從頭遍歷找前驅(qū)這就是設(shè)計(jì)上多付一個(gè) prev 指針換來的收益。2.3 模塊劃分讀入、調(diào)度、統(tǒng)計(jì)三層隔離接口只看 scheduler.hscheduler.h 是整個(gè)工程的門面四個(gè)公有函數(shù)把「數(shù)據(jù)進(jìn)來」到「結(jié)果出去」的鏈路全部串起來其余細(xì)節(jié)全部封裝在實(shí)現(xiàn)文件里// scheduler.h 對外暴露的接口main.cpp 只依賴這四個(gè)函數(shù) bool loadTasks(const char* path, TCB tasks[], int taskCount); void runScheduler(TCB tasks[], int taskCount, int policy, int timeSlice); void printGantt(TCB tasks[], int taskCount); void printStatistics(TCB tasks[], int taskCount);參數(shù)說明policy 是算法枚舉資源里約定 0FCFS、1SJF、2優(yōu)先級調(diào)度、3時(shí)間片輪轉(zhuǎn)timeSlice 只在 policy 為 3 時(shí)有意義表示每個(gè)任務(wù)一次最多占用的時(shí)鐘節(jié)拍數(shù)。loadTasks 負(fù)責(zé)把 data 目錄下的 txt 文件解析成 TCB 數(shù)組runScheduler 根據(jù) policy 走不同分支printGantt 輸出帶時(shí)間軸的執(zhí)行序列printStatistics 計(jì)算平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間和平均等待時(shí)間。三層之間不互相調(diào)用內(nèi)部函數(shù)比如 loadTasks 不會去碰 heap 的任何接口這樣做的實(shí)際收益是你想換一種輸入格式只需要改 loadTasks想加一種新調(diào)度算法只需要在 runScheduler 里加一個(gè) case 分支測試時(shí)也可以單獨(dú)驗(yàn)證每一層。我第一次改造這種結(jié)構(gòu)時(shí)感觸很深課設(shè)代碼最容易爛在「所有事情都塞在 main 里」而這個(gè)工程把邊界劃得很干凈二次開發(fā)時(shí)幾乎不用重構(gòu)。3. 核心代碼拆解一個(gè)任務(wù)從「到達(dá)」到「跑完」在調(diào)度器里的完整生命周期這一章是整套代碼最值得逐行讀的部分。調(diào)度器的本質(zhì)是一個(gè)按時(shí)鐘節(jié)拍推進(jìn)的模擬器每個(gè)節(jié)拍代表一個(gè)單位時(shí)間程序在一個(gè)大循環(huán)里不斷回答三個(gè)問題——當(dāng)前有沒有新任務(wù)到達(dá)CPU 上有沒有任務(wù)在跑如果沒有下一個(gè)該選誰理解了這條時(shí)間軸四種算法其實(shí)只是第三個(gè)問題的答案不同而已。3.1 TCB用結(jié)構(gòu)體把任務(wù)的「一生」記錄下來所有調(diào)度算法的輸入輸出都是圍繞任務(wù)控制塊TCB展開的它相當(dāng)于操作系統(tǒng)的進(jìn)程控制塊在課設(shè)里的簡化版typedef struct TCB { int pid; // 任務(wù)編號從 1 開始遞增 int arriveTime; // 到達(dá)時(shí)間單位是時(shí)鐘節(jié)拍 int serviceTime; // 需要的總 CPU 運(yùn)行時(shí)間 int remainTime; // 剩余運(yùn)行時(shí)間時(shí)間片輪轉(zhuǎn)要實(shí)時(shí)修改它 int priority; // 優(yōu)先級數(shù)值越小優(yōu)先級越高 int startTime; // 第一次被調(diào)度執(zhí)行的時(shí)間初始為 -1 int finishTime; // 執(zhí)行完成的時(shí)間初始為 -1 int status; // 0未到達(dá) 1就緒 2運(yùn)行 3完成 struct TCB* prev; // 雙向鏈表前驅(qū)指針 struct TCB* next; // 雙向鏈表后繼指針 } TCB;字段設(shè)計(jì)的幾個(gè)關(guān)鍵點(diǎn)remainTime 和 serviceTime 分開存是因?yàn)闀r(shí)間片輪轉(zhuǎn)會一次次打斷任務(wù)執(zhí)行serviceTime 是任務(wù)的固有屬性用來算周轉(zhuǎn)類指標(biāo)remainTime 是動態(tài)狀態(tài)歸零代表任務(wù)完成startTime 初始化為 -1 而不是 0是為了區(qū)分「任務(wù)真的在 0 時(shí)刻開始執(zhí)行」和「還沒執(zhí)行過」這個(gè)細(xì)節(jié)在計(jì)算帶權(quán)周轉(zhuǎn)時(shí)間時(shí)特別容易出錯(cuò)status 字段配合鏈表指針使用能快速判斷一個(gè)任務(wù)當(dāng)前是否還在就緒隊(duì)列里防止重復(fù)入隊(duì)。prev 和 next 直接嵌在 TCB 里而不是再包一層鏈表節(jié)點(diǎn)結(jié)構(gòu)是為了讓同一個(gè) TCB 既能在鏈表中被管理又能直接作為堆里的元素避免指針來回轉(zhuǎn)換的麻煩。3.2 就緒隊(duì)列雙向鏈表的尾插與 O(1) 摘除就緒隊(duì)列是 FCFS 和 RR 的基礎(chǔ)容器它維護(hù)一個(gè)全局雙向鏈表頭指針指向最先到達(dá)的任務(wù)尾指針指向最后到達(dá)的任務(wù)// 將任務(wù)掛到就緒隊(duì)列尾部FCFS 和 RR 都用它入隊(duì) bool appendReady(TCB* task) { if (task NULL) return false; if (readyHead NULL) { readyHead readyTail task; // 隊(duì)列為空 } else { readyTail-next task; // 掛在尾節(jié)點(diǎn)后面 task-prev readyTail; task-next NULL; readyTail task; // 更新尾指針 } readyCount; return true; } // 從就緒隊(duì)列中摘除指定任務(wù)已知節(jié)點(diǎn)時(shí) O(1) bool removeReady(TCB* task) { if (task-prev ! NULL) task-prev-next task-next; else readyHead task-next; // 刪的是頭節(jié)點(diǎn) if (task-next ! NULL) task-next-prev task-prev; else readyTail task-prev; // 刪的是尾節(jié)點(diǎn) task-prev task-next NULL; // 斷開防止野指針 readyCount--; return true; }邏輯說明appendReady 維護(hù)隊(duì)尾新任務(wù)永遠(yuǎn)從尾部進(jìn)入這樣先到達(dá)的任務(wù)天然排在前面FCFS 按鏈表順序取頭節(jié)點(diǎn)即可removeReady 最核心的價(jià)值在時(shí)間片輪轉(zhuǎn)場景——一個(gè)任務(wù)被搶占后重新入隊(duì)或者優(yōu)先級調(diào)度中一個(gè)高優(yōu)先級任務(wù)插隊(duì)后把正在運(yùn)行的任務(wù)放回隊(duì)列都需要從鏈表中間把某個(gè)節(jié)點(diǎn)摘掉再重新掛到尾部如果只有 next 指針必須從頭遍歷才能拿到前驅(qū)而雙向鏈表用 task-prev 直接回退刪除成本降為 O(1)。這兩個(gè)函數(shù)配合 readyCount 計(jì)數(shù)器還順帶解決了調(diào)度主循環(huán)的終止條件判斷。3.3 調(diào)度主循環(huán)時(shí)鐘節(jié)拍驅(qū)動下的策略分發(fā)scheduler.cpp 里的核心是一個(gè) for 循環(huán)clock 從 0 開始每輪加一模擬時(shí)間流逝for (int clock 0; running ! NULL || readyCount 0; clock) { // 第一步當(dāng)前時(shí)刻是否有任務(wù)到達(dá)到達(dá)則進(jìn)入就緒隊(duì)列 while (taskIndex taskCount tasks[taskIndex].arriveTime clock) { tasks[taskIndex].status READY; appendReady(tasks[taskIndex]); taskIndex; } // 第二步CPU 空閑且有就緒任務(wù)時(shí)按策略選一個(gè)執(zhí)行 if (running NULL readyCount 0) { running selectTask(clock, policy); if (running-startTime -1) running-startTime clock; running-status RUNNING; } // 第三步當(dāng)前任務(wù)執(zhí)行一個(gè)節(jié)拍 if (running ! NULL) { running-remainTime--; if (running-remainTime 0) { running-finishTime clock 1; // 完成時(shí)刻是下一拍 running-status FINISHED; running NULL; // 釋放 CPU } else if (policy POLICY_RR (clock 1) % timeSlice 0) { // 時(shí)間片耗盡任務(wù)回到就緒隊(duì)列尾部 running-status READY; appendReady(running); running NULL; } } }這段循環(huán)有三個(gè)容易寫錯(cuò)的地方資源里的實(shí)現(xiàn)處理得比較到位。第一是到達(dá)檢查用的是 while 而不是 if因?yàn)橥粫r(shí)刻可能多個(gè)任務(wù)一起到達(dá)第二是搶占語義SJF 和優(yōu)先級調(diào)度如果在非搶占模式下running 為 NULL 才發(fā)生調(diào)度而搶占式優(yōu)先級需要在第二步之前先判斷「新到達(dá)的任務(wù)是否比當(dāng)前任務(wù)的優(yōu)先級更高」資源默認(rèn)是非搶占版本改搶占只需在第二步前加一段比較邏輯第三是 finishTime 的計(jì)算任務(wù)在 clock 這一拍執(zhí)行完它的完成時(shí)刻應(yīng)該是 clock 1這是時(shí)間軸左閉右開的結(jié)果很多初版實(shí)現(xiàn)在這里少加 1導(dǎo)致周轉(zhuǎn)時(shí)間整體偏小我當(dāng)年就在這上面翻過車。3.4 二叉堆SJF 與優(yōu)先級調(diào)度共用的「最優(yōu)先」底座selectTask 函數(shù)內(nèi)部根據(jù) policy 分流SJF 和優(yōu)先級調(diào)度走的是同一個(gè)小根堆區(qū)別只在于堆節(jié)點(diǎn)比較的 key 是什么// 小根堆上浮新元素從底部向上調(diào)整到合適位置 void heapPush(PriorityQueue* q, TCB* task, int keyType) { q-data[q-size] task; int cur q-size; while (cur 0) { int parent (cur - 1) / 2; int curKey getKey(q-data[cur], keyType); int parentKey getKey(q-data[parent], keyType); if (parentKey curKey) break; // 父節(jié)點(diǎn)更小停止上浮 swap(q-data[cur], q-data[parent]); cur parent; } } // 小根堆下沉堆頂取出后把最后一個(gè)元素放到根部調(diào)整 TCB* heapPop(PriorityQueue* q) { if (q-size 0) return NULL; TCB* top q-data[0]; q-data[0] q-data[--q-size]; int cur 0; while (true) { int left cur * 2 1, right cur * 2 2; int smaller cur; if (left q-size getKey(q-data[left], q-keyType) getKey(q-data[smaller], q-keyType)) smaller left; if (right q-size getKey(q-data[right], q-keyType) getKey(q-data[smaller], q-keyType)) smaller right; if (smaller cur) break; swap(q-data[cur], q-data[smaller]); cur smaller; } return top; }邏輯說明getKey 是個(gè)小工具函數(shù)keyType 為 1 時(shí)返回 serviceTimekeyType 為 2 時(shí)返回 priority這樣同一套堆代碼同時(shí)服務(wù) SJF 和優(yōu)先級調(diào)度只改比較的字段不復(fù)制代碼。push 的上浮過程和 pop 的下沉過程都是標(biāo)準(zhǔn)的堆調(diào)整時(shí)間復(fù)雜度 O(log n)。這里有個(gè)課設(shè)答辯時(shí)值得講的細(xì)節(jié)SJF 和優(yōu)先級調(diào)度都需要在任務(wù)到達(dá)時(shí)把任務(wù)插入堆每次調(diào)度時(shí)從堆頂取最值如果就緒隊(duì)列用鏈表做每次取最值都是 O(n) 的全表掃描用堆之后整體復(fù)雜度從 O(n2) 降到 O(n log n)case3 里幾百個(gè)任務(wù)的樣本能直觀看到運(yùn)行耗時(shí)差異。4. 編譯運(yùn)行與結(jié)果驗(yàn)證三條命令跑出四種算法的對比數(shù)據(jù)到了實(shí)操環(huán)節(jié)。這份資源自帶的 Makefile 已經(jīng)處理好了頭文件依賴和編譯參數(shù)理論上你只需要在命令行執(zhí)行三個(gè)動作就能看到輸出結(jié)果但我會把每一步背后的含義也說明白這樣出問題時(shí)你知道去哪里排查。4.1 編譯與運(yùn)行命令行 Makefile 與 IDE 兩種姿勢cd TaskScheduler make clean make ./scheduler data/case1.txt 0 1參數(shù)說明第一個(gè)參數(shù)是測試數(shù)據(jù)文件路徑第二個(gè)參數(shù)是調(diào)度策略編號0FCFS1SJF2優(yōu)先級3RR第三個(gè)參數(shù)是時(shí)間片大小只在策略為 3 時(shí)生效其他策略下會被忽略。Makefile 里默認(rèn)了 g 編譯標(biāo)準(zhǔn)為 C11編譯選項(xiàng)帶上 -Wall 打開全部警告課設(shè)階段把警告當(dāng)錯(cuò)誤處理能幫你避開不少隱式類型轉(zhuǎn)換和未初始化變量的問題。如果你習(xí)慣用集成開發(fā)環(huán)境也可以把 src 目錄下所有 .cpp 文件加入工程頭文件路徑指向 src然后直接編譯 main.cpp效果完全一樣。我一般建議先用命令行跑通一次因?yàn)?Makefile 把整個(gè)構(gòu)建過程透明化了出錯(cuò)了能看到具體是哪個(gè)文件哪個(gè)函數(shù)的問題IDE 反而把編譯細(xì)節(jié)藏起來了。跑完之后終端會先打印一張文本形式的甘特圖用豎線分隔時(shí)間軸和任務(wù)編號然后打印每個(gè)任務(wù)的到達(dá)時(shí)間、開始時(shí)間、完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間最后是四項(xiàng)平均值。case1 只有 5 個(gè)任務(wù)你可以拿紙筆手動推一遍 FCFS 的結(jié)果跟程序輸出比對如果一致說明工程本身沒問題后面換算法和數(shù)據(jù)就是參數(shù)的事。4.2 輸入文件格式任務(wù)描述文件的字段約定data 目錄下的 txt 文件格式非常直白第一行是任務(wù)總數(shù)從第二行開始每行四個(gè)整數(shù)分別對應(yīng) TCB 里的 pid、arriveTime、serviceTime、priority5 1 0 8 3 2 2 5 1 3 3 1 4 4 6 4 2 5 8 2 5字段順序和 tcb.h 里的聲明順序保持一致loadTasks 用 fscanf 按 %d 逐個(gè)讀取遇到文件提前結(jié)束會自動報(bào)錯(cuò)并返回 false。這里有個(gè)坑要提醒priority 數(shù)值越小代表優(yōu)先級越高這是資源里統(tǒng)一的約定如果你自己造測試數(shù)據(jù)時(shí)把數(shù)值大小關(guān)系搞反優(yōu)先級調(diào)度的結(jié)果會完全反過來。另外到達(dá)時(shí)間可以不從 0 開始也不必嚴(yán)格遞增但同一個(gè)任務(wù)的到達(dá)時(shí)間不能晚于它自己的完成時(shí)間否則算出來的周轉(zhuǎn)時(shí)間是負(fù)數(shù)這是邏輯上就不合法的數(shù)據(jù)。4.3 結(jié)果驗(yàn)證周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、甘特圖怎么對得上程序輸出的統(tǒng)計(jì)指標(biāo)是課設(shè)報(bào)告的核心數(shù)據(jù)也是答辯時(shí)老師最可能追問的部分Task 1: arrive0 start0 finish8 turnaround8 weighted1.00 Task 2: arrive2 start8 finish13 turnaround11 weighted2.20 Task 3: arrive3 start13 finish14 turnaround11 weighted11.00 Average turnaround time: 10.00 Average weighted turnaround time: 3.55公式說明周轉(zhuǎn)時(shí)間 finishTime - arriveTime表示任務(wù)從到達(dá)系統(tǒng)到執(zhí)行完成經(jīng)歷的總時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 周轉(zhuǎn)時(shí)間 / serviceTime衡量的是「等待時(shí)間被放大了多少倍」短作業(yè)如果被長作業(yè)堵在后面這個(gè)值會非常大所以它是評估調(diào)度算法公平性的關(guān)鍵指標(biāo)。案例里 Task 3 運(yùn)行時(shí)間只有 1 個(gè)節(jié)拍卻等了 10 拍才執(zhí)行完帶權(quán)周轉(zhuǎn)時(shí)間沖到 11這就是典型的短作業(yè)吃虧場景也是 SJF 能顯著改善的指標(biāo)。你可以用程序輸出跟手算結(jié)果對一遍如果 FCFS 下對不上先檢查 finishTime 是不是按 clock 1 計(jì)的再檢查同一時(shí)刻多個(gè)任務(wù)到達(dá)時(shí)的入隊(duì)順序是否穩(wěn)定。5. 避坑指南課程設(shè)計(jì)與真實(shí)調(diào)度器之間的四個(gè)經(jīng)典翻車點(diǎn)這一章寫的是我在調(diào)試這類模擬器時(shí)遇到過的真實(shí)問題也是答辯時(shí)老師愛挖的坑。每一條都是「現(xiàn)象 → 原因 → 解決」的結(jié)構(gòu)你在跑通之后拿自己的測試數(shù)據(jù)去觸發(fā)一遍會比只看代碼理解得更深。5.1 新任務(wù)到達(dá)瞬間正在運(yùn)行的任務(wù)沒讓出 CPU現(xiàn)象使用搶占式優(yōu)先級調(diào)度時(shí)明明 4 個(gè)任務(wù)運(yùn)行時(shí)間都不長運(yùn)行結(jié)果里卻出現(xiàn)了一個(gè)高優(yōu)先級任務(wù)被低優(yōu)先級任務(wù)壓在后面執(zhí)行的怪異序列。 原因調(diào)度主循環(huán)只有在 running NULL 時(shí)才調(diào) selectTask 選新任務(wù)新任務(wù)到達(dá)只是被放進(jìn)了就緒隊(duì)列沒有在當(dāng)下立即觸發(fā)一次搶占判斷。資源默認(rèn)實(shí)現(xiàn)的是非搶占式調(diào)度搶占邏輯缺失。 解決在檢查新任務(wù)到達(dá)之后、執(zhí)行當(dāng)前任務(wù)之前增加一個(gè)搶占判斷分支如果新任務(wù) priority 比 running 的 priority 更小就把 running 放回就緒隊(duì)列并置空讓下一拍重新 selectTask。注意搶占的粒度是「一個(gè)完整時(shí)鐘節(jié)拍」新任務(wù)最早只能從下一拍開始執(zhí)行不能在同一拍內(nèi)完成切換。5.2 SJF 的饑餓問題被固定測試數(shù)據(jù)掩蓋現(xiàn)象case1 和 case2 跑 SJF 時(shí)一切正常但你自己生成一組「一個(gè)大長任務(wù) 若干個(gè)持續(xù)到達(dá)的短任務(wù)」的數(shù)據(jù)后發(fā)現(xiàn)長任務(wù)遲遲無法完成最后被迫地反復(fù)被短任務(wù)插隊(duì)。 原因SJF 每次選擇剩余運(yùn)行時(shí)間最短的任務(wù)如果短任務(wù)源源不斷到達(dá)長任務(wù)永遠(yuǎn)選不上這就是經(jīng)典的饑餓現(xiàn)象。課程設(shè)計(jì)通常不會用極端數(shù)據(jù)測試但答辯老師一定會問「SJF 的缺點(diǎn)是什么」。 解決工程里 SJF 用的是不可搶占版本已經(jīng)能緩解一部分問題真要做改進(jìn)可以改成 HRRN最高響應(yīng)比優(yōu)先響應(yīng)比 等待時(shí)間 運(yùn)行時(shí)間/ 運(yùn)行時(shí)間它天然兼具 SJF 的短作業(yè)優(yōu)先和 FCFS 的防饑餓特性改造成本只在 selectTask 里多算一個(gè)比值代碼量很小但答辯效果很好。5.3 時(shí)間片輪轉(zhuǎn)的完成時(shí)間多算一拍現(xiàn)象RR 策略下一個(gè)任務(wù)明明運(yùn)行了 5 拍服務(wù)時(shí)間也是 5打印出來的 finishTime 卻比預(yù)期大了 1周轉(zhuǎn)時(shí)間整體偏大。 原因把完成任務(wù)的那一拍直接寫成了 running-finishTime clock忽略了時(shí)鐘節(jié)拍是左閉右開區(qū)間——任務(wù)在第 clock 拍執(zhí)行完完成時(shí)刻應(yīng)該是 clock 1。同理時(shí)間片耗盡判斷寫成 clock % timeSlice 0 也會錯(cuò)一拍。 解決統(tǒng)一用 clock 1 作為完成時(shí)刻時(shí)間片耗盡判斷用 (clock 1) % timeSlice 0。寫完用 serviceTime 只有 1 的任務(wù)做最小測試它的 finishTime 必須等于 arriveTime 1這個(gè)用例能一秒暴露問題。5.4 多任務(wù)同時(shí)到達(dá)時(shí)就緒隊(duì)列的插入順序不穩(wěn)定現(xiàn)象兩份結(jié)構(gòu)相同、只有任務(wù)編號順序不同的測試數(shù)據(jù)在 FCFS 下跑出的甘特圖不一致某些任務(wù)的前后關(guān)系發(fā)生了對調(diào)。 原因loadTasks 按文件順序把任務(wù)讀入數(shù)組而調(diào)度主循環(huán)里檢查到達(dá)用的是 while (arriveTime clock)同一時(shí)刻到達(dá)的任務(wù)入隊(duì)順序取決于它們在這個(gè)時(shí)刻的檢查順序如果文件的寫入順序和任務(wù)編號順序不一致數(shù)組遍歷順序也會變鏈表尾插結(jié)果就會不同。 解決在 loadTasks 讀完后對 tasks 數(shù)組按 arriveTime 做一次穩(wěn)定排序相同到達(dá)時(shí)間的任務(wù)保持編號升序或者把 appendReady 改成按 pid 二次比較插入。穩(wěn)定的入隊(duì)順序是結(jié)果可復(fù)現(xiàn)的前提否則你寫報(bào)告時(shí)換一份數(shù)據(jù)格式前后兩組實(shí)驗(yàn)就對不上了。6. 二次開發(fā)把「一次讀入全部任務(wù)」改成「運(yùn)行時(shí)動態(tài)注入」的交互式調(diào)度器循環(huán)結(jié)構(gòu)的調(diào)度器最大的限制是任務(wù)集合在開始時(shí)就被定死時(shí)鐘循環(huán)只能消費(fèi)已經(jīng)讀入的數(shù)組。如果你想讓這個(gè)課設(shè)更有區(qū)分度我建議把它改成交互式版本不再是加載完整文件后一口氣跑完而是每到一個(gè)時(shí)鐘節(jié)拍先從文件或標(biāo)準(zhǔn)輸入讀入新到達(dá)的任務(wù)再決定誰執(zhí)行。改造的核心是把「提前讀入數(shù)組」變成「邊跑邊讀」。具體做法是在 main 里維護(hù)一個(gè)輸入流runScheduler 的循環(huán)每推進(jìn)一拍就嘗試從輸入流讀一行任務(wù)讀到就按 TCB 初始化并加入就緒隊(duì)列。原先 loadTasks 的批量解析可以保留為「預(yù)置數(shù)據(jù)」模式新增一個(gè) -i 參數(shù)interactive走動態(tài)注入路徑// 交互式注入每個(gè)時(shí)鐘節(jié)拍調(diào)用一次有新任務(wù)就返回 true bool tryInjectTask(FILE* fp, TCB tasks[], int taskCount, int clock) { TCB temp; if (fscanf(fp, %d %d %d %d, temp.pid, temp.arriveTime, temp.serviceTime, temp.priority) ! 4) return false; if (temp.arriveTime clock) { // 只接收當(dāng)前時(shí)刻的任務(wù) temp.remainTime temp.serviceTime; temp.startTime temp.finishTime -1; temp.status READY; tasks[taskCount] temp; appendReady(tasks[taskCount - 1]); } return true; }改造完成后驗(yàn)證方法也很直接先用原來的 case1 跑非交互模式再用交互模式逐個(gè)注入同樣的 5 個(gè)任務(wù)兩條路徑的輸出必須完全一致這個(gè)對拍實(shí)驗(yàn)?zāi)茏C明你的動態(tài)注入沒有改變調(diào)度語義。之后再設(shè)計(jì)一個(gè)「運(yùn)行期間臨時(shí)追加任務(wù)」的場景觀察追加任務(wù)的到達(dá)時(shí)間是否被正確插入到時(shí)間軸中。這個(gè)改造不僅讓課設(shè)從「靜態(tài)演示」升級成了「動態(tài)系統(tǒng)」答辯時(shí)還能順帶引出「任務(wù)預(yù)熱、批量到達(dá)」等真實(shí)系統(tǒng)話題遠(yuǎn)比念報(bào)告有說服力。從那以后我每次拿到一份課設(shè)工程都會先花半小時(shí)把「入口參數(shù)、模塊邊界、輸出口徑」三個(gè)問題畫清楚再動手改這個(gè)習(xí)慣幫我少踩了很多坑。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取