os-course-design/Report.md

操作系统课程设计：进程调度模拟器实验报告

1. 设计目的及意义

进程调度是操作系统核心功能，负责从就绪队列中选择进程分配CPU资源。本课程设计通过实现交互式进程调度模拟器，深入理解进程调度原理，掌握基于优先级的时间片轮转和多级反馈队列轮转算法，通过可视化展示直观比较不同算法的优劣。

2. 系统设计

2.1 系统架构

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 核心数据结构

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 优先级时间片轮转算法流程

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 多级反馈队列算法流程

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 优先级时间片轮转核心代码

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 多级反馈队列核心代码

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 前端模拟请求

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 调度过程渲染

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 典型调度时序

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 改进方向

• 支持更多调度算法（最短作业优先、优先级抢占式等）
• 增加资源管理模拟（内存分配、设备管理）
• 优化大量进程时的渲染性能
• 添加预设测试用例库和统计分析功能