# 操作系统课程设计：进程调度模拟器实验报告 ## 1. 设计目的及意义 进程调度是操作系统核心功能，负责从就绪队列中选择进程分配CPU资源。本课程设计通过实现交互式进程调度模拟器，深入理解进程调度原理，掌握基于优先级的时间片轮转和多级反馈队列轮转算法，通过可视化展示直观比较不同算法的优劣。 ## 2. 系统设计 ### 2.1 系统架构 ```mermaid graph TB A[浏览器前端] -->|HTTP/JSON| B[Go HTTP服务器] A --> A1[参数设置] A --> A2[PRR展示] A --> A3[MLFQ展示] A --> A4[算法对比] B --> B1[调度模拟API] B --> B2[静态文件服务] B1 --> B3[优先级时间片轮转] B1 --> B4[多级反馈队列轮转] ``` ### 2.2 核心数据结构 ```go type PCB struct { Name, Priority, ArrivalTime, NeedTime int/string UsedTime, State, StartTime, FinishTime int/string QueueLevel, WaitUntil, SliceUsedTime int } type Snapshot struct { Time int Processes []PCB Running string Queues [][]string Event string } ``` ### 2.3 优先级时间片轮转算法流程 ```mermaid stateDiagram-v2 [*] --> Ready: 新进程到达 Ready --> Execute: 调度器选中 Ready --> Execute: 高优先级抢占 Execute --> Ready: 时间片用完\n优先级+3 Execute --> Wait: 每3单位时间需I/O\n等待2单位时间 Execute --> Finish: 已用时间=需要时间 Wait --> Ready: 等待时间到达 Finish --> [*] note right of Execute 优先级: 数值越小越高 支持抢占: 就绪队列有高优先级进程时 立即抢占当前进程 end note ``` ### 2.4 多级反馈队列算法流程 ```mermaid stateDiagram-v2 [*] --> ReadyQ0: 新进程到达 ReadyQ0 --> ExecuteQ0: 从Q0选中(片=1) ReadyQ1 --> ExecuteQ1: 从Q1选中(片=2) ReadyQ2 --> ExecuteQ2: 从Q2选中(片=4) ExecuteQ0 --> ReadyQ1: Q0片用完\n降级到Q1 ExecuteQ1 --> ReadyQ2: Q1片用完\n降级到Q2 ExecuteQ2 --> ReadyQ2: Q2片用完\n留在Q2 ExecuteQ0 --> Wait: 需要I/O ExecuteQ1 --> Wait: 需要I/O ExecuteQ2 --> Wait: 需要I/O Wait --> ReadyQ0: 唤醒\n回到原队列 ExecuteQ0 --> Finish: 完成 ExecuteQ1 --> Finish: 完成 ExecuteQ2 --> Finish: 完成 Finish --> [*] note right of ReadyQ0 三级反馈队列: Q0: 时间片=1 (短进程优先) Q1: 时间片=2 (中等进程) Q2: 时间片=4 (长进程) 新进程和唤醒进程从Q0开始 end note ``` ## 3. 系统实现 ### 3.1 优先级时间片轮转核心代码 ```go func SimulatePriorityRR(processes []*PCB, timeSlice int) SimResult { var readyQueue []*PCB time := 0 for time <= maxTime { // 唤醒等待进程，处理新到达进程 for _, p := range procs { if p.State == StateWait && p.WaitUntil <= time { p.State = StateReady; readyQueue = append(readyQueue, p) } } // 抢占检查：高优先级进程抢占当前进程 if running != nil { for _, p := range readyQueue { if p.Priority < running.Priority { running.State = StateReady readyQueue = append(readyQueue, running); running = nil } } } // 按优先级选择进程执行 if running == nil && len(readyQueue) > 0 { sort.Slice(readyQueue, ...) // 优先级排序 running = readyQueue[0]; readyQueue = readyQueue[1:] } // 执行进程，记录快照 running.UsedTime++; running.SliceUsedTime++ if running.UsedTime >= running.NeedTime { running.State = StateFinish // 进程完成 } else if running.SliceUsedTime >= timeSlice { running.Priority += 3 // 优先级降低 if running.UsedTime%3 == 0 { running.State = StateWait; running.WaitUntil = time + 2 // I/O等待 } } time++ } } ``` ### 3.2 多级反馈队列核心代码 ```go func SimulateMLFQ(processes []*PCB, queueTimeSlices [3]int) SimResult { queues := [3][]*PCB{} // Q0:片=1, Q1:片=2, Q2:片=4 time := 0 for time <= maxTime { // 唤醒等待进程，新进程从Q0开始 for _, p := range procs { if p.State == StateWait && p.WaitUntil <= time { p.State = StateReady; queues[p.QueueLevel] = append(..., p) } if p.ArrivalTime == time && p.State == StateReady { p.QueueLevel = 0; queues[0] = append(queues[0], p) } } // 从最高优先级非空队列选择进程 running = selectFromMLFQ(queues) if running.StartTime == -1 { running.StartTime = time } // 执行进程，记录快照 running.UsedTime++; running.SliceUsedTime++ if running.UsedTime >= running.NeedTime { running.State = StateFinish // 进程完成 } else if running.SliceUsedTime >= queueTimeSlices[running.QueueLevel] { if running.QueueLevel < 2 { running.QueueLevel++ // 降级到下一级队列 } running.State = StateReady; running.SliceUsedTime = 0 } time++ } } ``` ### 3.3 前端模拟请求 ```javascript async function doSim(algo, ts, procs) { const resp = await fetch('/api/simulate', { method:'POST', headers:{'Content-Type':'application/json'}, body:JSON.stringify({algorithm:algo, timeSlice:ts, processes:procs}) }); return resp.json(); } ``` ### 3.4 调度过程渲染 ```javascript function renderStep(key) { const snap = state[key].data.snapshots[state[key].step]; // 更新当前执行进程、就绪队列、状态表 if (snap.running) { const rp = snap.processes.find(p=>p.name===snap.running); document.getElementById('running-'+key).innerHTML = `${rp.name} 优先级=${rp.priority} 已用=${rp.usedTime}`; } updateGantt(key, state[key].step); // 更新甘特图 } ``` ## 4. 系统运行效果 ### 4.1 调度流程对比 **示例进程配置**：P0(优先级3/到达0/需5), P1(优先级8/到达1/需3), P2(优先级5/到达2/需6), 时间片=2 **优先级时间片轮转调度序列**： ``` 时间 当前执行 就绪队列 事件 t=0 P0(3) - P0开始 t=2 P2(5) P0(6) P0时间片用完，被P2抢占 t=4 P0(6) P2(8) P2时间片用完，P0继续 t=6 P1(8) P0(9),P2(11) P0再次时间片用完，P1执行 ... ``` **多级反馈队列调度序列**： ``` 时间 当前执行 队列状态(Q0/Q1/Q2) 事件 t=0 P0 [P0]/[]/[] P0从Q0开始 t=1 P0(Q1) []/[P0]/[] P0用完Q0片，降级到Q1 t=3 P2(Q0) [P2]/[P0]/[] P2新进程从Q0开始 t=5 P0(Q2) []/[P2]/[P0] P0降级到Q2 ... ``` ### 4.2 可视化展示 系统提供四个主要展示界面： - **参数设置**：配置算法类型、时间片大小、进程参数 - **PRR展示**：动态展示优先级时间片轮转调度过程，包括就绪队列、状态表、甘特图 - **MLFQ展示**：动态展示三级队列调度过程，突出队列级别变化 - **算法对比**：比较两种算法的平均周转时间和性能特点 ### 4.3 典型调度时序 ```mermaid sequenceDiagram participant CPU participant P0 participant P1 participant P2 Note over CPU: 优先级时间片轮转 CPU->>P0: 执行(t=0-2) CPU->>P2: 抢占执行(t=2-4) CPU->>P0: 继续执行(t=4-5,完成) CPU->>P2: 继续执行(t=5-6) CPU->>P1: 执行(t=6-8,完成) CPU->>P2: 继续执行(t=8-9,完成) ``` ## 5. 设计总结 ### 5.1 关键问题解决 **抢占逻辑**：在时间循环中检查就绪队列，高优先级进程立即抢占当前进程，确保优先级高的进程及时执行。 **I/O等待机制**：PCB增加WaitUntil字段，进程每执行3单位时间后等待I/O 2单位时间，循环中检查唤醒条件。 **死锁检测**：就绪队列为空且所有进程在等待状态且无进程会唤醒时判定死锁。 ### 5.2 算法特点对比 | 特点 | 优先级时间片轮转 | 多级反馈队列轮转 | |------|----------------|----------------| | 队列管理 | 单一就绪队列 | 三级反馈队列 | | 时间片 | 固定统一 | 按队列递增(1,2,4) | | 优先级调整 | 时间片后+3 | 基于队列级别动态变化 | | 短进程响应 | 较慢 | 快速(Q0短片) | | 长进程公平性 | 可能饥饿 | Q2长片保证 | | 实现复杂度 | 较低 | 较高 | ### 5.3 经验体会 通过本次课程设计，深入理解了进程调度的理论与实践结合。多级反馈队列算法的"反馈"机制体现在进程的CPU使用行为会动态调整其队列位置和时间片长度。可视化展示使抽象算法原理变得直观，体现了可视化工具在教学中的价值。 ### 5.4 改进方向 - 支持更多调度算法（最短作业优先、优先级抢占式等） - 增加资源管理模拟（内存分配、设备管理） - 优化大量进程时的渲染性能 - 添加预设测试用例库和统计分析功能