3.0 本章概念

• 作业：作业是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合（不仅仅是程序的执行，还有程序的编译等等）。
• 作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还配有一份作业说明书，系统根据作业说明书对程序运行进行控制。在批处理系统中，以作业为单位从外存调入内存（或者说进程调度只是作业调度的内核部分。用户提交的应该是作业。系统将作业处理成进程之后在内核中进行调度）

• 作业步：把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为作业步。作业步相互独立又互相关联。如下图：

• 作业控制块：作业提交给系统进入后备状态后，系统将为每个作业建立一个作业控制块JCB。JCB在作业的整个运行过程中始终存在，并且其内容与作业的状态同步地动态变化。只有当作业完成并退出系统时，JCB才被撤消。可以说，JCB是一个作业在系统中存在的唯一标志，系统根据JCB才感知到作业的存在（相当于是作业的“PCB”）。作业控制块的内容如下：

• 多道程序度：即允许多少个作业同时在内存中运行。

• 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。（完成-到达）

• 平均周转时间：实际上就是若干个进程的周转时间平均值

• 带权周转时间：作业的周转时间T与系统为它提供服务的时间TS（也就是进程完成所需的时间）之比：T/TS

• 平均带权周转时间：若干个进程的带权周转时间的平均值

• 响应时间：是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间（常用于评价分时系统，因为分时系统要求交互性，用户希望系统快点响应）

• 截止时间：是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。（也叫做时限，即deadline）

• 吞吐量：是指在单位时间内系统所完成的作业数

• 响应比：（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间（注意这里的等待时间应该是指当等待的时间，一旦被调度了就要重置；要求服务时间应该是指剩余的服务时间）

• CPU利用率：

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

• 死锁的概念：指多个进程因竞争资源或相互通信而造成的一种僵局，都在等待着对方释放出自己所需的资源，但同时又不释放出自己已经占有的资源，若无外力作用，这些进程都将永远无法向前推进。

3.1 处理机调度的层次

3.1.1 高级调度

• 高级调度被称为作业调度、长程调度或接纳调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存。批处理系统需要有作业调度（因为需要从外存上调作业，所以主要用于批处理系统），分时和实时系统无需此调度（疑问：为什么不需要？所有的作业都在内存里吗）。
• 在每次执行作业调度时，都须做出以下两个决定
• 接纳多少个作业（取决于多道程序度，适当折衷）：作业太多 服务质量下降；作业太少 资源利用率低
• 接纳哪些作业 （取决于采用的调度算法）
• 设计目的：最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行（充分利用资源并且提高并发度）

3.1.2 低级调度

• 低级调度：低级调度又称为进程调度或短程调度，它所调度的对象是进程。三种类型OS都必须配置这级调度。（最基本调度）

• 低级调度的作用（因为对象是进程，所以很自然的就是决定调度哪个进程）：低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派进程执行把处理机分配给该进程的具体操作。（分派进程执行的具体操作应该也是低级调度的一部分，不然下面的低级调度功能里面就不会说什么上下文保护啥的了）

• 低级调度（进程调度）的方式：
• 非抢占方式：进程占用处理机直至自愿放弃或发生某事件被阻塞时，在把处理机分配给其他进程。（主动释放）
• 非抢占方式的优点：算法简单，系统开销小
• 非抢占方式的缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束
• 抢占方式：允许暂停某个正在执行的进程，将处理机重新分配给另一个进程。（被动释放）
• 抢占方式的优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。
• 抢占方式的缺点：抢占方式比非抢占方式调度所需付出的开销较大，且调度算法复杂。
• 抢占方式的原则
• 时间片原则。适用于分时、大多数实时以及要求较高的批处理系统
• 优先权原则。重要紧急作业优先权高。
• 短作业(进程)优先原则

• 低级调度中的基本机制
• 排队器：为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。
• 分派器(调度程序，也就是分派进程)：分派器把由进程调度程序所选定的进程从就绪队列中取出，然后进行上下文切换，将处理机分配给它。
• 上下文切换机制：当对处理机进行切换时，会发生两对（保存现场+恢复现场）上下文切换操作。

• 低级调度的功能
• 按某种算法选取进程（调度）。
• 保存处理机的现场信息（上下文切换第一步骤。这个是由分派进程执行的）
• 把处理器分配给进程（上下文切换第二步骤，也就是恢复被调度进程的现场。这也是由分派进程执行的）

• 分派程序的主要功能
• 进程切换
• 转到用户态
• 开始执行被选中的进程

3.1.3 中级调度

• 中级调度：负责将挂起的进程重新调进内存。
• 主要目的：为了提高内存利用率和系统吞吐量
• 中级调度的具体实现：实际上只有激活是由中级调度完成的（调出操作是由父进程、用户、OS、系统负荷等决定的），但是还是认为在中级调度中存在内外存的交换
• 使那些暂时不能运行的进程不再占用宝贵的内存资源，由中级调度将其调至外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。
• 当被挂起的进程重新具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

3.1.4 处理器调度层次小结

• 终端型作业：低级。（终端中就是一个个进程了）

• 批量性作业：高级---低级。（也就是批处理系统）

• 现代较完善的os具有三级调度。
• 低级调度运行频率最高，不宜复杂。
• 高级调度发生在一批作业完成，重新调入一批作业到内存的时候，执行频率低（一下子调一坨作业。那多道批处理系统是不是只有当内存中所有的进程都处理结束了才会执行一次高级调度？应该是这样的，因为高级调度的频率很低，如果不是这样的话那他的运行频率应该是跟低级调度差不多的）
• 中级调度介于上述两者之间

• 三级调度的比较





需要注意的就是只有批处理系统才有高级调度就好了
 
 

3.2 调度队列模型和调度准则

3.2.1 队列调度模型

• 仅有进程调度（低级调度）的调度队列模型：常见于分时系统
• 分时系统中用户直接创建的就是进程,在分时系统中，通常仅设有进程调度。系统把这些进程组织成一个就绪队列

• 如下图：



• 每个进程在执行时有三种情况（实际上就是进程转换图中执行状态的三条出边——转换为终止状态、就绪状态、阻塞状态）(就绪队列时间片轮转，常采用FCFS(FIFO)算法， FCFS(FIFO)队列。进程执行时三种情况：完成、时间片到、阻塞)
• 任务在给定时间片内已完成，释放处理机后为完成状态；
• 任务在时间片内未完成，进入就绪队列末尾；
• 在执行期间因某事件而阻塞

• 具有高级和低级调度的调度队列模型：在批处理系统中，不仅需要进程调度，而且还要有作业调度
• 就绪队列形式：在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队列首进程（与上面的分时系统区分，分时系统只是简单的先来先服务）
• 设置多个阻塞队列：根据事件的不同设置多个队列提高效率
• 如下图：



模型的主要区别：具有高级调度，具有多个阻塞队列
因为每次都是把处理机分配给就绪队列队首进程，并且该进程应该是优先级最高的，所以这个时候就没必要进行抢占了，所以在批处理系统中是不抢占的。

• 同时具有三级调度的调度队列模型：在OS中引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。同样，阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪（实际上就是通过中级调度引入了挂起和激活）
• 如下图：



也就是加上了两个挂起队列：就绪挂起队列、阻塞挂起队列

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

• 调度的目标（利用率、吞吐量、响应时间、公平）
• 提高处理机的利用率
• 提高系统吞吐量
• 尽量减少进程的响应时间
• 防止进程长期得不到运行

• 系统选择调度方式和算法的准则分为两种
• 面向用户的准则（也就是要满足用户对时间和紧急程度的需求）
• 周转时间短（评价批处理系统）：也就是（完成-到达的时间）小
• 响应时间快（评价分时系统）：也就是系统产生（首次响应-到达时间）小
• 截止时间的保证（评价实时系统）：在（某个时间点之前进程一定要执行结束）
• 优先权准则：（适用于三个系统）：让某些紧急的作业能得到及时处理。往往还需选择抢占式调度方式，才能保证紧急作业得到及时处理（在批处理中就不用抢占，是因为他将进程插入就绪队列的时候是按照优先级排列的，处理器只需要取最前面的进程就好了）
• 面向系统的准则
• 系统吞吐量高（评价批处理系统）：吞吐量是指在单位时间内，系统所完成的作业数。与批处理作业的平均长度有关
• 处理机利用率高：主要对大、中型多用户系统，对单用户或实时系统不重要（实时系统只要实时就好了）。
• 各类资源的平衡利用（内存、外存、I/O设备等）：主要对大、中型系统，对微型机或实时系统不重要（实时系统只要够实时就好了）。

• 引发进程调度的因素
• 正在执行的进程执行完毕，或因发生某事件而不能再继续执行（包括：当前执行进程被中断、时间片用完了、挂起自己、退出等）；
• 执行中的进程因提出I／O请求而暂停执行；
• 在进程通信或同步过程中执行了某种原语操作，如P、V操作原语，Block原语， Wakeup原语等。

• 调度时机：进程从运行状态切换到等待状态/进程被终结了
• 非抢占系统：当前进程主动放弃CPU时
• 可抢占系统：中断请求被服务例程响应完成时。当前进程被抢占：进程时间片用完/进程从等待切换到就绪。

• 进程切换相关概念
• 进程切换：当一个进程占用处理机执行完（或不能继续执行），则换另一个进程占用处理机执行，称为进程切换。
• 进程调度：把处理机分配给不同的进程占用执行，称为进程调度。
• 调度程序：实现分配处理机的程序称为调度程序
• 进程的上下文：执行现场称为进程的上下文。

• 进程切换基本步骤
• 保存当前进程的上下文
• 修改当前进程状态
• 将当前进程移动到相应队列（就绪队列或阻塞队列）
• 修改新进程状态
• 恢复新进程的上下文

3.3 调度算法

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

• 先来先服务（FCFS）：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程

• 优点：
• 有利于长作业（进程）
• 有利于CPU繁忙型作业（进程）

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

• 适用场景：用于批处理系统，不适于分时系统；适合于作业调度和进程调度

• 例题

3.3.2 短作业（进程）优先调度算法(SJF,SPF)(SRT)

• 短作业(进程)优先调度算法（SJF、SPF）：以要求运行时间长短进行调度，即启动要求运行时间最短（服务时间最短）的作业或者进程（SJF/SPF通常是不抢占的）
• 优点
• 能有效降低作业/进程的平均等待时间
• 提高系统的吞吐量
• 缺点
• 该算法对长作业不利，更严重的是可能将导致长作业(进程)长期不被调度。
• 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
• 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
• 无法实现人机交互
• 适用场景：适合于作业调度和进程调度

• 例题



注意：最先执行的是A，因为A到达的时刻为0，此时CPU是空闲状态。满足空闲让进原则。当A执行完的时候，所有的进程都到达了，在等待队列里面。此时SJF算法开始执行

• 最短剩余时间优先调度算法（SRT）：调度时选择预期剩余时间最短的进程（通常是可抢占的）
• 缺点：存在长进程被饿死的危险





抢占式SRT算法的核心是：总是选择剩余服务时间最短的进程执行。P1（服务时间7），到达时间0，立即执行。时间1被P2抢占（剩余时间6 vs. P2的5）。时间2 P2被P3抢占（P2剩余时间4>3）时间3时P4到达，P3和P4剩余时间都为2，而P3先到达，所以先执行P3。再执行P4。时间7，P2和P4的剩余时间都为4，但由于P2先到达，所以先执行P2。时间11执行P5(P5剩余时间为4，P1剩余时间为6)，然后时间15执行P1。
注意画出这样的SRT时间轴图

3.3.3 优先权调度算法（PSA）

• 非抢占式优先权算法（用于批处理、要求不严的实时）
• 系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。

• 抢占式优先权调度算法（用于要求严格的实时、性能要求较高的批处理和分时）
• 系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求。（只要出现一个新的就绪进程，就进行优先级比较）

• 优先权的类型
• 静态优先权：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变
• 静态优先权确定的依据
• 进程类型：系统进程高，一般用户进程低。
• 进程对资源的需求：进程的估计执行时间、内存需求量等。要求少的进程赋予较高的优先权
• 用户要求：紧迫程度、所付费用。
• 静态优先权的优点与缺点
• 优点：简单易行、系统开销小。
• 缺点：不够精确，可能出现优先权低的作业或进程长期得不到调度的情况。



注意：在这里的是优先数(整数)越大，优先权越高，越先执行。
• 动态优先权：随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能可规定，在就绪队列中的进程，随其等待时间的增长，其优先权以某一速率提高。
• 具有相同优先权初值的进程进入就绪队列，FCFS算法
• 具有各不相同的优先权初值的就绪进程，则优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机
• 当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以某一速率下降，则可防止一个长作业长期地垄断处理机。
Q:在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。有没有什么办法既考虑到短作业，又能够估计长作业呢？
A:如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。

• 从上面几种情况就可以排列组合出四种调度算法：抢占/非抢占的静态/动态优先级算法。

• 动态优先权算法——高响应比优先调度算法（HRRN）（Highest Response Ratio Next）
• 响应比优先级的计算
• 响应时间：是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
• HRRN调度算法的优缺点：HRRN是介于FCFS和SJ(P)F之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJ(P)F法，从而采用HRRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。



• 时间0，A到达后立即执行，完成于时间3。时间3，B开始执行，完成于时间9。时间9时就绪队列一种有CDE三个进程（由到达时间可以判断），计算相应比。等待时间=当前时间-到达时间，响应时间=等待时间+服务时间=当前时间-到达时间+服务时间，响应比R=响应时间/服务时间。当前时间为9。HRRN高响应比优先响应。执行C。完成时间13。再次计算响应比，当前时间为13。然后执行E。
• 抢占式见练习十四。
• 小结HRRN:等待时间相同的作业，则要求服务的时间愈短，其优先权愈高（对短作业有利）；要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，（先来先服务）长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机（对长作业有利）是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。缺点：要进行响应比计算，增加了系统开销。

3.3.4 基于时间片的轮转调度算法（RR）

• 基于时间片的轮转调度算法（RR）：系统将所有就绪进程按先来先服务原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，调度程序便停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
• 时间片大小的确定：时间片太大则退化为FCFS算法；时间片过小切换开销大
• 系统对响应时间的要求。（用户数一定时，成正比）
• 就绪队列中的进程数目。（保证响应时间，成反比）
• 系统的处理能力。（保证用户键入的命令能在一个时间片内处理完毕）
• 时间片轮转调度法优缺点：
• 时间片的大小对计算机性能的影响。
• 存在的问题：未有效利用系统资源（对于短的、计算型进程比较有利，因为该进程充分利用时间片，而I/O型进程却不利，因为在两次I/O之间仅需很少的CPU时间，却需要等待一个时间片）
• 适用场景：适合于进程调度，分时操作系统

3.3.5 混合多种调度算法 - 多级队列调度

• 混合多种调度算法 - 多级队列调度：多个就绪队列，不同的队列采用不同的调度方法
• 前台的就绪队列是交互性作业的进程，采用时间片轮转。
• 后台的就绪队列是批处理作业的进程，采用优先权或短作业优先算法。
• 调度方式有两种
• 优先调度前台，若前台无可运行进程，才调度后台。
• 分配占用CPU的时间比例，如：前台80%，后台20%

• 多级反馈队列（通常为抢占式。高优先级队列中有进程进入时，会抢占低优先级队列中进程的CPU。被抢占的进程不降级，回到原级队列的队尾，下次仍然执行该级队列的时间片。）
• 算法描述
• 按优先级由高到低设置多个队列 RQ0，RQ1 … RQn，高优先级队列时间片小。
• 一个刚进入系统的进程按FCFS放入最高的RQ0中。
• 当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。进程一次时间片没执行完，就降至下一级队列，以此类推，降至最低优先级队列后，一直在此队列中不再下降。在第n队列中便采取按时间片轮转方式运行。
• 系统优先调度高优先级队列中的进程，仅当RQ0空闲时才调度RQ1队列进程，以此类推。仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行。
• 如下图：
• 多级反馈队列调度算法的性能
• 终端型作业用户：交互型作业，通常较小，第一队列一个时间片即可完成
• 短批处理作业用户：第一队列一个时间片即可完成，或第一队列、第二队列各一个时间片
• 长批处理作业用户：可能到第N个队列，按时间片轮转，不必担心得不到处理

3.3.6 基于公平原则的调度算法

• 基于公平原则的调度算法
• 保证调度算法：保证的是绝对运行时间，即启动后在某个时间段内必须获得多少运行时间。例如N个进程平均分配时间。
• 公平分享调度算法：按照用户数量平均分配时间，而不是进程间平均分配

• 如下图：

3.4 实时调度

• 实时任务：任务的结束时间有严格约束(Deadline) ，即任务执行必须在Deadline之前完成。即实时任务具有紧迫性。

• 实时操作系统(RTOS)
• 对外部输入的信息，实时操作系统能够在规定的时间内处理完毕并做出反应
• 正确性：不仅依靠计算逻辑的正确，而且要求在规定的时间内得到该结果
• 通常给定一个开始时间或者结束时间的最后期限
• 多用于工业、军事等控制领域或实时信息处理方面
• 例子：嵌入式操作系统的实时性都比较强，可归为RTOS。VxWork/uCOS/嵌入式Linux操作系统(uClinux)/Windows CE

• 硬实时与软实时
• 硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标。
• 软实时系统的时限是柔性灵活的，它可以容忍偶然的超时错误。失败后造成的后果并不严重，例如在网络中仅仅轻微地降低了系统的吞吐量。
• 硬实时HRT与软实时SRT之间最关键的差别在于：软实时只能提供统计意义上的实时。例如，有的应用要求系统在95%的情况下都会确保在规定的时间内完成某个动作，而不一定要求100%

3.4.1 实现实时调度的基本条件

• 提供必要的调度信息
• 就绪时间。（该任务成为就绪状态的起始时间）
• 开始截止时间和完成截止时间。
• 处理时间。（任务开始执行到完成所需时间）
• 资源要求
• 优先级。(若错过开始截止时间则赋予“绝对”优先级)

• 系统处理能力强：若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。



上图中的周期时间是指任务执行的周期。
eg：假如系统中有6个硬实时任务，它们的周期时间都是50ms，而每次的处理时间为10ms，6*10/50>1，此时系统是不可调度的。

• 采用抢占式调度机制：调度程序先调度开始截止时间即将到达的任务。

• 具有快速切换机制
• 具有快速响应外部中断的能力：及时响应紧迫的外部事件的中断请求，要求快速的硬件中断机构，尽量短的禁止中断的时间间隔。
• 快速的任务分派能力：应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

3.4.2 实时调度算法的分类(未看)

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

• 抢占式调度算法
• 基于时钟中断的抢占式优先权调度算法（即时钟中断来了再进行切换）
• 立即抢占(Immediate Preemption)的优先权调度算法

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

• 最低松弛度优先即LLF(Least Laxity First)算法
• 松弛度=完成截止时间–剩余运行时间–当前时间
• 该算法按松弛度排序实时任务的就绪队列，松弛度值最小的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。
• 该算法主要用于可抢占调度方式中。
• 抢占方式与时机：当等待任务的松弛度值为0时才进行抢占（与其他调度算法的抢占时机不同，其他的都是当前进程放弃CPU，或者就绪队列发生变化了才会进行调度并抢占）
• 当有任务执行时，只有等待任务的松弛度值为0才会发生任务的调度，其他情况不发生调度。
• 任务执行结束后或无任务执行时，再比较等待任务的松弛度值，较小的先执行。

• 优先级倒置：高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞

• 如下图：



其中优先级：P1>P2>P3
• 优先级倒置的解决方法
• 假如进程P3在进入临界区后P3所占用的处理机就不允许被抢占——仅适用于临界区较短情况
• 采用动态优先级继承方法——防范中间优先级进程插入（防止上图中的P2进程插入）

3.5 产生死锁的原因和必要条件

• 死锁的概念：指多个进程因竞争资源或相互通信而造成的一种僵局，都在等待着对方释放出自己所需的资源，但同时又不释放出自己已经占有的资源，若无外力作用，这些进程都将永远无法向前推进。

• 资源分配图

• 产生死锁的原因
• 竞争资源
• 竞争不可抢占性资源引起死锁
• 竞争临时性(消耗性)资源引起进行死锁（临时性资源，可以创造（生产）和撤消（消耗）的资源，也称之为消耗性资源。如信号量、消息、buffer中的数据等资源。）
• 进程间推进顺序不当

• 死锁（Deadlock）的定义:如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。（各组进程因为相互等待对方持有的资源，导致各个进程都阻塞而无法向前推进的现象）

• 饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先(SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”

• 死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

• 产生死锁的必要条件
• 互斥条件 ：进程对分配到的资源进行排它性使用。只有对必须互斥使用的资源的争抢才会导致死锁
• 请求和保持条件 ：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又被其他进程占有，请求进程阻塞，但对已经获得的资源不释放。
• 不剥夺条件 ：进程已获得的资源，使用完之前不能被剥夺，只能用完自己释放。
• 循环等待条件 ：发生死锁时，必然存在进程—资源的循环等待链。其中每个进程都在等待下一个进程持有的资源（但有环路不一定死锁！！）
• 如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
• 出现第六个哲学家，3，4无

• 解决死锁的基本方法
• 预防死锁：设置某些限制条件，破坏四个必要条件中的一个或几个。
• 避免死锁：在资源的动态分配过程用某种方法防止系统进入不安全状态。（银行家算法）
• 死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

3.6 预防死锁的方法

• 破坏互斥条件

• 破坏不剥夺条件
• 进程在需要资源时才提出请求，一个已经保持了某些资源的进程，再提出新的资源要求而不能立即得到满足时，必须释放已经保持的所有资源，待以后需要时再重新申请。

• 破坏请求和保持条件
• 请求和保持条件 ：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又被其他进程占有，请求进程阻塞，但对已经获得的资源不释放。
• 如果源源不断的A类和B类进程，就会导致C类进程一直处于饥饿状态。

• 破坏循环等待条件
• 循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
• 所有进程对资源的请求必须严格按资源序号递增的次序提出，按序号递减的次序释放。

• 总结

3.7 避免死锁的方法

3.7.1 安全状态

• 安全状态
• 是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

• 并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能有进入死锁状态。系统处于安全状态时，不会进入死锁状态。

3.7.2 银行家算法

• 可利用资源向量Available。
• 一维数组，长度为m（m种资源），第j位代表第j类资源（Rj），Available［j］=K，则表示系统中现有Rj类资源K个。
• 这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。

• 最大需求矩阵Max。
• 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示Pi需要Rj类资源的最大数目为K。

• 分配矩阵Allocation。
• 这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。

• 需求矩阵Need。
• 这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need［i,j］=Max［i,j］-Allocation［i,j］

• Requesti是进程Pi的资源请求向量
• 一维数组，长度为m，表示本次申请的各种资源量。
• 如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。

3.7.3 安全性算法

• 设置两个向量
• 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;
• Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］=false; 当有足够资源分配给进程时， 再令Finish［i］=true。

• 从进程集合中找到一个能满足下述条件的进程：
• Finish［i］=false;
• Need［i,j］≤Work［j］； 若找到， 执行步骤(3)， 否则，执行步骤(4)。

• 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
• Work［j］=Work［j］+Allocation［i,j］; Finish［i］=true; go to step 2;

• 如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

3.7.4 银行家算法举例

3.8 死锁的检测与解除

3.9 练习

• 练习一
• 问题&答案：分时系统中是否存在高级调度？——不存在

• 练习二
• 问题&答案（B）



注意交换只有中级调度有，高级调度那个只能叫做移动，将作业从外存移动到内存

• 练习三
• 问题&答案：

• 练习四
• 问题&答案

• 练习五
• 问题&答案

• 练习六
• 问题&答案

• 练习七
• 问题&答案

• 练习八
• 问题&答案

• 练习九
• 问题&答案

• 练习十
• 问题&答案

• 练习十一
• 问题&答案

• 练习十二
• 问题&答案

• 练习十三
• 问题&答案



SPF；非抢占。时间9时有三个进程CDE，根据SPF，先执行E，再执行C，在执行D。

• 练习十四
• 问题&答案



时间2，Ra=（2-0+3）/3=1.7，Rb=1，Ra=（0+3）/3=1（这里A正在执行所以没有等待。）（老师说默认执行后来的那个任务，所以先执行B），所以执行B。时间4时，Rb=Rc=1，Ra=（4-2+3）/3，所以先执行A，执行1，时间5时A结束。计算Rb=（1+6)/6=1.1,Rc=(1+4)/4=1.25,所以先执行C。时间6时，Rd=1，Rc=1，Rb=（6-4+6）/6，所以执行B，执行到8时，E来,Re=1，Rb=1，Rc=（2+4）/4=1.5，Rd=（2+5）/5=1.4，执行C剩下的3时间到11，完成C任务.11时，Rb=（11-4+6）/6=2.2,Rd=（11-6+5）/5=2，Re=（11-8+2）/2=2.5，所以执行E，执行2到13完成E任务.时间13判断，Rb=（13-8+6）/6=1.8，Rd=（13-6+5）/5=2.4.所以执行B（发生错误，所以服务时间应该算剩余服务时间，等待时间是当前时刻-上一次该进程执行结束的时刻），执行2个时间到15，B任务结束，然后再进行D任务，执行5个时间到20，D任务结束。

• 练习十五
• 问题&答案



在时间4时，就绪队列里面有BCDE。Rb=（4-1+3）/3=2，Rc=1.4，Rd=1.5，Re=1，进行B。时间7，Rc=（7-2+5）/5=2；Rd=（7-3+2）/2=3；Re=（7-4+4）/4=1.75，执行D。时间9，Rc=（9-2+5）/5=2.4，Re=（9-4+4）/4=2.25，执行C。最后执行D。

• 练习十六
• 问题&答案
时刻8.0，执行P1,执行0.6时，P2到达，此时R2=R1=1,根据规定后来先执行，所以先执行P2，执行0.2后P3到达，此时R2=R3=1,R1=(8.8-8.6+2)/2=1,1,再执行P1 0.2。时刻9，R1=R4=1,R2=(9-8.8+0.6)/0.6=1.3,R3=(9-8.8+0.2)/0.2=2,所以执行P3 0.2到9.2完成P3。在时刻9.2，R1=(9.2-9+2)/2=1.1,R2=(9.2-8.8+0.6)/0.6=1.7,R4=(9.2-9+0.5)/0.5=1.4,所以执行P2，执行0.4到9.6完成P2。9.6时，R1=(9.6-9+2)/2=1.3,R4=(9.6-9+0.5)/0.5=2.2,执行P40.5到10.1完成P4,然后再执行P1(2-0.6-0.2=1.2)到11.3.
注意：等待时间=当前时间-上一次执行结束的时间/如果没有上一次执行，则是到达时间

• 练习十七
• 问题（使用时间片轮转调度以下进程）
• 答案一



顺序一定是先加入队列，再进行时间片轮转（移动到末尾，上移，执行队首）
• 答案二



顺序一定是先加入队列，再进行时间片轮转（移动到末尾，上移，执行队首）。→便捷方式书写，时间2，B到达，A移动到末尾，加入B。

• 练习十八
• 问题&答案





注意：时间1时B到达，此时队列为AB。当执行完时间片1后，调度程序将A送到末尾，即队列顺序变为BA，在下一个时间片执行队首。时间2时C到达，队列顺序为BAC，发生时间片轮转后，顺序变为ACB。（书写时可以简便写即上一个时间片的队首一定在末尾，剩下的依次上前一位，多出来的空给新加入的进程eg：时间3D到达，CB_A,即CBDA;时间4E到达，BDAEC……）

• 练习十九
• 问题
• 答案



进程一次时间片没执行完，就降至下一级队列。为什么时间5~6时，CB→BC

• 练习二十
• 问题
• 答案

• 练习二十一
• 问题
• 答案

• 练习二十二
• 问题&答案

• 练习二十三
• 问题
• 答案