“进程调度算法”，相信大家都不会陌生，怎么着都能说出个一二来，那假如面试官问我们“谈谈你了解的进程调度算法”，我们该怎么回答呢？这里给大家带来七种常见的进程调度算法：
详细回答
先来先服务（FCFS, First - Come, First - Served）：
- 工作原理：该算法又被称作FIFO（First In First Out），在作业调度与进程调度中均适用。每当进行进程调度时，系统会从就绪队列里挑选出最早进入该队列的进程，将其状态转变为执行态，并为其分配处理器资源，直至下一个调度时刻来临。
- 适用情景：适用于批处理系统，以及任务执行时长相差不大的场景。在这类场景中，按顺序执行任务能够保证一定的有序性。
- 优点：算法逻辑简洁明了，具备较高的公平性，严格按照进程进入就绪队列的先后顺序进行调度，先到的进程先获得处理机会。
- 缺点：存在明显弊端，可能引发“饥饿”现象。当长作业先进入队列时，会使得短作业长时间等待，从而被阻塞。此外，该算法效率欠佳，平均等待时间往往较长，故而不太适用于交互式系统。由于它无法及时响应交互请求，难以实现人机交互功能。同时，该算法未充分考量不同进程之间的差异，例如进程的紧急程度等因素。并且，在调度过程中，它相对更倾向于处理器密集型进程以及长进程，对其他类型进程不够友好。
短进程优先调度算法（SPF和SRT）：
工作原理：该算法可应用于作业调度和进程调度。需要说明的是，部分教材会将SPF专门指代非抢占式短进程优先调度算法，而把抢占式短进程优先调度算法称作最短剩余时间优先调度算法，即SRT。这里我们也遵循这种划分方式。
- 1> SPF（Shortest Process First）：属于非抢占式算法。在进行进程调度时，系统会依据就绪队列中各进程预估的处理器使用时间，每次调度都挑选预估剩余处理器使用时间最短的进程。在作业调度场景下，它也被称为短作业优先调度算法（Shortest Job First, SJF），系统会根据外存队列中各作业所要求的执行时间来调度进程，同样每次都会选择预估剩余处理器使用时间最短的作业。
- 2> SRT（Shortest Remaining Time）：这是一种抢占式算法，它会选择剩余运行时间最短的进程来执行。如果在当前进程运行期间，就绪队列中出现了所需运行时间更短的进程，那么这个进程会立即抢占处理器资源，而当前正在运行的进程状态会从执行态转变为就绪态。
适用情景：该算法比较适合批处理系统，特别是短作业数量较多的场景，能够有效提高系统整体处理效率。
优点：
- 1> SPF（Shortest Process First）：相较于先来先服务（FCFS）算法，SPF的性能更优。若在调度时满足“待调度进程同时可运行”或者“待调度进程几乎同时到达”的条件，那么SPF算法在平均等待时间和平均周转时间方面能达到最优效果。
- 2> SRT（Shortest Remaining Time）：SRT算法进一步优化了平均等待时间，让进程能更快地得到处理。
缺点：
- 1> SPF（Shortest Process First）：该算法存在一定弊端，长作业可能会陷入“饥饿”状态，长时间得不到执行机会。而且该算法依赖进程对自身运行时间进行预估，在预估过程中，可能会出现估算时间不准确的情况，甚至存在进程故意“谎报”时间以获取优先调度的问题。此外，和FCFS算法一样，它也没有充分考虑不同进程之间的差异性。
- 2> SRT（Shortest Remaining Time）：由于SRT算法需要频繁计算进程的剩余运行时间，这会带来较大的系统开销，影响系统整体性能。
优先级调度算法（PSA, Priority Scheduling Algorithm）：
工作原理：优先级调度算法可同时应用于作业调度和进程调度场景。在此算法中，作业或进程的优先级由外部赋予，系统只需依据这些外部赋予的优先级进行调度操作。从是否具备抢占特性来看，优先级调度算法可划分为“非抢占式优先级调度算法”与“抢占式优先级调度算法”。而按照在调度程序运行期间优先级是否能够动态变化，又可进一步分为“静态优先级”和“动态优先级”。
- 静态优先级指的是，各个进程的优先级在调度程序启动运行之初就已明确确定，并且在整个运行期间保持恒定不变。
- 动态优先级则意味着，在调度程序运行过程中，各个进程的优先级会根据具体情况进行动态调整。
适用情景：该算法适用于实时系统，或者那些需要对不同任务区分优先级的应用场景，能够确保重要任务优先得到处理。
优点：优先级调度算法具有很强的灵活性，它允许根据任务的重要程度和紧急程度动态调整进程或作业的优先级，从而更好地满足不同场景下的调度需求。
缺点：该算法也存在一些不足之处。低优先级的进程可能会因高优先级进程的持续占用资源而陷入“饥饿”状态，长时间得不到执行机会。此外，若采用动态优先级策略，系统需要不断地对进程优先级进行调整，这会增加额外的系统开销，影响系统的整体性能。
高响应比优先调度算法（HRRN, Highest Response Ratio Next）：
- 工作原理：高响应比优先调度算法在作业调度和进程调度场景中均适用。此算法综合考量进程（作业）的等待时间和运行时间来进行调度。其核心指标为响应比，计算公式为响应比 = (等待时间 + 运行时间) / 运行时间。随着进程等待时间的不断增加，其响应比会随之升高，也就意味着该进程的优先级会变高，从而更有可能被系统调度执行。
- 适用情景：该算法适用于批处理系统，尤其在任务执行时间差异较大的场景中表现出色。它能够同时兼顾进程的等待时间和运行时间，确保各类任务都能得到合理的调度。
- 优点：高响应比优先调度算法的显著优势在于兼顾了公平性和效率。它既避免了短进程长时间等待的问题，又不会让长进程一直得不到执行机会，从而有效减少了平均等待时间，提升了系统的整体性能。
- 缺点：该算法的主要不足之处在于每次调度时都需要计算响应比，这会增加系统的计算开销，在一定程度上影响系统的运行效率。
时间片轮转调度算法（RR, Round Robin）：
- 工作原理：时间片轮转调度算法可应用于进程调度，也能在批处理系统中用于作业调度。该算法把处理器的使用时间划分成一个个固定长度的时间片，以公平的方式分配给每一个处于就绪状态、等待使用处理器资源的进程。当时钟中断发生时，系统会更新当前进程在该时间片内剩余的可用时间。一旦某个进程所分配的时间片使用完毕，它将重新回到就绪队列中，等待下一次被分配时间片。系统会采用先来先服务（FCFS）算法来管理就绪队列，即按照进程到达就绪队列的先后顺序排列。每个时间片结束时，操作系统会暂停当前正在执行的进程，将其移至就绪队列的尾部，然后调度队列中的下一个就绪进程开始运行。通过这种方式，每个进程都能公平地获得使用处理器的机会，同时也确保了进程能够在合理的时间内得到响应。
- 适用情景：此算法非常适合分时操作系统和交互式系统，例如常见的桌面操作系统。在这类系统中，用户需要及时得到系统的响应，时间片轮转调度算法能够保证各个进程都有机会运行，从而满足用户的交互需求。
- 优点：时间片轮转调度算法具有较高的公平性，能够让所有进程在一定程度上平等地使用处理器资源，特别适合对公平性要求较高的交互式系统，能为用户提供较为流畅的使用体验。
- 缺点：该算法存在一个潜在问题，如果时间片设置得过大，该算法的调度效果会逐渐趋近于先来先服务（FCFS）算法，从而失去其本身在公平性和响应时间方面的优势。
多级队列调度算法（Multilevel Queue Scheduling）
工作原理：多级队列调度算法用于进程调度，将系统中的就绪队列划分为多个队列，分别适用于不同类型的进程（如计算密集型、I/O密集型）。每个队列可以采用不同的调度算法，如短进程优先或时间片轮转，以充分利用各种算法的优点。队列可以是抢占式或非抢占式，但需要注意优先级设置，以避免低优先级队列中的进程出现“饥饿”现象。在多处理器系统中，该算法可以为每个处理器分配特定的队列，提高处理效率和并行处理能力。
适用情景：适用于任务类型多样的系统，如同时包含批处理和交互式任务的环境。多级队列调度算法能够根据任务特点分配队列和调度策略，以提高系统性能和用户体验。
优点：灵活性高，允许根据任务类型和特点定制调度策略，优化资源利用和满足复杂场景的需求。
缺点：若优先级设置不合理，可能导致低优先级队列的进程“饥饿”，影响系统的公平性和整体性能。因此，需要合理设置优先级和调度策略。
多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）：
工作原理：该算法专为进程调度而设计。其核心思想是将整体的就绪队列拆分为多个子队列，每个子队列被分配不同的时间片大小，并按照从高到低的顺序赋予优先级。第一个子队列的优先级最高，随后的队列优先级依次降低。在每个子队列中，时间片的长短与其优先级相关联，通常高优先级队列的时间片较短，而低优先级队列的时间片则较长。
进程调度流程：当一个新进程被创建并分配系统资源后，它会被放置在第一个就绪队列的末尾，并按照先来先服务（FCFS）算法进行调度。如果该进程在一个时间片内未能完成任务，它将被降级到下一个优先级较低的队列，重新开始调度过程。这个过程不断重复，直到进程被降级到最低优先级队列。在最低优先级队列中，进程不再降级，而是依据时间片轮转调度算法（RR）等待调度。
抢占式调度机制：系统在进行调度决策时严格按照队列优先级进行。高优先级队列中的进程始终优先被调度。只有当较高优先级的队列中没有就绪进程时，才会调度较低优先级队列中的进程。如果当前正在运行的进程来自第i级队列，而第一级队列中出现新的就绪进程，系统会立即触发抢占机制，将正在运行的进程放回其队列末尾。
适用情景：该算法广泛应用于各种通用操作系统，如Linux、Windows等。
优点：具有动态调整进程优先级的能力，能够有效避免进程长时间得不到调度而陷入“饥饿”状态，适应通用操作系统的多样化需求。
缺点：由于算法逻辑复杂，在实际实现中可能会导致较大的系统开销。
知识拓展
- 七种调度算法的对比，如下表所示：
| 调度算法 | 是否可抢占 | 是否会导致“饥饿” | 算法考虑因素 | 优缺点 |
|---|---|---|---|---|
| FCFS（First - Come, First - Served） | 否 | 否 | 等待时间（进程到达时间） | 优点： 实现简单，公平对待进程，按照到达顺序调度。 缺点： 对短进程不利，若长进程先到达，短进程需长时间等待，导致系统整体效率不高 |
| SPF（Shortest Process First） | 是 | 是 | 进程预计运行时间 | 优点：能有效减少平均周转时间，提高系统吞吐量，优先处理短进程。 缺点：需要预知进程的运行时间，实际中难以准确估计；可能导致长进程饥饿 |
| SRT（Shortest Remaining Time） | 是 | 是 | 剩余最短运行时间 | 优点：能及时响应短进程，相比SPF更灵活，可动态调整调度。 缺点：同样依赖剩余运行时间的准确估计，且频繁抢占可能带来额外开销，长进程可能饥饿 |
| PSA（Priority Scheduling Algorithm） | 是（非抢占式和抢占式均可） | 是 | 进程的优先级 | 优点：可根据任务重要性进行调度，满足不同应用需求。 缺点：低优先级进程可能长期得不到执行机会，产生饥饿；确定合理优先级较困难 |
| HRRN（Highest Response Ratio Next） | 是（非抢占式和抢占式均可） | 否 | 响应比 = (等待时间 + 运行时间) / 运行时间 | 优点：综合考虑等待时间和运行时间，避免进程饥饿，兼顾短进程和长进程。 缺点： 每次调度都需计算响应比，增加了系统开销 |
| RR（Round Robin） | 是 | 否 | 所有进程公平分时使用处理器 | 优点：公平分配处理器时间，不会产生饥饿现象，适用于分时系统。 缺点： 若时间片设置不当，可能导致进程切换频繁，增加系统开销；对于计算量大的进程，响应时间可能较长 |
| Multilevel Queue Scheduling（多级队列调度） | 是（具体取决于队列设置） | 是（具体取决于队列设置） | 各个队列的调度策略 | 优点：可根据进程特性分类调度，提高系统效率，如将交互型和计算型进程分队列处理。 缺点：若队列设置不合理，可能导致某些队列的进程长期得不到服务 |
| Multilevel Feedback Queue Scheduling（多级反馈队列调度） | 是 | 是 | FCFS + RR（结合先来先服务和时间片轮转特点） | 优点：结合多种调度算法优点，能较好地适应不同类型进程，动态调整进程优先级和队列。 缺点：算法实现复杂，需要合理设置队列数量、优先级及时间片等参数 |
在多道程序系统里，多个作业会同时在系统中等待处理和执行。从一个作业被提交并加入等待队列开始，直至其运行结束，这期间可能会经历三种不同层次的调度，分别为“作业调度”“内存调度”以及“进程调度”。依据调度所发生的层次，它们又依次被称作“高级调度”“中级调度”和“低级调度”。下面将详细阐述这三种层次调度的具体情况。
高级调度（High Level Scheduling）
高级调度，也被称为作业调度或者长程调度。其调度的对象是处于外存中等待处理的作业。在多道程序系统中，作业通常首先会被存放在外存里，等待系统进行调度。高级调度的主要行为就是将合适的作业从外存调度到内存中，使得这些作业能够获得在系统中进一步运行的机会。
高级调度的发生频率相对较低。这是因为作业的提交通常不会非常频繁，而且高级调度需要综合考虑多个因素，如系统当前的资源使用情况、作业的优先级、作业所需的资源量等。系统会对这些外存中的作业进行评估和筛选，选择那些最适合当前系统状态的作业调入内存。例如，当系统的内存资源比较充足，且某个作业的优先级较高、所需资源也能得到满足时，高级调度就会将该作业从外存调入内存。高级调度就像是一个宏观的管理者，它站在较高的层面上，对作业的整体进入系统的过程进行把控，确保系统能够有条不紊地处理各个作业。
中级调度（Intermediate Scheduling）
中级调度又被叫做内存调度。它的调度对象是那些暂时不能运行的进程。在系统运行过程中，由于各种原因，有些进程可能暂时无法继续执行，比如它们可能在等待某些外部资源，或者系统的内存资源紧张，无法同时支持所有进程的运行。
中级调度的主要行为是将目标进程的相关数据和资源在内存和外存之间进行移动。具体来说，它可以将进程由就绪态转换为就绪挂起态，或者将阻塞态转换为阻塞挂起态，这涉及到进程 / 线程的七状态模型。当系统内存资源紧张时，中级调度会把一些暂时不需要运行的进程的数据和资源从内存转移到外存，这样可以释放出更多的内存空间供其他进程使用。而当系统内存资源充足，且这些挂起的进程满足运行条件时，中级调度又会将它们的数据和资源从外存调回内存，使其重新进入可运行状态。
中级调度的发生频率处于不高也不低的水平。它不像高级调度那样只在作业进入系统时进行，也不像低级调度那样频繁发生。中级调度会根据系统的内存使用情况和进程的状态动态地进行调整，以实现内存资源的合理利用和系统性能的优化。
低级调度（Low Level Scheduling）
低级调度也被称为进程调度。其调度对象是进程（或内核级线程）。在系统中，有多个进程（或内核级线程）同时竞争处理器资源，而低级调度的主要行为就是决定将处理器资源先分配给哪个进程（或内核级线程）。
低级调度的发生频率非常高。这是因为在系统运行过程中，进程的状态会不断发生变化，例如一个进程可能在执行过程中因为等待某个事件而进入阻塞状态，或者一个新的进程可能进入就绪状态。此时，低级调度就需要及时做出决策，重新分配处理器资源，以保证系统的高效运行。低级调度就像是一个微观的调度者，它时刻关注着各个进程（或内核级线程）的状态变化，根据一定的调度算法，如先来先服务、短进程优先等，快速地做出资源分配的决策，确保处理器资源能够被充分利用，各个进程（或内核级线程）能够有序地执行。