簡介面向大二學(xué)生數(shù)據(jù)結(jié)構(gòu)課程設(shè)計基于C/C實現(xiàn)的任務(wù)調(diào)度器系統(tǒng)覆蓋任務(wù)隊列、調(diào)度模塊與交互主程序適合需要完成同類選題、理解隊列結(jié)構(gòu)與任務(wù)管理流程的學(xué)生參考。壓縮包共38個文件大小約40.97MB包含VS2019解決方案、C源碼、任務(wù)隊列與調(diào)度管理相關(guān)頭文件、測試主程序、可直接運行的exe以及pdb、obj、tlog等編譯調(diào)試產(chǎn)生的中間文件工程目錄清晰解壓后用Visual Studio 2019打開即可復(fù)現(xiàn)運行效果。已有207名學(xué)生學(xué)習(xí)下載說明該選題在課程設(shè)計場景中具備一定代表性。通過該項目可以完整走一遍任務(wù)調(diào)度器的設(shè)計實現(xiàn)過程掌握任務(wù)隊列構(gòu)建、任務(wù)狀態(tài)維護、調(diào)度策略設(shè)計等核心思路也能借鑒其模塊劃分、工程組織方式和類圖設(shè)計便于快速改寫成自己的課程設(shè)計代碼、報告與答辯材料。1. 任務(wù)調(diào)度器這件課設(shè)為什么值得認真做很多人拿到任務(wù)調(diào)度器這個題目的第一反應(yīng)是去翻操作系統(tǒng)里的進程調(diào)度算法結(jié)果發(fā)現(xiàn)課設(shè)要求的是用數(shù)據(jù)結(jié)構(gòu)去模擬調(diào)度過程而不是真的實現(xiàn)一個操作系統(tǒng)調(diào)度內(nèi)核。先來先服務(wù)要排隊短作業(yè)優(yōu)先要快速找出最小服務(wù)時間時間片輪轉(zhuǎn)要環(huán)形取任務(wù)這背后對應(yīng)的是隊列、優(yōu)先隊列和循環(huán)隊列的設(shè)計與編碼能力。正因為如此它才成為數(shù)據(jù)結(jié)構(gòu)課程設(shè)計里最常被選中的題目之一——題目不大但能同時考到結(jié)構(gòu)體、指針、堆、隊列和排序穩(wěn)定性。這份方案面向正在準備數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的學(xué)生也面向想快速理清任務(wù)調(diào)度器完整實現(xiàn)思路的開發(fā)者給出的是從需求分析、數(shù)據(jù)結(jié)構(gòu)選型、模塊劃分到C語言核心實現(xiàn)的一整套可落地參考。適合拿來做C/C課設(shè)的藍本也適合在答辯時應(yīng)對你為什么要這樣設(shè)計的追問。2. 需求分析與技術(shù)選型先確定調(diào)度規(guī)則再決定用堆還是隊列2.1 課設(shè)任務(wù)書里最容易被忽略的四個需求點先別急著寫代碼我會把任務(wù)書拆成四個必答項。第一必須支持的調(diào)度算法。常見組合是FCFS先來先服務(wù)、SJF短作業(yè)優(yōu)先、RR時間片輪轉(zhuǎn)三種部分題目還會要求動態(tài)優(yōu)先級調(diào)度。第二任務(wù)輸入方式。多數(shù)要求從文件或控制臺讀入任務(wù)列表每條任務(wù)包含任務(wù)ID、到達時間和服務(wù)時間。第三結(jié)果輸出。通常要求打印調(diào)度順序、每個任務(wù)的開始時間、完成時間、等待時間、周轉(zhuǎn)時間以及平均周轉(zhuǎn)時間。第四邊界行為。比如兩個任務(wù)同時到達、服務(wù)時間相同、任務(wù)到達時間錯峰這些場景決定了算法能否正確處理排序穩(wěn)定性。以最常見的輸入文件為例5 T1 0 8 T2 1 4 T3 2 9 T4 3 5 T5 4 2第一行是任務(wù)總數(shù)之后每行依次是任務(wù)ID、到達時間、服務(wù)時間。表面上簡單但隱含了一個容易漏掉的需求任務(wù)不是一開始全部到達調(diào)度器必須在current_time小于下一個任務(wù)到達時間時等待。我一般會在需求分析里專門寫一條支持任務(wù)錯峰到達這樣設(shè)計就完整了。需求分析還會直接影響編碼邊界。比如如果任務(wù)書要求輸出每個任務(wù)的開始時間那Task里還需要記錄start_time如果要求支持任務(wù)隨機生成那么輸入層就要加一個生成器函數(shù)。很多同學(xué)拿到題就開寫寫著發(fā)現(xiàn)字段不夠用又回頭改結(jié)構(gòu)體來回浪費一個下午。我通常的做法是先在紙上畫一個輸入的樣例、一個輸出的樣例把字段對齊了再動鍵盤。2.2 數(shù)據(jù)結(jié)構(gòu)選型優(yōu)先隊列、普通隊列和數(shù)組各司其職任務(wù)調(diào)度器的核心數(shù)據(jù)結(jié)構(gòu)是就緒隊列但不同算法對隊列的要求彼此沖突。FCFS只需要先進先出用循環(huán)隊列即可SJF每次要選出服務(wù)時間最短的任務(wù)用最小堆最合適RR要按順序循環(huán)取任務(wù)本質(zhì)上又是循環(huán)隊列。如果只用數(shù)組加排序硬扛每來一個新任務(wù)就重新全排序代碼難寫且復(fù)雜度高更重要的是答辯時說不清楚為什么用這個結(jié)構(gòu)。因此在完整方案里我會同時實現(xiàn)兩個就緒容器一個二叉堆用于SJF和優(yōu)先級調(diào)度一個循環(huán)隊列用于FCFS和RR。二者都以Task指針為元素通過相同的隊列接口操作。下面這個表是我放在課設(shè)報告里的選型對比數(shù)據(jù)結(jié)構(gòu)適用算法核心操作時間復(fù)雜度循環(huán)隊列FCFS / RR入隊、出隊、判空O(1)二叉堆最小堆SJF / 優(yōu)先級調(diào)度插入、取最小、堆化O(log n)數(shù)組全部算法存儲原始任務(wù)、按id索引O(n)有一點需要特別說明SJF里的最短是指服務(wù)時間最小當服務(wù)時間相等時按到達時間排序。這就要求堆的比較函數(shù)不是只看service_time而是先比service_time再比arrive_time否則兩個服務(wù)時間相同的任務(wù)順序可能與手算結(jié)果不一致。這是后面的避坑章節(jié)里最容易翻車的一個點。在這個選型階段還有一個容易被當成玄學(xué)的點為什么時間片輪轉(zhuǎn)也要用隊列而不是鏈表。鏈表插入刪除雖然方便但循環(huán)隊列在固定大小任務(wù)數(shù)組的課設(shè)場景下更簡單不需要頻繁malloc/new。如果任務(wù)數(shù)上限已知預(yù)分配一個MAX_TASKS容量的數(shù)組用head和tail兩個下標維護隊列幾乎沒有內(nèi)存管理負擔。鏈表方案可以作為加分項寫在擴展思考里但核心代碼用循環(huán)隊列更容易講。2.3 用C還是C封裝與調(diào)試成本的權(quán)衡如果允許自由選擇語言我會優(yōu)先用C而不是C。原因有三第一C的結(jié)構(gòu)體和指針能直觀展示任務(wù)節(jié)點、堆、隊列之間的關(guān)系答辯老師很容易看出你掌握的程度第二C的STL會把priority_queue、queue這些容器都包裝好代碼量少了但老師一句你講講最小堆的堆化過程就可能答不上來第三C程序用gdb調(diào)試堆數(shù)組和隊列更透明每次push/pop后都能直接查看data數(shù)組的順序。如果你更習(xí)慣C也可以用class封裝Scheduler和Task但必須自己管理析構(gòu)和拷貝避免淺拷貝導(dǎo)致指針重復(fù)釋放。這個方案里給出的代碼以C語言為基準同時在注釋里標注了C改進點。我這里建議課設(shè)代碼控制在三個源文件main.c負責(zé)流程控制scheduler.c負責(zé)算法實現(xiàn)task_queue.c負責(zé)堆與隊列的操作。模塊清晰答辯時分頭講解很從容。選型確定后下一步需要把數(shù)據(jù)結(jié)構(gòu)封裝成統(tǒng)一接口讓調(diào)度算法不感知底層是堆還是隊列。比如我定義一組入隊、出隊、判空函數(shù)堆和循環(huán)隊列都實現(xiàn)同一套函數(shù)名內(nèi)部各自維護自己的存儲方式。這樣的抽象能讓后續(xù)切換算法時只改動一行設(shè)置代碼也為第3章的總體架構(gòu)設(shè)計做了鋪墊。3. 總體架構(gòu)設(shè)計三層結(jié)構(gòu)與五類模塊的職責(zé)劃分3.1 頂層分層輸入層、調(diào)度核心層、輸出層任務(wù)調(diào)度器整體采用三層結(jié)構(gòu)。輸入層負責(zé)解析任務(wù)文件、校驗數(shù)據(jù)比如任務(wù)數(shù)不能為0、服務(wù)時間不能為負數(shù)、時間片必須大于0等。調(diào)度核心層維護任務(wù)狀態(tài)機和三個調(diào)度算法這一層不關(guān)心數(shù)據(jù)是從文件還是控制臺來的。輸出層負責(zé)打印調(diào)度順序和統(tǒng)計指標。這樣的好處是算法切換不會影響輸入輸出新增算法時只需要在核心層添加一個函數(shù)。在課設(shè)報告里我會用一個模塊劃分表來說明模塊文件職責(zé)關(guān)鍵結(jié)構(gòu)/函數(shù)main.c解析命令行參數(shù)、組織流程Scheduler結(jié)構(gòu)體task_queue.c循環(huán)隊列與最小堆的操作enqueue、dequeue、heap_push、heap_popscheduler.c三種調(diào)度算法的狀態(tài)推進scheduler_fcfs / sjf / rroutput.c打印調(diào)度順序、計算統(tǒng)計量print_schedule、calc_avgmain函數(shù)中先用load_tasks()讀取任務(wù)數(shù)組再根據(jù)命令行參數(shù)創(chuàng)建Scheduler調(diào)用scheduler_run()最后調(diào)用print_result()。我會特別在main函數(shù)里保留一個打印中間狀態(tài)的開關(guān)調(diào)試時開啟答辯演示時關(guān)閉。在三層結(jié)構(gòu)的邊界上我還會留一個hook點調(diào)度核心層只暴露一個scheduler_run()接口和一個scheduler_set_algorithm()設(shè)置函數(shù)。這樣main.c無需關(guān)心算法內(nèi)部是用了堆還是隊列如果日后想支持動態(tài)優(yōu)先級搶占只需在Scheduler里增加一個priority字段并在比較函數(shù)中增加一條判斷即可。這種設(shè)計看似多寫幾行代碼但在答辯中被問到可擴展性時就能拿出實際的函數(shù)接口來證明而不是只說思路。3.2 任務(wù)狀態(tài)機新建、就緒、運行、完成任務(wù)不能共享同一塊隊列就完事每個任務(wù)都有自己的生命周期。我給Task設(shè)計一個state字段枚舉值分別代表NEW新建、READY就緒、RUNNING運行、FINISHED完成。調(diào)度流程是這樣的所有任務(wù)初始都是NEW當current_time推進到某個任務(wù)的到達時間時把它插入就緒隊列并置為READY調(diào)度器從就緒隊列取一個任務(wù)置為RUNNING并運行任務(wù)運行完成后置為FINISHED。以RR舉例任務(wù)T1第一次被調(diào)度時state由1變?yōu)?運行一個時間片未完成state回到1并插入隊尾等第二次出隊再次變?yōu)?運行完畢才變?yōu)?。如果沒有這中間一次READY回縮任務(wù)就可能在第二次被取出時還被當作RUNNING導(dǎo)致調(diào)度器認定它還在運行而不重新分配。狀態(tài)機把這個問題轉(zhuǎn)化成了簡單的枚舉判斷代碼里一眼能看清。這個狀態(tài)機最大的價值是避免重復(fù)入隊。RR算法里一個任務(wù)執(zhí)行完一個時間片但沒結(jié)束會被放回隊尾此時它的狀態(tài)應(yīng)該是READY而不是RUNNING而一個已經(jīng)FINISHED的任務(wù)如果因為下標判斷失誤再次被掃描到就會重復(fù)入隊。有了state每次入隊前檢查一下不是READY和RUNNING就能提前攔住錯誤。3.3 調(diào)度核心模塊統(tǒng)一接口與三個算法的策略選擇調(diào)度核心層我不會寫成三個相互獨立的大函數(shù)而是定義一個Scheduler結(jié)構(gòu)體來統(tǒng)一管理typedef struct { int algorithm; /* 0-FCFS 1-SJF 2-RR */ int time_slice; /* RR使用 */ int current_time; Task *tasks; int task_count; int finished_count; } Scheduler;然后提供一個scheduler_run()入口內(nèi)部通過switch調(diào)用不同的調(diào)度函數(shù)。每個調(diào)度函數(shù)只負責(zé)把task的finish_time寫好不直接打印結(jié)果。這樣統(tǒng)計模塊永遠從finish_time字段取數(shù)不會因為全局變量被改而算錯。使用統(tǒng)一接口還有一個微觀好處統(tǒng)計模塊在調(diào)度完成后遍歷任務(wù)數(shù)組不需要知道剛才跑的是哪個算法。算法的選擇只影響每個任務(wù)的finish_time不影響后續(xù)計算。這也讓main.c的代碼量大幅減少從開始到讀入?yún)?shù)再到輸出結(jié)果不超過60行。三種算法的推進邏輯分別是FCFS按到達順序入隊任務(wù)執(zhí)行完才讓出CPUSJF每步從最小堆堆頂取任務(wù)同樣不可搶占RR每個任務(wù)最多運行一個時間片沒做完就重新入隊尾部。對比來看SJF和FCFS都是運行到結(jié)束只是選擇順序不同RR才會在運行中途打斷。答辯時我會主動說出這個區(qū)別表明算法并不是簡單換排序。3.4 統(tǒng)計指標模塊周轉(zhuǎn)時間、等待時間與平均數(shù)的計算課程設(shè)計通常要求輸出平均周轉(zhuǎn)時間所以統(tǒng)計模塊要獨立于調(diào)度模塊。每個任務(wù)調(diào)度完成后只記錄finish_time統(tǒng)計時再統(tǒng)一計算周轉(zhuǎn)時間 finish_time - arrive_time等待時間 周轉(zhuǎn)時間 - service_time帶權(quán)周轉(zhuǎn)時間 周轉(zhuǎn)時間 / service_time。平均周轉(zhuǎn)時間則是所有任務(wù)周轉(zhuǎn)時間之和除以任務(wù)數(shù)。這里有一個容易踩坑的細節(jié)打印帶權(quán)周轉(zhuǎn)時間時如果用整數(shù)除法9/8會變成1而不是1.12。我會用浮點數(shù)保存結(jié)果printf保留兩位小數(shù)。另外當任務(wù)服務(wù)時間為0時帶權(quán)周轉(zhuǎn)時間會做除零運算我在輸入校驗里直接禁止服務(wù)時間小于等于0從根上規(guī)避掉這個黑匣子問題。輸出格式我建議用表格對齊方式比如每行打印任務(wù)ID、到達時間、服務(wù)時間、完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間。最后單獨一行打印平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。這樣的打印結(jié)果可以直接貼進課程設(shè)計報告不需要再手工整理。4. 關(guān)鍵實現(xiàn)堆、隊列與三種調(diào)度算法的落地代碼4.1 任務(wù)結(jié)構(gòu)體與最小堆的實現(xiàn)代碼從Task定義開始typedef struct Task { int id; /* 任務(wù)ID從1開始 */ int arrive_time; /* 到達時間 */ int service_time; /* 服務(wù)時間 */ int done_time; /* 已經(jīng)運行的時間RR用 */ int finish_time; /* 完成時間 */ int state; /* 0新建 1就緒 2運行 3完成 */ } Task;就緒容器我采用兩個獨立結(jié)構(gòu)體的方案先看最小堆typedef struct PQueue { Task *data[MAX_TASKS]; /* 存儲任務(wù)指針 */ int size; /* 堆中元素個數(shù) */ } PQueue; void heap_push(PQueue *h, Task *t) { int i h-size; h-data[i] t; while (i 0) { int p (i - 1) / 2; if (compare(h-data[i], h-data[p]) 0) { Task *tmp h-data[i]; h-data[i] h-data[p]; h-data[p] tmp; i p; } else { break; } } } Task *heap_pop(PQueue *h) { Task *top h-data[0]; h-data[0] h-data[--h-size]; int i 0; while (1) { int l 2 * i 1, r 2 * i 2, smallest i; if (l h-size compare(h-data[l], h-data[smallest]) 0) smallest l; if (r h-size compare(h-data[r], h-data[smallest]) 0) smallest r; if (smallest i) break; Task *tmp h-data[i]; h-data[i] h-data[smallest]; h-data[smallest] tmp; i smallest; } return top; }這段代碼的邏輯是heap_push從數(shù)組末尾上浮heap_pop先將堆頂與末尾元素交換并下沉正好對應(yīng)堆的兩個核心操作。MAX_TASKS采用宏定義如#define MAX_TASKS 100避免動態(tài)擴容引出的指針失效問題。compare函數(shù)是優(yōu)先級判定的核心int compare(Task *a, Task *b) { if (a-service_time ! b-service_time) { return a-service_time - b-service_time; } return a-arrive_time - b-arrive_time; }返回值小于0表示a應(yīng)排在b前面。這與普通排序的cmp函數(shù)保持一致。很多同學(xué)在這里會犯方向性錯誤寫成b-service_time - a-service_time導(dǎo)致最小堆變成最大堆這是最典型的翻車點。4.2 FCFS與SJF調(diào)度實現(xiàn)FCFS采用循環(huán)隊列這里給出調(diào)度主體的最簡版void scheduler_fcfs(Scheduler *sched) { CQueue q; init_queue(q); int next 0; while (sched-finished_count sched-task_count) { while (next sched-task_count sched-tasks[next].arrive_time sched-current_time) { sched-tasks[next].state 1; enqueue(q, sched-tasks[next]); next; } if (is_empty(q)) { sched-current_time; continue; } Task *t dequeue(q); t-state 2; t-finish_time sched-current_time t-service_time; sched-current_time t-finish_time; t-state 3; sched-finished_count; } }注意兩個細節(jié)第一個while負責(zé)把到點的新任務(wù)放入隊列第二個if用于處理隊列為空且任務(wù)尚未全部到達的情況這時current_time逐秒推進會稍慢但邏輯最簡單。如果追求效率可以直接跳到下一個任務(wù)的到達時間但仍要處理下一個任務(wù)也沒到齊的邊界。SJF與FCFS的結(jié)構(gòu)非常像只是把循環(huán)隊列換成最小堆取任務(wù)時從堆頂取void scheduler_sjf(Scheduler *sched) { PQueue h; h.size 0; int next 0; while (sched-finished_count sched-task_count) { while (next sched-task_count sched-tasks[next].arrive_time sched-current_time) { sched-tasks[next].state 1; heap_push(h, sched-tasks[next]); next; } if (h.size 0) { sched-current_time sched-tasks[next].arrive_time; continue; } Task *t heap_pop(h); t-state 2; t-finish_time sched-current_time t-service_time; sched-current_time t-finish_time; t-state 3; sched-finished_count; } }這段代碼與FCFS最大的區(qū)別在于兩處一是就緒容器由隊列變成堆二是隊列為空時不再用current_time而是直接跳躍到下一個任務(wù)的到達時間。跳躍寫法在SJF里更合理因為堆為空代表此刻沒有可執(zhí)行任務(wù)繼續(xù)逐秒加一不會改變堆中的內(nèi)容。4.3 時間片輪轉(zhuǎn)RR的實現(xiàn)與隊尾回插RR需要維護每個任務(wù)已經(jīng)運行的時間done_time時間片time_slice由命令行傳入。核心代碼void scheduler_rr(Scheduler *sched, int time_slice) { CQueue q; init_queue(q); int next 0; while (sched-finished_count sched-task_count) { while (next sched-task_count sched-tasks[next].arrive_time sched-current_time) { sched-tasks[next].state 1; enqueue(q, sched-tasks[next]); next; } if (is_empty(q)) { sched-current_time; continue; } Task *t dequeue(q); if (t-state 3) continue; /* 防御已完成任務(wù)不入隊 */ t-state 2; int need t-service_time - t-done_time; int run_time need time_slice ? time_slice : need; t-done_time run_time; sched-current_time run_time; if (t-done_time t-service_time) { t-state 1; enqueue(q, t); /* 沒做完放回隊尾 */ } else { t-finish_time sched-current_time; t-state 3; sched-finished_count; } } }這段代碼里最關(guān)鍵的是回插動作任務(wù)每輪只能運行一個時間片如果還沒完成done_time加滿當前時間片后重新入隊。需要特別注意的是回插的任務(wù)不能被重復(fù)計算到達時間所以next指針只負責(zé)新到達任務(wù)回插直接走enqueue隊列尾部。防御性的state3判斷是血淚經(jīng)驗曾經(jīng)有同學(xué)在任務(wù)完成瞬間又被調(diào)度器取出就是因為狀態(tài)沒有置為完成。4.4 命令行參數(shù)與運行配置為了讓課設(shè)更完整我會讓程序支持命令行參數(shù)./scheduler -a sjf -t input.txt -o result.txt -q 2各參數(shù)含義如下表參數(shù)說明默認值-a調(diào)度算法fcfs/sjf/rrfcfs-t任務(wù)文件路徑input.txt-o結(jié)果輸出文件stdout-q時間片大小RR2main函數(shù)中用getopt解析參數(shù)并用switch判斷算法。文件不存在或參數(shù)非法時打印輸入文件不存在不直接崩潰。這樣設(shè)計的好處是演示時可以在答辯現(xiàn)場用同一份任務(wù)文件分別跑三種算法對比輸出效果比只看代碼好得多。參數(shù)表可以放在設(shè)計文檔中代碼里只需要一個結(jié)構(gòu)體SchedConfig來保存。5. 常見問題與避坑指南五個最容易翻車的地方任務(wù)調(diào)度器這個課設(shè)代碼量不大但翻車點很集中。我見過的模擬項目里十個同學(xué)有七八個都卡在下面這幾類問題上。這里按現(xiàn)象→原因→解決的順序整理方便你在答辯前快速自查。5.1 比較函數(shù)方向?qū)懛醋疃倘蝿?wù)反而最后執(zhí)行現(xiàn)象SJF調(diào)度輸出里服務(wù)時間最短的任務(wù)出現(xiàn)在序列最后運行時間反而像最長作業(yè)優(yōu)先。 原因最小堆的compare返回值語義與預(yù)期相反。我見過很多初學(xué)者寫compare時參考qsort的寫法結(jié)果在堆的siftDown里又套了一層balance 0的符號翻轉(zhuǎn)負負得正。 解決統(tǒng)一約定compare(a,b) 0 表示 a 優(yōu)先級高于 b堆頂永遠存放compare值最小的元素。寫完compare后先把三個任務(wù)服務(wù)時間6、2、4按順序插入堆再全部彈出檢查是否得到2、4、6。這個測試只需10秒能避免后面所有算法結(jié)果錯亂。我一般會在單元測試代碼里直接寫上這個用例作為回歸檢查。5.2 時間片輪轉(zhuǎn)里任務(wù)重復(fù)入隊程序死循環(huán)現(xiàn)象RR運行到某個任務(wù)后發(fā)現(xiàn)它被調(diào)度了兩次或者printf刷屏不斷執(zhí)行同一個任務(wù)。 原因任務(wù)已經(jīng)完成但狀態(tài)沒有置為FINISHED或者調(diào)度器在新到達任務(wù)掃描時重復(fù)處理了已經(jīng)入隊的任務(wù)。 解決強制使用任務(wù)狀態(tài)機入隊前檢查state是否為NEW或FINISHED。更直接的防御是在調(diào)度器入口加一個斷言if (t-state 3) continue;同時維護一個next下標只掃描尚未入隊的新任務(wù)禁止每輪都從頭遍歷整個任務(wù)數(shù)組。這兩種手段疊加后重復(fù)入隊基本被根除。5.3 任務(wù)錯峰到達時程序卡在空隊列等待現(xiàn)象用全是0時刻到達的測試數(shù)據(jù)一切正常換成錯峰到達后程序要么長時間無輸出要么直接跳過任務(wù)。 原因調(diào)度器在隊列為空時沒有處理下一個任務(wù)還沒到達的情況。FCFS里用current_time能僥幸跑通但SJF里如果也這么做遇到下一個任務(wù)到達時間跨度很大程序會做大量無效循環(huán)觀感上像死機。 解決隊列為空時直接把current_time跳到下一個待入隊任務(wù)的到達時間。SJF代碼里的sched-current_time sched-tasks[next].arrive_time;就是這個用途。需要注意的是跳躍前要確保next下標有效也就是next task_count。否則說明所有任務(wù)都已經(jīng)處理完這本來也是退出循環(huán)的條件。5.4 動態(tài)分配產(chǎn)生的野指針和內(nèi)存泄漏現(xiàn)象程序測小數(shù)據(jù)正常加到50個任務(wù)后偶發(fā)崩潰或者使用valgrind檢查時發(fā)現(xiàn)一堆invalid read。 原因Task數(shù)組用malloc動態(tài)分配而隊列data數(shù)組里保存的是Task指針當任務(wù)數(shù)組被realloc擴容時舊指針全部失效。這是最典型的野指針來源。 解決課程設(shè)計場景下直接在棧上定義固定大小數(shù)組Task tasks[MAX_TASKS];并先讀入任務(wù)數(shù)再檢查是否超過MAX_TASKS。如果一定要動態(tài)分配就一次性malloc最大任務(wù)數(shù)不要做realloc。對于隊列中的指針只要任務(wù)數(shù)組地址不變指針始終有效。檢查泄漏時在gdb或valgrind下跑一遍完整測試會大大降低翻車概率。5.5 輸出結(jié)果與手算不一致平均周轉(zhuǎn)時間算錯現(xiàn)象調(diào)度順序看起來對但平均周轉(zhuǎn)時間比手算大很多或者帶權(quán)周轉(zhuǎn)時間出現(xiàn)1.00這種明顯不合理的數(shù)值。 原因統(tǒng)計時用全局current_time而不是任務(wù)自身的finish_time。由于RR會反復(fù)切換任務(wù)某個任務(wù)完成時current_time可能已經(jīng)被后續(xù)任務(wù)推進過直接用當前時間減到達時間必然出錯。 解決在任務(wù)完成時就把t-finish_time記錄好統(tǒng)計模塊只從finish_time字段取值。打印前先逐個輸出每個任務(wù)的arrive_time、finish_time、周轉(zhuǎn)時間與手算表逐項比對。這里我踩過一個坑帶權(quán)周轉(zhuǎn)時間用整數(shù)除法9/8算成1后來全部改成double輸出加上%.2f結(jié)果才正常。6. 驗收與答辯把課設(shè)做到能演示、能講透6.1 功能驗收清單在提交前我會用一個包含5個任務(wù)、3種算法的測試文件跑完整流程并對照手算結(jié)果。下表是最低驗收標準檢查項通過標準輸入解析能正確讀取文件非法參數(shù)給出提示不崩潰FCFS調(diào)度順序與手算完全一致SJF最短任務(wù)最先執(zhí)行服務(wù)時間相同時按到達順序RR每個任務(wù)每個時間片只運行一次回插正確統(tǒng)計平均周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間保留兩位小數(shù)魯棒性任務(wù)數(shù)0、時間片0、文件不存在均能友好退出6.2 答辯演示流程答辯時只講三條主線需求、選型、驗證。先花半分鐘說這個課設(shè)解決的問題是讓一組任務(wù)在三種調(diào)度策略下得到不同的執(zhí)行序列并量化對比再用同一組數(shù)據(jù)分別跑FCFS、SJF、RR指著輸出說SJF的平均周轉(zhuǎn)時間比FCFS低因為短任務(wù)優(yōu)先完成。最后結(jié)合代碼解釋為什么要用堆——SJF每次取任務(wù)需要O(log n)如果改用順序查找整體復(fù)雜度就到O(n2)。老師如果要你展示代碼優(yōu)先展示compare函數(shù)和RR的回插邏輯這兩個點最能體現(xiàn)出對數(shù)據(jù)結(jié)構(gòu)的理解。演示前準備一頁打印紙左側(cè)輸入、右側(cè)三個算法的輸出老師提問時不會因為現(xiàn)場敲命令而冷場。如果時間充?？梢渣c亮一個debug模式開關(guān)打印每個時間片的就緒隊列內(nèi)容這會讓演示顯得很扎實。這套完整的課程設(shè)計資源包含可編譯運行的C源碼、任務(wù)生成與測試用例、設(shè)計文檔框架和答辯PPT提綱拿到后可以直接對照修改。建議在動筆寫報告前先跑通功能再回頭整理文檔效率會高很多。我最初做模擬項目X時也曾在RR里把任務(wù)重復(fù)入隊調(diào)試到半夜翻車后來養(yǎng)成的習(xí)慣是每改一次算法先拿三個任務(wù)做手算再到程序里打印current_time和隊列內(nèi)容比對。從那以后我每次做調(diào)度類的課程設(shè)計都會強制自己走一遍手算結(jié)果 → 程序輸出 → 差異分析的流程。希望這份方案能幫到你少踩幾個坑。本文還有配套的精品資源點擊獲取