C语言实现进程调度算法：优先级与时间片轮转

1. 项目概述在嵌入式系统和操作系统开发中进程调度是一个核心概念。今天我要分享的是如何在C语言中实现一个简单的程序调度机制重点讲解高优先数调度算法和先来先服务算法的实现。这个项目非常适合想要深入理解操作系统底层原理的开发者特别是嵌入式方向的工程师。我选择用C语言实现这个调度器因为C语言足够底层能让我们清楚地看到调度机制是如何工作的。整个项目大约300行代码但包含了进程控制块(PCB)、时间片轮转、优先级调度等关键概念。通过这个实现你不仅能理解调度算法的原理还能掌握如何用C语言构建这样的系统级组件。2. 核心数据结构设计2.1 进程控制块(PCB)结构PCB是操作系统中表示进程的核心数据结构在我的实现中是这样定义的struct PCB { FILE* open_file; // 进程关联的文件指针 u8* file_name; // 文件名 clock_t arrive_time; // 到达时间 clock_t level_time; // 结束时间 int prior_number; // 优先级 u8 program_status; // 程序状态(WAIT/RUN/FINISH) u8 detection_null_or_value; // 是否为空 u8 occupy_time_slice_times; // 已占用CPU时间 int data_write_number; // 已写入数据长度 };这里有几个关键设计点使用clock_t记录时间精确到毫秒级优先级(prior_number)决定调度顺序program_status用枚举值表示进程状态通过文件操作模拟进程的实际工作注意在实际操作系统中PCB会包含更多信息如内存指针、寄存器状态等但我们的简化版本已经足够演示调度原理。2.2 工作队列设计为了实现进程调度我们需要管理工作队列struct program_queue { struct PCB pcb_buf[MAXLINE]; // 默认队列 struct PCB pcb_new_buf[MAXLINE]; // 新队列(用于排序) u32 queue_line; // 队列长度 u8 buf_state; // 当前使用哪个队列 };这个双队列设计很有讲究使用两个队列交替工作避免排序时的数据竞争buf_state标记当前活跃队列MAXLINE定义了队列最大长度(我设置为1024)2.3 时间片结构CPU时间片是调度的重要概念struct cpu_time_slice { clock_t start_time; // 开始时间 clock_t end_time; // 结束时间 u32 time_slice_bulk; // 时间片长度(ms) };初始化时我设置默认时间片为20msvoid init_time_slice(cpu_time_slice_t time_slice) { time_slice-time_slice_bulk 20; // 20ms一个时间片 }3. 核心算法实现3.1 优先级调度算法调度器的核心是队列排序算法我实现了按优先级排序void queue_sort(program_queue_t queue_t) { int len queue_t-queue_line; if(len 0) return; if(queue_t-buf_state BUF) { bzero_queue_new(queue_t); struct PCB tm; tm.program_status -1; PCB_T tmp_pcb tm; for(int i0; iqueue_t-queue_line; i) { for(int j0; jqueue_t-queue_line; j) { if(queue_t-pcb_buf[j].detection_null_or_value THENULL) continue; if(j 0) tmp_pcb (queue_t-pcb_buf[j]); else if(-1 tmp_pcb-program_status) tmp_pcb (queue_t-pcb_buf[j]); else { if(tmp_pcb-prior_number queue_t-pcb_buf[j].prior_number) { tmp_pcb (queue_t-pcb_buf[j]); } } } queue_t-pcb_new_buf[i] *tmp_pcb; tmp_pcb-detection_null_or_value THENULL; } queue_t-buf_state NEWBUF; } else { // 类似逻辑处理另一个队列 } }这个算法有几个关键点每次选择优先级最高(prior_number最小)的进程使用双队列避免排序时数据丢失时间复杂度为O(n²)对小规模队列足够3.2 时间片轮转实现每个进程执行一个时间片后会被暂停while(1) { // 进程开始执行 cts.end_time clock(); if(cts.end_time - cts.start_time cts.time_slice_bulk) { // 时间片用完的处理逻辑 if(_queue.buf_state BUF) { _queue.pcb_buf[i].program_status WAIT; _queue.pcb_buf[i].prior_number; // 优先级降低 _queue.pcb_buf[i].occupy_time_slice_times; _queue.pcb_new_buf[i] _queue.pcb_buf[i]; _queue.pcb_buf[i].detection_null_or_value THENULL; } break; } // 执行进程工作... }这里实现了精确的时间片控制时间片用完后的状态切换优先级动态调整(每次执行后优先级降低)4. 进程执行模拟4.1 文件操作模拟进程工作为了模拟进程的实际工作我使用文件操作作为示例if(VALUE[_queue.pcb_buf[i].data_write_number] \0) { // 进程完成任务 _queue.pcb_buf[i].level_time clock(); printf(program [ %s ] execute end... program run time: %d ms\n, _queue.pcb_buf[i].file_name, _queue.pcb_buf[i].level_time - _queue.pcb_buf[i].arrive_time); _queue.pcb_buf[i].detection_null_or_value THENULL; fclose(_queue.pcb_buf[i].open_file); program_numer--; break; }这个设计很巧妙每个进程向文件写入数据写入长度记录在data_write_number当写完预定数据(VALUE字符串)后进程结束4.2 进程状态转换进程在整个生命周期中有几种状态#define WAIT 0 // 等待状态 #define RUN 1 // 运行状态 #define FINISH 2 // 完成状态状态转换流程新建进程初始状态为WAIT被调度器选中后变为RUN时间片用完回到WAIT任务完成后变为FINISH5. 实战经验与调试技巧5.1 常见问题排查在实现过程中我遇到几个典型问题队列同步问题症状进程在队列中莫名其妙消失原因排序时没有正确处理队列切换解决添加buf_state标记当前活跃队列时间计算不准确症状进程执行时间与预期不符原因clock()返回值单位理解错误解决确认clock()返回毫秒数文件操作冲突症状进程无法正确写入文件原因文件指针未正确初始化解决添加文件打开检查5.2 性能优化建议队列排序优化当前实现是O(n²)复杂度可以改用优先队列数据结构或者使用更高效的排序算法时间片调整20ms可能对某些应用太长或太短可以设计动态调整算法根据系统负载自动调节内存管理当前使用固定大小数组可以改为动态内存分配添加内存不足处理逻辑6. 扩展思路这个基础调度器还可以进一步扩展实现更多调度算法短作业优先(SJF)轮转调度(Round Robin)多级反馈队列添加进程通信机制管道通信共享内存信号量可视化监控界面实时显示进程状态绘制调度时序图展示资源使用情况这个项目虽然代码量不大但完整演示了操作系统调度的核心原理。我在实现过程中特别注重代码的清晰性和可读性所有关键步骤都有详细注释。对于想要深入理解操作系统原理的开发者亲手实现这样一个调度器是非常有价值的学习经历。