第四章调度
4.1 调度的概念、层次
处理机调度（Processor Scheduling）是操作系统中的一个重要概念，它涉及到如何合理地分配CPU时间给各个进程，以提高系统资源利用率和系统吞吐量，同时确保进程的公平性和响应时间。处理机调度可以分为三个层次：高级调度（作业调度）、中级调度（内存调度）和低级调度（进程调度）。下面分别介绍这三个层次的基本概念以及它们之间的联系和对比。
1.高级调度（作业调度）
基本概念： 作业调度是最高级别的调度，它发生在批处理系统中。作业调度的主要任务是决定哪些作业应该被加载到内存中，以便转换成进程进行执行。作业调度通常在作业进入系统时进行，并且只在作业之间进行。
主要功能：
决定作业的执行顺序。
从外存调入内存。
作业的资源分配。
2.中级调度（内存调度）
基本概念： 中级调度，也称为内存调度，主要发生在具有虚拟内存的系统中。中级调度负责决定哪些进程应该被调入或调出内存，以便为其他进程腾出空间。
主要功能：
管理内存中的进程数量。
通过挂起和唤醒进程来动态调整内存中的进程数量。
配合虚拟内存管理，提高内存利用率。
3.低级调度（进程调度）
基本概念： 低级调度，也称为进程调度，是最频繁发生的调度。它负责决定哪个就绪状态下的进程应该获得CPU并执行。
主要功能：
决定进程的执行顺序。
进程的上下文切换。
进程的创建和终止。
4.三层调度的联系
层次性： 高级调度、中级调度和低级调度构成了操作系统调度的层次结构，每个层次解决不同的问题，并且相互配合以提高系统效率。
资源共享： 三个层次的调度共同管理CPU、内存等资源，确保资源的合理分配和有效利用。
调度策略： 各层次调度策略的选择和实施需要相互协调，以确保整个系统的调度策略一致性和有效性。
5.三层调度的对比
调度频率： 低级调度最频繁，中级调度次之，高级调度频率最低。
调度范围： 高级调度涉及作业，中级调度涉及进程，低级调度涉及进程的具体执行。
调度目的： 高级调度主要为了提高作业吞吐量，中级调度为了提高内存利用率，低级调度为了提高CPU利用率。
调度开销： 高级调度和中级调度的开销相对较大，因为它们涉及到作业或进程的调入调出，而低级调度开销较小，主要涉及上下文切换。
调度时间： 高级调度和中级调度的决策时间较长，因为它们需要更多的信息来做出决策，而低级调度的决策时间较短。
通过这三个层次的调度，操作系统能够更有效地管理资源，提高系统性能，满足不同用户和应用的需求。
6.进程的挂起状态
进程的挂起状态是指进程暂时被调到外存等待的状态，这种状态可以进一步细分为就绪挂起和阻塞挂起两种状态。挂起状态的引入，使得传统的五状态模型扩展为七状态模型，更细致地描述了进程在操作系统中的各种状态和转换。
7.进程的七状态模型
在七状态模型中，除了传统的五种状态（新建态、就绪态、运行态、阻塞态、终止态）之外，还包括了两种挂起状态：
挂起就绪态（Ready Suspend）：进程具备运行条件，但目前在外存中，只有当它被对换到内存时才能被调度执行。
挂起等待态（挂起阻塞态）（Blocked Suspend）：进程正在等待某个事件发生且在外存中。
8.引起进程状态转换的具体原因
等待态→挂起等待态：如果当前不存在就绪进程，那么至少有一个等待态进程将被对换出去成为挂起等待态。
挂起等待态→挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态。
挂起就绪态→就绪态：当内存中没有就绪态进程，或者挂起就绪态进程具有比就绪态进程更高的优先级，系统将把挂起就绪态进程转换成就绪态。
就绪态→挂起就绪态：操作系统根据当前资源状况和性能要求，也可以决定把就绪态进程对换出去成为挂起就绪态。
挂起等待态→等待态：当一个进程退出后，主存已经有了一大块自由空间，而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化。
挂起状态的引入主要是为了优化系统资源的利用，特别是内存资源。当内存资源不足时，可以将一些暂时不需要执行的进程挂起，释放内存空间给其他进程使用。当这些进程需要继续执行时，再将它们从外存调回内存，并恢复到相应的状态。
4.2 进程调度的时机，进程的切换和过程，方式
进程调度是操作系统中用于决定哪个进程获得CPU时间的过程。以下是关于进程调度的时机、进程的切换和过程以及调度方式的详细说明：
1.进程调度的时机
进程执行完毕：当一个进程执行完毕或因错误而结束时，需要调度其他进程运行。
进程请求等待：进程可能需要等待I/O操作或同步事件，这时会放弃CPU，调度其他进程。
进程优先级改变：当进程的优先级改变时，可能会触发调度。
时间片用尽：在时间片轮转调度算法中，进程使用完其分配的时间片后，将CPU让给其他进程。
I/O中断：硬件I/O操作完成时，可能会触发调度器选择新进程运行。
系统调用：进程执行系统调用后可能会离开CPU，调度器将选择其他进程运行。
2.进程的切换和过程
进程切换（上下文切换）涉及保存当前进程的状态（上下文），并加载下一个要执行进程的状态。这个过程通常包括以下步骤：
保存当前进程的上下文：这包括寄存器值、程序计数器、状态寄存器等。
更新进程控制块（PCB）：将当前进程的状态信息更新到其PCB中。
选择下一个进程：根据调度算法选择下一个要运行的进程。
加载下一个进程的上下文：将所选进程的上下文从其PCB加载到寄存器中。
跳转到新进程的代码：更新程序计数器，开始执行新进程的指令。
3.进程调度的方式
非抢占式调度：也称为协作式调度，当前进程必须主动放弃CPU，如执行完毕或等待I/O。
先来先服务（FCFS）：按照请求CPU的顺序调度进程。
短作业优先（SJF）：优先调度预计运行时间最短的进程。
抢占式调度：调度器可以强制暂停当前进程，将CPU分配给更高优先级的进程。
优先级调度：每个进程都有一个优先级，调度器根据优先级来分配CPU。
时间片轮转（Round Robin, RR）：每个进程分配一个时间片，轮流执行。
多级反馈队列（Multilevel Feedback Queue, MFQ）：结合了优先级和时间片轮转，具有多个队列，根据进程的行为动态调整优先级。
操作系统的进程调度策略是多样化的，不同的调度算法适用于不同的场景和需求。调度策略的选择直接影响到系统的性能，包括响应时间、吞吐量和CPU利用率。在设计调度策略时，还需要考虑公平性、系统的稳定性和实现的复杂性。
4.3 调度器和闲逛进程
1.调度器
调度器的主要职责是确保CPU始终在执行有用的任务，并尽可能地提高系统的整体性能。调度器的工作可以细分为以下几个部分：
选择策略：调度器根据预定的策略来选择下一个要运行的进程。这些策略可能包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度、时间片轮转（RR）或多级反馈队列（MFQ）等。
上下文切换：当调度器决定运行另一个进程时，它会执行上下文切换，保存当前进程的状态并加载新进程的状态。
资源分配：调度器不仅要分配CPU时间，还可能涉及内存、I/O设备等其他资源的分配。
性能优化：调度器尝试最大化系统的吞吐量、响应时间、CPU利用率和公平性。
2.闲逛进程
闲逛进程（Idle Process）是一个特殊的系统进程，其行为如下：
低优先级：闲逛进程通常具有最低的优先级，这样在系统中存在其他可运行的进程时，它们会优先获得CPU时间。
系统空闲时运行：当没有其他进程需要CPU资源时，调度器将选择闲逛进程运行。这保证了CPU不会无所事事，同时也提供了一个默认的执行路径。
节能模式：在闲逛进程运行期间，CPU可能会进入一种节能模式，降低功耗，因为此时没有用户进程需要处理。
执行指令：闲逛进程通常执行一些简单的循环指令或者直接进入休眠状态，这些操作几乎不消耗系统资源。
触发调度：当新的进程变为可运行状态时，闲逛进程会被抢占，新的进程将获得CPU时间。
闲逛进程的存在对于操作系统来说是非常重要的，因为它确保了CPU不会执行无意义的操作，并且在系统空闲时，调度器可以随时响应新的任务。在多核系统中，每个CPU核心可能都有自己的闲逛进程。
总结来说，调度器和闲逛进程都是操作系统中的重要组件，它们共同确保了系统的稳定运行和资源的高效利用。
4.4 调度算法的性能评价
下面是对调度算法性能指标的详细解释，包括CPU利用率、系统吞吐量、周转时间（及其变体）、等待时间和响应时间的定义和计算方法。
1.CPU利用率
定义：CPU利用率是指CPU在一段时间内执行进程的时间占总时间的比例。
计算：CPU利用率 = (CPU执行时间 / 总时间) * 100%
2.系统吞吐量
定义：系统吞吐量是指在单位时间内系统完成的进程数量。
计算：系统吞吐量 = 完成的进程数 / 总时间
3.周转时间
周转时间：
定义：从进程到达系统到进程完成所经过的时间。
计算：周转时间 = 完成时间 - 到达时间
平均周转时间：
定义：所有进程的周转时间之和除以进程数量。
计算：平均周转时间 = (周转时间1 + 周转时间2 + … + 周转时间n) / 进程数
带权周转时间：
定义：周转时间与实际运行时间的比率，用于考虑进程的实际运行时间。
计算：带权周转时间 = 周转时间 / 运行时间
平均带权周转时间：
定义：所有进程的带权周转时间之和除以进程数量。
计算：平均带权周转时间 = (带权周转时间1 + 带权周转时间2 + … + 带权周转时间n) / 进程数
4.等待时间
定义：等待时间是指进程在就绪队列中等待执行的时间总和。
计算：等待时间 = 周转时间 - 运行时间
5.响应时间
定义：响应时间是指从提交请求到系统首次产生响应的时间。
计算：响应时间 = 首次响应时间 - 请求提交时间
在不同的调度算法中，这些指标的表现会有所不同：
先来先服务（FCFS）：
CPU利用率：通常较高
系统吞吐量：中等
周转时间：可能较长，取决于作业到达顺序
平均周转时间：取决于作业到达顺序
带权周转时间：可能较高，特别是对于短作业
平均带权周转时间：可能较高
等待时间：可能较长，存在“饥饿”现象
响应时间：取决于请求到达的顺序
短作业优先（SJF）：
CPU利用率：通常较高
系统吞吐量：较高
周转时间：较短
平均周转时间：较短
带权周转时间：较低
平均带权周转时间：较低
等待时间：较短
响应时间：可能较长，特别是对于长作业
优先级调度：
CPU利用率：通常较高
系统吞吐量：取决于优先级分配
周转时间：取决于优先级
平均周转时间：取决于优先级
带权周转时间：取决于优先级
平均带权周转时间：取决于优先级
等待时间：可能较长，低优先级作业可能长时间等待
响应时间：取决于优先级
时间片轮转（RR）：
CPU利用率：通常较高
系统吞吐量：较高
周转时间：中等
平均周转时间：中等
带权周转时间：中等
平均带权周转时间：中等
等待时间：较短
响应时间：较短，适合交互式系统
多级反馈队列（MFQ）：
CPU利用率：通常较高
系统吞吐量：较高
周转时间：中等
平均周转时间：中等
带权周转时间：较低
平均带权周转时间：较低
等待时间：较短
响应时间：较短，适合各种类型的作业
调度算法的选择应该基于系统的特定需求和目标，不同的应用场景可能需要不同的性能权衡。
4.5 调度算法（1）
1.先来先服务（FCFS）
基本原理：按照作业到达的顺序进行调度，先到的作业先执行。
特点：
简单易实现。
公平，因为每个作业都会按照到达顺序得到服务。
性能分析：
CPU利用率：较高，尤其是在作业连续到达时。
系统吞吐量：中等，因为可能会因为长作业阻塞短作业。
周转时间：可能较长，特别是如果长作业先到达。
平均周转时间：取决于作业到达的顺序和作业长度。
等待时间：可能较长，特别是短作业跟随长作业时。
响应时间：与作业到达顺序一致。
缺点：存在“饥饿”现象，即短作业可能需要等待很长时间才能执行（称为“凸现”问题）。
2.短作业优先（SJF）
基本原理：优先调度预计运行时间最短的作业。
特点：
需要知道作业的运行时间。
可以是非抢占式的，也可以是抢占式的（称为SJF抢占式调度）。
性能分析：
CPU利用率：较高，因为减少了作业等待时间。
系统吞吐量：较高，因为可以快速完成多个短作业。
周转时间：较短，特别是对于短作业。
平均周转时间：较短，因为优先执行短作业。
等待时间：较短，因为作业通常不需要等待很久。
响应时间：对于抢占式SJF，响应时间较短。
缺点：可能导致长作业饥饿，即如果不断有新的短作业到达，长作业可能永远无法执行。
3.高响应比优先（HRRN）
基本原理：根据响应比来调度作业，响应比 = (等待时间 + 运行时间) / 运行时间。
特点：
结合了FCFS和SJF的优点，考虑了作业的等待时间。
随着等待时间的增加，作业的优先级提高。
性能分析：
CPU利用率：较高，因为作业的响应比随着等待时间增加而提高。
系统吞吐量：较高，因为能够平衡作业的等待和执行。
周转时间：中等，因为长作业最终会获得较高的优先级。
平均周转时间：中等，因为综合考虑了等待时间和运行时间。
等待时间：中等，因为等待时间长的作业最终会得到执行。
响应时间：中等，因为作业的响应比会随着等待时间增加而提高。
缺点：计算响应比需要额外的开销，可能不适合实时系统。
每种调度算法都有其适用的场景。FCFS适合作业长度相差不大的情况，SJF适合作业长度差异大且能够预知作业长度的情况，而HRRN适合需要平衡作业等待时间和执行时间的情况。在选择调度算法时，应根据具体的应用需求和系统特性来决定。
4.6 调度算法（2）
1.时间片轮转（Round Robin, RR）
基本原理：每个进程被分配一个固定的时间片（quantum），CPU按照顺序轮流执行进程，如果一个进程在其时间片内没有执行完，它将被挂起，放回就绪队列的末尾，然后CPU选择下一个进程执行。
特点：
公平性较高，因为每个进程都有机会在短时间内执行。
适用于分时系统，可以保证交互式任务的响应时间。
性能分析：
CPU利用率：较高，因为减少了进程切换的开销。
系统吞吐量：较高，特别是在进程数量较多时。
周转时间：取决于时间片的大小和进程数量。
平均周转时间：中等，因为所有进程都有机会被快速执行。
等待时间：中等，取决于时间片和进程数量。
响应时间：较短，适用于交互式系统。
缺点：时间片的大小对性能有显著影响，太小会导致频繁的进程切换，太大则可能降低响应时间。
2.优先级调度（Priority Scheduling）
基本原理：每个进程被赋予一个优先级，CPU按照优先级高的进程先执行。如果优先级相同，可以采用FCFS策略。
特点：
可以是抢占式的，也可以是非抢占式的。
适用于需要区分任务重要性的系统。
性能分析：
CPU利用率：较高，特别是抢占式优先级调度。
系统吞吐量：取决于进程优先级分配。
周转时间：可能较长，低优先级进程可能长时间得不到执行。
平均周转时间：取决于优先级分配。
等待时间：可能较长，特别是对于低优先级进程。
响应时间：对于高优先级进程较短。
缺点：可能导致低优先级进程饥饿，即如果高优先级进程不断到来，低优先级进程可能永远无法执行。
3.多级反馈队列（Multilevel Feedback Queue, MFQ）
基本原理：系统设置多个就绪队列，每个队列有不同的优先级。进程可以在队列之间移动，通常是随着等待时间的增加而提高优先级。时间片的大小可以随着队列优先级的降低而增大。
特点：
结合了RR和优先级调度的优点。
根据进程的行为动态调整优先级。
性能分析：
CPU利用率：较高，因为可以动态调整进程优先级。
系统吞吐量：较高，因为能够平衡不同类型的进程需求。
周转时间：中等，因为可以动态调整优先级。
平均周转时间：中等，取决于进程的行为和系统设置。
等待时间：中等，因为等待时间长的进程会提高优先级。
响应时间：较短，特别是对于交互式任务。
缺点：算法复杂，需要维护多个队列和动态调整优先级，可能增加系统开销。
每种调度算法都有其适用的场景。时间片轮转适用于分时系统和交互式任务，优先级调度适用于需要区分任务重要性的系统，而多级反馈队列适用于需要动态调整进程优先级的复杂系统。在选择调度算法时，应根据系统的具体需求和特性来决定。
4.7 调度算法（3）
多级队列调度（Multilevel Queue Scheduling）是一种进程调度算法，它将就绪队列分为多个不同的队列，每个队列有不同的优先级。这种调度策略通常用于满足不同类型进程的需求，并且可以根据队列的特性来调整调度策略。以下是多级队列调度的详细说明：
1.基本原理
队列划分：系统根据进程的特性（如进程类型、优先级等）将它们分配到不同的队列中。通常，队列的数量和优先级是固定的。
优先级：每个队列被赋予一个优先级，较高优先级的队列中的进程会优先获得CPU时间。
调度策略：每个队列可以采用不同的调度算法。例如，高优先级队列可能采用抢占式优先级调度，而低优先级队列可能采用时间片轮转调度。
队列间迁移：进程可以在队列之间迁移。这通常基于某些条件，如进程等待时间过长、进程行为改变等。
2.特点
灵活性：可以为不同类型的进程设置不同的调度策略。
优先级：确保了某些关键进程能够得到及时处理。
隔离性：不同队列的进程相对独立，减少了相互干扰。
3.调度过程
CPU分配：CPU首先服务于最高优先级的队列，直到该队列为空或达到某种条件（如时间片用完）。
队列内部调度：每个队列内部可以采用不同的调度算法，如FCFS、RR或优先级调度。
队列间迁移：进程可能会因为某些条件（如执行时间过长、I/O密集型操作等）而被迁移到其他队列。
4.性能分析
CPU利用率：较高，尤其是当高优先级队列中的进程频繁被调度时。
系统吞吐量：取决于队列的设置和进程的特性。
周转时间：可能因队列设置而异，高优先级队列中的进程通常有更短的周转时间。
等待时间：不同队列的进程等待时间不同，高优先级队列的等待时间通常较短。
响应时间：对于交互式任务，如果它们被分配到高优先级队列，响应时间会较短。
5.缺点
复杂性：管理多个队列和调度策略增加了系统的复杂性。
饥饿问题：如果低优先级队列中的进程长时间得不到CPU时间，可能会发生饥饿现象。
静态队列：在某些实现中，队列的设置是静态的，不适应动态变化的系统需求。
6.应用场景
多级队列调度适用于需要区分不同类型进程的系统和环境，例如，实时系统、分时系统、混合负载系统等。
总之，多级队列调度是一种有效的进程调度策略，它通过将进程分配到不同的队列并赋予不同的优先级，来满足不同类型进程的需求，从而提高系统的整体性能。
Last updated