单处理器调度

长中短 调度

调度条件：有限计算资源+给定执行顺序

进程执行的分配方法影响性能

长程调度：决定加入待执行进程池 中程调度：决定加入部分或全部位于内存中的进程集合 短程调度：决定处理器执行哪个可运行进程

长程：球队大名单 中程：比赛名单 短程：上场球员

长程调度

从批处理队列创建进程并加入 就绪/挂起队列或就绪队列

决定哪个程序可以进入系统中处理 ⇒ 控制了系统的并发度

完成后创建的新进程在可供中程调度、短程调度程序使用的队列中等待调度

何时创建新进程 通常由要求的系统并发度控制决定

分时系统接受所有用户授权的任务 直至系统饱和

中程调度

1. 阻塞队列 → 阻塞挂起队列
2. 就绪队列 → 就绪挂起队列
3. 阻塞结束后，阻塞挂起队列 → 就绪挂起队列

决定是否把进程添加到那些至少部分已在内存且可被执行的进程集中

是进程交换功能的一部分 （内存外存间交换）

短程调度

执行最频繁 包括中断 系统调用 信号

1. 将就绪队列中的进程调度到CPU中执行
2. 运行中的进程被阻塞或者重新进入就绪态
3. 阻塞队列中的进程进入就绪态

调度算法

短程调度

• 决策模式
  • 抢占式调度：可以去中断某个正在执行的进程并将其转为就绪态，将已分配给该进程的处理器重新分配给另一个进程
  • 非抢占式调度：一旦分配进程 必须等待进程完成执行才能分配新的进程
• 一些指标：
  • 对于单个进程
    • 周转时间：完成时间 – 提交时间
    • 响应时间：开始响应时间 – 提交时间
  • 对于一组进程
    • 吞吐量：单位时间完成的任务数量
    • 截止时间：硬性or软性 时限内完成/总任务数
  • 对于系统
    • 资源利用率

优先级

每个优先级一个队列 同优先级内FIFO

每个ready状态的进程放入对应队列

优化了周转时间&响应时间

问题：

1. 低优先级可能长期饥饿 ⇒ 长期闲置提高优先级
2. 未对吞吐和时限进行优化

调度中的公平性：避免引入新的进程饥饿

选择调度策略

画甘特图

示例：

• 非抢占
  • FCFS 先来先服务
    • 未优化吞吐量和周转时间
    • 短作业等待久
    
  • SPN 最短进程优先
    • 通常用于调度周期性的任务
    • 优化平均周转时间和吞吐
    • 长进程可能饥饿
    • 估计不准 ⇒ 可能直接终止
    
  • HRRN 最高响应比优先
    • 响应比 = （服务时间+等待时间）/ 服务时间
    • 综合考虑性能和公平
    • 一定程度避免长进程饥饿
    
• 抢占式
  • RR 轮转
    • 时间分片
      • 过小会导致频繁上下文切换 → 完成任务数量降低吞吐下降
      • 过大则偏向长进程 短进程长响应
    • 轮转顺序按队列来！！
    • 性能取决于分片大小+执行时间
    • 降低响应时间 而不是周转时间
    • 为待执行的进程分配等长CPU使用时间（时间片）
    • 新进程到达时加入队列 进行分配
    • 分配时间用尽 or 进程完成时 终止执行
    • 同一时刻 后来的先入队 CPU正在执行的再用尽时间片 排在新来的后面！！
    
  • SRT 最短剩余时间优先
    • 新进程到达 or 当前进程完成时触发
    • 相等就执行靠前的
    • 优化平均周转时间和吞吐
    • 偏向短进程 长进程可能饥饿
    
  • MLFQ 多级反馈队列
    • 无预测 纯用反馈
    • 每个优先级一个队列 每个进程到达时初始默认放入最高优先级队列
    • 分片结束前主动释放 保持优先级
    • 如果A的优先级 = B的优先级 轮转运行
    • 如果被抢占（包括用完时间片） 则移入低一级队列
    • 长进程连续降级 可能导致饥饿
    • 另一方案1：第i级队列分到的时间片长度为2的i次方
    • 另一方案2：每隔一段固定时间将所有进程优先级提到最高