一文读懂CPU调度算法：计算机的“任务指挥官”

2025-10-11

在操作系统的庞大体系中，CPU 调度处于核心地位，它如同交响乐的指挥家，协调着各个进程对 CPU 资源的使用，确保系统高效、稳定地运行。在多任务环境下，计算机系统中往往存在多个进程同时竞争 CPU 资源，而 CPU 在同一时刻只能处理一个进程，这就需要 CPU 调度算法来决定各个进程的执行顺序和占用 CPU 的时间。

CPU 调度的优劣直接影响着系统的性能和用户体验。高效的调度算法可以提高 CPU 的利用率，减少进程的等待时间，提升系统的响应速度，让用户感觉计算机运行流畅；而不合理的调度算法则可能导致 CPU 资源浪费，进程长时间等待，系统响应迟缓，甚至出现卡顿现象。因此，深入理解 CPU 调度算法对于优化操作系统性能至关重要。

一、CPU调度算法简介

1.1抢占式与非抢占式调度

在 CPU 调度的领域中，抢占式调度和非抢占式调度是两种基本的调度方式，它们的区别在于当一个进程正在执行时，是否允许其他进程抢占 CPU 资源。

非抢占式调度就像是一场按顺序进行的接力赛，一旦一个进程获得了 CPU 资源，它就会一直运行下去，直到完成任务或者因为某些原因（如等待 I/O 操作）主动放弃 CPU。这种调度方式实现起来相对简单，系统开销较小，因为不需要频繁地进行进程切换。但它也存在明显的缺点，如果一个长进程长时间占用 CPU，那么其他短进程可能需要等待很长时间才能得到执行机会，这会导致系统的整体响应速度变慢，用户体验变差。早期的批处理系统常采用这种调度方式，比如在一些大型的数据处理任务中，因为任务的连续性要求较高，非抢占式调度可以保证任务不受干扰地完成。

而抢占式调度则如同一场激烈的竞争，即使一个进程正在运行，只要有更高优先级或者更紧急的进程出现，当前进程就可能被中断，CPU 资源会被分配给更需要的进程。这就像在一场比赛中，随时可能有更有实力的选手加入并抢占当前选手的赛道。这种调度方式能够更好地满足实时性要求较高的任务，比如在视频会议软件运行时，需要实时处理音频和视频数据，抢占式调度可以确保这些关键任务能够及时获得 CPU 资源，保证音视频的流畅传输。但它也带来了一些问题，频繁的进程切换会增加系统的开销，需要额外的时间和资源来保存和恢复进程的上下文信息。

现代操作系统大多采用抢占式调度策略，像 Windows、Linux 等通用操作系统，都通过抢占式调度来保证系统的响应速度和多任务处理能力，确保各个进程能够得到及时的处理，提升用户体验。不过，在一些特定的场景下，非抢占式调度仍然有其用武之地，比如在一些对实时性要求不高，但对系统稳定性和任务连续性要求较高的专用系统中，非抢占式调度可以发挥其优势。

1.2调度算法的评价指标

为了衡量 CPU 调度算法的优劣，我们需要借助一些评价指标，这些指标就像是衡量调度算法性能的尺子，从不同角度反映了算法的效果。

CPU 利用率：CPU 利用率是指 CPU “忙碌” 的时间占总时间的比例。在计算机系统中，CPU 是最关键的资源之一，提高 CPU 利用率意味着让 CPU 尽可能多地处于工作状态，减少空闲时间，从而充分发挥硬件的性能。比如，在一个服务器系统中，如果 CPU 利用率长期处于较低水平，就说明系统资源没有得到充分利用，可能存在优化的空间；而如果 CPU 利用率过高，接近 100%，则可能导致系统负载过重，出现卡顿甚至崩溃的情况。理想情况下，我们希望 CPU 利用率能够保持在一个合理的高水平，既能充分利用资源，又不会使系统过于繁忙。吞吐量：吞吐量表示单位时间内完成作业的数量。它反映了系统的处理能力，吞吐量越高，说明系统在单位时间内能够处理的任务越多，效率也就越高。以文件服务器为例，系统在单位时间内成功传输和处理的文件数量就是其吞吐量的体现。如果调度算法能够合理地安排进程执行，提高系统的吞吐量，就能让服务器在相同时间内为更多用户提供文件服务，提升系统的整体性能。周转时间：周转时间是从作业提交到作业完成所经过的时间，包括作业等待时间、在就绪队列中排队的时间、在处理机上运行的时间以及进行输入 / 输出操作所花时间的总和。对于用户来说，周转时间是他们最关心的指标之一，因为它直接反映了用户提交的任务需要等待多久才能完成。例如，在编译一个大型项目时，从点击编译按钮到编译完成的整个时间就是周转时间。周转时间越短，用户就能越快得到结果，满意度也就越高。对于操作系统来说，平均周转时间可以用来衡量系统对多个作业的处理效率，平均周转时间越短，说明系统整体的处理能力越强。等待时间：等待时间是指进程 / 作业处于等待处理机状态时间之和。调度算法主要影响的就是进程的等待时间，因为一个作业总共需要被 CPU 服务多久、被 I/O 设备服务多久一般是确定不变的，而合理的调度算法可以尽量减少进程在就绪队列中的等待时间。比如在多任务处理中，如果某个进程长时间处于等待状态，就会影响整个系统的效率和用户体验。平均等待时间是评价调度算法优劣的重要指标之一，平均等待时间越短，说明调度算法能够更有效地安排进程执行，减少进程的等待时间。响应时间：响应时间是指从用户提交请求到首次产生响应所用的时间，在交互式系统中，这是一个非常重要的指标。比如在使用浏览器浏览网页时，从点击链接到页面开始显示内容的时间就是响应时间。用户希望响应时间越短越好，这样可以感受到系统的快速响应，提高交互体验。响应时间的长短不仅取决于 CPU 调度算法，还与系统的其他因素（如 I/O 速度、网络延迟等）有关，但调度算法在其中起着关键作用，通过合理地调度进程，优先处理用户的交互请求，可以有效缩短响应时间。

这些评价指标相互关联又相互制约，在设计和选择 CPU 调度算法时，需要综合考虑这些指标，根据不同的应用场景和需求，找到一个平衡点，以实现系统性能的最优化。

二、经典调度算法剖析

2.1先来先服务（FCFS）

先来先服务（First-Come, First-Served，FCFS）调度算法是一种最简单的调度算法，正如其名，它遵循 “先到先服务” 的原则，按照进程到达就绪队列的先后顺序来分配 CPU 资源，就像人们排队买票，先到的人先买。

假设有三个进程 P1、P2、P3，它们的到达时间和所需运行时间如下表所示：

进程

到达时间

运行时间

在 FCFS 算法下，调度顺序为 P1→P2→P3。P1 在 0 时刻到达，立即获得 CPU 开始运行，运行 7 个时间单位后完成；P2 在 2 时刻到达，等待 P1 运行结束后，从 7 时刻开始运行，运行 4 个时间单位后在 11 时刻完成；P3 在 4 时刻到达，等待 P1 和 P2 运行结束后，从 11 时刻开始运行，运行 1 个时间单位后在 12 时刻完成。

该算法的优点显而易见，它非常简单直观，易于实现，不需要额外的复杂计算和判断，只需要按照进程到达的顺序进行调度即可，就像生活中排队一样自然。同时，它也体现了一种公平性，每个进程都按照其到达的先后顺序获得服务机会，不会偏袒任何一个进程。

然而，FCFS 算法也存在明显的缺点。当有长进程先到达时，后面的短进程可能需要等待很长时间，导致短进程的周转时间和等待时间过长，系统整体效率降低。在上述例子中，P3 只需要运行 1 个时间单位，但它需要等待 P1 和 P2 运行完共 11 个时间单位，这对于 P3 来说是很不公平的，用户体验也会很差。这种情况在实际应用中可能会导致一些对响应时间要求较高的任务无法及时得到处理，影响系统的性能和用户体验。

2.2短作业优先（SJF）

短作业优先（Shortest Job First，SJF）调度算法，顾名思义，它的核心思想是优先调度所需运行时间最短的进程，旨在追求最少的平均等待时间、最少的平均周转时间和最少的平均带权周转时间，就像在一群人中，优先让完成任务所需时间最短的人先完成任务，以提高整体效率。

SJF 算法分为非抢占式和抢占式两种。非抢占式 SJF 算法在调度时，一旦一个进程被分配到 CPU，它就会一直运行直到完成，才会调度下一个进程。而抢占式 SJF 算法，也称为最短剩余时间优先（Shortest Remaining Time First，SRTF）算法，每当有新进程加入就绪队列时，如果新进程的剩余运行时间比当前正在运行进程的剩余运行时间更短，那么新进程会抢占 CPU，当前运行进程回到就绪队列。

假设有四个进程 P1、P2、P3、P4，它们的到达时间和运行时间如下表所示：

进程

到达时间

运行时间

在非抢占式 SJF 算法下，调度顺序为 P1→P3→P2→P4 。P1 在 0 时刻最早到达，先运行；在 P1 运行过程中，P2、P3、P4 陆续到达，由于 P3 运行时间最短，所以 P1 运行完后，P3 接着运行；然后是 P2 和 P4 按照到达顺序依次运行。

在抢占式 SJF（SRTF）算法下，调度过程会有所不同。0 时刻 P1 到达并运行；2 时刻 P2 到达，此时 P1 剩余运行时间为 5，P2 运行时间为 4，P1 继续运行；4 时刻 P3 到达，P1 剩余运行时间为 3，P2 剩余运行时间为 2，P3 运行时间为 1，P3 抢占 CPU 开始运行；5 时刻 P3 完成，P4 到达，此时 P1 剩余运行时间为 3，P2 剩余运行时间为 2，P4 运行时间为 4，P2 接着运行；7 时刻 P2 完成，P1 继续运行；11 时刻 P1 完成，P4 运行。

SJF 算法的优势在于能够有效减少平均等待时间和平均周转时间，提高系统的整体效率。因为它优先处理短作业，使得短作业能够快速完成，减少了它们在就绪队列中的等待时间，从而降低了整个系统的平均等待时间和平均周转时间。

但该算法也有局限性。在实际应用中，很难准确预测每个进程的执行时间，这就使得 SJF 算法的实施存在一定困难。如果进程的运行时间是由用户提供，可能并不准确，也就无法真正做到按照短作业优先进行调度。另外，SJF 算法对长作业不利，如果源源不断地有短作业到来，长作业可能会长时间得不到执行，产生 “饥饿” 现象，甚至可能会被 “饿死”，即一直得不到服务。

2.3时间片轮转（RR）

时间片轮转（Round-Robin，RR）调度算法主要用于分时操作系统，它的设计目标是公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应，保证系统的交互性。

在 RR 算法中，时间片是一个关键概念。时间片是指 CPU 分配给每个进程一次连续执行的时间长度。系统将所有就绪进程按照 FCFS 原则排成一个就绪队列，调度程序每次把 CPU 分配给就绪队列队首的进程，让其执行一个时间片。当时间片结束时，如果进程还未完成，该进程会被移到就绪队列的末尾，等待下一轮调度，就像一场接力赛，每个选手跑一段固定的距离（时间片）后，回到队伍末尾等待下一次机会。

假设有三个进程 A、B、C，它们的到达时间都为 0，运行时间分别为 5、3、2，时间片设为 2 。初始时，就绪队列中有 A、B、C 三个进程，A 在队首，获得 CPU 开始执行。2 个时间单位后，A 的时间片用完，A 未完成，被移到就绪队列末尾，此时就绪队列顺序为 B、C、A；B 成为队首，获得 CPU 执行 2 个时间单位后完成；接着 C 成为队首，执行 2 个时间单位后也完成；最后 A 再次获得 CPU，执行剩余的 1 个时间单位完成。

时间片的大小对系统性能有着重要影响。如果时间片设置得过大，每个进程都能在一个时间片内完成，RR 算法就会退化为 FCFS 算法，长进程会使短进程等待时间过长，降低系统的响应速度，就像接力赛中每个选手跑的距离过长，导致比赛节奏变慢。而如果时间片设置得过小，进程切换会过于频繁，系统会花费大量时间在保存和恢复进程的上下文信息上，实际用于进程执行的时间比例就会减少，系统开销增大，就像接力赛中频繁交接棒，浪费了很多时间在交接动作上。因此，合理设置时间片大小是 RR 算法的关键，一般需要根据系统的负载和进程特性来调整，以达到最佳的系统性能。

图片

2.4优先级调度

优先级调度算法是根据每个进程的优先级来决定它们的调度顺序，每个进程都被赋予一个优先级数值，通常是一个整数，优先级数值的高低表示优先级的高低（具体高低与实现有关，有些系统中数值越低优先级越高，有些则相反）。在这种算法中，具有较高优先级的进程会优先获得 CPU 资源，直到它完成执行或者被阻塞。

优先级的设定方式有多种。可以根据进程的类型来设定，比如系统进程的优先级通常高于用户进程，因为系统进程对于系统的正常运行至关重要；前台进程的优先级高于后台进程，以保证用户能够及时获得前台交互的响应。也可以根据进程的紧急程度来设定，紧急任务的优先级更高，确保其能够优先得到处理。还可以根据进程的资源需求等因素来设定优先级。

优先级调度算法也分为抢占式和非抢占式。在抢占式优先级调度中，当一个更高优先级的进程到达就绪队列时，它可以立即中断正在执行的低优先级进程，抢占 CPU 资源，就像在一场比赛中，突然有更重要的选手加入，当前选手必须立即让出赛道。而在非抢占式优先级调度中，当前正在运行的进程不会因为更高优先级的进程到达而被中断，直到其完成执行或因自身原因（如等待 I/O 操作）主动让出 CPU ，就像比赛选手必须完成自己的赛程才会让给其他选手。

优先级调度算法在带来优势的同时，也存在一些问题。其中最主要的问题就是饥饿问题，如果低优先级的进程一直得不到调度，就会产生 “饥饿” 现象，长时间无法执行，这对于低优先级进程来说是不公平的。为了解决这个问题，通常会引入优先级老化（Priority Aging）策略，即随着时间的推移，逐渐提高进程的优先级，使得低优先级进程在等待一段时间后，其优先级会升高，从而有机会获得 CPU 资源，得到执行，保证了系统的公平性。

2.5多级队列调度（MLQ）

多级队列调度（Multilevel Queue Scheduling，MLQ）算法是一种更复杂但更灵活的调度算法，它根据进程的不同特性或需求，将进程划分为多个队列，每个队列都有自己的调度算法和优先级，以满足不同类型进程的需求。

在多级队列调度系统中，通常会有多个就绪队列，例如可以设置系统进程队列、交互式进程队列、批处理进程队列等。不同队列的优先级不同，系统进程队列的优先级最高，因为系统进程对于系统的稳定运行至关重要；交互式进程队列的优先级次之，以保证用户交互的及时性；批处理进程队列的优先级相对较低，因为批处理任务通常对响应时间要求不高。

每个队列内部采用不同的调度算法。系统进程队列可能采用优先级调度算法，确保重要的系统进程能够优先获得 CPU 资源；交互式进程队列可采用时间片轮转调度算法，保证每个交互式进程都能及时得到响应；批处理进程队列则可以采用先来先服务调度算法，按照批处理任务的提交顺序依次处理。

当有新进程到达时，系统会根据进程的类型将其放入相应的队列。如果是系统进程，就放入系统进程队列；如果是交互式进程，就放入交互式进程队列；如果是批处理进程，就放入批处理进程队列。然后，调度程序会首先检查高优先级队列是否有进程等待执行，如果有，则从高优先级队列中选择一个进程进行调度；只有当高优先级队列为空时，才会考虑调度低优先级队列中的进程。

多级队列调度算法的优点在于它能够根据不同类型进程的特点，采用不同的调度策略，从而更好地满足各类进程的需求。对于对响应时间要求高的交互式进程，可以通过时间片轮转保证其及时响应；对于重要的系统进程，通过高优先级调度确保系统稳定运行；对于批处理进程，虽然优先级低，但也能按照顺序得到处理。但它也存在一些缺点，比如队列的划分和优先级的设置需要根据系统的实际情况进行精心调整，如果设置不当，可能会导致某些队列中的进程长时间得不到执行，或者系统资源分配不合理。

图片

2.6多级反馈队列调度（MLFQ）

多级反馈队列调度（Multilevel Feedback Queue Scheduling，MLFQ）算法是在多级队列调度算法的基础上发展而来的，它与 MLQ 算法的主要区别在于，MLFQ 中的进程可以在不同队列之间动态移动，而 MLQ 中的进程一旦进入某个队列，就固定在该队列中直到完成。

在 MLFQ 算法中，设置了多个就绪队列，各级队列的优先级从高到低，时间片从小到大。新进程到达时，首先进入第一级队列，按照 FCFS 原则排队等待分配时间片。当进程在当前队列中用完时间片但还未结束时，它会被移到下一级队列的队尾；如果此时已经在最下级的队列，则重新放回最下级队列队尾。只有当第 k 级队列为空时，才会为 k + 1 级队头的进程分配时间片。当一个进程在某一级队列中获得 CPU 执行时，如果在时间片内完成，则直接结束；如果被其他高优先级进程抢占处理机，该进程会重新放回原队列队尾。

例如，假设有三个进程 P1、P2、P3，它们的到达时间都为 0，运行时间分别为 10、4、2 。初始时，三个进程都进入第一级队列，该队列时间片设为 2 。P1 先获得 CPU 执行 2 个时间单位后未完成，被移到第二级队列队尾；P2 获得 CPU 执行 2 个时间单位后也未完成，同样被移到第二级队列队尾；P3 获得 CPU 执行 2 个时间单位后完成。此时第一级队列为空，调度第二级队列队首的 P2，P2 执行 2 个时间单位后完成。接着调度第二级队列队尾的 P1，P1 执行 2 个时间单位后未完成，被移到第三级队列队尾。由于第二级队列为空，继续调度第三级队列队首的 P1，如此循环，直到 P1 完成。

MLFQ 算法的优势在于它能够动态地调整进程的优先级。对于那些需要长时间运行的进程，随着它们在队列间的移动，其优先级会逐渐降低，获得的时间片会逐渐增大，避免了短进程被长进程长时间阻塞；而对于短进程，它们可以在高优先级队列中快速完成，提高了系统的响应速度。同时，MLFQ 算法不需要预先知道进程的执行时间，它根据进程的实际运行情况来动态调整调度策略，更加灵活和智能，适应了不同类型进程的需求，提高了系统的整体性能。

三、实际应用中的选择与优化

3.1不同场景下的算法选择

在实际应用中，不同的场景对 CPU 调度算法有着不同的需求，因此选择合适的调度算法至关重要。

批处理系统主要用于处理批量的计算任务，这些任务通常对响应时间要求不高，但对系统的吞吐量和资源利用率有较高要求。在批处理系统中，短作业优先（SJF）算法是一个比较合适的选择。因为 SJF 算法能够优先处理短作业，减少作业的平均等待时间和平均周转时间，从而提高系统的吞吐量。例如，在一个数据处理中心，有大量的数据分析任务需要处理，这些任务的规模和运行时间各不相同。使用 SJF 算法可以让那些运行时间较短的小型数据分析任务优先得到处理，快速完成并释放资源，使得系统能够在单位时间内处理更多的任务，提高整体效率。而先来先服务（FCFS）算法由于不考虑作业的长短，可能会导致长作业长时间占用 CPU，使短作业等待时间过长，降低系统的整体性能，所以不太适合批处理系统的需求。

分时系统强调的是多个用户能够同时交互使用系统，每个用户都希望自己的操作能够得到及时响应。时间片轮转（RR）算法是分时系统的典型调度算法。它将 CPU 时间划分为固定大小的时间片，轮流分配给各个就绪进程，使得每个进程都能在一定时间间隔内得到执行机会，保证了系统的交互性。比如在多个用户同时使用的服务器系统中，每个用户都在进行不同的操作，如文件编辑、网页浏览等。RR 算法可以确保每个用户的操作请求都能及时得到处理，不会出现某个用户的操作长时间得不到响应的情况，让用户感觉系统是在为自己单独服务，提高了用户体验。

实时系统则对任务的实时性要求极高，任务必须在规定的时间内完成，否则可能会导致严重后果。在实时系统中，最早截止时间优先（EDF）算法和最低松弛度优先（LLF）算法是常用的调度算法。EDF 算法根据任务的截止时间来确定优先级，截止时间越早的任务优先级越高，从而保证任务能够在截止时间前完成。例如在自动驾驶系统中，车辆需要实时处理各种传感器数据，如摄像头图像、雷达信号等，以做出及时的决策，如加速、刹车、转向等。EDF 算法可以确保这些实时任务按照截止时间的先后顺序得到及时处理，保证车辆的行驶安全。LLF 算法则根据任务的松弛度（即任务必须完成的时间减去当前时间再减去任务剩余执行时间）来确定优先级，松弛度越小的任务优先级越高。在一些工业控制系统中，对生产过程的控制有着严格的时间要求，LLF 算法可以根据任务的紧急程度动态调整优先级，确保关键任务能够优先得到处理，保证生产过程的顺利进行。

3.2算法优化与发展趋势

随着计算机技术的不断发展，CPU 调度算法也在不断优化和演进，以适应日益复杂的应用场景和更高的性能需求。

一方面，许多优化方向致力于结合多种算法的优点，以弥补单一算法的不足。例如，将优先级调度算法与时间片轮转算法相结合，形成优先级时间片轮转调度算法。在这种算法中，每个进程不仅有自己的优先级，还会被分配一定的时间片。高优先级的进程可以获得较长的时间片，以保证其能够尽快完成；而低优先级的进程则获得较短的时间片，但也能保证其有机会得到执行，避免了低优先级进程长时间得不到调度的 “饥饿” 问题。在一个既有实时任务又有普通任务的系统中，实时任务可以被赋予较高的优先级和较长的时间片，确保其能够及时响应；而普通任务则按照较低的优先级和较短的时间片进行调度，在不影响实时任务的前提下，也能得到合理的处理。

另一方面，平衡实时性和公平性也是算法优化的重要方向。在一些场景中，既要保证实时任务的严格时间要求，又要兼顾其他任务的公平执行。比如在多媒体播放系统中，既要确保音频和视频数据的实时播放，避免卡顿，又要保证系统中其他后台任务（如文件下载、系统更新等）能够正常运行，不被完全忽视。通过动态调整任务的优先级和时间分配，可以在满足实时性需求的同时，尽量保证系统的公平性。当系统检测到实时任务的负载较低时，可以适当提高其他任务的优先级，增加其执行时间；而当实时任务负载较高时，则优先保障实时任务的资源需求。

新兴技术的发展也对 CPU 调度算法产生了深远影响。随着多核处理器的普及，如何在多个核心之间合理分配任务，充分发挥多核的性能优势，成为了调度算法需要解决的新问题。一些针对多核处理器的调度算法应运而生，如负载均衡调度算法，它通过将任务均匀地分配到各个核心上，避免某个核心负载过重，而其他核心闲置的情况，提高了整个系统的性能和资源利用率。

在云计算环境中，大量的虚拟机和容器需要共享计算资源，这就要求调度算法能够根据不同租户的需求和资源使用情况，灵活地分配 CPU 资源，实现资源的高效利用和隔离，保证每个租户的服务质量。人工智能和机器学习技术的发展也为 CPU 调度算法带来了新的思路。通过对系统运行数据的学习和分析，调度算法可以更加智能地预测任务的执行时间、资源需求等信息，从而做出更合理的调度决策，进一步提升系统的性能和效率。

四、CPU调度算法案例实战

4.1案例背景与任务描述

假设我们有一个多道程序设计系统，该系统配备了一个处理器和若干外设。现在有 5 个作业需要在这个系统上运行，它们的相关信息如下表所示：

作业

到达时间

运行时间

优先级

使用资源顺序及占用时间

CPU: 10, I/O: 5, CPU: 9

CPU: 3

CPU: 2, I/O: 2, CPU: 2

CPU: 6, I/O: 3, CPU: 3

每个作业都有其到达时间、运行时间和优先级。作业在运行过程中会交替使用 CPU 和 I/O 资源，使用资源顺序及占用时间栏中，CPU 表示使用 CPU 资源的时间，I/O 表示使用 I/O 资源的时间。例如，J1 作业首先需要使用 CPU 10 个时间单位，然后使用 I/O 5 个时间单位，最后再使用 CPU 9 个时间单位才能完成。接下来，我们将分别使用 FCFS、SJF、RR、优先级调度算法对这 5 个作业进行调度分析。

4.2使用不同算法进行调度分析

(1)先来先服务（FCFS）算法

按照 FCFS 算法，作业按照到达时间的先后顺序进行调度。由于这 5 个作业的到达时间都是 0，所以它们的调度顺序就是在表格中的顺序，即 J1、J2、J3、J4、J5。

甘特图如下：

时间

0 - 10

10 - 15

15 - 24

24 - 27

27 - 30

30 - 32

32 - 34

34 - 40

40 - 43

43 - 46

作业

J1(CPU)

J1(I/O)

J1(CPU)

J2(CPU)

J3(CPU)

J4(CPU)

J4(I/O)

J4(CPU)

J5(CPU)

J5(I/O)

时间

46 - 49

----

作业

J5(CPU)

各作业的完成时间、周转时间、等待时间计算如下：

作业

完成时间

周转时间

等待时间

平均周转时间 = (24 + 27 + 30 + 34 + 49) / 5 = 32.8

平均等待时间 = (0 + 24 + 27 + 30 + 34) / 5 = 23

在 FCFS 算法下，长作业 J1 先执行，导致后面的短作业等待时间过长，平均周转时间和平均等待时间都比较大。

(2)短作业优先（SJF）算法

SJF 算法优先调度运行时间最短的作业。这里我们假设能够准确预知每个作业的运行时间。按照运行时间从小到大排序，作业调度顺序为 J2、J3、J4、J1、J5。

甘特图如下：

时间

0 - 3

3 - 6

6 - 8

8 - 10

10 - 15

15 - 24

24 - 30

30 - 33

33 - 36

36 - 42

作业

J2(CPU)

J3(CPU)

J4(CPU)

J4(I/O)

J4(CPU)

J1(CPU)

J1(I/O)

J1(CPU)

J5(CPU)

J5(I/O)

时间

42 - 45

----

作业

J5(CPU)

各作业的完成时间、周转时间、等待时间计算如下：

作业

完成时间

周转时间

等待时间

平均周转时间 = (3 + 6 + 10 + 24 + 45) / 5 = 17.6

平均等待时间 = (0 + 3 + 6 + 10 + 24) / 5 = 8.6

SJF 算法有效地减少了短作业的等待时间，平均周转时间和平均等待时间都比 FCFS 算法有明显改善，体现了其在处理短作业方面的优势。

(3)时间片轮转（RR）算法

假设时间片大小为 4，作业按照到达时间顺序进入就绪队列，依次获取时间片运行。

甘特图如下：

时间

0 - 4

4 - 7

7 - 10

10 - 14

14 - 18

18 - 22

22 - 24

24 - 26

26 - 28

28 - 30

作业

J1(CPU)

J2(CPU)

J3(CPU)

J4(CPU)

J1(CPU)

J5(CPU)

J1(CPU)

J4(CPU)

J5(CPU)

时间

30 - 32

32 - 34

34 - 36

36 - 38

38 - 40

40 - 42

42 - 44

44 - 46

46 - 48

48 - 49

----

作业

J5(I/O)

J4(I/O)

J4(CPU)

J1(I/O)

J1(CPU)

J5(I/O)

J5(CPU)

J1(CPU)

J5(I/O)

J5(CPU)

各作业的完成时间、周转时间、等待时间计算如下：

作业

完成时间

周转时间

等待时间

平均周转时间 = (49 + 7 + 10 + 34 + 49) / 5 = 30.6

平均等待时间 = (25 + 4 + 7 + 28 + 37) / 5 = 20.2

RR 算法保证了每个作业都能在一定时间内获得 CPU 执行机会，响应时间较为稳定，但由于进程切换频繁，导致平均周转时间和平均等待时间相对较高。

(4)优先级调度算法

按照优先级从高到低的顺序进行调度，作业调度顺序为 J5、J4、J1、J2、J3。

甘特图如下：

时间

0 - 6

6 - 9

9 - 12

12 - 14

14 - 16

16 - 18

18 - 24

24 - 29

29 - 32

32 - 35

作业

J5(CPU)

J5(I/O)

J5(CPU)

J4(CPU)

J4(I/O)

J4(CPU)

J1(CPU)

J1(I/O)

J1(CPU)

J2(CPU)

时间

35 - 38

----

作业

J3(CPU)

各作业的完成时间、周转时间、等待时间计算如下：

作业

完成时间

周转时间

等待时间

平均周转时间 = (12 + 18 + 29 + 32 + 35) / 5 = 25.2

平均等待时间 = (0 + 6 + 18 + 29 + 32) / 5 = 17

优先级调度算法根据作业的优先级进行调度，高优先级作业能够优先得到处理，使得高优先级作业的周转时间和等待时间相对较短，但低优先级作业可能会等待较长时间。

通过对以上四种调度算法的分析可以看出，不同的调度算法在不同的场景下有不同的性能表现。FCFS 算法简单直观，但对短作业不利；SJF 算法能有效减少短作业的等待时间，但需要预知作业运行时间；RR 算法保证了公平性和响应时间，但系统开销较大；优先级调度算法满足了不同优先级任务的需求，但可能导致低优先级任务饥饿。在实际应用中，需要根据具体的系统需求和任务特点来选择合适的调度算法，以提高系统的整体性能。

五、如何选择合适的CPU调度算法

5.1根据系统类型选择

(1)服务器系统

服务器通常需要处理大量的并发请求，对吞吐量和 CPU 利用率要求较高。在服务器系统中，短作业优先（SJF）算法或优先级调度算法可能更为合适。例如，在一个 Web 服务器中，会有大量的 HTTP 请求，这些请求可以看作是一个个的短作业。使用 SJF 算法能够优先处理那些处理时间较短的请求，从而提高系统的整体吞吐量，让服务器能够在单位时间内处理更多的请求。而对于一些关键业务，如数据库服务器中的数据查询和更新操作，可以为这些任务分配较高的优先级，采用优先级调度算法，确保重要任务能够及时得到处理，避免因为其他低优先级任务的干扰而导致响应延迟。

(2)桌面系统

桌面系统更注重用户的交互体验，对响应时间要求较高。时间片轮转（RR）算法是桌面系统中常用的调度算法。我们在使用电脑时，会同时打开多个应用程序，如浏览器、文档编辑软件、音乐播放器等。RR 算法可以保证每个应用程序都能在一定时间内获得 CPU 的执行机会，使得用户在操作不同应用程序时都能得到及时的响应，不会出现某个应用程序长时间无响应的情况，从而提供流畅的用户体验。此外，桌面系统也可以结合优先级调度算法，为前台应用程序分配较高的优先级，进一步提高用户与当前操作应用程序的交互响应速度。

(3)嵌入式系统

嵌入式系统资源有限，且很多情况下有实时性要求。对于硬实时嵌入式系统，如航空航天控制系统、汽车电子控制系统等，需要确保任务在规定的时间内完成，否则可能会导致严重的后果。在这种情况下，单调速率调度（RMS）算法或最早截止时间优先（EDF）算法比较适用。RMS 算法根据任务的周期来分配优先级，周期越短，优先级越高，适用于任务周期固定且已知的场景。

EDF 算法则根据任务的截止期限来分配优先级，距离截止期限越近的任务优先级越高，能够更灵活地应对任务截止期限变化的情况。对于软实时嵌入式系统，如智能家电中的控制系统，虽然对任务完成时间的要求相对宽松一些，但也需要保证任务能够在一定时间内得到处理。此时可以采用基于优先级的调度算法，并结合适当的抢占机制，确保高优先级的实时任务能够及时抢占 CPU 资源，同时也能兼顾其他非实时任务的执行。

5.2考虑任务特点选择

(1)计算密集型任务

计算密集型任务主要消耗 CPU 资源，需要进行大量的计算。对于这类任务，SJF 算法或优先级调度算法可能更能发挥优势。以科学计算中的矩阵运算任务为例，由于其计算量巨大，运行时间相对较长。

如果采用 SJF 算法，在能够准确预估任务运行时间的前提下，计算密集型任务可以在短作业较少时得到及时处理，提高 CPU 的利用率。若使用优先级调度算法，可以为计算密集型任务分配较高的优先级，确保它们在与其他类型任务竞争 CPU 资源时能够优先获得执行机会，从而加快计算速度，减少任务的执行时间。

(2)I/O 密集型任务

I/O 密集型任务大部分时间都在等待 I/O 操作完成，如文件读写、网络通信等。时间片轮转（RR）算法比较适合 I/O 密集型任务。因为 I/O 操作的速度相对较慢，当一个 I/O 密集型任务进行 I/O 操作时，CPU 处于空闲状态，RR 算法可以及时将 CPU 分配给其他就绪的任务，提高 CPU 的利用率。

例如，在一个文件服务器中，多个客户端同时请求读取文件，这些文件读取任务属于 I/O 密集型任务。采用 RR 算法，每个文件读取任务都能在时间片内尝试进行 I/O 操作，当某个任务进行 I/O 等待时，CPU 可以去处理其他任务，避免了 CPU 资源的浪费，同时也能保证每个客户端的请求都能得到及时响应。

(3)交互式任务

交互式任务对响应时间要求极高，用户希望操作能够立即得到反馈。RR 算法是交互式任务的首选算法。像我们日常使用的图形界面应用程序，如鼠标点击、键盘输入等操作都属于交互式任务。

RR 算法保证了每个交互式任务都能在短时间内获得 CPU 的执行机会，使得用户的操作能够迅速得到处理，界面能够及时更新，提供良好的交互体验。此外，为了进一步优化交互式任务的响应性能，还可以结合优先级调度算法，将交互式任务设置为较高的优先级，确保它们在系统繁忙时也能优先获得 CPU 资源，减少用户等待时间。

THE END