C语言进程调度算法实现FCFS/SJF/RR 3种算法对比与链表实战在操作系统的核心机制中进程调度算法如同交通信号灯决定着CPU资源的分配秩序。本文将深入探讨三种经典调度算法的C语言实现——先来先服务(FCFS)、短作业优先(SJF)和时间片轮转(RR)通过链表数据结构构建完整的调度系统并基于量化指标对比其性能差异。1. 进程控制块与链表基础进程调度算法的实现离不开对进程控制块(PCB)的精细管理。我们首先构建PCB结构体作为进程的身份证typedef struct _Pcb { int pid; // 进程标识符 char cPname; // 进程名称(A-E) int arriveP; // 到达时间 int taskLen; // 所需总时间 int remains; // 剩余执行时间 int beginP; // 开始执行时间 int finishP; // 完成时间 struct _Pcb* next; // 链表指针 } PCB;初始化函数InitPcbQue()创建包含5个测试进程的链表PCB* InitPcbQue() { int iArrivePoint[5] {0,1,2,3,4}; int iTaskLen[5] {4,3,5,2,4}; char cPname[5] {A,B,C,D,E}; PCB* head NULL; for(int i4; i0; i--) { // 逆序插入保证A在链表头 PCB* newNode (PCB*)malloc(sizeof(PCB)); newNode-pid i; newNode-arriveP iArrivePoint[i]; newNode-taskLen newNode-remains iTaskLen[i]; newNode-cPname cPname[i]; newNode-next head; head newNode; } return head; }关键细节链表采用头插法构建确保进程A始终位于链表首部这与FCFS算法的测试需求相符2. 先来先服务(FCFS)算法实现FCFS算法如同超市收银台的排队规则严格遵循到达顺序void FCFS_Schedule(PCB* head) { int currentTime 0; PCB* current head; while(current ! NULL) { current-beginP (currentTime current-arriveP) ? currentTime : current-arriveP; current-finishP current-beginP current-taskLen; currentTime current-finishP; printf(进程%c: 到达%d 开始%d 完成%d 周转%d\n, current-cPname, current-arriveP, current-beginP, current-finishP, current-finishP - current-arriveP); current current-next; } }执行示例输出进程A: 到达0 开始0 完成4 周转4 进程B: 到达1 开始4 完成7 周转6 进程C: 到达2 开始7 完成12 周转10 进程D: 到达3 开始12 完成14 周转11 进程E: 到达4 开始14 完成18 周转14FCFS算法的性能特点指标值平均周转时间9.0最大等待时间10CPU利用率90%缺陷分析当长进程如C先到达时后续短进程如D将产生护航效应导致平均等待时间飙升。3. 短作业优先(SJF)算法实现SJF算法如同医院急诊分诊优先处理耗时短的任务void SJF_Schedule(PCB* originalHead) { PCB* readyQueue NULL; int currentTime 0; // 将原始链表复制到临时链表 PCB* tempHead CopyPcbList(originalHead); while(tempHead ! NULL || readyQueue ! NULL) { // 将已到达进程移入就绪队列 while(tempHead ! NULL tempHead-arriveP currentTime) { PCB* arrived tempHead; tempHead tempHead-next; arrived-next NULL; InsertByShortest(readyQueue, arrived); } if(readyQueue NULL) { // CPU空闲 currentTime tempHead-arriveP; continue; } // 执行队首最短作业 PCB* current readyQueue; readyQueue readyQueue-next; current-beginP currentTime; current-finishP currentTime current-taskLen; currentTime current-finishP; printf(进程%c: 执行%d单位 周转%d\n, current-cPname, current-taskLen, current-finishP - current-arriveP); free(current); } }辅助函数InsertByShortest()实现按执行时间排序void InsertByShortest(PCB** head, PCB* newNode) { if(*head NULL || (*head)-taskLen newNode-taskLen) { newNode-next *head; *head newNode; return; } PCB* current *head; while(current-next ! NULL current-next-taskLen newNode-taskLen) { current current-next; } newNode-next current-next; current-next newNode; }SJF执行结果进程A: 执行4单位 周转4 进程D: 执行2单位 周转5 (到达3) 进程B: 执行3单位 周转7 (到达1) 进程E: 执行4单位 周转14 (到达4) 进程C: 执行5单位 周转16 (到达2)性能对比表算法平均周转时间最大等待时间响应时间方差FCFS9.01012.8SJF9.21222.16注意SJF虽降低平均等待时间但可能导致长进程饥饿——这是追求效率的代价4. 时间片轮转(RR)算法实现RR算法如同体育比赛的回合制给每个进程公平的时间份额void RR_Schedule(PCB* originalHead, int timeQuantum) { Queue readyQueue; InitQueue(readyQueue); int currentTime 0; PCB* current originalHead; while(1) { // 新进程到达处理 while(current ! NULL current-arriveP currentTime) { Enqueue(readyQueue, current); current current-next; } if(IsEmpty(readyQueue)) { if(current NULL) break; // 所有进程完成 currentTime current-arriveP; continue; } PCB* running Dequeue(readyQueue); int executeTime (running-remains timeQuantum) ? timeQuantum : running-remains; printf(时间%d-%d: 执行%c (%d→%d)\n, currentTime, currentTimeexecuteTime, running-cPname, running-remains, running-remains - executeTime); running-remains - executeTime; currentTime executeTime; if(running-remains 0) { Enqueue(readyQueue, running); } else { running-finishP currentTime; printf(进程%c完成! 周转时间%d\n, running-cPname, running-finishP - running-arriveP); free(running); } } }设置时间片为2单位的执行片段时间0-2: 执行A (4→2) 时间2-4: 执行B (3→1) 时间4-6: 执行C (5→3) 时间6-8: 执行D (2→0) 进程D完成! 周转时间5 时间8-10: 执行E (4→2) 时间10-12: 执行A (2→0) 进程A完成! 周转时间12 ...时间片大小的影响时间片长度平均周转时间上下文切换次数118.617214.29411.85工程权衡较小时间片提升响应速度但增加切换开销较长时间片则趋近FCFS行为5. 三种算法综合对比通过量化指标对比各算法特性指标\算法FCFSSJFRR(q2)平均周转时间9.09.214.2平均响应时间4.63.82.1吞吐量0.28任务/单位0.27任务/单位0.35任务/单位公平性低最低高适用场景批处理系统后台作业分时系统实际系统常采用多级反馈队列(MLFQ)等混合策略例如新进程进入高优先级队列(短时间片)消耗完时间片的进程降级定期提升长进程优先级底层队列采用FCFS调度这种设计既保证交互式任务的响应速度又避免长进程完全饥饿。