操作系统进程管理实验：PCB状态机、控制原语与调度算法落地

简介这份操作系统课程大报告以进程管理实验为核心面向计算机相关专业正在完成操作系统实验或课程设计的学生。内容完整覆盖PCB数据结构定义、链表式进程组织、进程创建与撤销原语、阻塞与唤醒原语以及多级反馈队列调度算法的实现思路并配有C语言源码、个人心得与运行结果截图便于对照原理图理解就绪、执行、阻塞、完成等状态之间的转换关系。压缩包仅含1个doc文件约289KB排版紧凑学院实验报告模板、原理方框流程图、程序功能结构图、数据结构与主要变量说明、函数说明、实验步骤源码及结果截图均集中在同一文档内可直接参考格式并复用调度流程。该资源已有1134人学习适合希望借助现成报告模板与可运行代码快速完成进程管理实验、加深对时间片轮转与FCFS调度理解的学习者。1. 从一次“进程跑飞”说起进程管理实验真正要交付什么多数人写操作系统大报告最先画的是课本上那张五状态图最晚写的才是能跑的代码。交上去的材料里状态迁移画得工工整整程序却只有几个空壳函数老师随手补一条用例——让阻塞中的进程被唤醒后立刻撤销它的父进程——程序不是死循环就是段错误。进程管理实验的难点从来不是背概念而是把 PCB、就绪队列、阻塞队列和调度器拼成一个能被反复打断、又不会自相矛盾的状态机。要交付的能力拆开就是六件事创建进程、撤销进程、阻塞进程、唤醒进程、按策略从就绪集合里挑一个占用 CPU、以及在每次状态变化后打印出可核对的结果。落到实现上就是四个控制原语加一个调度循环再配一套统一格式的日志。Linux 进程管理里的 fork、exit、wait、kill 正是这套语义的真实版本实验只是把内核开销换成了内存里的链表操作。动手顺序建议先用结构体把状态和字段固定下来再实现原语最后接调度器。反过来先写 RR 或优先级调度几乎一定返工因为调度器会不断追问“这个 PCB 现在到底在哪个队列里、状态字段和队列是否一致”。2. PCB 与状态机设计进程管理实验的数据结构怎么定2.1 PCB 结构体把状态、优先级和时间片一次说清C 语言做进程管理模拟PCB 就是唯一的真相来源。字段按用途分三类身份类pid、ppid、name、状态类state、wait_reason、调度统计类priority、time_slice、wait_ticks、cpu_ticks。不要图省事把 state 和“在哪个队列”分成两份数据一旦队列位置和 state 不一致后面每条断言都会失败。/* pcb.h —— 进程控制块与状态枚举 */ typedef enum { PROC_NEW, /* 新建PCB 已分配尚未进入就绪队列 */ PROC_READY, /* 就绪等待 CPU */ PROC_RUNNING, /* 运行模拟环境同一时刻只允许一个 */ PROC_BLOCKED, /* 阻塞等待事件不参与调度 */ PROC_TERMINATED /* 终止等待资源回收 */ } proc_state_t; typedef struct pcb { int pid; /* 进程标识单调递增撤销后不复用 */ int ppid; /* 父进程 pid级联撤销要用 */ char name[16]; /* 可读名截图和日志里对得上 */ proc_state_t state; /* 当前状态所有迁移都必须改它 */ int priority; /* 当前优先级数值越小越优先 */ int base_priority; /* 初始优先级反馈队列回滚用 */ int time_slice; /* 本轮的剩余时间片 */ int cpu_burst_left; /* 还需要多少 CPU 时间才能跑完 */ int wait_reason; /* 阻塞原因编码0 表示无 */ int in_ready_queue; /* 防重复入队的冗余标志 */ long wait_ticks; /* 累计等待时间统计平均等待时间 */ long cpu_ticks; /* 累计占用 CPU 时间 */ struct pcb *next; /* 队列链指针 */ } pcb_t;字段取舍的理由base_priority单独留一份是因为多级反馈队列会把优先级压低进程重新就绪时需要按规则回滚没这个字段就只能写死in_ready_queue看着冗余但它能挡住“同一个 PCB 被 enqueue 两次”这类最难查的 bug——一旦重复入队调度时会 double free崩溃点往往离出错点很远wait_ticks和cpu_ticks用 long是因为统计值要参与除法用 int 在几千轮模拟后容易溢出。2.2 五状态迁移矩阵哪些迁移合法哪些必须报错实现原语之前先把“谁能迁移到谁”写成表再把这个表翻译成is_legal_transition(from, to)函数。所有原语在改state之前先调一次非法迁移直接打印错误并退出。常见做法是把迁移表用二维数组存起来比一长串 if-else 更好维护也方便在报告里贴出来当设计依据。当前状态触发事件目标状态是否合法NEW资源分配完成READY是READY被调度器选中RUNNING是RUNNING时间片耗尽READY是RUNNING请求 I/O 或等待事件BLOCKED是RUNNING正常结束或被撤销TERMINATED是BLOCKED事件完成被唤醒READY是BLOCKED时间片耗尽—否READY请求 I/O—否TERMINATED任意事件—否反直觉的点在于BLOCKED → RUNNING也是非法迁移。很多同学图快唤醒时直接把进程置为 RUNNING 塞给调度器结果两个进程同时“运行”。正确做法是唤醒只把进程送回就绪队列由调度器决定它什么时候上 CPU。这条规则定死之后后面 RR 和抢占式优先级的实现会顺很多。2.3 就绪队列与阻塞队列的链表实现与哨兵结点队列用带哨兵头结点的双向链表最省心enqueue和dequeue都不需要判空分支。就绪队列用尾插保证先来先服务语义阻塞队列用尾插保证唤醒顺序稳定。/* queue.c —— 带头结点的队列操作 */ static pcb_t *ready_head, *ready_tail; /* 哨兵head 不存实际进程 */ static pcb_t *block_head, *block_tail; void enqueue(pcb_t **head, pcb_t **tail, pcb_t *p) { p-next NULL; (*tail)-next p; /* 尾哨兵的后继指向新结点 */ *tail p; /* 新结点成为新的尾 */ } pcb_t *dequeue(pcb_t **head, pcb_t **tail) { pcb_t *first (*head)-next; if (first NULL) return NULL; /* 队列空返回 NULL 而非崩溃 */ (*head)-next first-next; if (first *tail) *tail *head; /* 取走最后一个尾指针回退 */ first-next NULL; return first; }enqueue里把p-next先置 NULL是为了防止误传一个已经挂在别的链表上的 PCB把整条链污染成环。dequeue里判断first *tail这一步经常被漏写漏掉之后尾指针会指向已被取走的结点下一次入队就丢数据。初始化时ready_head ready_tail malloc(sizeof(pcb_t))哨兵只占位不存状态。3. 创建、撤销、阻塞、唤醒四个进程控制原语的实现与边界条件3.1 create 原语PID 分配、PCB 初始化与入队创建进程要做的三件事必须按顺序来分配 PCB 并填字段、设置合法初始状态 READY、入就绪队列。任何一步失败都要回滚不能留下半个进程。/* proc.c —— 创建原语 */ static int g_next_pid 1; /* PID 全局单调递增避免复用 */ extern pcb_t *ready_head, *ready_tail; extern pcb_t *g_current; /* 当前运行进程可能为 NULL */ int create_process(const char *name, int prio, int burst) { if (burst 0) return -1; /* 参数校验不允许零长度进程 */ pcb_t *p (pcb_t *)calloc(1, sizeof(pcb_t)); if (p NULL) return -1; /* 分配失败直接返回错误码 */ p-pid g_next_pid; p-ppid (g_current ! NULL) ? g_current-pid : 0; p-state PROC_READY; /* 创建完成即就绪 */ p-priority p-base_priority prio; p-cpu_burst_left burst; p-in_ready_queue 1; snprintf(p-name, sizeof(p-name), %s, name); enqueue(ready_head, ready_tail, p); log_event(p, CREATE, pid%d ppid%d prio%d burst%d, p-pid, p-ppid, prio, burst); return p-pid; /* 返回 PID调用方据此跟进 */ }参数说明prio只在初始时写入priority调度阶段可以改burst是本进程总共需要多少 CPU 时间调度器每轮从里面扣返回负值代表创建失败调用方必须检查否则后续按空指针操作。ppid取自当前运行进程是为了级联撤销时有据可查。3.2 destroy 原语级联撤销子进程与资源回收撤销比创建麻烦因为有父子关系。撤销一个进程时它的直接子进程要么一并撤销要么托孤给 init 进程。实验里更常见的是级联撤销写起来直观也便于截图。/* proc.c —— 级联撤销 */ void destroy_process(int pid) { pcb_t *p find_by_pid(pid); if (p NULL) return; /* 已不存在幂等返回 */ if (p-state PROC_RUNNING) { g_current NULL; /* 先让出 CPU防止悬空指针 */ } for (pcb_t *c first_child(p); c ! NULL; ) { pcb_t *next next_sibling(c); destroy_process(c-pid); /* 递归撤销深度受进程树限制 */ c next; } unlink_from_any_queue(p); /* 从就绪或阻塞队列摘除 */ p-state PROC_TERMINATED; log_event(p, DESTROY, pid%d reclaimed, p-pid); free(p); /* 最后一步才释放内存 */ }关键顺序先递归子进程再从队列摘除最后 free。如果先 free 再摘队列队列里留下的是野指针下一次调度直接读脏内存。递归深度等于进程树高度在模拟环境里一般不会爆栈但真跑几千层还是建议改成显式栈。3.3 block 与 wakeup成对出现与原子改状态阻塞和唤醒必须成对使用且只能由同一个wait_reason配对。唤醒一个不在阻塞队列里的进程、或者重复唤醒都必须被拒绝并记录告警。原语前置状态动作后置状态block(pid, reason)RUNNING出就绪队列、置 reason、入阻塞队列BLOCKEDblock(pid, reason)READY非法调用打印告警返回不变wakeup(pid)BLOCKED出阻塞队列、清 reason、入就绪队列READYwakeup(pid)READY/RUNNING非法调用打印告警返回不变/* proc.c —— 阻塞与唤醒 */ int block_process(int pid, int reason) { pcb_t *p find_by_pid(pid); if (p NULL || p-state ! PROC_RUNNING) return -1; if (!is_legal_transition(p-state, PROC_BLOCKED)) return -1; p-state PROC_BLOCKED; p-wait_reason reason; p-in_ready_queue 0; enqueue(block_head, block_tail, p); if (g_current p) g_current NULL; /* 让出 CPU */ log_event(p, BLOCK, reason%d, reason); return 0; } int wakeup_process(int pid) { pcb_t *p find_by_pid(pid); if (p NULL || p-state ! PROC_BLOCKED) return -1; unlink_from_block_queue(p); p-state PROC_READY; /* 只到就绪不直接运行 */ p-wait_reason 0; p-in_ready_queue 1; enqueue(ready_head, ready_tail, p); log_event(p, WAKEUP, pid%d re-queued, p-pid); return 0; }wakeup里不做调度决策只负责改状态和挪队列这一点和 2.2 的迁移矩阵严格对应。3.4 编译与最小回归测试三条能跑崩程序的用例写完原语先别急着接调度器用三条用例把边界压一遍。# 编译开启全部告警把隐式声明直接当错误 gcc -stdc11 -Wall -Wextra -Werror -g \ -o os_proc main.c proc.c queue.c log.c # 用例一同一个 PID 连续唤醒两次第二次必须返回 -1 ./os_proc --case double_wakeup # 用例二撤销父进程子进程应被级联回收进程计数归零 ./os_proc --case cascade_destroy # 用例三空就绪队列上调度调度器应返回 NULL 而不是崩溃 ./os_proc --case empty_ready逻辑说明-Werror把隐式函数声明变成编译失败避免log_event没声明这类问题拖到运行期才暴露--case参数在main里用strcmp分发每个用例只验证一条不变量。用例三特意在就绪队列为空时调用一次调度器这是模拟程序最常崩的位置——很多人默认队列里永远有人。4. 进程调度算法落地RR、抢占式优先级与多级反馈队列4.1 时间片轮转 RR时间片是唯一要调的参数RR 的实现就是“出队、跑一个时间片、再入队”。唯一的关键参数是time_slice它决定进程切换频率。时间片设成 1 会让日志刷屏、模拟开销盖过调度逻辑设成较大值比如 50会让 RR 退化成先来先服务长进程把短进程堵在后面。/* sched_rr.c —— 时间片轮转 */ void schedule_rr(int slice) { pcb_t *p dequeue(ready_head, ready_tail); if (p NULL) return; /* 无就绪进程CPU 空闲 */ p-state PROC_RUNNING; g_current p; int run (p-cpu_burst_left slice) ? p-cpu_burst_left : slice; p-cpu_burst_left - run; p-cpu_ticks run; p-time_slice slice; /* 每轮重置供日志展示 */ if (p-cpu_burst_left 0) { destroy_process(p-pid); /* 跑完进入终止 */ } else { p-state PROC_READY; /* 时间片用完回就绪队列 */ p-in_ready_queue 1; enqueue(ready_head, ready_tail, p); } g_current NULL; }run取cpu_burst_left和slice的较小值是为了让最后一个时间片只跑到进程实际需要的位置避免把统计到的 CPU 时间算多。time_slice字段本身不参与判断只用于日志展示判断永远用cpu_burst_left。4.2 抢占式优先级调度什么时候触发重新选主优先级调度和 RR 的最大差别是“谁有权把正在跑的进程赶下来”。抢占式只有在两个条件下才触发重选新进程入队且优先级高于当前进程或者当前进程被唤醒的进程挤掉。下面这段是新进程创建后立刻检查的钩子。调度场景是否抢占触发点新进程创建优先级更高是create 完成后调用 preempt_check时间片耗尽是定时器 tick阻塞自己是block 完成后立即重选被唤醒进程优先级更高是wakeup 完成后调用 preempt_check/* sched_prio.c —— 抢占检查 */ void preempt_check(pcb_t *candidate) { if (g_current NULL) return; /* 无人在跑不抢占 */ if (candidate-priority g_current-priority) return; pcb_t *victim g_current; victim-state PROC_READY; victim-in_ready_queue 1; enqueue(ready_head, ready_tail, victim); /* 被抢者回就绪队列 */ log_event(victim, PREEMPT, by pid%d, candidate-pid); schedule_priority(); /* 立刻重选 */ }参数说明priority数值越小优先级越高所以判断用表示“不高于当前就绪不动”。抢占的判断必须放在 create 和 wakeup 之后否则新加入的进程要等下一轮才被看见抢占语义就形同虚设。4.3 多级反馈队列降级、回滚与饥饿边界多级反馈队列最容易写错的是“降级后怎么回来”。常见做法是时间片翻倍、优先级降一级一旦进程阻塞后被唤醒按base_priority回到最初队列。如果只降不回一个反复阻塞的交互式进程会永久沉底这就是饥饿。/* sched_mfq.c —— 多级反馈队列的入队规则 */ void mfq_enqueue(pcb_t *p, int just_woke) { if (just_woke) { p-priority p-base_priority; /* 唤醒即回滚防饥饿 */ } else if (p-time_slice 0) { p-priority; /* 时间片耗尽降一级 */ p-time_slice * 2; /* 时间片翻倍减少切换 */ } p-in_ready_queue 1; enqueue(ready_head, ready_tail, p); }上限要设priority最大不超过MAX_LEVELtime_slice最大不超过MAX_SLICE否则低优先级进程时间片会膨胀到失去意义。降级和回滚两个方向都写全模拟结果才和课本里的曲线对得上。4.4 调度指标怎么算周转时间、带权周转时间与等待时间报告里的对比表不能靠手算用统计函数直接输出。指标公式说明周转时间完成时刻 − 到达时刻反映整体快慢带权周转时间周转时间 / 服务时间消除进程长短差异等待时间周转时间 − 服务时间只算排队耗时平均等待时间所有等待时间之和 / 进程数横向比算法/* stats.c —— 三项指标一次算完 */ void print_stats(pcb_t *table, int n) { double sum_turn 0, sum_wturn 0, sum_wait 0; for (int i 0; i n; i) { long turn table[i].finish_tick - table[i].arrive_tick; long wait turn - table[i].service_tick; sum_turn turn; sum_wturn (double)turn / table[i].service_tick; sum_wait wait; } printf(avg_turn%.2f avg_wturn%.2f avg_wait%.2f\n, sum_turn / n, sum_wturn / n, sum_wait / n); }finish_tick在进程终止时写入arrive_tick在 create 时写入service_tick是初始 burst。三者在同一个进程上必须保持一致否则指标算出来对不上日志截图也没法自圆其说。5. 运行结果验证与截图日志、断言和状态一致性检查5.1 用统一日志格式替代零散 printf零散的printf(here)在截图上毫无价值。把日志统一成固定格式每行都带 tick、pid、事件名和关键参数验收时一眼能读出状态流。/* log.c —— 统一事件日志 */ void log_event(pcb_t *p, const char *event, const char *fmt, ...) { printf([tick%04ld][pid%d][%-8s][%-8s] , g_tick, p-pid, state_name(p-state), event); va_list ap; va_start(ap, fmt); vprintf(fmt, ap); /* 事件附加参数由调用方决定 */ va_end(ap); printf(\n); }state_name把枚举转成字符串避免日志里出现裸数字。tick用%04ld补零截图时列对齐老师一眼就能看出谁是第几个被调度的。5.2 用断言守住五条不变量跑完整个用例之后加一组断言做收尾检查。这五条任何一条破掉说明前面的原语有逻辑漏洞。不变量断言表达式破掉意味着就绪队列中进程状态必为 READYq-state PROC_READYenqueue 时没改状态就绪与阻塞队列无交集两队列指针集合不相交unlink 漏摘运行进程唯一最多一个PROC_RUNNING抢占逻辑出错终止进程不在任何队列已 free 的 PID 不再出现释放顺序错队列长度非负count 0重复 dequeue/* check.c —— 收尾不变量检查失败即中止 */ void assert_invariants(void) { for (pcb_t *p ready_head-next; p; p p-next) assert(p-state PROC_READY); /* 不变量一 */ assert(count_running() 1); /* 不变量三 */ assert(!queues_overlap()); /* 不变量二 */ printf(all invariants passed at tick%ld\n, g_tick); }assert在发布版本会被NDEBUG关掉所以截图用 debug 版本跑gcc不带-DNDEBUG。断言失败会直接给出文件行号比事后翻日志快得多。5.3 截图前先跑一组可复现的输入截图最大的坑是“同样的输入跑出不同结果”根源通常是使用了未初始化的字段或随机数没固定种子。把输入写成文件种子写死跑两次 md5 一致再截。# 固定随机种子输入从文件读输出重定向到日志 ./os_proc --seed 20240501 --input cases/priority_demo.txt \ logs/run1.log 21 ./os_proc --seed 20240501 --input cases/priority_demo.txt \ logs/run2.log 21 diff logs/run1.log logs/run2.log echo reproduciblemd5sum logs/run1.log与run2.log一致截图才有说服力。报告里放三张图即可状态迁移日志、RR 与优先级的指标对比表、级联撤销的收尾断言输出。三张图对应 3.4 的三条回归用例逻辑闭合不需要额外解释。本文还有配套的精品资源点击获取