操作系统

处理机调度与死锁(一)

今天考完科目三之后接到导师的任务，关于处理机和死锁的算法问题，要求图形界面及动画演示(基于Python)。真的哭辽，完全没有头绪···在这里记录学习和解决的过程。

目录：

  1. 处理机调度的层次和调度算法的目标
  2. 作业与作业调度
  3. 进程调度
  4. 实时调度
  5. 死锁概述
  6. 预防死锁
  7. 避免死锁
  8. 死锁的检测与接触

一.处理机调度的层次和调度算法的目标

处理机是计算机系统中的重要资源。处理机调度算法对整个计算机系统的综合性能指标有重要影响。

从处理机调度的分类：

  • 高级调度（作业调度）：作业调度的周期较长，几分钟一次。
  • 中级调度（内外存交换）：介于高级与低级之间。
  • 低级调度（进程调度）：运行频率最高，10~100ms一次。

1.处理机调度层次

  • 高级调度
  • 低级调度
  • 中级调度

（1）高级调度

高级调度又称为“作业调度”“长程调度”“接纳调度”。

主要功能：根据某种算法，把外存上处于后备队列中的那些作业调入内存。

主要任务：< 选择作业 > < 为作业创建进程 > < 分配资源 > < 插入就绪队列 >

应用范围：< 批处理系统中配有作业调度 > < 分配和实时系统中通常没有作业调度 >

（2）低级调度

低级调度又称为“进程调度”或“短程调度”。

主要功能：根据某种算法，决定就绪队列中哪个进程先获得处理机，然后再由分派程序执行将处理机分配给进程的操作。

主要任务：< 保存处理机的现场信息 > < 按某种算法选取进程 > < 分配处理器 >

（3）中级调度

中级调度又称“内存调度”或“中程调度”。

主要目的：缓解内存紧张情况，提高内存利用率和系统吞吐量。

主要功能：按一定算法在内存和外存之间进行进程对换。

主要任务：是将内存中处于阻塞状态的某些进程换至外存，腾出内存空间以便将外存上已具备执行条件的进程换入内存。

应用范围：分时系统和具有虚拟存储器的系统中。

2.处理机调度算法的目标

（1）处理机调度算法的共同目标

  • 资源利用率

$ CPU资源利用率 = \frac{CPU有效工作时间} {CPU有效工作时间 + CPU空闲等待时间} $

  • 公平性

< 不出现进程饥饿现象 > < 公平性是相对的 >

  • 平衡性

合理安排不同类型的作业，CPU繁忙型、I/O繁忙型。

  • 策略强制执行

根据需要准确执行所定制的策略。

（2）批处理系统的目标

  • 平均周转时间短

周转时间（$T_i$）：指从作业（进程）被提交给系统开始，到作业完成为止的这段时间间隔。

kEK1II.png

$ T=\frac{1}{n}\sum_{i=1}^n T_i $

带权周转时间（W）：用于反应调度性能的指标，$ W=\frac{T}{T_s} $ （$T_s$为实际处理时间)

平均带权周转时间：$ W=\frac{1}{n}\sum_{i=1}^n\frac{T_i}{T_s} $

  • 系统吞吐量高

吞吐量：单位时间内系统所完成的作业数。

策略：选择短服务业运行。

  • 处理机利用率高

策略：选择计算量大的作业运行。

（3）分时系统的目标

  • 响应时间快

响应时间：从用户通过键盘提交一个请求开始，到首次产生响应为止（显示出结果）的一段时间间隔。

包括这三部分：

  • 把请求信息从键盘传送到处理机的时间。
  • 处理机对请求信息进行处理的时间。
  • 将响应信息回送到终端显示器的时间。
  • 均衡性

均衡性：指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

（4）实时系统的目标

  • 截至时间的保证

截至时间：某任务必须开始或完成的最迟时间。

（这是实时系统调度算法的一个主要目标；HRT任务与SRT任务对截止时间的要求有所差异。）

  • 可预测性

如多媒体系统中的视频播放就提供了请求的可预测性。

二.作业与作业调度

1.批处理系统中的作业

（1）作业和作业步

  • 作业：由程序、数据及作业说明书三部分组成。
  • 作业步（Job Step）：作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，其中每一个加工步骤又称为一个作业步：

< “编译”作业步 > < “链接装配”作业步 > < “运行”作业步 >

（2）作业控制块

  • 作业控制块

是作业在系统中存在的标志，保存了系统对作业进行管理和调度的全部信息。通常包括：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。

  • 作业的生命周期

  1. 作业进入系统时，由“作业注册”程序为作业建立JCB，然后根据作业类型将其放到相应的作业后备队列等待调度；

  2. 调度程序按一定的调度算法将调度到的作业装入内存；

  3. 作业运行期间，系统按照JCB中的信息对作业进行控制；

  4. 作业执行结束，系统负责回收它的资源，撤消它的JCB。

（3）作业运行的三个阶段和三种状态

  • 作业运行的三个阶段

收容阶段

运行阶段

完成阶段

  • 作业的三种状态

后备状态

运行状态

完成状态

2.作业调度的主要任务

  • 执行调度时的要解决的问题

接纳多少个作业。

接纳哪些作业（由调度算法决定，如FCFS、SJF、优先级调度算法等）。

  • 作业调度的应用范围

批处理系统中配有作业调度。

分时和实时系统中通常没有作业调度，但有接纳控制措施。

3.先来先服务调度算法（FCFS）和短作业优先调度算法（SJF）

（1）FCFS

  • 作业调度

按照作业提交的先后次序，从后备队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程，然后放入就绪队列。

  • 进程调度

从就绪队列中选择一个最先进入该队列的进程，为它分配CPU，使之运行；该进程一直运行到完成或发生阻塞。

在进程被唤醒后（如I/O完成），并不立即恢复执行，通常等到当前进程出让CPU。

  • 特点：

简单、易于实现、服务质量不佳。

取决于作业（进程）提交顺序。

较有利于长作业（进程）或CPU繁忙型的作业。

不利于短作业（进程）或I/O繁忙型作业。

  • 用途：

既可用于作业调度，也可用于进程调度。

很少作为进程调度的主要算法，但常作为辅助调度算法。

进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间 带权周转时间
A 0 1 0 1 1 1
B 1 100 1 101 100 1
C 2 1 101 102 100 100
D 3 100 102 202 199 1.99

周转时间：周转时间 = 完成时间 - 到达时间

平均周转时间：$ T=\frac{1}{n}\sum_{i=1}^n T_i $

带权周转时间：$带权周转时间 = \frac{周转时间}{服务时间}$

平均带权周转时间：求和取平均

（2）SJF

  • 作业调度

从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

  • 进程调度

对预计执行时间短的进程优先分配处理机。

  • 特点

能显著改善作业的平均周转时间。

在降低作业的平均等待时间同时，提高系统吞吐量。

必须预知作业的运行时间。

对长作业非常不利（饥饿）。

人机无法实现交互。

未考虑作业的紧迫程度。

  • 用途

可分别用于作业调度和进程调度。

4.优先级调度算法（PSA）和高响应比优先调度算法（HRRN）

（1）PSA（Priority-Scheduling Algorithm）

  • 基本思想：基于作业的紧迫程度，由外部赋予作业相应的优先级，调度时按优先级的高低进行调度。
  • 应用范围：用于批处理系统中的作业调度算法、多种操作系统及实时系统中的进程调度算法。
  • 作业调度：从后备队列中选择若干个优先权最高的作业调入内存。
  • 进程调度：是把处理机分配给就绪队列中具有最高优先权的进程。

（2）HRRN（Highest Response Ratio Next）

$优先权 = \frac{等待时间+要求服务时间}{要求服务时间} = \frac{响应时间}{要求服务时间} = R_p$

是一种__动态优先权调度算法__。

  • 调度规则：在当前作业完成或被阻塞时，选择$R_p$值最大的作业。
  • 特点

照顾了短作业。

先来先服务，等待时间越短，$R_p$越小。

不会使长作业长时间得不到服务，因为随着等待时间的增的，$R_p$也在增大，从而获得处理机。

  • 缺点：增加系统开销。因为每次调度时，都要进行响应比$R_p$的计算。

更新于 2019/01/23 — 21:51

三.进程调度

1.进程调度的任务、机制和方式

（1）进程调度的任务

  • 保存处理机的现场信息（当前进程的）
  • 按某种算法选取进程
  • 把处理机分配给进程（装入现场信息）

（2）进程调度中的三个基本机制

kZFtEV.png

  • 排队器：将系统中所有就绪进程按一定的方式排成一个或多个队列。
  • 分派器：把由进程调度程序所选定的程序，从就绪队列中取出，进行从分派队列进程到新选出进程间的上下文切换，将处理机分配给它。
  • 上下文切换机制

对处理机进行切换时，会发生两对上下文切换操作：

第一对上下文切换时，OS将保存当前进程的上下文，装入分派程序的上下文；第二对上下文切换时，移出分派程序，把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。

（3）进程调度方式

  • 非抢占方式（Nonpreemptive Mode）

引起调度的原因：

1）正在执行的进程执行完毕，或因发生某事件而不能再继续执行。

2）执行中的进程因提出I/O请求而暂停执行。

3）在进程通信或同步过程中执行了某种原语操作。

优点：实现简单，系统开销小，适用于大多数的批处理系统。

缺点：难以满足紧急任务的要求，不宜用于分时系统和大多数实时系统。

  • 抢占方式（Preemptive Mode）

抢占调度的原则：

1）优先权调度原则

2）短进程优先原则

3）时间片原则

优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务。

缺点：系统开销大。

2.转轮调度算法（RR）

（1）RR调度算法的基本原理

1）将系统中所有就绪进程按照FCFS原则，排成一个队列。

2）每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片长度从几个ms到几百ms。

3）在一个时间片结束时，发生时钟中断。

4）调度程序据此时暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队列队首进程

5）进程可以未使用完一个时间片，就让出CPU。

（2）进程切换时机

  • 一个时间片尚未用完

原因：

1）进程运行结束

2）进程阻塞

操作：

1）立即激活调度程序

2）调度就绪队列队首的进程运行

3）启动一个新的时间片

  • 一个时间片用完时

原因：进程尚未运行结束

操作：

1）计时器中断处理程序激活

2）调度程序将进程送至就绪队列末尾

（3）时间片大小的确定

  • 太大：响应时间受影响
  • 无穷大：退化为FCFS算法
  • 太小：增加系统开销
  • 选取：时间片大小一般选取略大于一次典型的交互所需要的时间

3.高优先级调度算法

（1）优先级调度算法的类型

  • 非抢占式优先权算法：

    处理机分配给就绪队列优先权最高的进程后，该进程就一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，才进行CPU的重新分配。

    应用范围：批处理系统、实时性要求不严的实时系统。

  • 抢占式优先权调度算法：

    处理机分配给就绪队列优先权最高的进程后，只要出现另一个优先权更高的进程时，便停止原来执行进程，把处理机分配给新出现的优先权最高的进程。

    应用范围：实时性要求比较严格的实时系统。

（2）优先级的类型

  • 静态优先级

进程优先级在创建进程时确定，整个运行期间保持不变。

确定优先权的依据：

1）进程类型：系统进程的优先级高于一般用户进程。

2）进程对资源的需求：资源要求少的进程赋予较高的优先级。

3）用户要求：根据进程的紧迫程序及用户的付费确定优先级。

特点：

1）简单易行，系统开销小，不够精确

2）可能会出现低优先权作业长期不被调度

  • 动态优先级

进程创建时赋予的优先权可以随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

如：优先权随执行时间而下降，随等待时间而升高。

优点：长短兼顾，可以防止某类作业长时间垄断CPU。

缺点：增加了系统开销。

4.多队列调度算法

  • 描述

1）将不同类型或性质的就绪进程固定分配在不同的就绪队列；

2）不同的就绪队列采用不同的的调度算法；

3）一个就绪队列中的进程可以设置不同优先级；

4）不同的就绪队列本身也可以设置不同的优先级。

比如：多处理机系统。

5.多级反馈队列调度算法（MFQ）

（1）调度机制

  • 设置多个就绪队列，并为各个队列赋予不同的优先权，第一个队列的优先级最高，优先级依次降低。
  • 赋予各个队列中进程执行时间片的大小也各不相同。优先权愈高，时间片愈小。
  • 新进程进入内存后，放在第一队列未尾，先来先服务；一个时间片内运行不完，则转下一队列。
  • 按队列顺序运行，最后一个队列按时间片轮转，其余按FCFS运行。
  • 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~（i - 1） 队列均空时，才会调度第i队列中的进程运行。
  • 如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~（i - 1）中的任何一个队列)，则此时须立即把正在运行的进程放回到第 i队列的末尾，把处理机分配给新到的高优先级进程。

（2）调度算法性能

  • 多级反馈队列调度算法：属于抢占式调度方式。
  • 调度算法的性能：具有较好的性能，能照顾到各种用户的利益

终端型作业用户

短批处理作业用户

长批处理作业用户

6.基于公平原则的调度算法

（1）保证调度算法

  • 保证调度算法向用户保证的是明确的性能，可以做到调度的公平性。
  • 保证处理机分配的公平性：如果系统中有n个相同类型的进程同时运行，须保证每个进程都获得相同的处理机时间 $\frac{1}{n}$。
  • 保证的是每个进程获得相同的处理机时间。
  • 实施公平调度算时，系统必须具备的功能：

1）跟踪计算每个进程自创建以来已经执行的处理时间；

2）计算每个进程应获得的处理机时间：$T_target = \frac{T_current - T_create}{n}$.

3）进程获得处理机时间的比率：$\frac{T_real}{T_target}$。

4）比较各进程获得处理机的时间比率。

5）调度程序选择比率最小的进程，将处理机分配给它，并让该进程一直运行到超过最接近它的进程比率为止。

（2）公平分享调度算法

  • 调度的公平性是针对用户，所有用户能获得相同的处理机时间，或所要求的时间比例。

例：系统中有2个用户，用户1有4个进程A、B、C、D，用户2只有1个进程E。

保证两个用户获得相同的处理机时间，则强制调度序列为：A E B E C E D E A E B E C E D E……

希望用户1获得的处理机时间是用户2的2倍，则强制调度序列为：A B E C D E A B E C D E A B E C D E ……

四.实时调度

1.实现实时调度的基本条件

（1）提供必要信息

  • 就绪时间
  • 开始或者完成截止时间
  • 处理时间
  • 资源需求
  • 绝对或相对优先级（硬实时或软实时）

（2）系统处理能力强

  • 单处理机情况下，要求满足下面限制条件：$ \sum_{i = 1}^m \frac{C_i}{P_i} <= 1$（其中$C_i$表示处理时间$P_i$表示周期时间)。

（3）采用抢占式调度机制

  • 以满足HRT任务对截止时间的要求。

（4）具有快速切换机制

  • 对外部中断的快速响应能力

1）系统具有快速硬件终端机构。

2）在中断处理时（硬件），禁止中断的时间间隔尽量短。

  • 相应地采用较小的调度单位（如线程），以减少任务切换的时间开销。

2.实时调度算法分类

  • 按实时任务性质分类

硬实时调度算法

软实时调度算法

  • 按调度方式分类

非抢占调度算法

抢占调度算法

（1）非抢占式调度算法

  • 特点：算法比较简单，易于实现
  • 分类

非抢占式轮转调度算法：秒级的响应时间，适用于一般实时信息处理系统或要求不太严格的实时控制系统

非抢占式优先级调度算法：秒级至数百毫秒级的响应时间，适用于有一定要求的实时控制系统。

（2）抢占式调度算法

  • 应用：要求较严格（响应时间为数十毫秒以下）的实时系统。
  • 分类

基于时钟中断的抢占式优先级调度算法：几十毫秒级至几毫秒级的响应时间，用于大多数的实时控制系统。

立即抢占（Immediate Preemption）的优先级调度算法：一旦出现外部中断，只要当前任务未处于临界资源，便立即剥夺当前任务的执行。调度延迟可低到几毫秒至100微妙。

3.最早截止时间优先（EDF）算法

  • 该算法是根据任务的开始截止时间来确定任务的优先级，任务的开始截止时间愈早，其优先级愈高。
  • 要求系统中保持一个实时任务就绪队列，该队列按各任务的截止时间的早晚排序。
  • 可采用非抢占调度方式，也可采用抢占调度方式。

（1）非抢占式调度方式用于非周期实时任务

例：对下面5个非周期性实时任务，按最早开始截止时间优先调度算法应如何进行CPU调度？

进程 到达时间 执行时间 开始截止时间
A 10 20 110
B 20 20 20
C 40 20 50
D 50 20 90
E 60 20 70

（2）抢占式调度方式用于周期实时任务

4.最低松弛度优先（LLF）算法

  • 该算法根据实时任务的松弛度来确定任务的优先级，任务的松弛度愈低，其优先级愈高。
  • 松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间
  • 要求系统中有一个按松弛度排序的实时任务就绪队列。
  • 主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它便立即抢占CPU，以保证按截止时间的要求完成任务。

例：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度是多少？

A的松弛度 = 200－100－10 ＝ 90ms

例：假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执行一次，执行时间为 25 ms。

5.优先级倒置

（1）优先级倒置的形成

  • 形成：OS广泛采用优先级调度算法和抢占调度方式，而系统中存在着影响进程运行的资源，可能产生“优先级倒置”的现象，即一个低优先级的任务持有一个被高优先级任务所需要的共享资源，高优先任务由于因资源缺乏而处于阻塞状态，一直等到低优先级任务释放资源为止。

优先级倒置的例子：有三个独立的并发进程P1、P2、P3，它们的优先级为： P1>P2>P3，P1与P3均会使用到一个临界资源。

P1: …P(mutex); CS-1; V(mutex); …

P2: … program2; …

P3: … P(mutex); CS-3; V(mutex); …

（2）优先级倒置的解决方法

  • 设置优先级上限：给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。
  • 优先级继承：当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。
  • 使用中断禁止：通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。

更新于 2019/01/24 — 14:46

至此前四部分完成，接下来第二篇会写死锁。

© 2018 - 2023 fmt.Println("Li Duo")
自认为是幻象波普星的来客
Built with Hugo
主题 Stack 由 Jimmy 设计