处理机调度

需熟练掌握系统调度指标以及调度算法，常在选择题中考察。

调度的指标

CPU利用率:
- 定义：它是CPU活跃时间与总观察时间的比率。通常表示为百分比。
- 说明：CPU利用率是衡量CPU工作效率的一个关键指标。如果CPU利用率接近100%，则表示CPU几乎一直在工作。如果利用率很低，可能意味着CPU有大量的空闲时间。
系统吞吐量:
- 定义：在单位时间内系统完成的工作量或进程数。
- 说明：高吞吐量意味着系统能在短时间内完成更多的工作或处理更多的进程。
周转时间:
- 定义：进程从提交到完成所经过的总时间。这包括了进程在等待、执行以及在其他各种队列中的时间。
- 说明：较短的周转时间通常是预期的，因为这意味着进程更快地得到处理和完成。
等待时间:
- 定义：进程在就绪队列中等待CPU时间的总时间。
- 说明：等待时间不包括任何I/O操作或其他需要的资源的等待时间。较低的等待时间是理想的，因为这意味着进程花费较少的时间只是在等待执行。
响应时间:
- 定义：从提交一个请求到收到第一个响应所经过的时间。在交互式系统中，响应时间通常非常关键。
- 说明：对于交互式任务（例如在GUI系统中的任务），响应时间尤为重要，因为用户通常期望快速的反馈。较短的响应时间提供了更好的用户体验。

系统调度过程

进程调度是计算机操作系统中的一种核心功能，它决定了哪个进程应该在给定的时间段内使用处理器。为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

高级调度（长程调度，Long-term Scheduling）:
- 功能：高级调度主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
- 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
- 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
中级调度（中程调度，Mid-term Scheduling）:
- 功能：中级调度涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
- 主要目标：为高级和初级调度器优化内存使用。
- 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
初级调度（短程调度，Short-term Scheduling）:
- 功能：初级调度决定哪个进程应当被赋予CPU时间片，即决定下一个运行在处理器上的进程。
- 主要目标：确保CPU的高效利用。
- 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

调度器是操作系统中负责决定下一个要执行的进程或线程的部分。
基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得CPU时间。
调度器通常分为长程、中程和短程调度器，如前文所述。

调度时机

调度的时机可能包括以下情况：

进程进入或退出系统
进程从运行状态变为阻塞状态
或者一个时间片结束。

调度方式

抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将CPU分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
非抢占式调度（Non-Preemptive）：在这种方式下，一旦CPU分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待I/O操作）。

闲逛进程

当没有其他进程可以执行时，系统会运行一个特殊的进程，称为闲逛进程或空闲任务。它的主要任务通常是简单的：使CPU保持忙碌。在某些系统中，闲逛进程可能会执行一些简单的任务，如背景清理。该进程通常具有最低的优先级，因此只有在没有其他进程可以运行时才会执行。

两种线程的调度

内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
对于内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
对于用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比内核级线程更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

1. 先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序分配CPU时间。先到达的进程先执行，直到完成或阻塞。

2. 最短作业优先

最短作业优先（Shortest Job First，SJF）该算法选择具有最短执行时间的进程，以最小化平均等待时间。它需要知道每个进程的执行时间，通常在实际系统中难以获得。

3. 优先级调度

进程被分配一个优先级，CPU总是分配给具有最高优先级的进程。这种算法可以是静态的（进程创建时分配优先级）或动态的（根据进程的行为和状态进行动态调整）。

4. 最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）这种算法根据进程的等待时间和执行时间比来选择下一个执行的进程，以提高响应性。

5. 时间片轮转

时间片轮转（Round Robin，RR）这是一种基于时间片的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的CPU时间分配。

6. 多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为多个队列，每个队列有不同的优先级和时间片大小。新创建的进程进入最高优先级队列，如果没有完成，它将下降到较低优先级的队列，直到完成。

上下文及其切换机制

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为上下文切换。

进程上下文内容

寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
程序计数器：表示进程的下一个指令的位置。
虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
I/O状态信息：包括打开的文件描述符、网络连接、I/O指针等。
CPU调度信息：例如进程优先级、计划器状态等。
资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
选择下一个要执行的进程：调度器决定下一个要运行的进程。
恢复下一个进程的状态：操作系统从新进程的PCB中恢复其上下文信息，包括寄存器值、程序计数器等。
开始执行新进程。