本次笔记内容： 8.1 背景 8.2 调度原则 8.3 调度算法1 8.4 调度算法2 8.5 实时调度 8.6 多处理调度与优先级反转
需要调度时，称为调度时机/调度点。
内核运行调度程序的条件（满足其一即可）： 一个进程从运行状态切换到等待状态；一个进程被终结了。 不可抢占：（比如在内核级时不能抢占） 调度程序必须等待时间结束。 可以抢占：（比如在用户级时可以抢占） 调度程序在中断被响应后执行；当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪；当前运行的进程可以被换出。基于什么原则选择进程执行。
进程A在进行I/O时，没有占用CPU；此时希望其他进程能有效利用CPU。使得CPU尽量的忙，充分利用资源。
评价指标
CPU使用率：CPU处于忙状态所占时间的百分比；吞吐量：在单位时间内完成的进程数量；周转时间：一个进程从初始化到结束，包括所有等待时间所花费的时间；等待时间：进程在就绪队列中的总时间；响应时间：从一个请求被提交到产生第一次相应所发费的总时间。评价指标间有矛盾 人们通常都需要“更快”地服务：
传输文件时的高带宽；玩游戏时的低延迟；这两个因素是独立的。和水管类比：大量的水是带宽，一打开水龙头就流出是低延迟。评价指标的期望：
减少响应时间：及时处理用户的输出并且尽快将输出提供给用户；
减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要；
增加吞吐量：减少操作系统、上下文切换的开销，并且提高系统资源的利用，如CPU，I/O设备。
减少等待时间：减少每个进程的等待时间。 上述指标其实是有矛盾的，比如很难同时满足响应时间和吞吐量：
低延迟调度增加了交互式表现：如果移动了鼠标，但是屏幕中的光标没有动，不妥；
但是操作系统需要保证吞吐量不受影响：我想要结束长时间的编程，所以操作系统必须不时进行调度，即使存在许多交互任务；
吞吐量是操作系统的计算带宽；
响应时间是操作系统的计算延迟。
因此，比如linux，desktop与sever应用两套不同的调度算法。
将“公平”作为重要指标
保证每个进程都占用相同的CPU时间；这公平么？如果一个用户比其他用户运行更多的进程怎么办？保证每个进程都等待相同的时间；公平通常会增加平均响应时间。如图，如果在前面的进程执行时间较长，周转时间会较长，如果用户请求后面的进程，可能会等待较长时间。
FCFS优点：
简单。 FCFS缺点：
平均等待时间波动较大；花费时间少的任务可能排在花费时间长的任务后面；可能导致I/O和CPU之间的重叠处理：CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待。在FCFS中，如果把短进程排到前面，周转时间会下降。因此提出短进程优先调度算法。
如果发现某个进程比当前进程剩余时间片还短，运行该进程进行抢占，则此类算法又称：Shortest-Remaining-Time（SRT，最短剩余时间）；如果不可抢占，则放到就绪进程第一个。
如上图，可以从数学上证明SJF可以产生最优平均等待时间。
SJF问题：
可能导致饥饿：连续的短任务流会使长任务饥饿，短任务可用时的任何长任务的CPU时间都会增加平均等待时间；
需要预知未来：如何预估下一个CPU突发的持续时间？可以询问用户。但如果用户欺骗？就杀死进程。那如果用户不知道怎么办？
如上图，可以由执行历史预估执行时间。
如上图，蓝线为预测结果。
R=(w+s)/s R=(w+s)/s
上式中，w为waiting time等待时间；s为service time执行时间。选择R值最高的进程。
HRRN问题：
对抢占性的支持不够；依然需要预估service time。上图为轮循算法的示例。
如上图，P2所需时间为8，小于20，执行结束后自动切换到下一个时间片。
RR问题：
RR花销：额外的上下文切换；时间量子过大，则等待时间过长，极限情况退化成FCFS；时间量子过小，则反应迅速，但是吞吐量由于大量的上下文切换开销受到影响；（时间量子由经验决定，随着计算机性能的提升，LINUX原来设置为0.01秒，现在是0.001秒）因此，选择一个合适的时间量子，并且维持上下文切换开销处于1%以内。
如上图，将FCFS与时间片不同的RR作对比，发现FCFS更好。这是因为Best FCFS切换上下文较少，但是没有公平性。
多级队列：
就绪队列被划分成独立的队列（E.g. 前台（交互），后台（批处理））；每个队列拥有自己的调度策略（E.g. 前台-RR，后台-FCFS）；调度必须在队列间进行： 固定优先级：先处理前台，然后处理后台，可能导致饥饿；时间切片：每个队列都得到一个确定的能够调度其进程的CPU总时间，比如80% - 给使用RR的前台，20%给使用FCFS的后台。多级反馈队列：
可以根据情况（反馈）调整进程的优先级、队列。CPU密集型（时间片用的很多）每用一个时间片，降一个优先级；这样，交互性较好的进程可以排到优先级高的就绪队列中。
如此，可以区分进程在动态中反映出的特征。
如上图，可以通过建立数学模型、概率论中的队列模型、虚拟等方法。现在倾向于实现的方法进行检验，因为很多细节数模无法表达。
实际调度算法比上面提到的六种算法复杂，但也体现着其基本思想。
实时调度所面对的系统为Real Time System（实时系统）。工控、火车调度等规定时间必须完成的系统为实时系统。
对于实时系统：
时间约束的及时性（deadlines）很重要；速度和平均性能相对不重要；时间约束的可预测性是其主要特性。实时系统可分为：
强实时系统：需要在保证的时间内完成重要的任务，必须完成；弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须。比如视频掉帧，就是弱实时系统的体现。
如上图，蓝色为具体任务执行时间。
如上图，周期任务，任务的一种实例。
在任务执行开始前，就决定了调度顺序。
如上图，RM是一种较为经典的静态优先级调度算法。
在过程中会产生变化。
EDF是一种较为经典的动态优先级调度算法，在任务执行过程中，由任务与Deadline间隔决定该谁执行。
如今，手机、台式机都是多处理器环境。
多处理器的CPU调度更加复杂：
多个相同的单处理器组成一个多处理器；优点：负载共享。对称多处理器（SMP）：
每个处理器运行自己的调度程序；需要在调度程序中同步。NASA发现火星探测车经常重启，最后发现是操作系统调度相关的原因。
如图，是优先级反转实例：T1优先级最高，T3最低。T3先开始执行，在t2时访问一块共享资源。t3时优先级更高的T1开始执行，执行到t4，需要访问共享资源，但是此时共享资源还在T3中，因此需要T3继续执行，执行到t5，T2开始执行，T3因此开始等待T2，T1继续等待T3。直到t7时T3执行结束，共享资源释放，T1继续执行。
如果系统认为T1断断续续，则认为不稳定，重启系统。
如上图，可以使用优先级继承的方法解决该问题。T3在t3时继承T1的优先级。
如上图，还可以使用“优先级天花板”技术，给资源也赋上优先级。
