Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

处理机的调度

Posted on In ,
Symbols count in article: 5.7k Reading time ≈ 5 mins.

处理机的多级调度

  • 作业调度(宏观)：决定哪些程序调入计算机系统
  • 进程调度(微观)：决定哪个（些）进程占用CPU，使用多长时间等

    作业调度

作业及作业调度的功能

一般来说，计算机系统把用户要求处理的一项工作称为一个作业。

作业有四种状态：
1.提交状态 用户将程序和数据提交计算中心；
2.后备状态 将作业录入到后援存储设备；
3.执行状态 作业调入计算机系统内存；
4.完成状态 作业计算完成的善后处理。

image-20200104223306933

作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。
功能：
1.确定数据结构，记录已进入系统的各作业的情况（JCB，Job Control Block）；
2.按一定的调度算法，从后备作业中选择一个或几个作业进入内存；
3.分配资源，为被选中的作业创建进程，并为其申请系统资源；
4.作业结束后作善后处理。

每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见下表。

作业名
资源要求 估计运行时间
最迟完成时间
要求的主存量
要求外设的类型及台数
要求文件量和输出量
资源使用情况 进入系统的时间
开始运行的时间
已运行的时间
内存地址
外设台号
类型 控制方式
作业类型
优先级
状态数

性能的衡量

作业调度算法规定了从后备作业中选择作业进入系统内存的原则。

确定调度算法时应考虑的因素
1.应与系统的整体设计目标一致
2.考虑系统中各种资源的负载均匀
3.保证作业的执行
4.对一些专用资源的使用特性的考虑

平均周转时间和带权平均周转时间
image-20200104225107056

作业调度算法

  • 先来先服务调度算法（FCFS）

    • 先来先服务算法是按作业来到的先后次序进行调度的，换句话说，调度程序每次选择的作业是等待时间最久的，而不管作业的运行时间的长短。这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。
  • 短作业优先调度算法（SJF）
    • 短作业优先调度算法考虑作业的运行时间，每次总是选择一个运行时间最小的作业调入内存（系统）
    • 在一般情况下这种调度算法比先来先服务调度算法的效率要高一些。实现相对先来先服务调度算法要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死现象。
  • 响应比高者优先调度算法
    • 先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑了作业的运行时间，而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。
      image-20200104225428235
    • 响应比高者优先调度算法从理论上讲是比较完备的，但需要作业调度程序：
      • 统计作业的等待时间
      • 使用用户估计的运行时间
      • 作浮点运算（这是系统程序最忌讳的）
      • 复杂，开销大
  • 优先数调度算法（Priority Scheduling）
    • 优先数调度算法是终合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。
    • 这种算法的关键：
      • 如何终合考虑多种因素及其关系确定优先数
      • 优先数是否动态变化
      • 优先数什么时候变化

进程/线程调度

进程调度/分派

处理机分配由调度和分派两个功能组成：

  • 调度：依照确定的策略将一批进程排序，排在首位的进程一定是满足调度原则，可被选择的进程；组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。
  • 分派：是指当处理机空闲时，从就绪队列队首中移一个PCB，并将该进程投入运行。

调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这种进程将进入相应的等待队列中，并让出CPU，调用进程分派程序选择一个就绪进程占用CPU；当一进程被唤醒时，这种进程将插入到就绪进程队列中。
在一般的操作系统教材中把上述功能称为进程调度。

功能：

  • 记录和保持系统中所有进程的有关情况和状态特征
    进程调度的信息记录在PCB中，包括进程的状态、调度优先级（优先数）、就绪进程队列等。
  • 决定分配（处理机）策略
    • 先来先服务
    • 优先数调度策略
    • 调度策略的不同，组织就绪进程队列的方式不同
  • 实施处理机的分配和回收
    • 调度算法的选择（调度算法）
      • 先来先服务算法（FCFS）
      • 短进程优先算法（SPF）
      • 高响应比优先调度算法（HRRN）
      • 优先级调度算法（PSA）
      • 基于时间片的轮转调度算法（RR）
    • 调度时机的选择（调度时机）
      和调度方式相关
    • 实施进程调度（调度程序）

进程调度方式
若一个进程正在处理机上运行，若有一个更为紧迫的进程来到，系统的处理方式有：
(1) 非剥夺方式(不可抢先，non-preemptive)：进程已执行，若一个更为紧迫的进程来到，必须该进程执行完或时间片到，才让更紧迫的进程执行。
(2) 可剥夺方式(可抢先，preemptive)：有更紧迫的进程到来，中止当前进程的执行，立即让更紧迫的进程执行。

进程调度算法

进程优先数调度算法

  • 优先数调度算法赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU。
  • 如何确定进程的优先数？
  • 优先数是固定的，还是随着该进程运行的情况的变化而变化？

进程优先数调度算法优先数的确定

  • 静态优先数
    • 进程的优先数在进程创建时确定后就不再变化。
    • 系统确定（运行时间、使用资源，进程的类型）
    • 用户确定（紧迫程度，计费有关）
    • 系统与用户结合
    • 缺点：很多计算优先数所依赖的特征都将随进程的推进改变，静态优先数并非自始至终都能准确地反映出这些特性。
  • 动态进程优先数
    • 系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。

循环轮转调度算法（Round Robin）

  • 把系统的响应时间分成若干时间片（ Time Quantum or Time Slice）
  • 进程被调度到后，占用一个时间片
  • 多个进程循环轮转占用CPU

时间片长度的选择

  • 轮转法的性能取决于时间片（记为q,q = t / n ,t 为用户能接收的响应时间，n为进入系统的进程数）长度的选择，进程间在CPU上的切换需要时间。
  • q足够大到每一进程执行完，FCFS (先到先服务)
  • q 适当 ––– 进程均匀执行
  • q 太小 ––– 开销太大，有切换时间，CPU利用率低。
  • 通常来说，选择时间片为10~100毫秒左右比较适宜，上下文切换时间少于10微秒。

与时间片大小有关的因素

  • 系统响应时间(进程等待时间)
  • 就绪进程个数（就绪队列长度）
  • 轮换时间 (切换时间)

简单循环轮转虽然比较简单，但由于采用固定时间片和仅有一个就绪队列，可对其进行改性：

  • 将固定时间片改为可变时间片
  • 将单就绪队列改为多就绪队列

多级反馈队列

设有N个队列（Q1,Q2….QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。

对于优先级最低的队列来说，里面是遵循时间片轮转法。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。

各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。

算法描述：
1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
3、对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
4、在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。
5、在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

img

UNIX系统进程调度

优先数的确定

  • 系统设置
    在sleep（）中设置将要进入睡眠状态进程的优先数，如果是等待较紧迫的事件，优先数设置较小，一般为负数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。例如0＃进程（－100优先数）；
    +所有处于用户态运行进程同步（一般情况下为大于0）。
  • 优先数的计算
    p_pri = min{127, (p_cpu/16+p_nice+PUSER)}
    其中：
    p_cpu: 进程占用CPU的程度
    p_nice: 用户通过系统调用nice(priority)设置的进程优先数
    PUSER: 常数，其值为100

Linux系统的进程调度

Linux进程调度目标和特点

  • 进程调度程序是内核的组成部分，负责选择下一个要运行的进程。
  • 进程调度可看作在可运行态进程之间分配有限的处理器间资源的内核子系统。
  • 进程调度程序是如Linux这样的多任务操作系统的基础。
  • Linux进程调度策略
    • 基于动态优先级和可变时间片的调度
    • 调度方式为可抢占式调度

调度目标

  • 实现算法复杂度为O(1)级的调度
    • 进程调度算法保证在恒定的时间内完成
    • 算法执行时间与系统中处于就绪(可运行)状态的进程个数无关
  • 提高交互性能
    • 提高交互性能，保证系统能快速响应
  • 保证公平
    • 在合理设定的时间范围内，没有进程会出现饥饿状态，
    • 也不会有进程获得大量的时间片
  • 实现对称多处理器（SMP）可扩展性

I/O消耗型和处理器消耗型的进程

  • I/O消耗型进程
    大部分时间是使用外部设备，交互式进程具有此特征
  • 处理器消耗型进程
    大部分时间是使用CPU，计算进程具有此特征

交互式的程序都是I/O消耗型的。
Linux为了保证交互式应用，优化了进程的响应，更倾向于优先调度I/O消耗型进程，但并未忽略处理器消耗型程序。

进程调度的特点

  • Linux系统实现了基于进程过去行为的启发式算法；
  • Linux系统选择优先级高的进程先运行，相同优先级的进程按循环方式调度；
  • 动态优先级依进程占有CPU的情况、休眠时间的长短来增、减 ；
  • 系统根据进程优先级调整分配给它的时间片；
  • 实施可抢占调度方式

动态优先级

  • 基于优先级的调度
    优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度。
  • 静态优先级
    • 静态优先级在进程创建时确定，新创建的进程继承父进程的静态优先级;
    • 静态优先级的取值范围是100(最高优先级)  139(最低优先级)，取值越小，优先级越高;
    • 用户可以通过系统调用改变nice值，从而改变自己拥有的静态优先级。
  • 动态优先级
    • 每个进程有一个动态优先级，它是进程调度程序选择可运行进程所使用的参数，
      其取值范围是100(最高优先级) ~ 139(最低优先级)
    • 动态优先级的计算
      动态优先级 = max(100，min(静态优先级－ bonus + 5，139))
      bonus是范围 0 ～ 10的值，
                值小于5表示降低动态优先级以示惩罚
          值大于5表示增加动态优先级以示奖励
      进程调度使用的是动态优先级，通过effective_prio( )函 数来计算一个进程的动态优先级。

确定I/O消耗型和处理器消耗型进程的方法

  • 依据 —— 进程睡眠时间的长短
    若进程睡眠时间长 —— I/O消耗型
    若进程睡眠时间短 ——处理器消耗型
  • 方法
    Linux记录进程睡眠和执行时间 (存放在task_struct的sleep_avg域中)，范围：0 ～ MAX_SLEEP_AVG，默认值为10ms
    • 当进程从开始休眠到要恢复执行这一时间内，sleep_avg增加，直到达到MAX_SLEEP_AVG为止；
    • 进程每执行一个时钟节拍， sleep_avg递减，直到0为止

进程休眠时间与bonus值的关系

平均休眠时间 bonus值
大于或等于0， 小于 100ms 0
大于或等于100，小于 200ms 1
大于或等于200，小于 300ms 2
大于或等于300，小于 400ms 3
大于或等于400，小于 500ms 4
大于或等于600，小于 700ms 6
大于或等于700，小于 800ms 7
大于或等于800，小于 900ms 8
大于或等于900，小于 1000ms 9
大于1s 10

可变时间片
Linux系统的目标

  • 对交互式进程,系统提供较长的时间片
  • 调度程序根据进程的优先级动态调整分配给它的时间片

时间片处理的时机

  • 创建新进程时的处理
    • 新创建的子进程和父进程均分父进程剩余的时间片
  • 进程用完时间片时的处理
    • 当一个进程的时间片用完时，依任务的静态优先级重新计算时间片；
    • task_timeslice()函数为给定任务返回一个新的时间片

时间片的使用

  • 一个进程拥有的时间片可分多次使用，放弃CPU时进入活动队列
  • 当一个进程的时间片耗尽时，认为是过期进程，进入过期队列

时间片的计算

  • 基本时间片
    静态优先级本质上决定了进程的基本时间片
 (140 －静态优先级) ×20    若静态优先级 ＜ 120
 (140 －静态优先级) ×5      若静态优先级 ≥ 120
静态优先级越高(值越小)，基本时间片越长。

活动队列和过期队列
每个处理器维护两个优先级数组—— 活动数组和过期数组

  • 活动数组上的可执行队列中的进程都有剩余时间片
  • 过期数组上的可执行队列中的进程都已耗尽时间片
    当一个进程的时间片耗尽时，被移至过期队列中；
    当活动数组上的可执行队列中的所有进程都已耗尽时时间片，这时，在活动数组和过期数组之间切换指针。