CPU处理器调度
CPU处理器调度
何为处理器调度
CPU是计算机最重要的资源之一。由于在多道程序系统中会出现多个进程同时共享CPU资源，这必然导致多个进程对CPU的竞争。那么，如何把CPU分配给众多处于就绪状态进程中的某一个，使得这种分配下的CPU的利用率最高，且又保证个进程都能顺利运行，这就是CPU调度所要解决的问题。处理器调度分为作业调度和处理器调度。
CPU的三级调度
在操作系统中，CPU调度是指根据一定的策略和算法，决定将哪些进程调度到CPU上执行的过程。CPU调度通常分为三个层次：高级调度（作业调度）、中级调度（内存调度）和低级调度（进程调度）。
- 高级调度（作业调度）：高级调度也被称为作业调度，是在多道程序环境下进行的调度层次。其主要任务是从作业队列中选择适当的作业，将其调入内存，并分配系统资源（如内存空间和设备）给这些作业。高级调度的目标是提高整体系统的吞吐量和资源利用率。因为高级调度涉及到将作业从外存调入内存，所以它的开销比较大，通常发生在作业提交或作业完成时。
- 中级调度（内存调度）：中级调度也被称为内存调度或页调度，是在分页系统中进行的调度层次。其主要任务是根据内存的可用情况，选择合适的进程或页面调入内存，或将不活跃的进程或页面调出内存，以控制内存的使用和提高内存利用率。中级调度的目标是通过合理的页面置换策略，减少页面调度的开销，并为进程调度提供足够的内存空间。
- 低级调度（进程调度）：低级调度也被称为进程调度，是在进程级别进行的调度层次。其主要任务是从就绪队列中选择一个进程，并将CPU分配给该进程，使其开始执行。低级调度的目标是提高CPU利用率、减少响应时间和实现公平的进程调度。常见的低级调度算法包括先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（RR）等。
这三个层次的调度相互配合，共同完成进程的调度工作。高级调度负责作业的选择和资源分配，中级调度负责内存的管理和页面置换，而低级调度负责选择可运行进程，并将CPU分配给它们。通过合理的调度策略和算法，可以实现系统资源的高效利用、进程的公平调度和系统的高性能运行。
处理器调度队列模型
- 仅有进程调度的调度队列模型
- 具有高级和低级调度的队列模型
- 同时具有三级调度的调度队列模型
进程调度的方式、时机和过程
方式
进程调度中的可剥夺式和不可剥夺式是两种不同的调度方式，用于决定进程是否可以被强制剥夺CPU的执行时间。下面是对这两种调度方式的介绍：
- 可剥夺式调度（Preemptive Scheduling）：
- 可剥夺式调度是指操作系统具有强制剥夺正在执行的进程的能力，以便将CPU分配给其他优先级更高的进程。在可剥夺式调度中，一个正在执行的进程可以被抢占，即中断当前进程的执行，并将CPU分配给更高优先级的进程。可剥夺式调度通常基于进程的优先级、时间片轮转或其他调度算法来进行进程切换。
- 可剥夺式调度的优点是能够及时响应高优先级进程的请求，并提高系统的响应性和实时性。然而，频繁的进程切换会增加调度开销，并可能导致进程上下文切换的开销。因此，在选择可剥夺式调度时需要权衡实时性要求和系统性能。
- 不可剥夺式调度（Non-preemptive Scheduling）：
- 不可剥夺式调度是指操作系统不具有强制剥夺正在执行的进程的能力，直到该进程自愿放弃CPU或发生阻塞。在不可剥夺式调度中，一个进程获得CPU后，将一直执行直到完成或主动释放CPU。
- 不可剥夺式调度的优点是减少了进程切换的开销，避免了因频繁切换而引起的性能损失。然而，如果一个进程长时间占用CPU，其他优先级更高的进程可能会被阻塞，导致响应时间延迟和资源利用不高。
选择可剥夺式调度还是不可剥夺式调度，取决于系统的需求和性能目标。对于实时系统或需要高响应性的环境，可剥夺式调度通常更合适。而对于一些非实时系统或资源利用较高的环境，不可剥夺式调度可能更适用。
时机
进程调度在操作系统中发生的时机通常包括以下三个情况：
- 创建一个新进程后：当一个新的进程被创建并添加到就绪队列时，进程调度器会在这个时机选择一个就绪的进程，并将CPU分配给它开始执行。这确保了新进程有机会运行，并能够使用系统资源。
- 运行进程终止：当一个正在运行的进程完成它的执行任务，或者由于异常情况（如错误、中断）而终止时，进程调度器会在这个时机选择下一个就绪的进程，并将CPU切换给它。这确保了CPU的连续利用，避免了空闲时间。
- 运行进程阻塞：当一个正在运行的进程发出阻塞请求，例如等待某个输入/输出操作完成或等待某个事件发生时，进程调度器会在这个时机选择下一个就绪的进程，并将CPU分配给它。这样可以避免被阻塞的进程占用CPU时间，提高系统的并发性和资源利用率。
在这些时机上，进程调度器会根据预定的调度算法和策略，选择下一个合适的进程来执行。常见的调度算法包括先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（Round Robin）等。通过合理的调度决策，可以实现公平的进程调度、优化系统的性能和资源利用，并满足不同类型的应用需求。
过程
进程调度是操作系统中的一个关键过程，负责选择合适的进程并分配CPU资源。它通常包括以下几个步骤：
- 保存当前运行进程的现场信息：当调度器决定要切换当前运行的进程时，首先需要保存当前进程的上下文信息，也称为进程的现场。这包括保存进程的寄存器状态、程序计数器（PC）、堆栈指针等重要信息。通过保存这些信息，确保了进程在切换后能够恢复到相同的执行状态。
- 选择即将运行的进程：在保存当前进程的现场信息后，调度器会根据预定的调度算法和策略从就绪队列中选择一个合适的进程作为下一个要运行的进程。选择的标准可以包括进程的优先级、剩余执行时间、等待时间等。调度算法的选择会影响进程的公平性、响应时间和系统的吞吐量。
- 为新选中的进程恢复现场：一旦选择了即将运行的进程，调度器会从该进程的保存的现场信息中恢复相关的寄存器状态、PC、堆栈指针等。这样，新选中的进程就可以从之前被暂停的位置继续执行，并继续使用CPU资源。
以上过程是进程调度的基本流程。它确保了多个进程在共享的CPU上能够合理地轮流执行，实现系统资源的高效利用和进程的公平调度。每个步骤的具体实现会依赖于操作系统的设计和调度算法的选择。
单处理器调度算法
调度原则
单处理器调度算法是用于在单个处理器上调度多个进程的算法。以下是几个常见的调度原则，用于指导单处理器调度算法的设计和实现：
- 公平性（Fairness）：调度算法应该尽量保证进程之间的公平性，即每个进程都有机会获得CPU资源并得到执行。这可以通过合理的进程优先级设置、时间片轮转等方式来实现。公平性确保了系统中的所有进程都能够得到适当的服务。
- 响应时间（Response Time）：调度算法应该能够提供快速的响应时间，即尽快将CPU分配给新到达的进程或等待时间较长的进程。较短的响应时间可以提高系统的交互性能，并使用户获得更好的体验。
- 吞吐量（Throughput）：调度算法应该尽量提高系统的吞吐量，即单位时间内完成的进程数量。高吞吐量可以提高系统的资源利用率和工作效率，使更多的进程得到执行。
- 资源利用率（Resource Utilization）：调度算法应该合理利用CPU资源，避免过度闲置或过度占用的情况。通过有效地分配CPU时间片、合理的进程切换策略等，可以提高资源利用率，确保CPU资源得到最大化的利用。
- 预测性能（Predictability）：调度算法应该具有一定的可预测性，即能够在一定程度上预测进程的执行行为和资源需求。可预测的调度算法有助于系统管理员和应用程序开发者进行性能优化和资源规划。
在实际应用中，具体的调度算法可以根据不同的系统需求和性能目标进行选择和调整。常见的单处理器调度算法包括先来先服务（FCFS）、最短作业优先（SJF）、时间片轮转（Round Robin）、优先级调度等。这些算法在不同的场景和工作负载下具有各自的优势和适用性。
常用调度算法
下面是对常用的调度算法的简要介绍：
- 先来先服务（First-Come, First-Served，FCFS）：先来先服务是一种非抢占式调度算法，它按照进程到达的顺序进行调度。当一个进程进入就绪队列后，CPU会被分配给等待时间最长的进程。这种算法简单直观，但可能会导致长作业等待时间过长，也称为"饥饿"问题。
- 时间片轮转（Round Robin，RR）：时间片轮转是一种抢占式调度算法，每个进程被分配一个固定长度的时间片（时间量子），当时间片用完后，CPU会被切换到下一个进程。如果一个进程在时间片结束前没有完成，它将被放回就绪队列的末尾。时间片轮转可确保公平性和响应性，但可能导致上下文切换频繁和额外的调度开销。
- 优先级调度（Priority Scheduling）：优先级调度根据进程的优先级来进行调度，优先级可以是静态的（由系统管理员分配）或动态的（根据进程特征或历史行为计算）。具有最高优先级的进程会被首先调度，如果有多个进程具有相同的最高优先级，则采用先来先服务的方式处理。优先级调度可以根据需求分配不同的优先级，但可能出现优先级反转和饥饿问题。
- 多级反馈调度（Multilevel Feedback Queue，MLFQ）：多级反馈调度是一种动态调度算法，它将进程划分为多个优先级队列，每个队列具有不同的时间片大小。初始时，所有进程都进入最高优先级队列，如果进程的时间片用完而没有完成，则将其降低一个优先级并移到下一个队列。如果进程等待时间过长，也可以提升其优先级。多级反馈调度可以平衡短作业和长作业的执行，并提供适应性和灵活性。
这些调度算法各有特点，适用于不同的场景和需求。在实际应用中，可以根据系统的特性和性能要求选择合适的调度算法，或结合多种算法进行调度策略的组合使用。
实时调度
实时调度是一种针对实时系统设计的调度算法，其中任务的执行时间对于系统的正确性和可靠性至关重要。实时系统要求任务能够在给定的时间限制内完成，并满足实时性要求。
实时调度算法通常分为两种类型：硬实时调度和软实时调度。
- 硬实时调度（Hard Real-Time Scheduling）：硬实时调度要求系统中的任务严格按照预定的截止时间执行。如果任务在截止时间之前无法完成，系统将被认为是失败的。常见的硬实时调度算法包括最早截止时间优先（Earliest Deadline First，EDF）和最短执行时间优先（Shortest Execution Time First，SETF）等。这些算法根据任务的截止时间或执行时间来进行调度，以确保任务能够按时完成。
- 软实时调度（Soft Real-Time Scheduling）：软实时调度允许一定程度的违约，即任务的截止时间可以被延迟，但延迟不能超过一定的限制。软实时调度算法通常考虑任务的优先级和重要性，以最大化系统的性能和效益。常见的软实时调度算法包括优先级调度算法、最早截止时间优先（Earliest Deadline First，EDF）等。
实时调度算法的目标是最大化任务的满足率和系统性能，同时满足实时性要求。这要求调度算法能够合理分配CPU资源，并根据任务的截止时间、优先级、执行时间等因素进行调度决策。实时调度算法的设计需要考虑系统的实时性需求、任务的特性和约束，以及调度算法的复杂性和开销。