操作系统——进程调度
整理自《操作系统概念 第9版》、参考《王道考研》教学视频
基本概念
对于单处理器系统，同一时间只有一个程序可以运行；其他进程都应等待，直到CPU空闲并可调度为止。多道程序的目标是，始终允许某个进程运行以最大化CPU利用率。
CPU的进程属性：周期进行CPU执行和I/O等待。进程在这两个状态之间不断交替。进程执行从CPU执行开始，之后I/O执行；接着另一个CPU执行，接着另一个I/O执行。
需要调度的情况：运行态——等待态（I/O请求、wait调用）、运行态——就绪态（出现中断）、等待态——就绪态（I/O完成）、进程终止。第一种和第四种除了调度没有选择，则调度方案为非抢占式或协作的，否则即为抢占的。
调度程序是一个模块，用来将CPU控制交给短期调度程序选择的进程。调度程序的功能：切换上下文、切换到用户模式、跳转到用户程序的合适位置，以便重新启动程序。调度程序停止一个进程而启动另一个所需的时间称为调度延迟。
调度准则
CPU使用率：使CPU尽可能忙碌。范围从40%（轻负荷系统）到90%（重负荷系统）。
**吞吐量：**在一个时间单元内进程完成的数量。
**周转时间：**从进程提交到进程完成的时间段被成为周转时间。周转时间为所有时间段之和，包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行。
**等待时间：**在就绪队列中等待所花的时间和。
**响应时间：**从提交请求到产生第一响应的时间。是开始响应的时间，而非输出响应所需的时间。
调度算法
先到先服务（FCFS）
先请求CPU的进程首先分配到CPU。FCFS策略可以通过FIFO队列很容易地实现，当一个进程进入就绪队列时，它的PCB会被链接到队列尾部。所有其他进程都等待一个大进程释放CPU形成护航效果，与让较短进程先进行相比，会导致CPU和设备的使用率降低。FCFS是非抢占式调度算法。
最短作业优先调度（SJF）
将每个进程与其下次CPU执行调度长度关联起来。当CPU空闲时，它被赋给具有最短CPU执行的进程。可以证明SJF调度算法是最优的。对于给定的一组进程，SJF算法的平均等待时间最小。SJF常用于长期调度。
虽然SJF算法是最优的，但是不能在短期CPU调度级别上加以实现，因为无法知道下次CPU执行的长度。可以通过指数平均进行计算。$\tau_{n+1}=αt_n+(1-\alpha)\tau_n $ 其中为第n个CPU执行长度，设为下次CPU执行预测值。因此，对于，其取值范围为[0,1]，代表了最近和过去历史在预测中的权重。
SJF算法可以是抢占式或非抢占式的。抢占式SJF调度有时称为最短剩余时间优先。
优先级调度算法
SJF算法是优先级调度算法的一个特例。每个进程都有一个优先级与其关联，而具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。可以是抢占式或非抢占式的。主要问题是无穷阻塞或饥饿，解决方案之一是老化，增加在系统中等待很长时间的进程的优先级。
轮转调度（RR）
轮转调度算法专门为分时系统设计。将一个较小时间单元定义为时间量或时间片。就绪队列作为循环队列。CPU调度程序循环整个就绪队列，为每个进程分配不超过一个时间片的CPU。RR算法的性能很大程度取决于时间片的大小。如果时间片很大，则退化为FCFS；如果时间片很小，则导致大量的上下文切换。
多级队列调度
不同类型的进程对不同的响应时间有要求。多级队列调度算法将就绪队列分成多个单独队列。根据进程属性，如内存大小、进程优先级、进程类型等，一个进程永久分到一个队列。每个队列有自己的调度算法。
多级反馈队列调度
允许进程在队列之间迁移。根据不同CPU执行的特点来区分进程。如果进程使用过多的CPU时间，那么它会被移到更低的优先级队列。这种方案将I/O密集型和交互进程放在更高优先级队列上。此外，在较低优先级队列中等待过长的进程会被移到更高优先级队列，以此阻止饥饿的发生。
线程调度
在支持线程的操作系统上，内核级线程才是操作系统调度的。用户级线程是由线程库来管理的，内核并不知道它们。用户级线程为了运行在CPU上，最终应映射到相关的内核级线程，但是这种映射可能不是直接的，可能采用轻量级进程（LWP）。
竞争范围
用户级和内核级线程之间的一个区别在于它们是如何调度的。
进程竞争范围（PCS） 实现多对多和多对一模型的系统线程库会调度用户级线程，以便在LWP上运行。竞争CPU是发生在同一进程的线程之间。通常采用优先级调度，通常允许更高优先级的线程抢占当前运行的线程；在具有相同优先级的线程之间，没有时间分片的保证。
系统竞争范围（SCS） 决定哪个内核级线程调度到一个处理器上。采用一对一模型的系统，如Windows\Linux\Solaris，只采用SCS调度。
多处理器调度
多处理器调度的方法分为非对称多处理和对称多处理（SMP）。
SMP系统试图避免将进程从一个处理器移到另一个处理器，而是试图让一个进程运行在同一个处理器上。这称为处理器亲和性，即一个进程对它运行的处理器具有亲和性。其中，试图保持进程运行在同一处理器却不保证的情况称为软亲和性，有的系统提供系统调用，允许某个进程运行在某个处理器子集上称为硬亲和性。
对于SMP系统，重要的是保持所有处理器的负载平衡，以便充分利用多处理器的优点。负载平衡通常有两种方法：拉迁移和推迁移。一个特定的任务周期性地检查每个处理器的负载，如果发现不平衡，那么通过将进程从超载处理器推到空闲或不太忙的处理器；空闲处理器从忙处理器上拉一个等待任务则称为拉迁移。推迁移和拉迁移不必相互排斥。
将多个处理器放置在同一个物理芯片上，从而产生多核处理器。处理器核的多线程有两种方法：粗粒度和细粒度的多线程。对于粗粒度的多线程，线程一直在处理器上执行，直到一个长延迟事件发生，线程之间的切换成本较高。细粒度多线程在更细的粒度级别上切换线程（通常在指令周期的边界上）。细粒度系统的架构设计有线程切换的逻辑，因此，线程之间切换的成本很小。
实时CPU调度
软实时系统 不保证会调度关键实时进程；只保证这类进程优先于非关键进程。
硬实时系统 在截止期限前完成；在截止期限后完成与没有完成是同样的结果。
从事件发生到事件得到服务的这段时间称为事件延迟。中断延迟是从CPU收到中断到中断处理程序开始的时间。步骤：1.完成正在执行的指令；2.确定中断类型；3.保存当前状态；4.ISR处理中断。调度延迟是从停止一个进程到启动另一个进程所需的时间。
冲突分为两个部分：抢占在内核中运行的任何线程；释放高优先级进程所需的、低优先级进程占有的资源。
单调速率调度
抢占的、静态优先级，调度周期性任务。周期越短，优先级越高；周期越长，优先级越低。单调速率调度可认为是最优的，因为如果一组进程不能由此算法调度，它不能由任何其他分配静态优先级的算法来调度。调度N个进程的最坏情况下的CPU利用率为
最早截止期限优先调度
根据截止期限动态分配优先级。理论上最佳。但在实际中由于上下文切换和中断处理的代价，这种级别的CPU利用率是不可能的。
比例分享调度
在所有应用之间分配T股。如果一个应用程序接收N顾的时间，那么确保了它将有N/T的总的处理器时间。采用准入控制策略，确保每个进程能够得到分配时间。
算法评估
分析评估法，使用给定算法和系统负荷，生成一个公式或数字，以便评估在该负荷下的算法性能。
确定性模型：采用特定的预先确定的负荷，计算在给定负荷下每个算法的性能。（根据例子计算）
排队模型：设n为平均队列长度（不包括正在服务的进程），W为队列的平均等待时间， 为新进程到达队列的平均到达率（如每秒3个进程）。在进程等待的W时间内，个新进程会到达队列。 根据这个公式中的两个计算第三个。但其准确性不高。
仿真：仿真程序有一个代表时钟的变量；随着这个变量值的增加，模拟程序修改系统状态以便反映设备、进程和调度程序的活动。随着仿真的运行，表明算法性能的统计数据被收集并打印。
实现：用于评估一个调度算法的唯一完全精确方式是：对它进行编程，放在操作系统内并观察它如何工作。但代价高，环境变化不可控。