3.0 本章概念

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

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

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

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

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

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

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

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

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

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

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

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

• CPU利用率：

3.1 处理机调度的层次

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

• 低级调度：低级调度又称为进程调度或短程调度，它所调度的对象是进程。三种类型OS都必须配置这级调度。（最基本调度）
• 低级调度的作用（因为对象是进程，所以很自然的就是决定调度哪个进程）：低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派进程执行把处理机分配给该进程的具体操作。（分派进程执行的具体操作应该也是低级调度的一部分，不然下面的低级调度功能里面就不会说什么上下文保护啥的了）
• 低级调度（进程调度）的方式：
• 非抢占方式：进程占用处理机直至自愿放弃或发生某事件被阻塞时，在把处理机分配给其他进程。（主动释放）
• 非抢占方式的优点：算法简单，系统开销小
• 非抢占方式的缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束
• 抢占方式：允许暂停某个正在执行的进程，将处理机重新分配给另一个进程。（被动释放）
• 抢占方式的优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。
• 抢占方式的缺点：抢占方式比非抢占方式调度所需付出的开销较大，且调度算法复杂。
• 抢占方式的原则
• 时间片原则
• 优先权原则
• 短作业(进程)优先原则
• 低级调度中的基本机制
• 排队器：为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。
• 分派器(调度程序，也就是分派进程)：分派器把由进程调度程序所选定的进程从就绪队列中取出，然后进行上下文切换，将处理机分配给它。
• 上下文切换机制：当对处理机进行切换时，会发生两对（保存现场+恢复现场）上下文切换操作。
• 低级调度的功能
• 按某种算法选取进程（调度）。
• 保存处理机的现场信息（上下文切换第一步骤。这个是由分派进程执行的）
• 把处理器分配给进程（上下文切换第二步骤，也就是恢复被调度进程的现场。这也是由分派进程执行的）

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

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





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

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

• 队列调度模型
• 仅有进程调度（低级调度）的调度队列模型：常见于分时系统（分时系统中用户直接创建的就是进程）。
• 如下图：



• 每个进程在执行时有三种情况（实际上就是进程转换图中执行状态的三条出边——转换为终止状态、就绪状态、阻塞状态）
• 任务在给定时间片内已完成，释放处理机后为完成状态；
• 任务在时间片内未完成，进入就绪队列末尾；
• 在执行期间因某事件而阻塞
• 具有高级和低级调度的调度队列模型：在批处理系统中，不仅需要进程调度，而且还要有作业调度
• 就绪队列形式：在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队列首进程（与上面的分时系统区分，分时系统只是简单的先来先服务）
• 设置多个阻塞队列：根据事件的不同设置多个队列提高效率
• 如下图：



模型的主要区别：具有高级调度，具有多个阻塞队列
因为每次都是把处理机分配给就绪队列队首进程，并且该进程应该是优先级最高的，所以这个时候就没必要进行抢占了，所以在批处理系统中是不抢占的
• 同时具有三级调度的调度队列模型：在OS中引入中级调度后，进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。同样，阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪（实际上就是通过中级调度引入了挂起和激活）
• 如下图：



也就是加上了两个挂起队列

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

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

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

3.3 调度算法

• 先来先服务（FCFS）：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程
• 优点：
• 有利于长作业（进程）
• 有利于CPU繁忙型作业（进程）
• 缺点
• 不利于短作业（进程），特别是来的较晚的短作业（进程）。
• 不利于I/O繁忙型作业（进程）
• 适用场景：用于批处理系统，不适于分时系统；适合于作业调度和进程调度

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

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

• 优先权调度算法（PSA）
• 非抢占式优先权算法（用于批处理、要求不严的实时）：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程
• 抢占式优先权调度算法（用于要求严格的实时、性能要求较高的批处理和分时）：系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求。
• 优先权的类型
• 静态优先权：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变
• 静态优先权确定的依据
• 进程类型：系统进程高，一般用户进程低。
• 进程对资源的需求：进程的估计执行时间、内存需求量等。要求少的进程赋予较高的优先权
• 用户要求：紧迫程度、所付费用。
静态优先权的优点与缺点
• 优点：简单易行、系统开销小。
• 缺点：不够精确，可能出现优先权低的作业或进程长期得不到调度的情况。
• 动态优先权：随进程的推进或随其等待时间的增加而改变，以获得更好的调度性能可规定，在就绪队列中的进程，随其等待时间的增长，其优先权以某一速率提高
• 具有相同优先权初值的进程进入就绪队列，FCFS算法
• 具有各不相同的优先权初值的就绪进程，则优先权初值低的进程，在等待了足够的时间后，其优先权便可能升为最高，从而可以获得处理机
• 当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以某一速率下降，则可防止一个长作业长期地垄断处理机

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

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

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

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

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

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

• 如下图：

3.4 实时调度

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

• 实时操作系统
• 对外部输入的信息，实时操作系统能够在规定的时间内处理完毕并做出反应
• 正确性：不仅依靠计算逻辑的正确，而且要求在规定的时间内得到该结果
• 通常给定一个开始时间或者结束时间的最后期限
• 多用于工业、军事等控制领域或实时信息处理方面

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

• 实现实时调度的基本条件
• 提供必要的调度信息
• 就绪时间。（该任务成为就绪状态的起始时间）
• 开始截止时间和完成截止时间。
• 处理时间。（任务开始执行到完成所需时间）
• 资源要求
• 优先级。 若错过开始截止时间则赋予“绝对”优先级
• 系统处理能力强：若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。



上图中的周期时间是指任务执行的周期
• 采用抢占式调度机制：调度程序先调度开始截止时间即将到达的任务。
• 具有快速切换机制
• 具有快速响应外部中断的能力：及时响应紧迫的外部事件的中断请求，要求快速的硬件中断机构，尽量短的禁止中断的时间间隔。
• 快速的任务分派能力：应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

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

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

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

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

• 如下图：



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

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

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

• 产生死锁的原因
• 竞争资源
• 进程间推进顺序不当

3.6 预防死锁的方法

3.7 避免死锁的方法

3.8 死锁的检测与解除

3.9 练习

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

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



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

• 练习三
• 问题&答案：

• 练习四
• 问题&答案

• 练习五
• 问题&答案

• 练习六
• 问题&答案

• 练习七
• 问题&答案

• 练习八
• 问题&答案

• 练习九
• 问题&答案

• 练习十
• 问题&答案

• 练习十一
• 问题&答案

• 练习十二
• 问题&答案

• 练习十三
• 问题&答案

• 练习十四
• 问题&答案

• 练习十五
• 问题&答案

• 练习十六
• 问题&答案

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

• 练习十八
• 问题&答案

• 练习十九
• 问题
• 答案

• 练习二十
• 问题
• 答案

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

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

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