【操作系统】作业调度（高级调度）

野性酷女 2022-07-14 04:53 340阅读 0赞

# 作业和作业步 #

## 作业 (job) ##

*  作业是把命令、程序和数据按照预先确定的次序结合在一起，并提交给系统的一个组织单位。
 *  或者：作业是用户交给系统的具有独立功能的任务。
 *  作业：程序和数据 + 作业说明书
 *  在批处理系统中，是以作业为基本单位从外存调入内存  
    的。

## 作业步 (job step) ##

一个典型的作业可分成三个作业步：  
1.“编译”作业步；  
2.“连结装配”作业步；  
3.“运行”作业步。

# 作业控制块 JCB #

在多道批处理系统中通常有上百个作业，为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的 JCB的组成内容有所区别。

**JCB 是作业在系统中存在的唯一标志**。作业进入系统时由系统为每个作业建立一个 JCB；当作业退出系统时，则它的 JCB 也一起被撤消。

# 作业运行的三个阶段和三种状态 #

## 收容阶段 ##

当用户完成作业的提交，作业存在于外存中，系统建立JCB。在它还未被调度去执行前，该作业处于后备状态。

## 运行阶段 ##

作业被调度进入内存，并以进程的形式存在，其状态是执行状态。处于执行状态的作业可以有多个。

**处于执行状态的作业并不意味着一定在 CPU 上运行**，是否运行依赖于进程控制。

## 完成阶段 ##

当作业已经完成其指定的功能，便进入停止状态，系统回收已分配资源。

# 作业调度的主要任务 #

## 接纳多少作业 ##

*  即多道程序的“道”。
 *  太多则可能会影响系统的服务质量（如周转时间太长），太少又将导致系统资源利用率和吞吐量的下降。
 *  根据系统的规模和运行速度来确定，同时要求 I/O 型进程与 CPU 型进程中和调度。

## 接纳哪些作业 ##

取决于采用何种调度算法（先来先服务、短作业优先等）

# 先来先服务调度算法 FCFS #

## 基本思想 ##

按进程（作业）进入就绪（后备）队列的先后次序来分配处理机（为其创建进程）。

一般采用非剥夺的调度方式。

例如：![例题][20161128103247477]

![例题][20161128103335681]

![例题][20161128103653857]

FCFS 调度算法的平均作业周转时间与作业提交的顺序有关。

FCFS 调度算法的特点：

*  简单，但效率不高。
 *  有利于 CPU 繁忙型作业。
 *  不利于 I/O 繁忙型作业。
 *  现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系- 统和实时系统中。但它常被结合在其它调度策略中使用。

![例题][20161128104739493]

# 短作业优先调度算法（SJF） #

*  用于作业调度
 *  主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，-将它们调入内存运行。
 *  类似地，用于进程调度的是短进程优先调度算法（SPF）

例如

![例题][20161128105203245]

## FCFS 与 SJF 的比较 ##

![比较][20161128105600586]

## 短作业优先调度算法的优缺点 ##

优点

*  能有效降低作业的平均等待时间。
 *  能有效缩短进程的平均周转时间。
 *  提高了吞吐量。

缺点

*  对长作业不利。
 *  没有考虑作业的紧迫程度。
 *  作业执行时间、剩余时间仅为估计。

SJF 算法虽然是优化的，但在 CPU 调度中很难实现。

# 优先级调度算法 #

对于 FCFS，等待时间是优先级。对于 SJF，作业的长短是优先级。

优先级调度算法(Priority-Scheduling Algorithm, PSA)以作业的紧迫程度为优先级。

系统选择优先级最高的几个作业装入内存。

优先级调度算法也用于进程调度，系统在可运行的进程中选择优先级最高者使其投入运行。

优先级的类型

*  静态优先级
 *  动态优先级

## 静态优先级 ##

优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般用整数表示，小表示优先级高。

确定原则：

*  进程类型（系统进程 > 用户进程）
 *  进程对资源的需求（要求少的有较高的优先权）
 *  用户要求（紧急程度和付费情况）

优点：简单，开销小。  
缺点：公平性差（对低优先权进程）

## 动态优先级 ##

动态优先级在进程的存在过程中不断发生变化。

动态优先级的变化取决于：

*  进程的等待时间
 *  进程的运行时间
 *  进程使用资源的情况

动态优先权确定方法的资源利用率高，公平性好，但开销较大，实现较为复杂。

高响应比优先算法 (HRRN)采用动态优先权。

## 高响应比优先调度算法 ##

FCFS 只考虑了作业的等待时间，忽略了运行时间。SJF 只考虑了作业的运行时间，忽略了等待时间。

高响应比优先调度算法(Highest Response Ratio Next,HRRN) 既考虑了作业的等待时间，也考虑了作业的运行时间，是一种动态优先级调度算法。

![公式][20161128110206891]

周转时间：从提交到完成的时间间隔。响应时间：在交互式系统中，从提交请求到产生首次响应的时间，而不是到产生输出结果所需的时间。

如等待时间相同，则要求服务时间越短其优先权越高→SJF。  
如要求服务时间相同，优先权决定于等待时间→FCFS。  
对长作业，若等待时间足够长，优先权也高，也能获得CPU。

例如：

![例题][20161128110636142]

![示例][20161128110957815]

# 不同调度算法对同一个调度实例的性能分析 #

![比较][20161128111055784]

[20161128103247477]: /images/20220714/ef35c3f834d34647b6e507a5eb45d006.png
[20161128103335681]: /images/20220714/a274c7634c92420ebbcd636e625dec0a.png
[20161128103653857]: /images/20220714/818328a44af743179a41f75d4e9eca7c.png
[20161128104739493]: /images/20220714/631719583f334a679562f6aea3f94e14.png
[20161128105203245]: /images/20220714/8d5ff3ab325d452aa53eb0fad148fe9e.png
[20161128105600586]: /images/20220714/f0932fe445334fe0bbbd4720310b24f0.png
[20161128110206891]: /images/20220714/ea6e5dc9d6b24c68b434ec5c79405db5.png
[20161128110636142]: /images/20220714/d1d7d848c4cd44c58fbe1ccc63103f43.png
[20161128110957815]: /images/20220714/b653878406d04de488df128b63043436.png
[20161128111055784]: /images/20220714/7e6ccae0a1c743d884e8c3b765298f9c.png