简介面向大二数据结构课程设计的任务调度器系统基于C/C实现完整覆盖从任务定义、优先级排队到调度执行的典型流程适合正在完成课程设计或希望深入理解数据结构实际应用的同学参考。压缩包共38个文件约40.97MB工程主体包括C源文件与头文件.cpp/.hpp、Visual Studio 2019解决方案与项目文件.sln/.vcxproj/.filters以及编译生成的exe、obj、pdb等可执行与调试文件解压后直接用VS2019打开即可运行查看效果。已有207人学习使用具备一定的参考价值。资源提供完整可运行源码、测试入口及类图设计文件帮助读者快速读懂基于队列、链表等结构的调度算法实现并可直接在此框架上继续扩展功能。1. 任务调度器一个课设题里最常被低估的数据结构战场不是吓唬人同一个任务调度器课设题每年都有两拨人交作业一拨写了两三百行 if 嵌套把任务塞进数组硬排序答辩时被问一句“就绪队列用的什么结构”就卡住另一拨先把调度算法和数据结构对上号代码没多几行但从 FCFS 迁到时间片轮转、优先级抢占、多级反馈队列都只是换一个容器的事。这个课设题的价值不在“调度器”三个字而在于它把队列、堆、链表、状态机全放进同一个场景逼你回答一个真问题任务到了往哪放、谁先走、怎么换人。2. 把需求拆到能写代码任务模型、状态机与调度算法矩阵2.1 四个必须先定下来的东西任务、状态、算法、指标拿到这个题第一件事不是开 IDE而是把题目当黑匣子拆一遍。输入是一批任务的描述输出是一张调度时间表和一张指标报表黑匣子里面只有四件事任务长什么样、任务有哪些状态、支持哪几种调度算法、用什么指标评价。这四个问题不定下来后续每一个新需求都会变成到处打补丁。任务对象建议用一个 Task 结构体承载字段至少是下面这张表里的内容。很多同学一上来做“万能结构体”塞十几个字段结果自己都不清楚每个字段在当前算法里有没有被读到维护成本全花在黑匣子里。字段含义主要参与的调度pid任务编号全部算法arrival_time到达时间FCFS、所有算法的到达判断service_time服务时间SJF、HRRN、指标计算remaining_time剩余服务时间RR、抢占式调度priority优先级HPF、MLFQstart_time首次被调度时间指标计算finish_time完成时间指标计算算法方面基础课设覆盖 FCFS、SJF、HRRN、RR 四种足够。HRRN 按响应比动态计算可以看作 SJF 的平滑版代码里其实只是比较器不同。如果题目点名要求支持多级反馈队列那再往容器层面加队列这部分放到最后讲。指标也要先定义好因为它决定数据结构和比较器。平均周转时间和平均带权周转时间这两个指标能暴露绝大多数容器选型错误。你在选容器之前先想清楚我要不要按 service_time 取最小要不要把任务原样放回队尾这两个问题会直接引出堆和队列两个完全不同的实现方向。2.2 任务状态机就绪、运行、阻塞、完成四个状态怎么建模任务状态必须用枚举而不是散落的 int 宏可读性和 switch 分支的整洁度都会好很多。常见做法是给状态一个独立枚举类型代码里最好只用四种状态不要额外造“等待输入”“暂停”这种自找麻烦的状态。typedef enum { TASK_READY, TASK_RUNNING, TASK_BLOCKED, TASK_DONE } TaskState;状态迁移只有四条任务到达后进入就绪就绪队列队首被 CPU 选中后进入运行运行中被时间片打断或被更高优先级任务抢占时回到就绪运行完所有剩余服务时间后进入完成。阻塞状态只在模拟 I/O 等待时才出现如果选题没有明确要求模拟 I/O就不要在基础代码里实现否则每 tick 都要扫描阻塞队列调度器主循环会变得很难调。主循环的设计原则是只负责三件事的触发新任务到达、时间片耗尽、服务完成。状态迁移集中在一个函数里做不要在 while 主循环里到处改 state。这样后续切换抢占式调度时只需要多一个事件源不用动状态机本身。完成状态有一个边界必须注意任务剩余时间归零的那个 tick 就应该记录完成时间并立刻从运行态摘除不能等“下一个 tick 再检查”否则所有周转时间都会多算一个单位。这是我调试时踩过的坑后面避坑部分再展开。2.3 先定评价指标再做算法选型在把算法选型之前先把指标公式写在注释里。周转时间 T 是任务从到达系统到完成的时间跨度带权周转时间 W 是 T 除以实际需要的服务时间W 越接近 1 说明任务被照顾得越精准。平均带权周转时间把短作业的等待放大用来暴露“长作业把短作业堵死”的场景。double avg_turnaround total_turnaround / completed_count; double avg_weighted_turnaround total_weighted_turnaround / completed_count; double throughput completed_count / (double)current_time;吞吐量是完成任务数除以总仿真时长这个指标能反映调度器整体的“压榨效率”。三个指标一起看能看出算法是不是偏科FCFS 平均周转可能还能看但带权一定难看SJF 带权好看但长作业可能被饿得脸色发白。数据结构选型跟着指标走要按 service_time 取最小就绪容器必须是最小堆要按到达先后排队就用顺序队列要按时间片轮转队列还得支持放回队尾。换句话说指标公式一旦写在纸上容器选型基本就定了一半。3. 数据结构选型任务调度器把队列、堆、链表焊到一个战场3.1 为什么第一版代码不能靠数组硬顶部分同学觉得数组最直观任务到达就arr[count] task调度时遍历找到 service_time 最小的下标。代码第一天很舒服第二天要加 RR 就开始痛苦时间片到期的任务放回队尾数组要搬移新任务插入到中间也要搬移队首出队还要搬移。如果不对数组做循环队列改造三次搬移会把主循环搞出几百行 if。要区分两件事任务全集也就是所有要仿真的任务可以用数组但运行中的动态容器也就是就绪队列不能用裸数组模拟。裸数组的 O(n) 出队和 O(n) 插入在任务量 100 时看不出来但在报告的复杂度分析那一栏一定不好看。更实际的问题是把你的代码交给另一个人改时对方看到数组只能继续在数组里打补丁。常见做法是FCFS 和 RR 用带头结点的单向链表SJF 和 HPF 用二叉堆如果题目要求时间片轮转的对比实验再多实现一个环形数组。下面把三种容器各自说清楚。3.2 顺序队列FCFS 和 RR 的公共底座FCFS 很简单新任务到达就插到尾部CPU 空闲时从头取一个。用链表实现时关键是同时维护 head 和 tail 两个指针避免每次入队都从头遍历。这里我给一个可以直接用的链表队列骨架。typedef struct Node Node; struct Node { Task* task; Node* next; }; typedef struct { Node* head; /* 队首出队位置 */ Node* tail; /* 队尾入队位置 */ int length; } LinkedQueue; void enqueue(LinkedQueue* q, Task* t) { Node* n (Node*)malloc(sizeof(Node)); n-task t; n-next NULL; if (q-tail) { q-tail-next n; } else { q-head n; } q-tail n; q-length; } Task* dequeue(LinkedQueue* q) { if (q-length 0) return NULL; Node* n q-head; Task* t n-task; q-head n-next; if (q-head NULL) { q-tail NULL; } free(n); /* 只释放节点不释放 Task 本身 */ q-length--; return t; }这里有两个细节值得说。一是出队时对 tail 的置空处理绝对不能省如果只移动 head 不处理 tail下一次入队时会通过旧 tail 写入链表直接成环。二是free(n)只释放链表节点Task 本身是由外部持有的释放策略要看任务对象是否在堆上分配。后面避坑部分会专门讲这个。FCFS 用这个队列天然匹配RR 也用同一个队列只是多一个“时间片耗尽后重新入队”的操作。所以顺序队列是整个任务调度器里复用率最高的容器。3.3 最小堆SJF 和 HPF 的最省心选择SJF 每次要从就绪队列里取 service_time 最小的任务。用链表插入排序也可以但每次入队要 O(n) 找位置而且任务常常在运行中到达链表的维护逻辑会更碎。二叉堆是常规做法插入 O(log n)取堆顶 O(1)整体复杂度最稳。这里给一个数组实现的最小堆数组下标从 1 开始方便用i / 2找父节点。typedef struct { Task** data; /* 数组从下标 1 开始 */ int capacity; int size; } Heap; void heap_push(Heap* h, Task* t) { if (h-size h-capacity) { h-capacity * 2; h-data (Task**)realloc(h-data, h-capacity * sizeof(Task*)); } int i h-size; /* 小根堆父节点键值小于等于子节点 */ while (i 1 h-data[i / 2]-service_time t-service_time) { h-data[i] h-data[i / 2]; i / 2; } h-data[i] t; } Task* heap_pop(Heap* h) { if (h-size 0) return NULL; Task* ret h-data[1]; Task* last h-data[h-size--]; int i 1; while (i * 2 h-size) { int child i * 2; if (child 1 h-size h-data[child 1]-service_time h-data[child]-service_time) { child; } if (h-data[child]-service_time last-service_time) break; h-data[i] h-data[child]; i child; } h-data[i] last; return ret; }比较器是这里最容易翻车的地方SJF 用 service_time 的最小堆HPF 如果想让值越大优先级越高就把比较方向反过来变成最大堆。很多同学把 SJF 的堆直接改成比较 priority 字段时只改一半导致堆顶取出来既不是最短也不是最高优先这个属于典型比较器串线。为什么用数组而不是链表实现堆数组按下标找父子节点是 O(1)链表要额外存两个指针缓存也不友好。容量建议直接开成任务数的两倍再加一避免中途扩容影响调试。3.4 环形数组RR 的另一个选项与边界RR 也可以不用链表用定长环形数组实现就绪队列一个数组加 head、tail、count 三个下标入队时 tail 后移出队时 head 后移超过容量则取模回绕。这种写法适合任务数量固定且上限明确的场景比如你可以确认就绪队列最多 128 个任务。#define MAX_QUEUE 128 typedef struct { Task* slots[MAX_QUEUE]; int head; int tail; int count; } RingQueue; int enqueue_ring(RingQueue* q, Task* t) { if (q-count MAX_QUEUE) return -1; q-slots[q-tail] t; q-tail (q-tail 1) % MAX_QUEUE; q-count; return 0; }有了这个基础RR 时间片调度里“任务回到队尾”只需要一句 enqueue_ring。但注意环形数组有个隐藏边界一旦容量需要动态增长取模公式和容量绑定扩容后所有下标都要重新映射正确处理起来比链表麻烦得多。所以我的建议是FCFS/RR 用链表SJF/HPF 用堆环形数组只在确定队列上限后作为对比实现来写。4. 核心实现调度循环、时间片与三个必调参数4.1 统一调度循环支持四种算法的最小骨架调度器的心脏是一个仿真主循环每一轮代表一个时间片 tick。循环里按固定顺序做三件事先接收新到达的任务再处理当前任务的运行状态最后从就绪队列补位。顺序错了整个时间线就会偏一格。void run_scheduler(Simulator* sim, Policy policy) { while (sim-unfinished_count 0) { /* 1. 把到达时间 当前时间的任务放入就绪队列 */ while (sim-next_task_idx sim-task_count sim-tasks[sim-next_task_idx].arrival_time sim-current_time) { add_to_ready(sim, sim-tasks[sim-next_task_idx], policy); sim-next_task_idx; } /* 2. 如果 CPU 空闲从就绪队列取一个任务 */ if (sim-current_task NULL) { sim-current_task take_from_ready(sim, policy); if (sim-current_task ! NULL) { sim-current_task-state TASK_RUNNING; if (sim-current_task-start_time 0) { sim-current_task-start_time sim-current_time; } sim-quantum_used 0; } } /* 3. 执行一个时间单位 */ if (sim-current_task ! NULL) { sim-current_task-remaining_time--; sim-quantum_used; if (sim-current_task-remaining_time 0) { sim-current_task-finish_time sim-current_time 1; sim-current_task-state TASK_DONE; sim-unfinished_count--; sim-current_task NULL; } else if (policy RR sim-quantum_used sim-quantum_size) { sim-current_task-state TASK_READY; add_to_ready(sim, sim-current_task, policy); sim-current_task NULL; } } sim-current_time; } }很多人的习惯是先推进时间再接收任务这样会把到达时间刚好等于当前 tick 的任务漏掉一个单位。我这里用arrival_time current_time判断同时先入队再执行保证任务不会迟到。完成优先于时间片到期这个顺序必须固定如果先判断时间片一个剩余时间为 0 的任务还会被放回队尾再跑一轮完成时间会多算。take_from_ready函数负责按 policy 决定从队列还是堆取任务add_to_ready负责按 policy 决定是插链表尾部还是压入堆。这样四种算法共用一套主循环切换算法只需要改比较器不需要动循环结构。4.2 三个必调参数时间片、任务数量、随机种子运行调度器之前先调三个参数它们直接决定仿真结果能不能复现、能不能用来对比参数建议值调参说明QUANTUM_SIZE3~5 tick时间片太小会让上下文切换频繁平均带权周转时间偏大时间片太大则 RR 退化成 FCFSTASK_COUNT10~15 个太少指标没有统计意义太多不容易肉眼核对时间线SEED固定如 20240601固定随机种子后每次运行结果一致答辩时可以用同一份数据复现做实验报告时时间片建议做一组梯度对比1、3、5、10。你会在结果里看到时间片越小长作业被切得越碎短作业也不能一口气跑完平均带权周转时间反而不好看。这个梯度数据是报告里最直观的一张表。随机种子容易被忽略。如果不固定每次运行任务都不一样两个算法之间的对比就没有公平性。固定种子之后你才能在同一个任务集上比较四种算法也能在答辩现场复现同一个结果。4.3 算法切换与指标统计把比较器做成参数调度算法的差异本质上就是容器和比较器的差异。把比较器定义成函数指针可以让主循环完全不知道“我现在跑的是 SJF 还是 HPF”。typedef int (*TaskComparator)(const Task* a, const Task* b); int cmp_arrival(const Task* a, const Task* b) { return a-arrival_time - b-arrival_time; /* FCFS */ } int cmp_service(const Task* a, const Task* b) { return a-service_time - b-service_time; /* SJF */ } int cmp_priority_desc(const Task* a, const Task* b) { return b-priority - a-priority; /* HPF */ }比较器方向的一致性很关键堆内部认为自己弹出的元素是“最小”的那个。HPF 用最大堆时可以取反比较器也可以把 priority 取反后存入堆。但如果只反转一个地方堆会不稳定出现“看起来优先级高的任务每次最后才完成”的诡异现象。建议单独写一个验证函数入堆 5 个乱序任务连续 pop 后看顺序是否符合预期。指标统计放在调度循环之后。注意用浮点数计算不要用整数除法平均带权周转时间一旦被截断和手工验算对不上就麻烦了。double total_turnaround 0; double total_weighted_turnaround 0; for (int i 0; i task_count; i) { double T tasks[i].finish_time - tasks[i].arrival_time; double W T / tasks[i].service_time; total_turnaround T; total_weighted_turnaround W; } printf(avg_T%.2f avg_W%.2f\n, total_turnaround / task_count, total_weighted_turnaround / task_count);5. 避坑手册任务调度器里 5 个让代码“玄学”故障的雷区5.1 坑一链表只释放节点不释放任务体内存泄漏发病慢现象模拟器跑几十轮后内存占用只增不减Task 数量调到 1000 时程序直接卡死。 原因出队时只free(node)而 Task 本身是在任务到达时 malloc 的没人负责释放。链表节点和任务对象是两个生命周期必须分开管理。 解决定义destroy_queue先遍历队列释放所有 Task 指针再释放节点。如果你把任务放进全局数组而不是堆上那节点里只存结构体拷贝也行但要保证 Task 对象的所有权和生命周期在项目里只有一个主人。5.2 坑二RR 入队方向写反轮转变成栈式调度现象任务 A、B、C 顺序到达跑 RR 一轮后完成顺序变成 C、B、A。 原因把新到任务或者超时任务用头插法插到了队首队列实际上变成了栈。 解决RR 的入队必须严格在 tail 端操作。代码注释里直接写一行“RR: ENQUEUE AT TAIL ONLY”提醒自己。调试时打印队列顺序队首到队尾必须保持到达顺序一旦发现反序优先查入队函数。5.3 坑三非抢占算法被写成伪抢占SJF 指标错得离谱现象SJF 跑出来的平均带权周转时间竟然比 FCFS 还差。 原因主循环每 tick 都重新扫描就绪队列取 service_time 最小的任务导致 CPU 上的任务随时可能被换下来等于实现成了抢占式 SJF而课设通常要求非抢占。 解决非抢占模式下只在current_task NULL时才重新选任务抢占模式则在新任务到达时比较当前任务和队首任务的优先级。要明确区分两种模式并在报告里写清楚你采用的是哪一种。5.4 坑四任务生成器让优先级全为 0HPF 退化成 FCFS现象HPF 调度结果看起来跟 FCFS 一模一样优先级完全没起作用。 原因随机任务生成时priority rand() % 10可能生成一堆 0也可能所有任务优先级都相同比较器返回恒等值堆结构形同虚设。 解决生成参数用rand() % PRIORITY_RANGE 1保证优先级在 1 到 10 之间。并且把任务列表打印到控制台看一眼优先级分布是否合理。另一个相关问题是随机种子没固定每次运行任务不同导致优先级对结果的影响没法稳定复现。5.5 坑五时间片耗尽与任务完成同 tick先判定完成现象任务剩余时间已经归零却仍被放回队尾再跑了一轮完成时间多算一个 tick。 原因判断顺序写成先检查时间片是否耗尽再检查剩余时间是否为 0。 解决每个 tick 先递减 remaining_time然后先判断是否为 0完成优先于时间片到期。这个顺序放错RR 的周转时间会系统性偏大而且很难从最终指标看出来。注意以上五条坑全部能在输出指标上被抓住但如果你没有先打印每个任务的 start_time 和 finish_time光看平均指标很难定位。调试时优先打印逐任务明细再看汇总这个顺序能省下一半的排查时间。6. 从能跑到能拿高分固定用例手工验算与三个加分改造6.1 先用 5 个任务的固定用例验证指标写代码之前先准备一个固定任务集手工算好期望指标。这里给一组我常用的用例tick 从 0 开始SJF 按非抢占模式计算PID到达服务FCFS 完成FCFS 周转SJF 完成SJF 周转P0044444P1137698P22512101816P332141163P4441814139手工算下来的结果是FCFS 平均周转 9.00平均带权周转 2.80SJF 平均周转 8.00平均带权周转约 2.12。程序输出和这两个值对不上就说明某个环节有 bug对上了再换更大的随机任务集。6.2 加分改造一控制台画出甘特图答辩时老师第一眼看的就是时间轴。在调度循环里记录每个 tick 正在运行的任务 pid然后打印成一行甘特图能直观看出时间片切换的位置。/* 每 tick 推进时记录当前任务 pid */ timeline[current_time] current_task ? current_task-pid : -1; void print_gantt(int* timeline, int total_tick) { for (int t 0; t total_tick; t) { if (timeline[t] 0) { printf(P%d , timeline[t]); } else { printf(IDLE ); } } printf(\n); }甘特图还能用来验证边界比如 RR 时间片从 3 改成 5 后切换点应该精确出现在第 5、10、15 个 tick 上如果切换点提前或延后说明时间片计数的位置错了。6.3 加分改造二与三多级反馈队列与阻塞事件模拟想拿高分可以在基础调度的外部加两个扩展。第一个是多级反馈队列 MLFQ三个队列Q1 时间片 1Q2 时间片 3Q3 时间片不断翻倍新任务先进 Q1时间片耗尽未完成就降级到下一级。这个扩展几乎不需要改容器只需要三个 LinkedQueue 和一个“降级”规则但它能体现你对调度器的理解深度。第二个扩展是阻塞事件模拟给 Task 增加io_need字段任务运行过程中随机触发 I/O 等待进入 TASK_BLOCKED 状态阻塞若干 tick 后重新回到就绪队尾。这里会让状态机真正运转起来也能帮你提前练一遍阻塞队列的管理。我自己做这个课设时的教训是先跑固定用例指标算对了再谈可视化最后才加新算法。排序和比较器这类“裁判逻辑”一旦结果怪异不要先怀疑调度循环先打印每个任务的 start_time 和 finish_time跟手工表逐项对。把这条变成肌肉记忆后任务调度器课程设计基本就不会翻车。希望帮到你。本文还有配套的精品资源点击获取
