操作系统调度算法

这是一篇关于操作系统调度算法的思维导图，包含短作业优先SJF：缺点：对长作业不利，可能导致饥饿，难以做到真正的短作业优先。

调度算法

• 先来先服务FCFS
  • 非抢占式
    • 优点：实现简单，公平
    • 缺点：对短作业不利
  • 考虑等待时间&运行时间
    • 等待时间√
    • 运行时间×
  • 饥饿
    • 不会
• 短作业优先SJF
  • 默认：非抢占式
    • 优点："最短的"平均时间/周转时间
    • 缺点：对长作业不利，可能导致饥饿，难以做到真正的短作业优先
  • 抢占式：最短剩余时间优先算法SRTN
  • 考虑等待时间&运行时间
    • 等待时间×
    • 运行时间√
  • 饥饿
    • 会
• 高响应比优先HRRN
  • 非抢占式
    • 优点：FCFS，SJF折中，综合考虑等待时间和运行时间
  • 抢占式
  • 考虑等待时间&运行时间
    • 等待时间√
    • 运行时间√
  • 饥饿
    • 不会
• 时间片轮转（RR）
  • 抢占式
    • 优点：公平，响应快，适合分时操作系统
    • 缺点：由于高频率的进程切换，因此有一定开销，不区分任务的紧急程度
  • 饥饿
    • 不会
• 调度算法的评价指标
  • 响应时间
    • 从用户提交到首次产生响应所用的时间
    • 响应比=等待时间+要求服务的时间/要求服务时间
  • 等待时间
    • 进程/作业=等待被服务的时间之和
    • 平均等待时间=进程/作业=等待时间的平均值
  • CPU利用率
    • 利用率=忙碌的时间/总时间
  • 系统吞吐量
    • 系统吞吐量=总共完成了多少道作业/总共花了多少时间
  • 周转时间
    • 周转时间=作业完成时间-作业提交时间
    • 平均周转时间=各作业周转时间之和/作业数
    • 带权周转时间=作业周转时间/作业实际运行的时间
    • 平均带权周转时间=各作业带权周转时间之和/作业数
• 优先级调度算法
  • 抢占式，非抢占式
    • 优点：用优先级区分紧急程度，重要程度，适用于实时操作系统，可灵活地调整对各种作业/进程的偏好程度
    • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
  • 饥饿
    • 会
• 多级反馈队列调度算法
  • 抢占式
    • 优点：所有算法折中
    • 优点： 公平（FCFS），新进程很快得到响应（RR），短进程较少时间完成（SPF），灵活调整对各种进程的偏好程度
    • 缺点：无
  • 饥饿
    • 会
• 早期批处理系统
• 交互式系统
• 进程调度
• 进程和作业调度