1. 项目概述与核心价值又到了期末操作系统课的大作业如期而至。这次的任务是“用C语言实现几种经典的进程调度算法”相信不少同学拿到这个题目时既兴奋又有点无从下手。兴奋的是这终于不再是纸上谈兵可以亲手用代码模拟CPU如何“翻牌子”选进程运行了无从下手的是课本上的算法描述看似清晰但真要用代码把FCFS、SJF、HRRN、RR这些调度器“造”出来中间隔着数据结构设计、状态机转换、时间片轮转等一系列具体问题。我当年也在这个作业上花了整整一周调试到深夜是常事。但做完之后对进程调度、就绪队列、上下文切换这些核心概念的理解比背十遍书都来得深刻。这个项目本质上是一个离散事件模拟器它不涉及真正的硬件中断或多线程并发而是通过一个虚拟的“系统时钟”和精心设计的数据结构来模拟CPU调度行为并统计各项性能指标。对于计算机专业的学生而言这是一个绝佳的、将抽象理论转化为具体代码能力的训练场。无论你是正在为作业发愁的同学还是想巩固操作系统底层知识的开发者跟着这篇笔记我们一起来把这个调度模拟器从零搭建起来。2. 整体设计与核心思路拆解在动手写代码之前我们必须把整个模拟器的运行逻辑想清楚。一个常见的误区是直接对着算法伪代码开始写main函数这样很容易陷入细节导致程序结构混乱难以扩展新的调度算法。2.1 模拟器的心脏事件驱动模型我们的程序世界是一个简化版的计算机系统。这里没有真正的硬件时钟中断那么如何推动时间前进并触发“进程到达”、“进程结束”、“时间片用完”这些事件呢答案是事件驱动。我们可以维护一个全局时钟变量current_time它代表了模拟器中的当前时间。同时我们维护一个未来事件列表。最开始所有进程的“到达时间”就是这个列表里的事件。模拟器的主循环就是不断地从事件列表中取出下一个即将发生的事件将current_time快进到该事件的发生时间然后处理这个事件比如让一个进程开始运行、结束运行或让出CPU。处理事件的过程可能会产生新的事件比如一个进程开始运行后就预定了一个“结束运行”事件再将其加入事件列表。如此循环直到所有事件处理完毕。这种设计的好处是逻辑清晰且与真实操作系统内核中“中断驱动”的调度思想有异曲同工之妙。我们不需要用sleep或忙等待模拟效率极高。2.2 进程的“身份证”PCB结构体设计在操作系统中每个进程都有一个进程控制块PCB来记录它的所有信息。在我们的模拟器里也需要一个类似的结构体。这是整个程序的数据核心。typedef struct Process { int pid; // 进程ID int arrival_time; // 到达时间 int burst_time; // 需要的总CPU执行时间服务时间 int remaining_time; // 剩余执行时间用于RR和SJF int start_time; // 首次开始运行的时间 int finish_time; // 完成时间 int waiting_time; // 等待时间 int turnaround_time; // 周转时间 float response_ratio; // 响应比专用于HRRN struct Process *next; // 指向下一个进程的指针用于链表 } Process;关键字段解析remaining_time: 这是实现可剥夺调度如RR和动态计算如SJF中判断最短剩余时间的关键。进程每运行一个单位时间此值减1减到0即完成。start_timefinish_time: 用于计算周转时间finish_time - arrival_time和等待时间start_time - arrival_time。注意一个进程可能被多次调度如RRstart_time记录的是它第一次获得CPU的时间。response_ratio: 这是高响应比优先HRRN算法的核心。响应比 等待时间 要求服务时间/ 要求服务时间。它需要在每次调度点动态计算。2.3 调度算法的统一接口为了让程序结构更优雅便于扩展和维护想象一下老师突然要求加一个优先级调度我们应该为所有调度算法定义一个统一的函数接口。typedef Process* (*Scheduler)(Process* ready_queue); // 这是一个函数指针类型它指向一个函数该函数接收当前就绪队列头指针 // 返回一个指针指向被选中的那个要运行的进程。这样在模拟器主循环中我们只需要调用current_scheduler(ready_queue)就能得到下一个该运行的进程而current_scheduler可以在FCFS、SJF、HRRN、RR之间切换。这是一种简单的策略模式应用。2.4 性能评估指标我们关注什么模拟的最终目的是为了比较不同算法的优劣。我们主要关注以下几个核心指标平均周转时间进程从提交到完成所经历的时间平均值。越小越好意味着进程完成得快。平均等待时间进程在就绪队列中等待时间的平均值。越小越好意味着CPU利用率高进程响应快。平均响应时间对于RR等交互式系统进程从第一次提交到第一次获得CPU的时间平均值。在代码中我们会在每个进程结束时finish_time确定后立即计算它的周转时间和等待时间并累加。最后输出平均值。3. 核心数据结构与工具函数实现有了清晰的思路我们就可以开始搭建基础设施了。这部分代码是所有调度算法共享的基石。3.1 进程链表管理我们选择单链表来管理就绪队列和所有进程。因为它简单、直观且足够满足我们的需求不需要随机访问主要是头部插入、尾部插入和遍历。// 工具函数创建一个新进程 Process* create_process(int pid, int arrival, int burst) { Process* p (Process*)malloc(sizeof(Process)); p-pid pid; p-arrival_time arrival; p-burst_time burst; p-remaining_time burst; // 初始时剩余时间等于总时间 p-start_time -1; // -1 表示尚未开始 p-finish_time -1; p-waiting_time 0; p-turnaround_time 0; p-response_ratio 0.0; p-next NULL; return p; } // 工具函数将进程插入就绪队列尾部用于FCFS等维护顺序的队列 void enqueue(Process** ready_queue, Process* proc) { if (*ready_queue NULL) { *ready_queue proc; proc-next NULL; } else { Process* temp *ready_queue; while (temp-next ! NULL) { temp temp-next; } temp-next proc; proc-next NULL; } } // 工具函数从就绪队列头部移除一个进程用于出队调度 Process* dequeue(Process** ready_queue) { if (*ready_queue NULL) return NULL; Process* proc *ready_queue; *ready_queue (*ready_queue)-next; proc-next NULL; // 隔离出来 return proc; }注意这里的enqueue是简单的尾插法。但在SJF或HRRN中我们可能需要根据某种优先级剩余时间、响应比将进程插入到队列的合适位置而不是简单地插到尾部。届时我们会实现专门的插入函数。3.2 事件管理与模拟主循环框架我们简化事件管理不显式地维护一个事件队列而是通过“进程列表”和“当前时间”来推导事件。主循环的逻辑如下初始化读取或生成所有进程按到达时间排序放入一个“未来进程列表”。当还有进程未完成时循环 a.检查到达事件将current_time时刻及之前到达的所有进程从“未来进程列表”移入“就绪队列”。 b.检查就绪队列是否为空 - 空说明CPU空闲将current_time快进到下个进程的到达时间。 - 非空调用调度函数选出下一个要运行的进程。 c.处理运行事件根据调度算法决定此进程运行多久可能是整个burst_time也可能是一个时间片time_quantum。 d.更新系统时间current_time增加此次运行的时间。 e.更新进程状态减少该进程的remaining_time。如果减为0则标记完成计算其各项指标否则根据算法将其重新放回就绪队列或等待下次调度。循环结束输出所有进程的详细信息和平均指标。这个框架像是一个总导演而具体的调度算法是演员它们只负责回答“现在该谁上场”这个问题。4. 四大调度算法的具体实现与难点剖析现在进入最核心的部分。我们将逐一实现四种算法并重点讲解其中的易错点和技巧。4.1 先来先服务FCFS这是最简单的算法其核心是维护一个先进先出FIFO的就绪队列。调度时永远选择队首的进程。Process* fcfs_scheduler(Process* ready_queue) { // FCFS就是选择当前就绪队列的第一个进程 return ready_queue; // 直接返回队首指针 } // 在模拟主循环中调用fcfs_scheduler后我们会用dequeue将其从队首取出。实现要点与坑点非抢占一旦进程开始运行就会一直运行到完成。在模拟中这意味着我们选中一个进程后current_time直接增加该进程的remaining_time中间不会被打断。** convoy效应护航效应**这是FCFS的著名缺点。如果队列前面是一个长进程后面跟着很多短进程那么短进程的等待时间会变得非常长导致平均等待时间飙升。你的模拟结果应该能清晰地反映出这一点。计算等待时间一个进程的等待时间 start_time - arrival_time。注意只有在进程第一次被调度时start_time -1才设置start_time。4.2 非抢占式短作业优先SJF非抢占式SJF的关键在于调度只发生在有进程完成时。当CPU空闲或一个进程运行结束时系统会从当前就绪队列中选择预估运行时间burst_time最短的那个进程来运行。Process* sjf_scheduler(Process* ready_queue) { if (ready_queue NULL) return NULL; Process *shortest ready_queue; Process *current ready_queue-next; Process *prev_shortest NULL; Process *prev ready_queue; // 遍历链表找到burst_time最小的进程 while (current ! NULL) { if (current-burst_time shortest-burst_time) { shortest current; prev_shortest prev; } prev current; current current-next; } // 将选中的进程从链表中移除 if (prev_shortest NULL) { // 最短进程是队首 ready_queue shortest-next; } else { prev_shortest-next shortest-next; } shortest-next NULL; return shortest; }实现要点与坑点“非抢占”的含义在模拟中即使一个更短的进程在某个长进程运行期间到达长进程也不会被中断。我们必须等到当前进程自然结束后才会重新调用调度器此时新到达的短进程才会被考虑。这是与抢占式SJF最短剩余时间优先的根本区别。如何选择“短作业”我们需要遍历整个就绪队列来寻找burst_time最小的进程。这里使用链表时间复杂度是O(n)。对于作业数不多的大作业来说完全足够。饥饿问题理论上如果一直有短作业到达长作业可能永远得不到执行。但在非抢占式且所有作业同时到达的假设下这个问题不明显。你的报告里可以讨论这一点。4.3 高响应比优先HRRNHRRN是对SJF的一种改进旨在缓解长作业的饥饿问题。响应比R (W S) / S其中W是等待时间S是要求服务时间。每次调度时选择响应比最高的进程。因为等待时间W在分子上一个作业等得越久其响应比越高被选中的机会就越大。float calculate_response_ratio(Process* proc, int current_time) { int waiting_time current_time - proc-arrival_time; return (waiting_time proc-burst_time) / (float)(proc-burst_time); } Process* hrrn_scheduler(Process* ready_queue, int current_time) { if (ready_queue NULL) return NULL; Process *highest ready_queue; Process *current ready_queue-next; Process *prev_highest NULL; Process *prev ready_queue; // 先计算第一个进程的响应比 highest-response_ratio calculate_response_ratio(highest, current_time); float max_ratio highest-response_ratio; // 遍历计算并比较响应比 while (current ! NULL) { current-response_ratio calculate_response_ratio(current, current_time); if (current-response_ratio max_ratio) { highest current; prev_highest prev; max_ratio current-response_ratio; } prev current; current current-next; } // 将选中的进程从链表中移除代码类似SJF略 // ... (移除highest进程的链表操作) return highest; }实现要点与坑点动态计算响应比必须在每次调度点重新计算因为每个进程的等待时间W随着current_time的推移在不断增长。数据类型(WS)/S的结果可能是小数所以response_ratio字段和计算函数返回值要用float。比较时使用。何时调度和SJF一样HRRN通常也是非抢占的调度发生在进程完成或CPU空闲时。4.4 时间片轮转RRRR算法给每个进程分配一个固定的CPU时间片。进程运行一个时间片后如果还没结束就会被剥夺CPU重新排到就绪队列的末尾然后调度队首的下一个进程。Process* rr_scheduler(Process** ready_queue, int time_quantum, int* remaining_quantum) { // remaining_quantum 是一个指针用于跟踪当前运行进程在本轮中剩余的时间片 // 如果它为0或负数说明需要调度一个新进程 if (*remaining_quantum 0) { // 需要调度新进程 if (*ready_queue NULL) return NULL; // 就绪队列空 Process* scheduled dequeue(ready_queue); // 从队首取出 *remaining_quantum time_quantum; // 重置时间片 return scheduled; } else { // 继续运行当前进程在模拟主循环中我们通常不会在这里返回新进程 // 这个分支更多是用于状态维护。实际调度决策在主循环中通过判断remaining_quantum来做。 return NULL; // 表示继续运行当前进程 } } // 在模拟主循环中RR的逻辑与其他算法有显著不同 // 1. 每次只增加 current_time 一个最小单位如1或一个时间片。 // 2. 当前运行进程的 remaining_time 减1同时 remaining_quantum 也减1。 // 3. 检查 remaining_time 是否为0进程结束或者 remaining_quantum 是否为0时间片用完。 // 4. 如果时间片用完但进程未结束则将此进程 enqueue 回就绪队列尾部。 // 5. 然后调用 rr_scheduler 获取下一个进程此时 remaining_quantum 为0会触发重新调度。实现要点与坑点时间片大小的选择这是RR算法的灵魂。时间片太大退化成FCFS时间太小进程切换开销上下文切换占比过高系统吞吐量下降。在你的模拟程序中时间片应作为一个可配置的常量如#define TIME_QUANTUM 4。就绪队列的管理RR的就绪队列必须是标准的FIFO队列。新到达的进程插入队尾被时间片剥夺的进程也插入队尾。“当前运行进程”的状态你需要一个变量如Process* running_proc来记录当前正在占用CPU的进程。还需要一个变量如int remaining_quantum来记录该进程在当前轮次中剩余的时间片。性能指标的计算对于RRstart_time仍然是进程第一次获得CPU的时间。waiting_time的计算需要小心每次进程在就绪队列中等待其等待时间都在增加。一种简单的实现方式是在每个时间单位为就绪队列中的所有进程的waiting_time加1。5. 模拟主循环的整合与代码框架将以上所有部分整合起来是项目成功的关键。下面给出一个高度简化的主循环伪代码框架以RR为例展示如何将事件处理、调度、状态更新串联起来。int main() { // 初始化读取进程数据按到达时间排序存入 all_processes 列表 Process* all_processes load_processes(); Process* ready_queue NULL; Process* running_proc NULL; int current_time 0; int time_quantum 4; int remaining_quantum 0; // 当前运行进程剩余时间片 int completed 0; int total_processes count_of(all_processes); // 主循环 while (completed total_processes) { // 步骤1处理到达事件 while (all_processes ! NULL all_processes-arrival_time current_time) { Process* arrived dequeue(all_processes); // 从未来队列取出 enqueue(ready_queue, arrived); // 加入就绪队列 printf(Time %d: Process P%d arrived.\n, current_time, arrived-pid); } // 步骤2检查是否需要调度CPU空闲或时间片用完 if (running_proc NULL || remaining_quantum 0) { // 如果当前有进程在运行但时间片用完且未结束则放回就绪队列 if (running_proc ! NULL running_proc-remaining_time 0) { enqueue(ready_queue, running_proc); printf(Time %d: Process P%d time slice expired, re-queued.\n, current_time, running_proc-pid); } // 调用调度器获取下一个进程 running_proc rr_scheduler(ready_queue, time_quantum, remaining_quantum); if (running_proc ! NULL) { if (running_proc-start_time -1) { running_proc-start_time current_time; // 记录首次开始时间 } printf(Time %d: Process P%d starts running.\n, current_time, running_proc-pid); } else { // 就绪队列为空且没有进程在运行CPU空闲 // 可以快进时间到下一个进程到达时间 if (all_processes ! NULL) { current_time all_processes-arrival_time; continue; // 跳回循环开始处理到达事件 } } } // 步骤3如果没有进程运行则时间无法推进理论上上面已处理快进 if (running_proc NULL) { // 这种情况应该不会发生除非所有进程都已完成 break; } // 步骤4模拟运行一个单位时间 current_time; running_proc-remaining_time--; remaining_quantum--; // 步骤5更新就绪队列中所有进程的等待时间每个时间单位加1 Process* p ready_queue; while (p ! NULL) { p-waiting_time; p p-next; } // 步骤6检查当前运行进程是否结束 if (running_proc-remaining_time 0) { running_proc-finish_time current_time; running_proc-turnaround_time running_proc-finish_time - running_proc-arrival_time; // waiting_time 已经在步骤5中累计了 printf(Time %d: Process P%d finished. TT%d, WT%d\n, current_time, running_proc-pid, running_proc-turnaround_time, running_proc-waiting_time); completed; running_proc NULL; // CPU变空闲 remaining_quantum 0; // 重置时间片 } } // 输出统计结果 print_statistics(all_processes); return 0; }注意这是一个概念性框架省略了内存释放、错误处理等细节。对于FCFS、SJF、HRRN这些非抢占算法循环逻辑会更简单一旦开始运行一个进程就直接将current_time推进到该进程结束中间不检查到达事件因为非抢占。6. 输入输出设计与测试用例一个友好的程序需要有清晰的输入输出。输入可以来自文件也可以直接在代码中初始化。6.1 输入格式设计建议使用简单的文本文件格式例如processes.txt进程ID 到达时间 服务时间 1 0 5 2 2 3 3 4 2 4 6 4每行代表一个进程。在main函数开始时读取这个文件并创建进程链表。6.2 输出信息模拟过程中可以输出时间线便于调试Time 0: P1 arrived. Time 0: P1 starts running. (FCFS Selected) Time 5: P1 finished. TT5, WT0 Time 5: P2 starts running. ...最终输出一个汇总表格和平均指标调度算法: FCFS 进程ID | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 等待时间 -------------------------------------------------------------------- P1 | 0 | 5 | 0 | 5 | 5 | 0 P2 | 2 | 3 | 5 | 8 | 6 | 3 ... 平均周转时间: 7.25 平均等待时间: 4.506.3 关键测试用例设计几组有代表性的测试数据能凸显不同算法的特点默认用例进程交错到达服务时间长短不一。用于基本功能验证。护航效应用例一个超长进程如服务时间100在0时刻到达紧接着在1时刻到达多个短进程服务时间1。观察FCFS下短进程极长的等待时间以及SJF/HRRN的改善。SJF饥饿用例理论测试连续有短作业到达观察长作业是否会被无限期推迟在非抢占SJF中如果长作业很晚才开始可能不会。RR时间片测试使用同一组进程分别用很小如1和很大如大于所有进程服务时间的时间片测试观察平均周转时间和等待时间的变化趋势。7. 常见问题与调试心得这是我当年调试时踩过的坑和总结的技巧希望能帮你节省时间。7.1 指针操作与内存管理链表操作是出错重灾区。野指针和内存泄漏每次malloc创建进程在程序结束前一定要free。链表删除节点时注意正确更新next指针避免访问已释放的内存。链表头指针的传递像enqueue,dequeue,sjf_scheduler这些函数需要修改链表头记得传递Process**指针的指针否则修改可能无法生效。调试技巧写一个print_queue(Process* head)函数随时打印就绪队列里的进程ID和剩余时间这是最直观的调试手段。7.2 时间推进逻辑错误这是模拟逻辑的核心容易混乱。FCFS/SJF/HRRN的非抢占在进程运行期间current_time是直接跳到完成时刻的。在这段“跳跃”的时间里可能有新进程到达。你必须在“跳跃”之前就处理好所有在这段时间内到达的进程将它们加入就绪队列。我的做法是在决定运行进程P从时间T1到T2之前先扫描未来进程列表把所有到达时间在(T1, T2]这个区间内的进程都提前加入到就绪队列中。RR的时间片与时间单位在RR模拟中current_time每次递增1一个最小时间单位。这更贴近真实系统的“时钟滴答”。要确保时间片time_quantum、剩余时间remaining_time和current_time的推进是同步的。7.3 状态变量初始化与更新start_time初始化为-1在进程第一次被调度时设置为current_time。判断条件是if (proc-start_time -1)。waiting_time的更新时机对于FCFS/SJF/HRRN可以在进程结束时计算waiting_time start_time - arrival_time。前提是start_time记录准确。对于RR必须在每个时间单位手动为就绪队列中的所有进程增加等待时间。因为一个进程可能多次进出就绪队列。remaining_time在进程被创建时等于burst_time每运行一个单位时间减1。7.4 算法切换与代码组织为了让程序能方便地切换算法建议使用函数指针数组。typedef Process* (*SchedulerFunc)(Process**, int, int*); // 适配RR // 或者 typedef Process* (*SchedulerFunc)(Process*); // 适配FCFS/SJF SchedulerFunc schedulers[] {fcfs_scheduler, sjf_scheduler, hrrn_scheduler, rr_scheduler}; char* scheduler_names[] {FCFS, Non-preemptive SJF, HRRN, Round Robin};在main函数里可以通过一个循环依次用不同的调度器运行同一组测试数据并输出对比结果这样写实验报告时数据获取非常方便。最后这个项目的魅力在于当你看到自己编写的程序输出不同算法下差异显著的性能指标时课本上那些枯燥的定义瞬间就变得生动起来。调试过程虽然痛苦但每一次解决bug你对进程、队列、状态和时间的理解就会加深一层。不妨在实现基本功能后尝试增加一些扩展比如实现抢占式的SJF最短剩余时间优先或者给每个进程增加一个优先级实现多级反馈队列MLFQ这会让你的大作业在众多项目中脱颖而出。
C语言实现进程调度算法：从理论到实践的完整项目指南
1. 项目概述与核心价值又到了期末操作系统课的大作业如期而至。这次的任务是“用C语言实现几种经典的进程调度算法”相信不少同学拿到这个题目时既兴奋又有点无从下手。兴奋的是这终于不再是纸上谈兵可以亲手用代码模拟CPU如何“翻牌子”选进程运行了无从下手的是课本上的算法描述看似清晰但真要用代码把FCFS、SJF、HRRN、RR这些调度器“造”出来中间隔着数据结构设计、状态机转换、时间片轮转等一系列具体问题。我当年也在这个作业上花了整整一周调试到深夜是常事。但做完之后对进程调度、就绪队列、上下文切换这些核心概念的理解比背十遍书都来得深刻。这个项目本质上是一个离散事件模拟器它不涉及真正的硬件中断或多线程并发而是通过一个虚拟的“系统时钟”和精心设计的数据结构来模拟CPU调度行为并统计各项性能指标。对于计算机专业的学生而言这是一个绝佳的、将抽象理论转化为具体代码能力的训练场。无论你是正在为作业发愁的同学还是想巩固操作系统底层知识的开发者跟着这篇笔记我们一起来把这个调度模拟器从零搭建起来。2. 整体设计与核心思路拆解在动手写代码之前我们必须把整个模拟器的运行逻辑想清楚。一个常见的误区是直接对着算法伪代码开始写main函数这样很容易陷入细节导致程序结构混乱难以扩展新的调度算法。2.1 模拟器的心脏事件驱动模型我们的程序世界是一个简化版的计算机系统。这里没有真正的硬件时钟中断那么如何推动时间前进并触发“进程到达”、“进程结束”、“时间片用完”这些事件呢答案是事件驱动。我们可以维护一个全局时钟变量current_time它代表了模拟器中的当前时间。同时我们维护一个未来事件列表。最开始所有进程的“到达时间”就是这个列表里的事件。模拟器的主循环就是不断地从事件列表中取出下一个即将发生的事件将current_time快进到该事件的发生时间然后处理这个事件比如让一个进程开始运行、结束运行或让出CPU。处理事件的过程可能会产生新的事件比如一个进程开始运行后就预定了一个“结束运行”事件再将其加入事件列表。如此循环直到所有事件处理完毕。这种设计的好处是逻辑清晰且与真实操作系统内核中“中断驱动”的调度思想有异曲同工之妙。我们不需要用sleep或忙等待模拟效率极高。2.2 进程的“身份证”PCB结构体设计在操作系统中每个进程都有一个进程控制块PCB来记录它的所有信息。在我们的模拟器里也需要一个类似的结构体。这是整个程序的数据核心。typedef struct Process { int pid; // 进程ID int arrival_time; // 到达时间 int burst_time; // 需要的总CPU执行时间服务时间 int remaining_time; // 剩余执行时间用于RR和SJF int start_time; // 首次开始运行的时间 int finish_time; // 完成时间 int waiting_time; // 等待时间 int turnaround_time; // 周转时间 float response_ratio; // 响应比专用于HRRN struct Process *next; // 指向下一个进程的指针用于链表 } Process;关键字段解析remaining_time: 这是实现可剥夺调度如RR和动态计算如SJF中判断最短剩余时间的关键。进程每运行一个单位时间此值减1减到0即完成。start_timefinish_time: 用于计算周转时间finish_time - arrival_time和等待时间start_time - arrival_time。注意一个进程可能被多次调度如RRstart_time记录的是它第一次获得CPU的时间。response_ratio: 这是高响应比优先HRRN算法的核心。响应比 等待时间 要求服务时间/ 要求服务时间。它需要在每次调度点动态计算。2.3 调度算法的统一接口为了让程序结构更优雅便于扩展和维护想象一下老师突然要求加一个优先级调度我们应该为所有调度算法定义一个统一的函数接口。typedef Process* (*Scheduler)(Process* ready_queue); // 这是一个函数指针类型它指向一个函数该函数接收当前就绪队列头指针 // 返回一个指针指向被选中的那个要运行的进程。这样在模拟器主循环中我们只需要调用current_scheduler(ready_queue)就能得到下一个该运行的进程而current_scheduler可以在FCFS、SJF、HRRN、RR之间切换。这是一种简单的策略模式应用。2.4 性能评估指标我们关注什么模拟的最终目的是为了比较不同算法的优劣。我们主要关注以下几个核心指标平均周转时间进程从提交到完成所经历的时间平均值。越小越好意味着进程完成得快。平均等待时间进程在就绪队列中等待时间的平均值。越小越好意味着CPU利用率高进程响应快。平均响应时间对于RR等交互式系统进程从第一次提交到第一次获得CPU的时间平均值。在代码中我们会在每个进程结束时finish_time确定后立即计算它的周转时间和等待时间并累加。最后输出平均值。3. 核心数据结构与工具函数实现有了清晰的思路我们就可以开始搭建基础设施了。这部分代码是所有调度算法共享的基石。3.1 进程链表管理我们选择单链表来管理就绪队列和所有进程。因为它简单、直观且足够满足我们的需求不需要随机访问主要是头部插入、尾部插入和遍历。// 工具函数创建一个新进程 Process* create_process(int pid, int arrival, int burst) { Process* p (Process*)malloc(sizeof(Process)); p-pid pid; p-arrival_time arrival; p-burst_time burst; p-remaining_time burst; // 初始时剩余时间等于总时间 p-start_time -1; // -1 表示尚未开始 p-finish_time -1; p-waiting_time 0; p-turnaround_time 0; p-response_ratio 0.0; p-next NULL; return p; } // 工具函数将进程插入就绪队列尾部用于FCFS等维护顺序的队列 void enqueue(Process** ready_queue, Process* proc) { if (*ready_queue NULL) { *ready_queue proc; proc-next NULL; } else { Process* temp *ready_queue; while (temp-next ! NULL) { temp temp-next; } temp-next proc; proc-next NULL; } } // 工具函数从就绪队列头部移除一个进程用于出队调度 Process* dequeue(Process** ready_queue) { if (*ready_queue NULL) return NULL; Process* proc *ready_queue; *ready_queue (*ready_queue)-next; proc-next NULL; // 隔离出来 return proc; }注意这里的enqueue是简单的尾插法。但在SJF或HRRN中我们可能需要根据某种优先级剩余时间、响应比将进程插入到队列的合适位置而不是简单地插到尾部。届时我们会实现专门的插入函数。3.2 事件管理与模拟主循环框架我们简化事件管理不显式地维护一个事件队列而是通过“进程列表”和“当前时间”来推导事件。主循环的逻辑如下初始化读取或生成所有进程按到达时间排序放入一个“未来进程列表”。当还有进程未完成时循环 a.检查到达事件将current_time时刻及之前到达的所有进程从“未来进程列表”移入“就绪队列”。 b.检查就绪队列是否为空 - 空说明CPU空闲将current_time快进到下个进程的到达时间。 - 非空调用调度函数选出下一个要运行的进程。 c.处理运行事件根据调度算法决定此进程运行多久可能是整个burst_time也可能是一个时间片time_quantum。 d.更新系统时间current_time增加此次运行的时间。 e.更新进程状态减少该进程的remaining_time。如果减为0则标记完成计算其各项指标否则根据算法将其重新放回就绪队列或等待下次调度。循环结束输出所有进程的详细信息和平均指标。这个框架像是一个总导演而具体的调度算法是演员它们只负责回答“现在该谁上场”这个问题。4. 四大调度算法的具体实现与难点剖析现在进入最核心的部分。我们将逐一实现四种算法并重点讲解其中的易错点和技巧。4.1 先来先服务FCFS这是最简单的算法其核心是维护一个先进先出FIFO的就绪队列。调度时永远选择队首的进程。Process* fcfs_scheduler(Process* ready_queue) { // FCFS就是选择当前就绪队列的第一个进程 return ready_queue; // 直接返回队首指针 } // 在模拟主循环中调用fcfs_scheduler后我们会用dequeue将其从队首取出。实现要点与坑点非抢占一旦进程开始运行就会一直运行到完成。在模拟中这意味着我们选中一个进程后current_time直接增加该进程的remaining_time中间不会被打断。** convoy效应护航效应**这是FCFS的著名缺点。如果队列前面是一个长进程后面跟着很多短进程那么短进程的等待时间会变得非常长导致平均等待时间飙升。你的模拟结果应该能清晰地反映出这一点。计算等待时间一个进程的等待时间 start_time - arrival_time。注意只有在进程第一次被调度时start_time -1才设置start_time。4.2 非抢占式短作业优先SJF非抢占式SJF的关键在于调度只发生在有进程完成时。当CPU空闲或一个进程运行结束时系统会从当前就绪队列中选择预估运行时间burst_time最短的那个进程来运行。Process* sjf_scheduler(Process* ready_queue) { if (ready_queue NULL) return NULL; Process *shortest ready_queue; Process *current ready_queue-next; Process *prev_shortest NULL; Process *prev ready_queue; // 遍历链表找到burst_time最小的进程 while (current ! NULL) { if (current-burst_time shortest-burst_time) { shortest current; prev_shortest prev; } prev current; current current-next; } // 将选中的进程从链表中移除 if (prev_shortest NULL) { // 最短进程是队首 ready_queue shortest-next; } else { prev_shortest-next shortest-next; } shortest-next NULL; return shortest; }实现要点与坑点“非抢占”的含义在模拟中即使一个更短的进程在某个长进程运行期间到达长进程也不会被中断。我们必须等到当前进程自然结束后才会重新调用调度器此时新到达的短进程才会被考虑。这是与抢占式SJF最短剩余时间优先的根本区别。如何选择“短作业”我们需要遍历整个就绪队列来寻找burst_time最小的进程。这里使用链表时间复杂度是O(n)。对于作业数不多的大作业来说完全足够。饥饿问题理论上如果一直有短作业到达长作业可能永远得不到执行。但在非抢占式且所有作业同时到达的假设下这个问题不明显。你的报告里可以讨论这一点。4.3 高响应比优先HRRNHRRN是对SJF的一种改进旨在缓解长作业的饥饿问题。响应比R (W S) / S其中W是等待时间S是要求服务时间。每次调度时选择响应比最高的进程。因为等待时间W在分子上一个作业等得越久其响应比越高被选中的机会就越大。float calculate_response_ratio(Process* proc, int current_time) { int waiting_time current_time - proc-arrival_time; return (waiting_time proc-burst_time) / (float)(proc-burst_time); } Process* hrrn_scheduler(Process* ready_queue, int current_time) { if (ready_queue NULL) return NULL; Process *highest ready_queue; Process *current ready_queue-next; Process *prev_highest NULL; Process *prev ready_queue; // 先计算第一个进程的响应比 highest-response_ratio calculate_response_ratio(highest, current_time); float max_ratio highest-response_ratio; // 遍历计算并比较响应比 while (current ! NULL) { current-response_ratio calculate_response_ratio(current, current_time); if (current-response_ratio max_ratio) { highest current; prev_highest prev; max_ratio current-response_ratio; } prev current; current current-next; } // 将选中的进程从链表中移除代码类似SJF略 // ... (移除highest进程的链表操作) return highest; }实现要点与坑点动态计算响应比必须在每次调度点重新计算因为每个进程的等待时间W随着current_time的推移在不断增长。数据类型(WS)/S的结果可能是小数所以response_ratio字段和计算函数返回值要用float。比较时使用。何时调度和SJF一样HRRN通常也是非抢占的调度发生在进程完成或CPU空闲时。4.4 时间片轮转RRRR算法给每个进程分配一个固定的CPU时间片。进程运行一个时间片后如果还没结束就会被剥夺CPU重新排到就绪队列的末尾然后调度队首的下一个进程。Process* rr_scheduler(Process** ready_queue, int time_quantum, int* remaining_quantum) { // remaining_quantum 是一个指针用于跟踪当前运行进程在本轮中剩余的时间片 // 如果它为0或负数说明需要调度一个新进程 if (*remaining_quantum 0) { // 需要调度新进程 if (*ready_queue NULL) return NULL; // 就绪队列空 Process* scheduled dequeue(ready_queue); // 从队首取出 *remaining_quantum time_quantum; // 重置时间片 return scheduled; } else { // 继续运行当前进程在模拟主循环中我们通常不会在这里返回新进程 // 这个分支更多是用于状态维护。实际调度决策在主循环中通过判断remaining_quantum来做。 return NULL; // 表示继续运行当前进程 } } // 在模拟主循环中RR的逻辑与其他算法有显著不同 // 1. 每次只增加 current_time 一个最小单位如1或一个时间片。 // 2. 当前运行进程的 remaining_time 减1同时 remaining_quantum 也减1。 // 3. 检查 remaining_time 是否为0进程结束或者 remaining_quantum 是否为0时间片用完。 // 4. 如果时间片用完但进程未结束则将此进程 enqueue 回就绪队列尾部。 // 5. 然后调用 rr_scheduler 获取下一个进程此时 remaining_quantum 为0会触发重新调度。实现要点与坑点时间片大小的选择这是RR算法的灵魂。时间片太大退化成FCFS时间太小进程切换开销上下文切换占比过高系统吞吐量下降。在你的模拟程序中时间片应作为一个可配置的常量如#define TIME_QUANTUM 4。就绪队列的管理RR的就绪队列必须是标准的FIFO队列。新到达的进程插入队尾被时间片剥夺的进程也插入队尾。“当前运行进程”的状态你需要一个变量如Process* running_proc来记录当前正在占用CPU的进程。还需要一个变量如int remaining_quantum来记录该进程在当前轮次中剩余的时间片。性能指标的计算对于RRstart_time仍然是进程第一次获得CPU的时间。waiting_time的计算需要小心每次进程在就绪队列中等待其等待时间都在增加。一种简单的实现方式是在每个时间单位为就绪队列中的所有进程的waiting_time加1。5. 模拟主循环的整合与代码框架将以上所有部分整合起来是项目成功的关键。下面给出一个高度简化的主循环伪代码框架以RR为例展示如何将事件处理、调度、状态更新串联起来。int main() { // 初始化读取进程数据按到达时间排序存入 all_processes 列表 Process* all_processes load_processes(); Process* ready_queue NULL; Process* running_proc NULL; int current_time 0; int time_quantum 4; int remaining_quantum 0; // 当前运行进程剩余时间片 int completed 0; int total_processes count_of(all_processes); // 主循环 while (completed total_processes) { // 步骤1处理到达事件 while (all_processes ! NULL all_processes-arrival_time current_time) { Process* arrived dequeue(all_processes); // 从未来队列取出 enqueue(ready_queue, arrived); // 加入就绪队列 printf(Time %d: Process P%d arrived.\n, current_time, arrived-pid); } // 步骤2检查是否需要调度CPU空闲或时间片用完 if (running_proc NULL || remaining_quantum 0) { // 如果当前有进程在运行但时间片用完且未结束则放回就绪队列 if (running_proc ! NULL running_proc-remaining_time 0) { enqueue(ready_queue, running_proc); printf(Time %d: Process P%d time slice expired, re-queued.\n, current_time, running_proc-pid); } // 调用调度器获取下一个进程 running_proc rr_scheduler(ready_queue, time_quantum, remaining_quantum); if (running_proc ! NULL) { if (running_proc-start_time -1) { running_proc-start_time current_time; // 记录首次开始时间 } printf(Time %d: Process P%d starts running.\n, current_time, running_proc-pid); } else { // 就绪队列为空且没有进程在运行CPU空闲 // 可以快进时间到下一个进程到达时间 if (all_processes ! NULL) { current_time all_processes-arrival_time; continue; // 跳回循环开始处理到达事件 } } } // 步骤3如果没有进程运行则时间无法推进理论上上面已处理快进 if (running_proc NULL) { // 这种情况应该不会发生除非所有进程都已完成 break; } // 步骤4模拟运行一个单位时间 current_time; running_proc-remaining_time--; remaining_quantum--; // 步骤5更新就绪队列中所有进程的等待时间每个时间单位加1 Process* p ready_queue; while (p ! NULL) { p-waiting_time; p p-next; } // 步骤6检查当前运行进程是否结束 if (running_proc-remaining_time 0) { running_proc-finish_time current_time; running_proc-turnaround_time running_proc-finish_time - running_proc-arrival_time; // waiting_time 已经在步骤5中累计了 printf(Time %d: Process P%d finished. TT%d, WT%d\n, current_time, running_proc-pid, running_proc-turnaround_time, running_proc-waiting_time); completed; running_proc NULL; // CPU变空闲 remaining_quantum 0; // 重置时间片 } } // 输出统计结果 print_statistics(all_processes); return 0; }注意这是一个概念性框架省略了内存释放、错误处理等细节。对于FCFS、SJF、HRRN这些非抢占算法循环逻辑会更简单一旦开始运行一个进程就直接将current_time推进到该进程结束中间不检查到达事件因为非抢占。6. 输入输出设计与测试用例一个友好的程序需要有清晰的输入输出。输入可以来自文件也可以直接在代码中初始化。6.1 输入格式设计建议使用简单的文本文件格式例如processes.txt进程ID 到达时间 服务时间 1 0 5 2 2 3 3 4 2 4 6 4每行代表一个进程。在main函数开始时读取这个文件并创建进程链表。6.2 输出信息模拟过程中可以输出时间线便于调试Time 0: P1 arrived. Time 0: P1 starts running. (FCFS Selected) Time 5: P1 finished. TT5, WT0 Time 5: P2 starts running. ...最终输出一个汇总表格和平均指标调度算法: FCFS 进程ID | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 等待时间 -------------------------------------------------------------------- P1 | 0 | 5 | 0 | 5 | 5 | 0 P2 | 2 | 3 | 5 | 8 | 6 | 3 ... 平均周转时间: 7.25 平均等待时间: 4.506.3 关键测试用例设计几组有代表性的测试数据能凸显不同算法的特点默认用例进程交错到达服务时间长短不一。用于基本功能验证。护航效应用例一个超长进程如服务时间100在0时刻到达紧接着在1时刻到达多个短进程服务时间1。观察FCFS下短进程极长的等待时间以及SJF/HRRN的改善。SJF饥饿用例理论测试连续有短作业到达观察长作业是否会被无限期推迟在非抢占SJF中如果长作业很晚才开始可能不会。RR时间片测试使用同一组进程分别用很小如1和很大如大于所有进程服务时间的时间片测试观察平均周转时间和等待时间的变化趋势。7. 常见问题与调试心得这是我当年调试时踩过的坑和总结的技巧希望能帮你节省时间。7.1 指针操作与内存管理链表操作是出错重灾区。野指针和内存泄漏每次malloc创建进程在程序结束前一定要free。链表删除节点时注意正确更新next指针避免访问已释放的内存。链表头指针的传递像enqueue,dequeue,sjf_scheduler这些函数需要修改链表头记得传递Process**指针的指针否则修改可能无法生效。调试技巧写一个print_queue(Process* head)函数随时打印就绪队列里的进程ID和剩余时间这是最直观的调试手段。7.2 时间推进逻辑错误这是模拟逻辑的核心容易混乱。FCFS/SJF/HRRN的非抢占在进程运行期间current_time是直接跳到完成时刻的。在这段“跳跃”的时间里可能有新进程到达。你必须在“跳跃”之前就处理好所有在这段时间内到达的进程将它们加入就绪队列。我的做法是在决定运行进程P从时间T1到T2之前先扫描未来进程列表把所有到达时间在(T1, T2]这个区间内的进程都提前加入到就绪队列中。RR的时间片与时间单位在RR模拟中current_time每次递增1一个最小时间单位。这更贴近真实系统的“时钟滴答”。要确保时间片time_quantum、剩余时间remaining_time和current_time的推进是同步的。7.3 状态变量初始化与更新start_time初始化为-1在进程第一次被调度时设置为current_time。判断条件是if (proc-start_time -1)。waiting_time的更新时机对于FCFS/SJF/HRRN可以在进程结束时计算waiting_time start_time - arrival_time。前提是start_time记录准确。对于RR必须在每个时间单位手动为就绪队列中的所有进程增加等待时间。因为一个进程可能多次进出就绪队列。remaining_time在进程被创建时等于burst_time每运行一个单位时间减1。7.4 算法切换与代码组织为了让程序能方便地切换算法建议使用函数指针数组。typedef Process* (*SchedulerFunc)(Process**, int, int*); // 适配RR // 或者 typedef Process* (*SchedulerFunc)(Process*); // 适配FCFS/SJF SchedulerFunc schedulers[] {fcfs_scheduler, sjf_scheduler, hrrn_scheduler, rr_scheduler}; char* scheduler_names[] {FCFS, Non-preemptive SJF, HRRN, Round Robin};在main函数里可以通过一个循环依次用不同的调度器运行同一组测试数据并输出对比结果这样写实验报告时数据获取非常方便。最后这个项目的魅力在于当你看到自己编写的程序输出不同算法下差异显著的性能指标时课本上那些枯燥的定义瞬间就变得生动起来。调试过程虽然痛苦但每一次解决bug你对进程、队列、状态和时间的理解就会加深一层。不妨在实现基本功能后尝试增加一些扩展比如实现抢占式的SJF最短剩余时间优先或者给每个进程增加一个优先级实现多级反馈队列MLFQ这会让你的大作业在众多项目中脱颖而出。