任务调度器课程设计：链表与二叉堆实现FCFS、SJF等四种算法

简介：面向大二数据结构课程设计的任务调度器完整实现，基于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 数据结构选型：为什么就绪队列用双向链表，优先级调度用二叉堆

这是答辩时老师最爱问的问题，也是这份资源设计的隐藏主线。调度器里有两类核心操作：一类是「任务到达后插入就绪集合」，另一类是「每次调度时取出下一个要执行的任务」。不同的算法对这两类操作的频率要求不一样，于是选型也不一样。

这份资源的组合方案是「双向链表 + 二叉堆」：就绪队列本体用双向链表，因为时间片轮转要把被抢占的任务重新挂到队尾，FCFS 也是天然的先到先服务顺序，链表尾插正好 O(1)；而 SJF 和优先级调度需要反复「取出当前最优任务」，如果每次都用链表的 O(n) 遍历，20 个任务的样例看不出问题，case3 随机生成几百个任务时差距就会非常明显，所以这两类算法走的是二叉堆。值得注意的是，双向链表在这里还有一个隐藏优势：时间片轮转里任务可能被执行一半后被抢走，此时它还在链表中，需要按节点直接摘除，双向链表在已知节点的情况下删除是 O(1)，单向链表还得从头遍历找前驱，这就是设计上多付一个 prev 指针换来的收益。

2.3 模块划分：读入、调度、统计三层隔离，接口只看 scheduler.h

scheduler.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 是算法枚举，资源里约定 0=FCFS、1=SJF、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 时返回 serviceTime，keyType 为 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

参数说明：第一个参数是测试数据文件路径，第二个参数是调度策略编号（0=FCFS，1=SJF，2=优先级，3=RR），第三个参数是时间片大小，只在策略为 3 时生效，其他策略下会被忽略。Makefile 里默认了 g++ 编译标准为 C++11，编译选项带上 -Wall 打开全部警告，课设阶段把警告当错误处理能帮你避开不少隐式类型转换和未初始化变量的问题。如果你习惯用集成开发环境，也可以把 src 目录下所有 .cpp 文件加入工程，头文件路径指向 src，然后直接编译 main.cpp，效果完全一样。我一般建议先用命令行跑通一次，因为 Makefile 把整个构建过程透明化了，出错了能看到具体是哪个文件哪个函数的问题，IDE 反而把编译细节藏起来了。

跑完之后终端会先打印一张文本形式的甘特图，用竖线分隔时间轴和任务编号，然后打印每个任务的到达时间、开始时间、完成时间、周转时间、带权周转时间，最后是四项平均值。case1 只有 5 个任务，你可以拿纸笔手动推一遍 FCFS 的结果跟程序输出比对，如果一致，说明工程本身没问题，后面换算法和数据就是参数的事。

4.2 输入文件格式：任务描述文件的字段约定

data 目录下的 txt 文件格式非常直白，第一行是任务总数，从第二行开始每行四个整数，分别对应 TCB 里的 pid、arriveTime、serviceTime、priority：

5 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: arrive=0 start=0 finish=8 turnaround=8 weighted=1.00 Task 2: arrive=2 start=8 finish=13 turnaround=11 weighted=2.20 Task 3: arrive=3 start=13 finish=14 turnaround=11 weighted=11.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 个任务，两条路径的输出必须完全一致，这个对拍实验能证明你的动态注入没有改变调度语义。之后再设计一个「运行期间临时追加任务」的场景，观察追加任务的到达时间是否被正确插入到时间轴中。这个改造不仅让课设从「静态演示」升级成了「动态系统」，答辩时还能顺带引出「任务预热、批量到达」等真实系统话题，远比念报告有说服力。从那以后我每次拿到一份课设工程，都会先花半小时把「入口参数、模块边界、输出口径」三个问题画清楚再动手改，这个习惯帮我少踩了很多坑。希望帮到你。

本文还有配套的精品资源，点击获取