操作系统 之 调度算法

2020-03-25   86 次阅读


课堂笔记归纳

先来先服务调度算法(FCFS)

既可以用于作业调度,也可以用于进程调度

特点

  • 本质:仅考虑“到达时间”
  • 实现简单
  • 貌似公平
  • 实际上对**短作业(运行时间较短的作业)**不公平

短作业/短进程优先调度算法(SJF/SPF)

  • 既可以用于作业调度(SJF),也可以用于进程调度(SPF)
  • 用于作业调度,每次调度都是从后备作业队列中选择一个要求服务时间最短的作业
  • 用于进程调度,每次调度都是从就绪队列中选择一个执行时间最短的进程,为之分配处理机

特点

  1. 本质 : 仅考虑“执行时间”
  2. 实现困难 : 估算执行时间很难(对现代计算机科学无法解决)
  3. 有利于短作业
  4. 对长作业不公平

高优先权优先调度算法(FPF)

  • 既可以用于作业调度,也可以用于进程调度
  • 用于作业调度时,系统将从后备队列中选择若干个优先权最高的作业,装入内存
  • 用于进程调度时,该算法是把处理机分配给就绪队列中优先权最高的进程

优先权

算法的核心

  • 反映 作业/进程执行时的迫切程度,是对调度所考虑的实际因素的算法抽象
  • 通常用一个整型数来表示
  • 也分为非抢占与抢占

优先权确定

  • 静态优先权:进程创建的时候确定(进程类型,资源需求与用户要求等),直到进程执行结束保持不变
  • 动态优先权: 进程创建时确定(根据进程类型、资源需求与用户要求等),在进程执行过程中可以发生变化

高响应比优先调度算法

  • 用于作业调度
  • 系统从后备队列中响应若干个响应比最高的作业,装入内存,投入运行

核心: 对等待作业以一定速率α提高其优先权

特点

  • 如果作业的等待时间相等,则要求服务的时间越短,其优先权越高,该算法有利于短作业
  • 当要求服务时间相同时,作业的优先权决定于其等待时间,等待时间越长,其优先权越高
  • 对于长作业,作业的+
  • 既照顾了短作业,又考虑了作业到达的先后次序

时间片轮转调度算法(RR)

  • 用于作业调度

时间片

时间片选择:

  • 固定时间片
  • 可变时间片(现代大部分操作系统的选择)

时间片大小选择:

  • 不能太大也不能太小
  • 太大 : 影响最大响应时间
  • 太小 : 单位时间内调度的开销过大

多级反馈队列调度算法(MFQ)

设置多个就绪队列,为个队列赋予不同的优先级
为了补偿优先级低的队列,优先级低的队列时间片更大
仅当优先级高的队列空闲时才会调度优先级低队列中的内容

思想

  • 对新创建的进程,首先将它们放入第一队列(先来的总是有最高优先权),按FCFS原则排队等待调度
  • 当轮到该进程执行时如果能在该时间片内完成则完成, 否则调度程序将该进程转入第2队列的末尾,同样按FCFS原则等待调度,如果仍然未完成则调度到第三队列,以此类推,直到最后一个队列

特点

  • 避免了实现计算各种进程所需的执行时间
  • 具有较好的性能能较好地满足各种类型用户的需要

实时调度算法的分类

非抢占式调度算法

    1. 非抢占式轮转调度算法
    • 将所有实时任务排成队列,轮流投入运行当任务完成就重新排到队列末尾
    • 调度时选择队首进程
    • 实时响应时间:数秒到数十秒
    1. 非抢占式优先调度算法
    • 为所有实时任务设定优先权,高优先权进程到达队列排到队首,以待当前任务执行完毕
    • 调度时选择队首进程
    • 实时响应时间: 数百毫秒-数秒

抢占式调度算法

    1. 基于时钟中断的抢占式优先权调度算法
    • 为所有实时任务设定优先权
    • 高优先权进程到达队列,排到队首,以等待时钟中断到达时调度到CPU上执行
    • 调度时选择队首进程
    • 实时响应时间: 数毫秒到数十毫秒
    1. 立即抢占的优先权调度算法
    • 为所有实时任务设定优先权
    • 高优先权进程到达队列,主要当前进程不在临界区,则立刻抢占CPU
    • 调度时选择队首进程
    • 实时响应时间: 数百微秒 - 数微秒

最早截止时间优先调度算法(EDF)

  • 根据任务的开始截止时间来确定任务的优先级
  • 截止时间越早,其优先级越高
  • 该算法要求在系统中保持一个实时任务就绪队列,该队列按照各任务截止时间的早晚顺序,具有最早截止时间的任务排在队列的最前面
  • 调度程序在选择任务时,总是选择就绪队列中的第一个任务,为之分配处理机,使之投入运行

最低松弛度优先调度算法(LLF)

  • 根据任务的紧急程度(松弛度)来确定任务的优先级
  • 松弛度 = 必须完成时间 - 本身运行时间 - 当前时间
  • 调度程序在选择任务时,总是选择就绪队列中紧急程度最大的任务为之分配处理机,使之投入运行

优先级倒置问题

  • 正常:高优先级进程先执行,低优先级进程后执行
  • 特殊情况:低优先级进程先执行,高优先级进程后执行
  • 后果:高优先级进程执行被延迟

解决方法
优先级继承 : 当低优先级进程阻塞高优先级进程,将低优先级进程的优先级提高到被它阻塞进程的最高优先级进程的优先级

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议