进程调度
进程调度
进程调度器是个内核子系统，其功能是把有限的处理器资源分配给系统中的各个进程。决定哪个进程可以运行、何时运行、运行多久是进程调度器的基本功能
在单处理机上，如果系统能交错的运行多个进程，从用户角度似乎是同时运行多个进程，就称该操作系统是“多任务”的。在多处理机上，多任务操作系统支持进程真正在不同处理器上并行执行
多任务操作系统可以分为两大类：协同式和抢占式。Linux实现了抢占式，调度器决定某个进程何时停止运行，而由另一个进程运行，这种中止正在运行的进程而由另一个进程运行的行为称作“抢占”，进程在被抢占前所能运行的时间称为“时间片”
当前Linux使用的调度器称为“完全公平调度器”，这个名称源于该调度器采用了“公平入队”策略，公平入队是一个调度算法，对竞争进程采取公平访问资源的策略
时间片
进程调度器分配给进程的时间片对于系统的全局行为和性能而言，是至关重要的。如果时间片太长，降低了并发运行，用户会感到明显的延迟；相反，如果时间片太短，大量的时间浪费在了进程调度上
Linux的完全公平调度器，以一种怪异的方式解决“时间片大小”这一难题：不用时间片
I/O约束型进程和处理器约束型进程
一直消耗完所有可用时间片的进程称为“处理器约束型进程”。这类进程需要获取大量CPU资源，会消耗掉调度器分配的全部CPU。最简单的例子是如下的一个无限循环：
1 | |
相反，多数时间出于阻塞状态等待资源的进程称为“I/O约束型进程”
两者的区别在于：处理器约束的应用期望会获取尽可能长的时间片，尽快完成任务；I/O约束型应用不需要很长的时间片，如果调度器能够优先执行，则会受益；这类应用，在阻塞后越快被唤醒就可以调越多的I/O请求，应用就能更好地利用系统硬件资源
平衡这两种应用的不同需求难如登天，而且，大多数应用是混合约束型：有些进程是I/O约束型，有些进程则是处理器约束型
抢占式调度
在传统UNIX进程调度中，内核会给所有就绪进程分配一个时间片。当进程消耗完其时间片，内核就会挂起该进程，开始运行另一个进程。如果系统没有就绪进程，内核就会给消耗完时间片的进程重新分配时间片，并再次运行这些进程。因此，进程在创建或终止时分别进入和退出就绪进程列表，阻塞在I/O，或者被唤醒，这个过程反复执行
通过这种方式，所有的进程最后都有机会运行。这种行为方式制定了UNIX调度中没有明确指出但非常重要的规则：所有进程都必须运行
完全公平调度器(CFS)
完全公平调度器引入了一种非常不同的算法、称为公平调度，它消除了时间片作为处理器访问分配单元，相反地，它给每个进程分配了处理器的时间比例。算法很简单：CFS在最初给N个进程分配1/N的处理器时间。然后CFS通过优先级权衡每个进程的比例，调整分配，默认的优先级是0，权值是1，则比例不变。优先级的值越小，优先级越高，权值越高
目标延迟
要确定每个进程真正的执行时间，万确公平调度器需要把比例划分成一个固定的周期。该周期称为“目标延迟”，它表示系统的调度延迟。假设“目标延迟”设置为20ms，存在两个优先级相同的可运行进程，CFS会先执行一个进程10ms再执行另一个程序10ms，如此不断重复，如果有五个优先级相同的进程，则每个执行4ms
最小粒度
当有200个可运行进，如果目标延迟是20ms，那么每个进程只有100微秒，考虑到频繁切换进程导致的“切换开销”，CFS引入了另一个关键因素：最小粒度
“最小粒度”是指任一进程所运行的时间长的基准值。所有进程不管分配到的处理器比例是多少，都至少运行最小粒度的时间（除非被阻塞）