operating system

1. 调度级别

调度级别

1.1 高级调度

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

这时候带来两个问题

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

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

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

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

1.2 中级调度

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

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

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

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

1.3 低级调度

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

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

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

低级调度也称微观调度。

因此,低级调度的功能是

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

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

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

  1. 非抢占式

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

  2. 抢占方式

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

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

低级调度时机一般有

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

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

每个进程执行时:

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

低级调度

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

高级和低级调度

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

三级调度

2. 调度原则与评估标准

调度评估标准有如下几个

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

2.1 调度原则

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

2.2 调度算法

  1. 调度算法

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

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

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

    FCFS

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

    PFCFS

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

  3. 短作业(进程)优先(SJ(P)F)调度算法

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

    SJF

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

    SPF

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

  4. 高响应比优先(HRN)调度算法

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

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

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

    jhrn

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

    phrn

  5. 最高优先权(HPF)调度算法

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

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

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

    hpf

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

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

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

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

    RR

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

  7. 多级队列调度算法

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

  8. 多级反馈队列调度算法

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

    多级反馈队列调度算法

    多级反馈队列调度例子

3. 实时调度

实时任务有如下特点

  1. 紧迫性

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

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

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

3.1 基本条件

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

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

一般采用抢占方式。

  1. 时间片轮转调度算法

    满足数秒内

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

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

常用的实时调度算法

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

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

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

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

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

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

4. 死锁

资源竞争导致僵局。需要外力干预。

4.1 产生死锁原因

  1. 资源竞争
  2. 进程推进顺序非法
  3. 竞争非剥夺性资源

危险区,禁区

4.2 产生死锁的必要条件

  1. 互斥条件:请求的资源为临界资源
  2. 请求和保存条件:申请新资源、保持旧资源
  3. 不剥夺条件:已获得的资源,在使用完之前,不被外力剥夺
  4. 环路等待条件:互相等待资源

4.3 处理死锁的基本方法

  1. 预防死锁

    设置某些限制条件,破坏产生死锁的必要条件之一

    1. 一次将资源全部分配(摒弃 “请求和保持” 条件)
    2. 当请求的资源得不到满足时,放弃已分配资源(摒弃 “不剥夺” 条件)
    3. 对资源的申请必须按一定顺序进行(摒弃 “环路等待” 条件)
  2. 避免死锁

    在资源的动态分配过程中,用某种方法去防止系统进入不安全状态。

  3. 检测死锁

    检测出死锁原因,采取措施,接除死锁。

  4. 解除死锁

    剥夺资源或通过撤销进程,收回一些资源。

4.5 Dijkstra 银行家算法

  1. 进程需求资源数如果大于现有资源数,不分配
  2. 预分配,检查是否存在一个进程序列,可以安全执行完成。存在则分配,否则不分配。

银行家算法样例

4.6 死锁定理

  1. 在资源分配图中,找到一个可获得所有资源的进程结点Pi,使之变成孤立点(释放资源)
  2. 再找另一个可获得所有资源的进程结点 Pj ,使之变成孤立点
  3. 重复 2
  4. 如果所有进程都变成孤立点,则没有死锁;否则,存在死锁 。