企业官网建设流程全解析

C语言实现四种进程调度算法性能对比与实战解析

1. 进程调度算法概述与实验环境搭建

进程调度是操作系统核心功能之一，它决定了CPU资源的分配策略。在本次实验中，我们将通过C语言完整实现四种经典调度算法：先来先服务(FCFS)、短作业优先(SJF)、高优先级优先(HPF)和时间片轮转(RR)，并对它们的性能指标进行量化对比分析。

实验环境准备需要以下工具：

• GCC编译器（建议版本9.4.0或更高）
• 任意Linux/Unix开发环境
• 基础C语言开发工具链（make、gdb等）

核心数据结构PCB（进程控制块）定义如下：

typedef struct PCB { char name[20]; // 进程名称 int arrivetime; // 到达时间 int running_time; // 服务时间 int priority; // 优先级 int start_time; // 开始时间 int done_time; // 结束时间 int copyRunning_time; // 用于RR算法的时间片计算 float zztime; // 周转时间 float dqzztime; // 带权周转时间 struct PCB* next; // 队列指针 } Program;

提示：实验代码中使用了动态队列结构管理就绪进程，这种设计比固定数组更贴近实际操作系统实现。

2. 先来先服务(FCFS)算法实现与分析

FCFS是最简单的调度策略，严格按照进程到达顺序进行服务。其核心特点是：

• 非抢占式调度
• 实现简单但平均等待时间较长
• 对I/O密集型进程不利

关键实现代码：

void FCFS(PCB pro[], int num) { sortWithEnterTime(pro, num); // 按到达时间排序 PCBQueue* queue = (PCBQueue*)malloc(sizeof(PCBQueue)); Queueinit(queue); EnterQueue(queue, &pro[0]); int time = pro[0].arrivetime; while (queue->size > 0) { PCB* curpro = poll(queue); if (time < curpro->arrivetime) time = curpro->arrivetime; curpro->start_time = time; curpro->done_time = time + curpro->running_time; curpro->zztime = curpro->done_time - curpro->arrivetime; curpro->dqzztime = curpro->zztime / curpro->running_time; time += curpro->running_time; // 处理新到达的进程... } }

性能测试数据对比：

从测试数据可见，FCFS的平均周转时间明显高于SJF，特别是在短进程较多的场景下表现较差。

3. 短作业优先(SJF)算法深度解析

SJF算法通过优先服务短进程来优化系统平均周转时间，其特点包括：

• 非抢占式实现简单但需要预知运行时间
• 可能导致长进程饥饿
• 理论上的最优平均周转时间

动态队列管理实现：

void EnterQueueOfRuntime(PCBQueue *ready_queue, PCB *program) { PCB *p = ready_queue->firstProg->next; PCB *q = ready_queue->firstProg; while(p) { if(p->running_time > program->running_time) { program->next = p; q->next = program; break; } q = p; p = p->next; } if(!p) { // 插入队尾 ready_queue->LastProg->next = program; ready_queue->LastProg = program; program->next = NULL; } ready_queue->size++; }

实际测试中发现几个关键问题：

1. 预测准确性依赖：算法效果高度依赖对进程运行时间的准确预测
2. 实时系统适用性：不适合交互式系统，因为短作业可能不断抢占
3. 实现复杂度：需要维护有序队列，时间复杂度为O(n)

4. 高优先级优先(HPF)算法实战

HPF算法根据进程优先级进行调度，可分为：

• 静态优先级：创建时确定不变
• 动态优先级：运行时根据情况调整

优先级队列实现技巧：

void EnterQueueOfPriority(PCBQueue *ready_queue, PCB *program) { PCB *p = ready_queue->firstProg->next; PCB *q = ready_queue->firstProg; while(p) { if(p->priority < program->priority) { // 值越大优先级越高 program->next = p; q->next = program; break; } q = p; p = p->next; } if(!p) { // 插入队尾 ready_queue->LastProg->next = program; ready_queue->LastProg = program; program->next = NULL; } ready_queue->size++; }

常见优先级设计策略：

1. 系统进程 > 用户进程
2. 交互式进程 > 批处理进程
3. I/O密集型 > CPU密集型

5. 时间片轮转(RR)算法与性能优化

RR算法通过时间分片实现公平调度，特别适合分时系统：

void RR(PCB pro[], int num) { int timeslice; printf("请输入时间片大小:"); scanf("%d", &timeslice); PCBQueue* queue = (PCBQueue*)malloc(sizeof(PCBQueue)); Queueinit(queue); EnterQueue(queue, &pro[0]); int time = 0; while (queue->size > 0) { PCB* curpro = poll(queue); if (time < curpro->arrivetime) time = curpro->arrivetime; if (timeslice >= curpro->running_time) { // 进程可在本时间片完成 time += curpro->running_time; curpro->done_time = time; // 计算周转时间... } else { // 进程未完成，放回队列 time += timeslice; curpro->running_time -= timeslice; EnterQueue(queue, curpro); } } }

时间片大小选择建议：

• 太小：上下文切换开销过大
• 太大：退化为FCFS
• 经验值：通常设置为20-50ms

6. 四种算法性能对比与场景建议

通过统一测试数据集（5个进程）得到以下对比结果：

场景选型建议：

1. 批处理系统：SJF（已知运行时间）或HPF
2. 交互式系统：RR（时间片轮转）
3. 实时系统：HPF（基于严格优先级）
4. 通用系统：多级反馈队列（结合RR和HPF）

7. 高级优化技巧与扩展方向

动态优先级调整策略：

// 在每次时间片结束时调整 if(curpro->running_time > 0) { curpro->priority -= 1; // 逐步降低长进程优先级 EnterQueueOfPriority(queue, curpro); }

扩展方向建议：

1. 实现多级反馈队列(MLFQ)
2. 添加进程I/O阻塞模拟
3. 可视化调度过程（使用ncurses库）
4. 多核CPU调度扩展

实际项目中遇到的典型问题：

• 优先级反转问题及解决方案（优先级继承）
• 负载均衡考虑
• 能耗感知调度

通过本实验的完整实现，开发者可以深入理解操作系统的核心调度机制，为后续学习更复杂的调度策略打下坚实基础。