The Processor Scheduling

处理机调度的层次 Process Scheduling Levels

概述 Overview

处理机是计算机系统中的重要资源,在多道程序环境下，进程数目通常多于处理机的数目,系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程;处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度

• WHAT：按什么原则分配 CPU 调度算法
• WHEN：何时分配 CPU 调度的时机
• HOW：如何分配 CPU 调度过程及进程的上下文切换

作业 JOB

作业是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合
作业是一个比程序更广泛的概念，可以包含多个程序和数据，还配有一份作业说明书，系统根据作业说明书来对作业中的程序进行控制。在批处理系统中，以作业为单位从外存调入内存
用户为了让计算机完成某个特定任务，首先编写成源程序，然后提交给计算机通过编译或汇编、连接、装配、运行等步骤，最终由计算机输出用户所需要的运行结果。从计算机管理的角度看，上述一系列的由计算机执行的任务的集合就是作业。

Job and task are today vague, ambiguous terms, especially task. A “job” often means a set of processes, while a “task” may mean a process, a thread, a process or thread, or, distinctly, a unit of work done by a process or thread.
job, task and process, what’s the difference

作业步 Job Step

计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完成作业的一部分特定工作;把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为作业步
作业的各个作业步虽然功能相对独立，但它们之间相互关联，往往是一个作业步的执行需要使用上一个作业步的执行结果。

从用户把源程序提交给计算机系统到得出运算结果要经过若干个工作步骤，首先计算机系统要对用户的源程序进行编辑工作来进行语法检查，再由编译或汇编工作生成目标代码。由连接工作形成装入模块，然后通过装入工作将装入模块装入内存。最后由运行工作得出运行结果。5 个步骤，每步都完成一项相对独立的工作

作业状态转换 Job State Transition

JCB

作业提交给系统进入后备状态后，系统将为每个作业建立一个作业控制块 JCB。
JCB 在作业的整个运行过程中始终存在，并且其内容与作业的状态同步地动态变化。只有当作业完成并退出系统时，JCB 才被撤消。可以说，JCB 是一个作业在系统中存在的唯一标志，系统根据 JCB 才感知到作业的存在
作业控制块 JCB 中包含了对作业进行管理的必要信息，JCB 中的信息一部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作业运行过程中的动态信息
JCB 的具体内容因系统不同而异

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

处理机调度的层次

• 在多道程序系统中，一个作业从提交到执行，通常都要经历多级调度,如高级调度、低级调度、中级调度以及 I/O 调度等
• 系统的运行性能在很大程度上取决于调度,如吞吐量的大小、周转时间的长短、响应的及时性等
• 调度是多道系统的关键

类型	运行频率	运行时间	算法复杂性	存储	OS
进程调度	高	短	低	内存中	批处理,实时,分时
中程调度	中	较短	中	内外存互换	批处理,实时,分时
作业调度	低	长	高	外存到内存	批处理

引起进程调度的事件：

1. 正在执行的进程正常终止或异常终止
2. 正在执行的进程因某事件而阻塞(如提出 IO 请求后阻塞,调用wait()后阻塞,在进程通信或同步过程中执行了某种原语操作，如 P、V 操作原语，Block 原语， Wakeup 原语等后阻塞)
3. 在引入时间片的系统中，时间片用完，进程被抢占
4. 在抢占式系统中，就绪队列中的某进程优先级高于当前进程,或有更高优先级的进程进入就绪队列

高级调度 High Scheduling

高级调度 High Scheduling：又称作业调度、准入调度、长程调度或接纳调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存;它发生在一批作业完成，重新调入一批作业到内存的时候，执行频率低。批处理系统需要有作业调度，分时和实时系统无需此调度。主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行;

例：对资源需求不同的作业进行合理搭配
科学计算往往需要占用大量的 CPU 时间，属于 CPU 繁忙型作业，对于 I/O 设备的使用少；
数据处理要求占用较少的 CPU 时间，但要求大量 I/O 时间，属于 I/O 繁忙型作业；
有些递归计算，产生大量中间结果，需要很多内存单元存放它们，这属于内存繁忙型作业。
如果能把它们搭配在一起，程序 A 在使用处理机，程序 B 在利用通道 l，而程序 C 恰好利用通道 2 等，这样一来，A、B 和 C 从来不在同一时间使用同一资源，每个程序就好像单独在一个机器上运行

在每次执行作业调度时，都须做出以下两个决定：

1. 接纳多少个作业（取决于多道程序度）
   • 作业太多 服务质量下降
   • 作业太少 资源利用率低
2. 接纳哪些作业 （取决于采用的调度算法）

调度评价指标

多道程序度 Degree Of Multiprogramming：即允许多少个作业同时在内存中运行。
周转时间 Turnaround Time：指从作业被提交给系统开始，到作业完成为止的这段时间间隔,也称为作业周转时间
带权周转时间 Weighted Turnaround Time：作业的周转时间 T 与系统为它提供服务的时间 TS 之比,称为带权周转世界,$WTT=\frac{T_{周转时间}}{T_{预计运行时间}}$
吞吐量 Throughput：是指在单位时间内系统所完成的作业数
服务时间 Service Time：作业的预计运行时间
响应比 Response Ratio：$RR=\frac{T_{等待时间} + T_{预计运行时间}}{T_{预计运行时间}}=\frac{T_{响应时间}}{T_{预计运行时间}}$,注意 RR>=1

低级调度 Low Scheduling

低级调度又称为进程调度或短程调度，它所调度的对象是进程。三种类型 OS 都必须配置这级调度(最基本调度);低级调度用于决定就绪队列中的哪个进程应获得处理机，然后由分派进程 Dispatcher执行把分配处理机给相应进程的具体操作。其时间尺度通常是毫秒级的,且是系统中最频繁的调度,要求在实现时做到高效

低级调度基本机制

1. 排队器为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。
2. 分派器(调度程序) 分派器把由进程调度程序所选定的进程从就绪队列中取出，然后进行上下文切换，将处理机分配给它。
3. 上下文切换机制当对处理机进行切换时，会发生两对上下文切换操作。

低级调度功能

1. 按某种算法选取进程（调度）。
2. 保存处理机的现场信息（上下文切换第一步骤）
3. 恢复新进程的 CPU 现场,从而把处理器分配给新进程（上下文切换第二步骤）。

进程调度方式

非抢占方式 Non-preemptive Mode：进程占用处理机直至自愿放弃或发生某事件被阻塞时，在把处理机分配给其他进程。

进程正在处理机上执行时，新就绪的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才转让处理机。

优点：算法简单，系统开销小
缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束

抢占方式 Preemptive Mode：允许暂停某个正在执行的进程，将处理机重新分配给另一个进程。

进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程

优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。
缺点：抢占方式比非抢占方式调度所需付出的开销较大，且调度算法复杂。

抢占方式 Preemptive Mode

• 时间片原则:适用于分时、大多数实时以及要求较高的批处理系统
• 优先权原则:重要紧急作业优先权高
• 短作业(进程)优先原则。

中级调度 Intermediate-Level Scheduling

中级调度 Intermediate-Level Scheduling,又称中程调度(Medium-Term Scheduling);
主要目的：为了提高内存利用率和系统吞吐量。
具体实现：

• 使那些暂时不能运行的进程不再占用宝贵的内存资源，而将其调至外存的交换区(swap space)去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。
• 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

调度队列模型和调度准则

调度模型 Scheduling Model

三级调度都涉及进程的队列。可以形成以下三种调度队列模型

• 仅有进程调度(低级调度)
• 具有高级和低级调度
• 具有三级调度

仅有进程调度

在分时系统中，通常仅设有进程调度,系统把这些进程组织成一个就绪队列,每个进程在执行时，可能有以下几种情况

• 进程获得 CPU 正在执行；
• 任务在给定时间片内已完成，释放处理机后为完成状态；
• 任务在时间片内未完成，进入就绪队列末尾；
• 在执行期间因某事件而阻塞。
  

  就绪队列时间片轮转，常采用 FCFS(FIFO)算法， FCFS(FIFO)队列。
  进程执行时三种情况：完成、时间片到、阻塞

具有高级和低级调度

在批处理系统中，不仅需要进程调度，而且还要有作业调度
就绪队列的形式:在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队列首进程
设置多个阻塞队列:根据事件的不同设置多个队列提高效率

常采用高优先权优先调度算法
可采用优先队列，进程来时按优先权插队，从队首调度 （效率高）
可采用无序列表，每次调度时，先比较优先权
多个阻塞队列

同时具有三级调度的调度队列模型

在 OS 中引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。同样，阻塞状态进一步分成内存阻塞和外存阻塞两种状态。
在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；
在中级调度的作用下，又可使外存就绪转为内存就绪。

选择调度方式和调度算法的若干准则

在不同的系统中通常采用不同的调度方式和算法。

调度的目标

• 提高处理机的利用率
• 提高系统吞吐量
• 尽量减少进程的响应时间
• 防止进程长期得不到运行

系统选择调度方式和算法的准则

调度评价指标术语

1. 面向用户的准则
   • 周转时间短:用来评价批处理系统的性能、选择作业调度方式与算法的重要准则之一
     • 作业在外存后备队列上等待调度的时间。
     • 进程在就绪队列等待调度的时间。
     • 进程在 CPU 上的执行时间。
     • 等待 I/O 操作完成的时间。
   • 响应时间快:用来评价分时系统的性能、选择进程调度算法的重要准则之一
     这里的响应时间，是指从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
     • 从键盘输入的请求信息传送到处理机的时间。
     • 处理机对请求信息进行处理的时间。
     • 将所形成的响应回送到终端显示器的时间。
   • 截止时间的保证:用来评价实时系统的性能、选择实时调度算法的重要准则之一
     截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。（也叫做时限，即 deadline）
     • 开始截止时间。
     • 终止/完成截止时间。
   • 优先权准则:适合批处理、分时和实时系统
     • 让某些紧急的作业能得到及时处理。
     • 往往还需选择抢占式调度方式，才能保证紧急作业得到及时处理。
2. 面向系统的准则
   • 系统吞吐量高:评价批处理系统
     • 吞吐量是指在单位时间内，系统所完成的作业数
     • 与批处理作业的平均长度有关
   • 处理机利用率高。主要对大、中型多用户系统，对单用户或实时系统不重要。
     $CPU利用率 = \frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$
   • 各类资源的平衡利用:如内存、外存、I/O 设备等;主要对大、中型系统，对微型机或实时系统不重要。

进程切换

进程切换:当一个进程占用处理机执行完(或不能继续执行)，则切换另一个进程占用处理机执行，称为进程切换。
进程调度:把处理机分配给不同的进程占用执行，称为进程调度。实现分配处理机的程序称为调度程序
在进程切换时，要保护执行现场。执行现场称为进程的上下文 context

进程切换基本步骤

1. 保存当前进程的上下文
2. 更新当前运行进程的 PCB，将其状态改为就绪 Ready 或阻塞 Blocked
3. 将 PCB 插入就绪队列或阻塞队列
4. 改变需要投入运行的进程的 PCB，将其状态改为运行 Running
5. 恢复新进程的上下文

调度算法

FCFS

先到先服务调度算法(FCFS，First Come First Served) 按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；适合于作业调度和进程调度;用于批处理系统，不适于分时系统

• 优点：
  • 有利于长作业（进程）
  • 有利于 CPU 繁忙型作业（进程）
• 缺点：
  • 不利用短作业（进程），特别是来的较晚的短作业（进程）。
  • 不利于 I/O 繁忙型作业（进程）

SJF

短作业优先的调度算法(SJF，Shortest Job First) 以要求运行时间长短进行调度，即启动要求运行时间最短的作业;可以分别用于作业调度和进程调度

• 短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行；
• 短进程优先(SPF)调度算法，则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。
• 优点
  • 能有效降低作业/进程的平均等待时间
  • 提高系统的吞吐量。
• 缺点
  • 该算法对长作业不利，更严重的是可能将导致长作业(进程)长期不被调度
  • 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理
  • 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度
  • 无法实现人机交互

SRT

最短剩余时间优先调度算法(SRT,Shortest Remaining Time) 调度时选择预期剩余时间最短的进程。当一个新进程加入到就绪队列时，它可能比当前运行的进程具有更短的剩余时间。因此，只要新进程就绪，调度器可能抢占当前正在运行的进程。可能存在长进程被饿死的危险。

PSA

优先权调度算法(PSA,Priority) 适合于作业调度和进程调度

• 优先权类型
  • 静态优先权:静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。优点是简单易行、系统开销小。缺点：不够精确，可能出现优先权低的作业或进程长期得不到调度的情况。
  • 动态优先权:动态优先权随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能
• 确定进程优先权的依据有
  • 进程类型: 系统进程高，一般用户进程低。
  • 进程对资源的需求:进程的估计执行时间、内存需求量等。要求少的进程赋予较高的优先权。
  • 用户要求:紧迫程度、所付费用。
• 非抢占式优先权算法（用于批处理、要求不严的实时 OS）系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。
• 抢占式优先权调度算法（用于要求严格的实时、性能要求较高的批处理和分时 OS）系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求
  Note: 只要新的进程到达并加入到就绪队列中，就进行优先权比较
  • 高响应比优先调度算法(HRRN,High Response Ratio Next),优先权的变化规律可描述为：$优先权 = \frac{等待时间+预计运行时间}{预计运行时间}$ 由于等待时间与预计运行时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比 RP。据此，又可表示为$R_p = \frac{等待时间+预计运行时间}{预计运行时间} = \frac{响应时间}{预计运行时间}$

    HRRN 是介于 FCFS 和 SJ(P)F 之间的一种折中算法,HRRN 调度算法的优点是能够较好地平衡服务时间短和等待时间长的进程，避免了“饥饿”现象。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于 SJ(P)F 算法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 算法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。

Round-Robin

时间片轮转调度算法(RR，Round-Robin):时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法,适合于进程调度。

• 基本原理
  系统将所有就绪进程按 FCFS 原则，排成一个队列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片(Time Slice)。当时间片用完时，由一个计时器发出时钟中断请求，调度程序便根据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
  
• Time Slice 大小确定
  需考虑系统对响应时间的要求,就绪队列中进程的数量,系统的处理能力(保证用户键入的命令能在一个时间片内处理完毕)
  • 时间片太短，会增加进程切换的开销，降低系统吞吐量
  • 时间片太长，退化成 FCFS
• 优缺点
  时间片的大小对计算机性能的影响。
  存在的问题：未有效利用系统资源。
  对于短的、计算密集型任务(CPU-bound)比较有利，因为该进程充分利用时间片，而 I/O 密集型(I/O-bound)任务却不利(虽然进程大部分时间都在等待 I/O，它仍然会被分配到 CPU 时间片。这可能导致 CPU 资源的浪费)
  常用于分时系统及事务处理系统。

MQ

多级队列调度算法 (MQ,Multilevel Queue):就绪队列被分解为多个独立的队列，每个队列具有自己的调度算法。前台的就绪队列是交互性作业(Interactive Job)的进程，采用时间片轮转。后台的就绪队列是批处理作业(Batch Job)的进程，采用优先权或短作业优先算法。
调度方式有两种：① 优先调度前台，若前台无可运行进程，才调度后台 ② 分配占用 CPU 的时间比例，如：前台 80%，后台 20%

什么是交互性作业(Interactive Job)和批处理作业(Batch Job)？
Interact Job: 与用户交互的作业,在执行这类作业时，用户可以输入命令，系统立即响应并返回结果;例如 UNIX shell 的ls
Batch Job:批处理作业是在没有用户交互的情况下自动执行的一组命令或程序;些作业通常被组织成批次，一次性提交给系统，然后按照预定的顺序或优先级执行

MFQ

多级反馈队列调度算法(MFQ，Multilevel Feedback Queue):最通用的调度算法，多数 OS 都使用该方法或其变形，如 UNIX、Windows 等。它可以看作是更成熟的多级队列调度,其任务可以在队列之间移动,从而更细致的区分任务

ATTENTION

注意：MFQ 统一为抢占式
高优先级队列中有进程进入时，会抢占低优先级队列中进程的 CPU。被抢占的进程不降级，回到原级队列中，下次仍然执行该级队列的时间片。

MFQ 调度算法

• 设置多个就绪队列,记作 RQ0，RQ1 … RQn，并为各个队列赋予不同的优先级队列。 第一个队列的优先级最高，第二个次之，其余各队列的优先级逐个降低。规定高优先级队列时间片小
• 一个新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统；进程一次时间片没执行完，就降至下一级队列，以此类推，降至最低优先级队列后，一直在此队列中不再下降。
• 系统优先调度高优先级队列中的进程，仅当 RQ0 空闲时才调度 RQ1 队列进程，以此类推

隋唐小练

MFQ 性能

• 对于终端型作业用户，其所提交的作业大都属于较小的交互型作业，系统只要使这些作业在箫 1 队列规定的时间片内完成，终端型作业用户就会感到满足。
• 对于短批处理作业用户，如果其作业在第 1 队列中执行一个时间片即可完成，便可获得与终端作业一样的响应时间。对于稍长批处理作业用户，其作业通常只须在第 2 队列和第 3 队列各执行 1 个时间片即可完成，周转时间仍然较短。
• 对于长批处理作业用户，其将依次在第 1,2…n 个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。因此，多级反馈队列调度算法能满足多用户需求。

基于公平原则的调度算法

1. 保证调度算法
   保证的是绝对运行时间，即启动后在某个时间段内必须获得多少运行时间。
   例如 N 个进程平均分配时间。

2. 公平分享调度算法
   按照用户数量平均分配时间，而不是进程间平均分配。

例：公平分享调度算法
用户 1 有 4 个进程 ABCD
用户 2 有 1 个进程 E

1. 时间片轮转法:ABCDEABCDEABCDEABCDE……
2. 所有用户获得相同的处理机时间:AEBECEDEAEBECEDEAEBECEDE……
3. 用户 1 获得的处理机时间是用户 2 的两倍:ABECDEABECDEABECDEABECDE……

实时调度

基础概念

实时任务：任务的结束时间有严格约束(Deadline),即任务执行必须在 Deadline 之前完成;具有紧迫性。
前述算法不能很好地满足实时系统对调度的特殊要求，所以引入实时调度。
实时操作系统 RTOS Real-Time Operating System 对外部输入的信息，实时操作系统能够在规定的时间内处理完毕并做出反应正确性:不仅要求计算逻辑的正确，而且要求在规定的时间内得到该结果通常给定一个开始时间或者结束时间的最后期限;多用于工业、军事等控制领域或实时信息处理方面
硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标
软实时系统的时限是柔性灵活的，它可以容忍偶然的超时错误。失败后造成的后果并不严重，例如在网络中仅仅轻微地降低了系统的吞吐量
硬实时 HRT 与软实时 SRT之间最关键的差别在于：软实时只能提供统计意义上的实时。例如，有的应用要求系统在 95%的情况下都会确保在规定的时间内完成某个动作，而不一定要求 100%
优先级倒置: 即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。

实现实时调度的基本条件

1. 提供必要的调度信息

• 任务的到达时间,开始截止时间,执行时间,完成截止时间
• 资源要求
• 优先级(若错过开始截止时间则赋予“绝对”优先级)

2. 系统处理能力强
   若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。
   假定系统中有 m 个周期性的硬实时任务，它们的处理时间可表示为 Ci ，周期时间表示为 Pi，则在单处理机情况下，必须满足$\sum_{i=1}^{m} \frac{C_i}{P_i} \leq 1$;若为多处理机系统,假设有 n 个处理机，则需满足$\sum_{i=1}^{m} \frac{C_i}{P_i} \leq n$
3. 采用抢占式调度机制:调度程序先调度开始截止时间即将到达的任务。
4. 具有快速切换机制

• 具有快速响应外部中断的能力:及时响应紧迫的外部事件的中断请求
• 快速的任务分派能力:使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

实时调度算法分类

非抢占式调度算法

1. 非抢占式轮转调度算法（如工业生产群控系统）
   调度程序每次选择队列中的第一个任务投入运行。该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行，而调度程序再选择下一个(队首)任务运行。
   常用于要求不太严格的实时控制系统。
2. 非抢占优先权调度算法
   如果在实时系统中存在着要求较为严格(响应时间为数百毫秒)的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。常用于有一定要求的实时控制系统。

抢占式调度算法

1. 基于时钟中断的抢占式优先权调度算法
2. 立即抢占(Immediate Preemption)的优先权调度算法

常见的实时调度算法

最早截止时间优先即 EDF(Earliest Deadline First) 算法

优先级确定：根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。
实时任务就绪队列：按各任务截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。
调度顺序：总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。
适用范围：既可用于抢占式调度，也可用于非抢占式调度方式中。

最低松弛度优先即 LLF(Least Laxity First)算法

$Laxity = Deadline - RemainingServiceTime - CurrentTime$
松弛度=完成截止时间–剩余运行时间–当前时间 (假设从现在执行任务, 完成的时间为 t1, 则松弛度为截止时间-t1)

该算法按松弛度排序实时任务的就绪队列，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。
该算法主要用于可抢占调度方式中。

抢占方式和时机

• 当等待任务的松弛度值为 0 时才进行抢占
• 当有任务执行时，只有等待任务的松弛度值为 0 才会发生任务的调度，其他情况不发生调度。
• 任务执行结束后或无任务执行时，再比较等待任务的松弛度值，较小的先执行。