企业官网建设流程全解析

简介：面向大二数据结构课程设计的任务调度器系统，基于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 结构体承载，字段至少是下面这张表里的内容。很多同学一上来做“万能结构体”，塞十几个字段，结果自己都不清楚每个字段在当前算法里有没有被读到，维护成本全花在黑匣子里。

算法方面，基础课设覆盖 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 三个必调参数：时间片、任务数量、随机种子

运行调度器之前，先调三个参数，它们直接决定仿真结果能不能复现、能不能用来对比：

做实验报告时，时间片建议做一组梯度对比：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 坑四：任务生成器让优先级全为 0，HPF 退化成 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 按非抢占模式计算：

手工算下来的结果是：FCFS 平均周转 9.00，平均带权周转 2.80；SJF 平均周转 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 时间片 1，Q2 时间片 3，Q3 时间片不断翻倍；新任务先进 Q1，时间片耗尽未完成就降级到下一级。这个扩展几乎不需要改容器，只需要三个 LinkedQueue 和一个“降级”规则，但它能体现你对调度器的理解深度。

第二个扩展是阻塞事件模拟：给 Task 增加io_need字段，任务运行过程中随机触发 I/O 等待，进入 TASK_BLOCKED 状态，阻塞若干 tick 后重新回到就绪队尾。这里会让状态机真正运转起来，也能帮你提前练一遍阻塞队列的管理。

我自己做这个课设时的教训是：先跑固定用例，指标算对了，再谈可视化，最后才加新算法。排序和比较器这类“裁判逻辑”，一旦结果怪异，不要先怀疑调度循环，先打印每个任务的 start_time 和 finish_time，跟手工表逐项对。把这条变成肌肉记忆后，任务调度器课程设计基本就不会翻车。希望帮到你。

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