处理机调度之作业调度

时间  2021-05-27 标签 操作系统 先来先服务算法 短作业优先算法 优先级调度算法 高响应比优先调度算法 处理机调度的层次

3.1处理机调度的层次和调度算法

先行知识

  • 处理机调度的主要目标
    • 充分有效地利用处理机（CPU）资源
  • 处理机调度的对象
    • 作业、进程
  • 作业与进程的关系
    • 作业是任务实体，如：一次计算，一个控制过程
    • 进程是执行实体，是系统分配资源的基本单位
    • 一个作业由一个以上进程组成
      在这里插入图片描述

1、处理机调度的层次

⑴高级调度（单向）

  • 又称长程调度或作业调度。
  • 高级调度主要用于多道批处理系统中。
    在这里插入图片描述

⑵低级调度

  • 又称为进程调度或短程调度。
  • 进程调度是基本调度，所有系统都必须配备。
    在这里插入图片描述

⑶中级调度（双向）

  • 又称为内存调度。
  • 主要目的是提高内存利用率和系统吞吐量。
  • 中级调度实际上就是存储器管理中的对换功能。
  • 可任选。
    在这里插入图片描述

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

总体目标

  • ①资源利用率：为提高系统的资源利用率，应使系统中的处理机和其他所有资源都尽可能地保持忙碌状态。
    在这里插入图片描述
  • ②公平性：指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。
  • ③平衡性：使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。
  • ④策略强制执行：系统中的某些策略比如安全策略在必要的时候必须执行，即使会造成某些工作的延迟也要执行。

三种基本操作系统的目标

在这里插入图片描述

周转时间

  • 平均周转时间：在这里插入图片描述
  • 带权周转时间：W=T/Ts
  • 平均带权周期时间：

3.2作业与作业调度

3.2.1批处理系统中的作业及调度

1、作业和作业步

  • （1）作业：作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。
  • （2）作业步：作业中相对独立又相互关联的加工步骤。

2、作业控制块JCB

在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。

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

  • ⑴收容阶段→后备状态
  • ⑵运行阶段→运行状态
  • ⑶完成阶段→完成状态

4、作业调度的主要任务

按照一定的调度算法，从外存的后备队列中，选取某些作业调入内存，并为它们创建进程、分配必要的资源。

  • 在每次执行作业调度时，须做出以下两个决定：
    • 接纳多少个作业
      取决于多道程序度，即允许多少个作业同时在内存中运行。
    • 接纳哪些作业
      取决于所采用的调度算法。

3.2.2先来先服务和短作业优先调度算法

1.先来先服务FCFS(first-come first-served)：

  • 该算法按照作业到达的先后次序进行调度。
    • 优点:实现简单。
    • 缺点:
      • 没考虑作业（进程）的优先级。
      • 效率不高，只顾及作业等候时间，没考虑作业要求服务时间的长短；不利于短作业。

FCFS算法示例

下表列出了A、B、C、D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，计算出各自的周转时间和带权周转时间。
在这里插入图片描述

FCFS的特点

  • 比较有利于长作业，而不利于短作业。

  • 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

    • CPU繁忙型作业：该类作业需要大量的CPU时间进行计算而很少请求I/O。如通常的科学计算。
    • I/O繁忙型作业：指CPU进行处理时，需频繁的请求I/O。目前大多数事务处理都属于I/O繁忙型作业。

  • 貌似“公平”！短作业等待时间长。

  • 属于非抢占式！

2.短作业优先SJF（short job first）：

  • 该算法从队列中选出一个最短的作业进行调度。
    • 优点：平均周转时间最短。
    • 缺点：①对长作业不利；②必须预知作业的运行时间

SJF算法示例

在这里插入图片描述
注意，调度过程中，从就绪队列中选出作业的顺序是：
A ->D->B->E->C（对于最先到达的作业A先执行）

最短剩余时间优先算法SRTF（Shortest Remaining Time First）(抢占式)

如采用最短剩余时间优先算法SRTF（Shortest Remaining Time First），情况将如何变化。
在这里插入图片描述

SJF算法优缺点

  • 算法容易实现；
  • 能有效降低作业的平均等待时间；
  • 忽视了作业等待时间，对长作业不利，有可能导致长作业（进程）长期不被调度（出现饥饿现象）；
  • 要精确知道一个作业的运行时间比较困难的。

3.23优先级调度算法和高响应比优先调度算法

1.优先级调度算法(priority-scheduling algorithm,PSA)

基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。这样就可以保证紧迫性作业优先运行。

优先级算法示例

假定在单CPU条件下有下列要执行的作业按顺序先后到达：
在这里插入图片描述
① 用执行时间图描述非抢占优先级调度算法执行这些作业的情况（数值越大优先级越高）。
在这里插入图片描述
② 算出各作业的周转时间和带权周转时间
在这里插入图片描述

2.高响应比优先调度算法(Highest Response Ratio Next,HRRN)

高响应比优先调度算法既考虑了作业的等待时间，又考虑作业运行时间，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。

  • 高响应比优先算法的实现：
    在这里插入图片描述
    由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先级又相当于响应比RP。据此，又可表示为：
    在这里插入图片描述

高响应比优先算法示例

  • 有两个作业A和B，
  • 分别在7:00和8:30到达系统，
  • 它们估计的计算时间分别为0.8小时和0.1小时，
  • 系统在9:00开始以高响应比优先调度算法进行调度，
  • 请问在单道执行时这两道作业被选中的次序以及选中时的响应比。
    在这里插入图片描述
  • 在9:00开始调度时，两个作业的响应比如下：
    • A作业的响应比=1+120/48=3.5
    • B作业的响应比=1+30/6=6
  • 因此，先选中作业B!
  • 当作业A执行时，其响应比=1+(120+6)/48=3.625

公式深入理解

在这里插入图片描述

  • 算法基本思想： HRRN算法在当前作业执行完时,计算剩余作业的响应比，选取响应比最高的作业投入运行。
    • 举例：以下四个作业先后到达系统，按HRRN进行调度，请给出调度顺序：在这里插入图片描述
      • 开始只有作业1，被选中,执行时间20ms；
      • 作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被 选中，执行时间5ms；
      • 作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15ms；
      • 作业2执行完毕，作业4被选中，执行时间10ms；
      • 平均作业周转时间T = (20+15+35+35)/4 = 26.25
      • 平均带权作业周转时间W = (20/20+15/5+35/15+35/10)/4 = 2.46

HRRN算法优缺点

  • 既考虑作业等待时间，又考虑作业的运行时间 ；
  • 既照顾短作业又不使长作业的等待时间过长 ;
  • 计算响应比需要耗费时间。
联系我们 沪ICP备2021010478号-7