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