操作系统：实验一：进程调度算法模拟——动态优先数与PCB管理的C语言实现

1. 动态优先数调度算法基础动态优先数调度算法是操作系统中常见的进程调度策略之一它的核心思想是根据进程的优先级动态分配CPU资源。与静态优先级不同动态优先数会随着进程运行状态的变化而调整这使得系统能够更灵活地响应不同进程的需求。在实现动态优先数调度时每个进程都会被赋予一个初始优先数通常数值越大优先级越高。当一个进程获得CPU时间片执行后如果它没有完成全部工作系统会降低它的优先数。这样做的目的是防止高优先级进程长期独占CPU资源从而提高系统的公平性。举个例子假设系统中有三个进程A、B、C初始优先数分别为5、3、1。第一轮调度时进程A会最先执行。执行一个时间片后如果A还未完成它的优先数降为4。此时三个进程的优先数变为4、3、1下一轮调度时A仍然优先级最高。只有当A的优先数降到低于B时B才有机会获得CPU资源。2. PCB设计与进程状态管理2.1 PCB数据结构设计进程控制块(PCB)是操作系统中管理进程的核心数据结构它包含了系统管理进程所需的全部信息。在我们的C语言实现中PCB结构体定义如下typedef struct pcb { char name[10]; // 进程名 char state; // 进程状态(W:就绪, R:运行, F:完成) int priority; // 动态优先数 int total_time; // 需要运行的总时间 int elapsed_time; // 已运行时间 struct pcb *next; // 指向下一个PCB的指针 } PCB;这个结构体包含了进程调度的关键信息name字段标识进程方便调试和输出state字段记录进程当前状态实现三态转换priority字段存储动态变化的优先数两个时间字段实现时间片管理next指针用于构建就绪队列2.2 进程状态转换逻辑在我们的模拟系统中进程有三种基本状态就绪态(W)进程已准备好等待CPU资源运行态(R)进程正在CPU上执行完成态(F)进程已完成全部工作状态转换规则如下新创建的进程初始状态为就绪态(W)调度器从就绪队列选择优先级最高的进程将其状态改为运行态(R)进程运行一个时间片后如果已运行时间等于总时间转为完成态(F)否则优先数减1转回就绪态(W)这种状态转换机制通过简单的条件判断即可实现if(p-elapsed_time p-total_time) { p-state F; // 转为完成态 free(p); // 释放PCB } else { p-priority--; // 优先数减1 p-state W; // 转回就绪态 insert_to_ready_queue(p); // 重新插入就绪队列 }3. 调度器核心实现3.1 就绪队列管理就绪队列采用单向链表结构组织新进程加入时需要根据优先级找到合适的位置。我们实现了一个排序插入函数void insert_by_priority(PCB **queue, PCB *process) { process-next NULL; // 队列为空或新进程优先级最高 if(*queue NULL || process-priority (*queue)-priority) { process-next *queue; *queue process; return; } // 寻找插入位置 PCB *current *queue; while(current-next ! NULL process-priority current-next-priority) { current current-next; } // 插入新进程 process-next current-next; current-next process; }这个函数保证了就绪队列始终按优先级从高到低排列调度时只需取队列首元素即可获得最高优先级进程。3.2 调度循环实现主调度循环负责不断从就绪队列选取进程执行直到所有进程完成。基本流程如下void schedule() { int time_slice 0; while(ready_queue ! NULL) { time_slice; printf(\n--- 时间片 %d ---\n, time_slice); // 获取最高优先级进程 PCB *current ready_queue; ready_queue ready_queue-next; current-next NULL; // 执行进程 run_process(current); // 处理执行后状态 if(current-state ! F) { insert_by_priority(ready_queue, current); } } printf(\n所有进程执行完成总时间片%d\n, time_slice); }每次循环代表一个时间片的执行主要完成以下工作从就绪队列取出队首进程执行该进程增加已运行时间根据执行结果更新进程状态未完成的进程重新插入就绪队列4. 完整代码实现与测试4.1 完整源代码以下是整合了所有功能的完整实现#include stdio.h #include stdlib.h typedef struct pcb { char name[10]; char state; int priority; int total_time; int elapsed_time; struct pcb *next; } PCB; PCB *ready_queue NULL; void insert_by_priority(PCB **queue, PCB *process) { process-next NULL; if(*queue NULL || process-priority (*queue)-priority) { process-next *queue; *queue process; return; } PCB *current *queue; while(current-next ! NULL process-priority current-next-priority) { current current-next; } process-next current-next; current-next process; } void create_processes() { int count; printf(输入进程数量: ); scanf(%d, count); for(int i 0; i count; i) { PCB *p (PCB *)malloc(sizeof(PCB)); printf(输入进程%d名称、优先数、总时间: , i1); scanf(%s %d %d, p-name, p-priority, p-total_time); p-state W; p-elapsed_time 0; p-next NULL; insert_by_priority(ready_queue, p); } } void print_queue() { PCB *current ready_queue; printf(就绪队列: ); while(current ! NULL) { printf(%s(P%d)-, current-name, current-priority); current current-next; } printf(NULL\n); } void run_process(PCB *process) { process-state R; process-elapsed_time; printf(执行进程: %s\n, process-name); printf(状态: %c, 优先数: %d, 已运行/总时间: %d/%d\n, process-state, process-priority, process-elapsed_time, process-total_time); if(process-elapsed_time process-total_time) { printf(进程 %s 完成\n, process-name); process-state F; free(process); } else { process-priority--; process-state W; } } void schedule() { int time_slice 0; while(ready_queue ! NULL) { time_slice; printf(\n--- 时间片 %d ---\n, time_slice); print_queue(); PCB *current ready_queue; ready_queue ready_queue-next; current-next NULL; run_process(current); if(current-state ! F) { insert_by_priority(ready_queue, current); } } printf(\n所有进程执行完成总时间片%d\n, time_slice); } int main() { create_processes(); schedule(); return 0; }4.2 测试用例与结果分析我们使用以下测试数据验证调度器进程数量: 3 进程1: A 3 2 进程2: B 1 1 进程3: C 2 3预期执行顺序时间片1: A(3)执行优先数降为2时间片2: C(2)执行优先数降为1时间片3: A(2)执行优先数降为1同时完成时间片4: B(1)和C(1)竞争B先执行并完成时间片5: C(1)执行优先数降为0时间片6: C(0)执行并完成实际运行输出与预期完全一致验证了调度算法的正确性。通过这种逐步执行和状态检查的方式可以确保动态优先数调度算法的每个细节都正确实现。5. 扩展与优化思路5.1 算法优化方向当前实现的时间复杂度主要来自就绪队列的插入操作。当进程数量较多时可以考虑以下优化使用优先队列堆数据结构管理就绪队列将插入和提取操作的时间复杂度从O(n)降到O(log n)实现多级反馈队列将不同优先级的进程分组管理添加时间片耗尽检查防止单个进程运行时间过长5.2 功能扩展建议为了使模拟系统更接近真实场景可以考虑添加以下功能进程阻塞机制增加I/O等待状态模拟进程等待外部事件优先级提升策略对长时间未执行的进程适当提升优先级防止饥饿更丰富的进程创建方式支持从文件读取进程描述或随机生成测试用例可视化界面使用图形化方式展示调度过程和队列状态变化这些扩展能够帮助学生更深入地理解操作系统调度机制的复杂性为后续学习更高级的调度算法打下基础。