简介面向大二数据结构课程设计的任务调度器完整实现基于C/C在Visual Studio 2019环境下开发适合需要完成同类课题或希望深入理解任务调度与队列、优先级等数据结构应用的学生参考。压缩包共38个文件约40.97MB包含源代码文件cpp/hpp、Visual Studio工程文件sln/vcxproj/filters、编译运行产生的exe、pdb、obj及日志文件等打开工程即可查看完整实现并运行验证。目前已有207人学习下载。资源提供可直接运行的任务调度器Demo涵盖任务队列管理、优先级调度等核心模块代码结构清晰并附有类图文件可帮助读者快速理清模块关系为课程设计答辩和功能扩展提供实用参考。1. 任务调度器把数据结构课上的「链表和堆」变成能跑出结果的完整工程每年数据结构课程设计的题目池里几乎都会出现一个「任务调度器」。它听起来像操作系统的事但实际上整份作业的核心矛盾只有一个一批任务在不同时刻到达每个任务要跑多久、优先级多高各不相同你要用什么样的数据结构把它们组织起来才能让「下一个该执行谁」这个判断既快又公平。这份用 C/C 写成的课程设计资源把 FCFS先来先服务、SJF短作业优先、时间片轮转、优先级调度四种算法全部落成了可编译、可运行、可出报告对比的工程。适合正在备战的课设学生也适合想借一个真实项目复习链表、二叉堆和模拟器设计的开发者。你拿到的不是只贴代码的片段而是覆盖「设计—实现—测试—报告」全流程的完整交付物。2. 项目结构拆解压缩包里藏着「源码 文档」两条线先分清再动手解压之后先别急着点开 main.cpp。我见过太多人拿到课设资源第一件事就是找主函数结果被十几个文件绕晕最后连编译都过不去。这份资源遵循了课程设计最常见的「双轨」组织方式一条线是能编译运行的 C/C 工程另一条线是写报告用的需求分析、详细设计和测试文档。先花十分钟把目录结构摸清楚后面调试和写报告都会省下大量时间。2.1 目录结构src、data、docs 三层每个文件都能对号入座TaskScheduler/ ├── src/ │ ├── tcb.h # 任务控制块任务状态与时间属性的定义 │ ├── queue.h / queue.cpp # 就绪队列双向链表的接口与实现 │ ├── heap.h / heap.cpp # 二叉堆SJF 和优先级调度的共同底座 │ ├── scheduler.h # 调度器对外接口策略入口与统计函数 │ ├── scheduler.cpp # 四种调度算法的核心逻辑 │ └── main.cpp # 程序入口读文件、跑调度、打印结果 ├── data/ │ ├── case1.txt # 5 个任务的经典测试用例便于肉眼验算 │ ├── case2.txt # 20 个任务含到达时间冲突和优先级重复 │ └── case3.txt # 随机生成的大样本用于验证性能 ├── docs/ │ ├── 需求分析.md # 题目要求拆解与功能清单 │ ├── 详细设计.md # 数据结构选型、模块划分、伪代码 │ └── 测试报告.md # 四组算法对比数据与图表说明 └── Makefile # 一键编译依赖关系和清理目标都已配好src 目录是真正的工程核心头文件和实现文件成对出现职责划分得很清楚tcb.h 只定义数据结构不掺任何算法逻辑queue 和 heap 是通用的容器层跟具体调度策略解耦scheduler 层才负责「用哪个容器、按什么规则选任务」。data 目录里的三个测试用例是容易被忽略但价值很高的部分case1 的任务数量少、时间干净就是为了让你能拿笔在纸上验算一遍结果case3 则是压测用的能逼出时间复杂度上的问题。docs 目录在交课设时几乎是刚需详细设计文档里的伪代码可以直接当作报告的核心章节来扩写。2.2 数据结构选型为什么就绪队列用双向链表优先级调度用二叉堆这是答辩时老师最爱问的问题也是这份资源设计的隐藏主线。调度器里有两类核心操作一类是「任务到达后插入就绪集合」另一类是「每次调度时取出下一个要执行的任务」。不同的算法对这两类操作的频率要求不一样于是选型也不一样。数据结构插入取出最值删除指定节点适合的算法数组O(n) 移动O(n) 扫描O(n)数据量小、代码简单单向链表O(1) 头插/尾插O(n) 遍历O(n) 需找前驱FCFS、简单 RR双向链表O(1) 尾插O(n) 遍历O(1) 已知节点FCFS、RR、抢占式优先级二叉堆O(log n)O(1) 取堆顶O(log n) 重建SJF、非抢占优先级这份资源的组合方案是「双向链表 二叉堆」就绪队列本体用双向链表因为时间片轮转要把被抢占的任务重新挂到队尾FCFS 也是天然的先到先服务顺序链表尾插正好 O(1)而 SJF 和优先级调度需要反复「取出当前最优任务」如果每次都用链表的 O(n) 遍历20 个任务的样例看不出问题case3 随机生成几百个任务时差距就会非常明显所以这两类算法走的是二叉堆。值得注意的是双向链表在这里还有一个隐藏优势时间片轮转里任务可能被执行一半后被抢走此时它还在链表中需要按节点直接摘除双向链表在已知节点的情况下删除是 O(1)单向链表还得从头遍历找前驱这就是设计上多付一个 prev 指针换来的收益。2.3 模块划分读入、调度、统计三层隔离接口只看 scheduler.hscheduler.h 是整个工程的门面四个公有函数把「数据进来」到「结果出去」的链路全部串起来其余细节全部封装在实现文件里// scheduler.h 对外暴露的接口main.cpp 只依赖这四个函数 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);参数说明policy 是算法枚举资源里约定 0FCFS、1SJF、2优先级调度、3时间片轮转timeSlice 只在 policy 为 3 时有意义表示每个任务一次最多占用的时钟节拍数。loadTasks 负责把 data 目录下的 txt 文件解析成 TCB 数组runScheduler 根据 policy 走不同分支printGantt 输出带时间轴的执行序列printStatistics 计算平均周转时间、平均带权周转时间和平均等待时间。三层之间不互相调用内部函数比如 loadTasks 不会去碰 heap 的任何接口这样做的实际收益是你想换一种输入格式只需要改 loadTasks想加一种新调度算法只需要在 runScheduler 里加一个 case 分支测试时也可以单独验证每一层。我第一次改造这种结构时感触很深课设代码最容易烂在「所有事情都塞在 main 里」而这个工程把边界划得很干净二次开发时几乎不用重构。3. 核心代码拆解一个任务从「到达」到「跑完」在调度器里的完整生命周期这一章是整套代码最值得逐行读的部分。调度器的本质是一个按时钟节拍推进的模拟器每个节拍代表一个单位时间程序在一个大循环里不断回答三个问题——当前有没有新任务到达CPU 上有没有任务在跑如果没有下一个该选谁理解了这条时间轴四种算法其实只是第三个问题的答案不同而已。3.1 TCB用结构体把任务的「一生」记录下来所有调度算法的输入输出都是围绕任务控制块TCB展开的它相当于操作系统的进程控制块在课设里的简化版typedef struct TCB { int pid; // 任务编号从 1 开始递增 int arriveTime; // 到达时间单位是时钟节拍 int serviceTime; // 需要的总 CPU 运行时间 int remainTime; // 剩余运行时间时间片轮转要实时修改它 int priority; // 优先级数值越小优先级越高 int startTime; // 第一次被调度执行的时间初始为 -1 int finishTime; // 执行完成的时间初始为 -1 int status; // 0未到达 1就绪 2运行 3完成 struct TCB* prev; // 双向链表前驱指针 struct TCB* next; // 双向链表后继指针 } TCB;字段设计的几个关键点remainTime 和 serviceTime 分开存是因为时间片轮转会一次次打断任务执行serviceTime 是任务的固有属性用来算周转类指标remainTime 是动态状态归零代表任务完成startTime 初始化为 -1 而不是 0是为了区分「任务真的在 0 时刻开始执行」和「还没执行过」这个细节在计算带权周转时间时特别容易出错status 字段配合链表指针使用能快速判断一个任务当前是否还在就绪队列里防止重复入队。prev 和 next 直接嵌在 TCB 里而不是再包一层链表节点结构是为了让同一个 TCB 既能在链表中被管理又能直接作为堆里的元素避免指针来回转换的麻烦。3.2 就绪队列双向链表的尾插与 O(1) 摘除就绪队列是 FCFS 和 RR 的基础容器它维护一个全局双向链表头指针指向最先到达的任务尾指针指向最后到达的任务// 将任务挂到就绪队列尾部FCFS 和 RR 都用它入队 bool appendReady(TCB* task) { if (task NULL) return false; if (readyHead NULL) { readyHead readyTail task; // 队列为空 } else { readyTail-next task; // 挂在尾节点后面 task-prev readyTail; task-next NULL; readyTail task; // 更新尾指针 } readyCount; return true; } // 从就绪队列中摘除指定任务已知节点时 O(1) bool removeReady(TCB* task) { if (task-prev ! NULL) task-prev-next task-next; else readyHead task-next; // 删的是头节点 if (task-next ! NULL) task-next-prev task-prev; else readyTail task-prev; // 删的是尾节点 task-prev task-next NULL; // 断开防止野指针 readyCount--; return true; }逻辑说明appendReady 维护队尾新任务永远从尾部进入这样先到达的任务天然排在前面FCFS 按链表顺序取头节点即可removeReady 最核心的价值在时间片轮转场景——一个任务被抢占后重新入队或者优先级调度中一个高优先级任务插队后把正在运行的任务放回队列都需要从链表中间把某个节点摘掉再重新挂到尾部如果只有 next 指针必须从头遍历才能拿到前驱而双向链表用 task-prev 直接回退删除成本降为 O(1)。这两个函数配合 readyCount 计数器还顺带解决了调度主循环的终止条件判断。3.3 调度主循环时钟节拍驱动下的策略分发scheduler.cpp 里的核心是一个 for 循环clock 从 0 开始每轮加一模拟时间流逝for (int clock 0; running ! NULL || readyCount 0; clock) { // 第一步当前时刻是否有任务到达到达则进入就绪队列 while (taskIndex taskCount tasks[taskIndex].arriveTime clock) { tasks[taskIndex].status READY; appendReady(tasks[taskIndex]); taskIndex; } // 第二步CPU 空闲且有就绪任务时按策略选一个执行 if (running NULL readyCount 0) { running selectTask(clock, policy); if (running-startTime -1) running-startTime clock; running-status RUNNING; } // 第三步当前任务执行一个节拍 if (running ! NULL) { running-remainTime--; if (running-remainTime 0) { running-finishTime clock 1; // 完成时刻是下一拍 running-status FINISHED; running NULL; // 释放 CPU } else if (policy POLICY_RR (clock 1) % timeSlice 0) { // 时间片耗尽任务回到就绪队列尾部 running-status READY; appendReady(running); running NULL; } } }这段循环有三个容易写错的地方资源里的实现处理得比较到位。第一是到达检查用的是 while 而不是 if因为同一时刻可能多个任务一起到达第二是抢占语义SJF 和优先级调度如果在非抢占模式下running 为 NULL 才发生调度而抢占式优先级需要在第二步之前先判断「新到达的任务是否比当前任务的优先级更高」资源默认是非抢占版本改抢占只需在第二步前加一段比较逻辑第三是 finishTime 的计算任务在 clock 这一拍执行完它的完成时刻应该是 clock 1这是时间轴左闭右开的结果很多初版实现在这里少加 1导致周转时间整体偏小我当年就在这上面翻过车。3.4 二叉堆SJF 与优先级调度共用的「最优先」底座selectTask 函数内部根据 policy 分流SJF 和优先级调度走的是同一个小根堆区别只在于堆节点比较的 key 是什么// 小根堆上浮新元素从底部向上调整到合适位置 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; // 父节点更小停止上浮 swap(q-data[cur], q-data[parent]); cur parent; } } // 小根堆下沉堆顶取出后把最后一个元素放到根部调整 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 是个小工具函数keyType 为 1 时返回 serviceTimekeyType 为 2 时返回 priority这样同一套堆代码同时服务 SJF 和优先级调度只改比较的字段不复制代码。push 的上浮过程和 pop 的下沉过程都是标准的堆调整时间复杂度 O(log n)。这里有个课设答辩时值得讲的细节SJF 和优先级调度都需要在任务到达时把任务插入堆每次调度时从堆顶取最值如果就绪队列用链表做每次取最值都是 O(n) 的全表扫描用堆之后整体复杂度从 O(n²) 降到 O(n log n)case3 里几百个任务的样本能直观看到运行耗时差异。4. 编译运行与结果验证三条命令跑出四种算法的对比数据到了实操环节。这份资源自带的 Makefile 已经处理好了头文件依赖和编译参数理论上你只需要在命令行执行三个动作就能看到输出结果但我会把每一步背后的含义也说明白这样出问题时你知道去哪里排查。4.1 编译与运行命令行 Makefile 与 IDE 两种姿势cd TaskScheduler make clean make ./scheduler data/case1.txt 0 1参数说明第一个参数是测试数据文件路径第二个参数是调度策略编号0FCFS1SJF2优先级3RR第三个参数是时间片大小只在策略为 3 时生效其他策略下会被忽略。Makefile 里默认了 g 编译标准为 C11编译选项带上 -Wall 打开全部警告课设阶段把警告当错误处理能帮你避开不少隐式类型转换和未初始化变量的问题。如果你习惯用集成开发环境也可以把 src 目录下所有 .cpp 文件加入工程头文件路径指向 src然后直接编译 main.cpp效果完全一样。我一般建议先用命令行跑通一次因为 Makefile 把整个构建过程透明化了出错了能看到具体是哪个文件哪个函数的问题IDE 反而把编译细节藏起来了。跑完之后终端会先打印一张文本形式的甘特图用竖线分隔时间轴和任务编号然后打印每个任务的到达时间、开始时间、完成时间、周转时间、带权周转时间最后是四项平均值。case1 只有 5 个任务你可以拿纸笔手动推一遍 FCFS 的结果跟程序输出比对如果一致说明工程本身没问题后面换算法和数据就是参数的事。4.2 输入文件格式任务描述文件的字段约定data 目录下的 txt 文件格式非常直白第一行是任务总数从第二行开始每行四个整数分别对应 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 逐个读取遇到文件提前结束会自动报错并返回 false。这里有个坑要提醒priority 数值越小代表优先级越高这是资源里统一的约定如果你自己造测试数据时把数值大小关系搞反优先级调度的结果会完全反过来。另外到达时间可以不从 0 开始也不必严格递增但同一个任务的到达时间不能晚于它自己的完成时间否则算出来的周转时间是负数这是逻辑上就不合法的数据。4.3 结果验证周转时间、带权周转时间、甘特图怎么对得上程序输出的统计指标是课设报告的核心数据也是答辩时老师最可能追问的部分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公式说明周转时间 finishTime - arriveTime表示任务从到达系统到执行完成经历的总时间带权周转时间 周转时间 / serviceTime衡量的是「等待时间被放大了多少倍」短作业如果被长作业堵在后面这个值会非常大所以它是评估调度算法公平性的关键指标。案例里 Task 3 运行时间只有 1 个节拍却等了 10 拍才执行完带权周转时间冲到 11这就是典型的短作业吃亏场景也是 SJF 能显著改善的指标。你可以用程序输出跟手算结果对一遍如果 FCFS 下对不上先检查 finishTime 是不是按 clock 1 计的再检查同一时刻多个任务到达时的入队顺序是否稳定。5. 避坑指南课程设计与真实调度器之间的四个经典翻车点这一章写的是我在调试这类模拟器时遇到过的真实问题也是答辩时老师爱挖的坑。每一条都是「现象 → 原因 → 解决」的结构你在跑通之后拿自己的测试数据去触发一遍会比只看代码理解得更深。5.1 新任务到达瞬间正在运行的任务没让出 CPU现象使用抢占式优先级调度时明明 4 个任务运行时间都不长运行结果里却出现了一个高优先级任务被低优先级任务压在后面执行的怪异序列。 原因调度主循环只有在 running NULL 时才调 selectTask 选新任务新任务到达只是被放进了就绪队列没有在当下立即触发一次抢占判断。资源默认实现的是非抢占式调度抢占逻辑缺失。 解决在检查新任务到达之后、执行当前任务之前增加一个抢占判断分支如果新任务 priority 比 running 的 priority 更小就把 running 放回就绪队列并置空让下一拍重新 selectTask。注意抢占的粒度是「一个完整时钟节拍」新任务最早只能从下一拍开始执行不能在同一拍内完成切换。5.2 SJF 的饥饿问题被固定测试数据掩盖现象case1 和 case2 跑 SJF 时一切正常但你自己生成一组「一个大长任务 若干个持续到达的短任务」的数据后发现长任务迟迟无法完成最后被迫地反复被短任务插队。 原因SJF 每次选择剩余运行时间最短的任务如果短任务源源不断到达长任务永远选不上这就是经典的饥饿现象。课程设计通常不会用极端数据测试但答辩老师一定会问「SJF 的缺点是什么」。 解决工程里 SJF 用的是不可抢占版本已经能缓解一部分问题真要做改进可以改成 HRRN最高响应比优先响应比 等待时间 运行时间/ 运行时间它天然兼具 SJF 的短作业优先和 FCFS 的防饥饿特性改造成本只在 selectTask 里多算一个比值代码量很小但答辩效果很好。5.3 时间片轮转的完成时间多算一拍现象RR 策略下一个任务明明运行了 5 拍服务时间也是 5打印出来的 finishTime 却比预期大了 1周转时间整体偏大。 原因把完成任务的那一拍直接写成了 running-finishTime clock忽略了时钟节拍是左闭右开区间——任务在第 clock 拍执行完完成时刻应该是 clock 1。同理时间片耗尽判断写成 clock % timeSlice 0 也会错一拍。 解决统一用 clock 1 作为完成时刻时间片耗尽判断用 (clock 1) % timeSlice 0。写完用 serviceTime 只有 1 的任务做最小测试它的 finishTime 必须等于 arriveTime 1这个用例能一秒暴露问题。5.4 多任务同时到达时就绪队列的插入顺序不稳定现象两份结构相同、只有任务编号顺序不同的测试数据在 FCFS 下跑出的甘特图不一致某些任务的前后关系发生了对调。 原因loadTasks 按文件顺序把任务读入数组而调度主循环里检查到达用的是 while (arriveTime clock)同一时刻到达的任务入队顺序取决于它们在这个时刻的检查顺序如果文件的写入顺序和任务编号顺序不一致数组遍历顺序也会变链表尾插结果就会不同。 解决在 loadTasks 读完后对 tasks 数组按 arriveTime 做一次稳定排序相同到达时间的任务保持编号升序或者把 appendReady 改成按 pid 二次比较插入。稳定的入队顺序是结果可复现的前提否则你写报告时换一份数据格式前后两组实验就对不上了。6. 二次开发把「一次读入全部任务」改成「运行时动态注入」的交互式调度器循环结构的调度器最大的限制是任务集合在开始时就被定死时钟循环只能消费已经读入的数组。如果你想让这个课设更有区分度我建议把它改成交互式版本不再是加载完整文件后一口气跑完而是每到一个时钟节拍先从文件或标准输入读入新到达的任务再决定谁执行。改造的核心是把「提前读入数组」变成「边跑边读」。具体做法是在 main 里维护一个输入流runScheduler 的循环每推进一拍就尝试从输入流读一行任务读到就按 TCB 初始化并加入就绪队列。原先 loadTasks 的批量解析可以保留为「预置数据」模式新增一个 -i 参数interactive走动态注入路径// 交互式注入每个时钟节拍调用一次有新任务就返回 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) { // 只接收当前时刻的任务 temp.remainTime temp.serviceTime; temp.startTime temp.finishTime -1; temp.status READY; tasks[taskCount] temp; appendReady(tasks[taskCount - 1]); } return true; }改造完成后验证方法也很直接先用原来的 case1 跑非交互模式再用交互模式逐个注入同样的 5 个任务两条路径的输出必须完全一致这个对拍实验能证明你的动态注入没有改变调度语义。之后再设计一个「运行期间临时追加任务」的场景观察追加任务的到达时间是否被正确插入到时间轴中。这个改造不仅让课设从「静态演示」升级成了「动态系统」答辩时还能顺带引出「任务预热、批量到达」等真实系统话题远比念报告有说服力。从那以后我每次拿到一份课设工程都会先花半小时把「入口参数、模块边界、输出口径」三个问题画清楚再动手改这个习惯帮我少踩了很多坑。希望帮到你。本文还有配套的精品资源点击获取