多任务

现代Linux系统也许有100个进程在内存，但是只有一个处于可运行状态。
Linux是抢占式多任务模式。

Linux的进程调度

Linux2.5内核开始采用O（1）调度程序，对大服务器工作负载很理想但对于交互性桌面系统表现不佳。
2.6.23内核后使用RSDL增加了交互性，此时被称为CFS（完全公平调度算法）

策略

I/O消耗型和处理器消耗型的进程

GUI属于I/O消耗型，多数时间都在等待键鼠交互操作。
应当降低处理器消耗型的调度频率，以延长其运行时间。
Linux更倾向于IO消耗型进程，也并未忽略处理器消耗型进程。

进程优先级

Linux采用了两种不同范围的优先级范围。
1：使用nice值，范围【-20，19】，默认0，越大优先级越低。Linux nice代表时间片比例，mac os nice代表时间片的绝对值。
2：实时优先级，其值可配。范围【0，99】，越高优先级越大。任何实时进程优先级都高于普通进程。

时间片

Linux的CFS调度器并没有直接分配时间片到进程，将处理器的使用比划分给了进程。进程所获处理器的时间和负载密切相关。受nice值得影响。
Linux的CFS调度器抢占时机取决于进程的处理器使用比，若大于当前进程则抢占。

调度策略的活动

对于一个文字编辑程序和一个视频处理程序，一般操作系统会分配文字编辑器更高的优先级和更多的时间片。Linux则是nice值相同，即平分50%时间，但是当文字编辑程序要使用处理器时，CFS发现其时间没到50%，会抢占视频处理程序执行。

Linux调度算法

调度器类

Linux调度器是模块方式，可以针对不同类型的进程选择合适的调度算法。
完全公平调度（CFS）是针对普通进程的调度类。

Unix系统的进程调度

CFS完全摒弃时间片而是分配进程一个处理器的使用比重，这样CFS确保了进程调度有恒定的公平性，将切换频率置于不断变动中。

公平调度

CFS的最小粒度（最小时间片长度）为1ms，时间片分配时间根据目标延迟以及nice值决定的比例计算而得。所以说其实如果进程无限大的话，改法并不公平。但是能保证正常情况下是公平的。

Linux调度的实现

时间记账

所有的调度器都必须对进程运行时间做记账。

  1. 调度器实体结构,CFS不再有时间片的概念，但是它也必须维护每个进程运行时间记账，为了确保每个进程只在公平分配给它的处理器时间运行。CFS使用调度器实体结构struct sched_entity作为名为se的成员变量，嵌入进程描述符struct task_struct内。
  2. 虚拟实时，struct sched_entity结构中的vruntime变量存放进程的虚拟运行时间，虚拟时间是以ns为单位的，与定时器节拍不再相关。vruntime可以准确地测量给定进程的运行时间，而且可知道谁应该是下一个被运行的进程。

进程选择

当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。
CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小的vruntime值的进程。红黑树是一种以树节点形式存储的数据，这些数据都对应一个键值，可通过键值快速检索节点上的数据。

  1. 挑选下一个任务，CFS调度器选取待运行的下一个进程，是所有进程中vruntime最小的那一个，对应的便是树最左侧的叶子节点。
  2. 向树中加入进程，CFS如何将进程加入rbtree中，以及如何缓存最左叶子节点。这一切发生在进程变为可运行状态（被唤醒）或是通过fork()调用第一次创建进程时。enqueue_entity()函数实现了这一目的。改函数更新运行时间和其他一些统计数据，然后调用_enqueue_entity()进行繁重的插入操作，把数据项真正插入到红黑树中。
  3. 从树中删除进程, 删除动作发生在进程堵塞或者终止时。

    调度器入口

    进程调度的主要入口点是函数schedule()，它会找到一个最高优先级的调度类，其需要有自己的可运行队列。

    睡眠和唤醒

    休眠（被阻塞）进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反：进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。
  4. 等待队列， 等待队列是由等待某些事件发生的进程组成的简单链表。
  5. 唤醒， 唤醒指定等待队列上的所有进程。

    抢占和上下文切换

    上下文切换，就是从一个可执行进程切换到另一个可执行的进程。由函数context_switch()负责，每当新的进程被选出来准备投入运行时，schedule()就会调用该函数。内核提供了一个need_resched标志表明是否需要重新执行一次调度，内核也就知道什么时候调用schedule()。当某个进程应该被抢占或优先级高的进程进入可执行状态时或中断返回或系统调用返回用户空间，会设置标志位。

    用户抢占

    内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。即用户抢占发生在
  • 从系统调用返回用户空间时。
  • 从中断处理程序返回用户空间时。

内核抢占

Linux完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时候抢占正在执行的内核任务。安全即没有持有锁，即preempy_count=0且need_resched被设置，中断返回内核空间时，就可调度。同样若内核阻塞或显式调用schedule()也会显式抢占。

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR，普通的非实时的调度策略是SCHED_NORMAL.这些策略被一个特殊的实时调度器管理。

  1. SCHED_FIFO, 不基于时间片，可以一直执行下去，其比任何SCHED_NORMAL级的进程都先得到调度。更高优先级的SCHED_FIFO或SCHED_RR才能抢占。优先级一样的就轮流执行。
  2. SCHED_RR,带有时间片的SCHED_FIFO，耗尽时间片时，只能调度同一优先级的进程。
    【 总结】：对于SCHED_FIFO进程，高优先级总是立即抢占低优先级进程，但低优先级决不能抢占SCHED__RR任务，即使它的时间片耗尽。
    Linux提供的是软实时工作方式，SCHED_RR与SCHED_FIFO优先级范围【0，99】，而SCHED_NORMAL使用nice值。

    与调度相关的系统调度

    Linux提供了一个系统调用族，用于管理与调度程序的相关参数。这些系统调用可以用来操作和处理进程优先级、调度策略及处理器绑定，同时还提供了显式地将处理器交给其他进程的机制。

    与调度策略和优先级相关的系统调用

    sched_setscheduler()和sched_getscheduler()用于设置和获取进程的调度策略和实时优先级。sched_setparam()和sched_getparam()用于设置和获取进程的实时优先级。

    与处理器绑定有关的系统调用

    Linux调度程序提供强制的处理器绑定机制。

    放弃处理器时间

    Linux通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。