operating system

思考如下问题

  1. 为什么要进行处理机调度?
  2. 调度算法有哪几种?结合前面学的分时操作系统和实时操作系统,思考那种调度算法比较适合这两种操作系统

1. 调度的概念

1.1 调度的基本概念

调度级别

1.2 调度的层次

高级调度即作业调度,它决定允许哪些作业参与竞争CPU和其它系统资源。将一个或一批作业从后备状态变为运行状态,高级调度是为作业分配虚拟处理机,也称宏观调度、接纳调度。

这时候带来两个问题

  1. 接纳多少作业?接纳太多会增加周转时间,太少会降低计算机吞吐量。
  2. 接纳哪些作业?这时候要靠调度算法实现,例如先来先服务,短作业优先等。

根据调度算法和计算机当前状态,高级调度功能会挑选一个或多个后备作业投入运行,为选中的作业分配基本的内存和设备资源并建立进程,将进程实体装入内存。

高级调度的时机包括如下三个

  1. 如果当前运行的作业数目少于计算机系统允许的最大作业数目,且存在后备作业。
  2. 当一作业运行终止而被撤销后,且存在后备作业。
  3. 在分时系统中,当一用户被核准注册。

中级调度决定哪些进程可参与竞争CPU。

中级调度将进程从活动态(活动就绪、活动阻塞)变为静止的挂起态(静止就绪、静止阻塞);或相反。

中级调度实际上是实现“挂起”和“激活”操作。

中级调度也称为进程交换调度,通常仅用于分时(操作)系统。


低级调度即进程(线程)调度。

低级调度决定哪个进程可获得CPU。

低级调度从活动就绪队列中挑选一个进程,将它变为运行态,同时启动CPU执行该进程。

低级调度也称微观调度。

因此,低级调度的功能是

  1. 选择下一个进程(调度算法)
  2. 切换(处理器分派、现场保存和恢复)

调度的基本机制有排队器、分派器(跳转/iret)、切换机制。

低级调度的方式分为两种,分别是抢占式和非抢占式。

  1. 非抢占式

    进程获得 CPU 后,一直执行完成或自动阻塞。导致紧急任务可能被滞后。

  2. 抢占方式

    进程获得 CPU 后,允许其它进程依据一定的原则抢占 CPU 资源,例如

    • 时间片原则
    • 优先级原则
    • 短作业优先原则

低级调度时机一般有

  1. 现行进程执行完成或自动阻塞。
  2. 在采用抢占方式的系统中,发生了某种抢占事件。例如时间片到、新进程创建、睡眠进程被唤醒、进程优先级修改。

1.3 三级调度的联系

1.4 仅有低级调度的调度队列模型

每个进程执行时:

  1. 进程在时间片内已完成,进入完成状态。
  2. 未完成(但时间片用完),放在就绪队列后。
  3. 因某事件,进入阻塞状态。

低级调度

1.5 具有高级和低级进程调度的调度队列模型

高级和低级调度

1.6 具有三级调度的调度队列模型

三级调度

2. 调度的时机、切换与过程

3. 进程调度方式

4. 调度的基本准则

调度评估标准有如下几个

  1. 周转时间:作业(进程)从提交(进入时刻)到完成的时间称为该作业的周转时间 。
  2. 平均周转时间:n 个周转时间的平均值。
  3. 带权周转时间:周转时间/实际运行时间=权值,带权周转时间是一个比值。
  4. 平均带权周转时间:所有带权周转时间之和/n
  5. 平均等待时间:等待时间之和/n

4.2 调度原则

  1. 面向用户的原则
    • 周转时间短
    • 响应时间快
    • 截止时间的保证
    • 优先权准则
  2. 面向系统的原则
    • 系统吞吐量高
    • 处理机利用率好
    • 各类资源的平衡使用

5. 典型的调度算法

处理机调度实际上是一种资源 (处理机) 分配。调度算法是指根据系统的资源分配策略所规定的资源分配算法。目标不同、系统不同,则调度算法各异。

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

作业调度:从后备队列中,选择一个或多个最先进入该队列的作业。

FCFS

进程调度:从就绪队列中,选择一个最先进入该队列的进程,把处理机分配给它,一直运行完或自动阻塞。

PFCFS

以非抢占方式工作,可用于作业与进程调度。

5.2 短作业优先(SJF)调度算法

作业调度:从后备队列中,选择一个或多个估计执行时间最短的作业。

SJF

进程调度:从就绪队列中,选择一个估计需CPU时间最短的进程,把处理机分配给它。

SPF

可以抢占方式和非抢占方式工作,可用于作业调度与进程调度。在抢占方式中,最短时作业(进程)将以最快的速度完成。

5.3 优先级调度算法

作业调度:从后备队列中,选择一个优先权最高的作业 。

进程调度:从就绪队列中,选择一个优先权最高的进程,把处理机分配给它 。

静态优先权、非抢占方式进程HPF调度举例

hpf

可用于作业与进程调度,但动态优先权算法只用于进程调度 。抢占方式可用于实时系统。

5.4 高响应比优先调度算法

考虑了已等待时间,等待时间越长,响应比越高。

Rp = (已等待时间+要求服务时间)/要求服务时间

作业调度:从后备队列中,选择一个响应比 Rp 最高的作业。

jhrn

进程调度:从就绪队列中,选择一个响应比Rp最高的进程,把处理机分配给它。

phrn

5.5 时间片轮转调度算法

RR 调度算法是一种抢占方式的进程调度算法。RR依据公平服务原则,在一定时间内,为每个进程轮转服务一次,RR每次为一个进程执行一个时间片,若进程未结束,则将进程插入到就绪队列的尾部。

可以根据优先权,对优先权高的进程分配较长的时间片,但总的时间片轮转时间应满足要求。

RR

如果 q 继续扩大,就会变成 FCFS 调度算法。适合于分时系统。

5.6 多级反馈队列调度算法

设置多个就绪队列,并从高到低赋予不同的优先级,每个队列采用FCFS算法,时间片长度从高优先级到低优先级依次增加(一般加倍)(S1<S2<…<Sn) 。

多级反馈队列调度算法

多级反馈队列调度例子

5.7 多级队列调度算法

将就绪队列分成多种不同队列(前台轮转就绪队列、后台FCFS就绪队列)。 每个进程每个时刻固定地分属于一个队列。 不同队列采用不同的调度算法(前台就绪队列采用RR调度算法,后台就绪队列采用FCFS算法)。 只有当前台就绪队列空时,才执行后台队列中的进程。

6. 实时调度

实时任务有如下特点

  1. 紧迫性

    未能及时完成将有严重后果

  2. 截止时间(最迟时间)

    必须在截止时间之前开始或结束。有开始截止时间和完成截止时间。

6.1 实时调度的基本条件

实现实时系统的调度需要提供必要的调度信息

  1. 就绪时间
  2. 开始截止时间/完成截止时间
  3. 处理时间
  4. 资源要求
  5. 优先级

一般采用抢占方式。

  1. 时间片轮转调度算法

    满足数秒内

  2. 立即抢占的优先权调度算法

    满足毫秒级别的实时控制。

常用的实时调度算法

  1. 最早开始截止时间优先(EDF)算法

    开始截止时间越早,优先级越高。

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

    根据任务的紧急(松弛)程度确定任务的优先级。

    松弛度(LF)=完成时间-处理时间-当前时间

LLF采用抢占调度方式,当某个任务的松弛度(LF)降为 0 时,立即调度并执行