1. 多任务

抢占式：进程可被调度程序强制挂起，让其它进程运行；

非抢占式：除非进程主动停止，否则它会一致运行。

2. 调度策略

2.1. I/O消耗型与CPU消耗型进程

前者大部分时间提交或等待I/O请求，后者大部分时间用于执行代码。

Linux倾向于调度I/O消耗型进程，缩短响应时间。

2.2. 进程优先级

两种优先级范围：

nice值：-20到+19，默认0，越大则优先级越低；（仅对普通进程有效）
rtprio值：实时优先级，0~99，可配置，越大则优先级越高（仅对实时进程有效）。此外任何实时进程的优先级都高于普通进程。

2.3. 时间片

调度策略一般都有默认时间片，一般较短，默认如10ms。

对于Linux的CFS调度（完全公平调度），时间片是根据处理器使用比例划分的，并受nice值影响。（CFS发现进程使用CPU比当前进程小，则当前进程被抢占，新进程投入运行，因此I/O密集型的进程会有更短的响应时间）

3. Linux调度算法

3.1. 调度器类

以模块方式提供，允许有多种不同的调度算法。

CFS是一个针对普通进程的调度类，Linux为SCHED_NORMAL(POSIX为SCHED_OTHER)。

3.2. Unix中的进程调度

Unix会根据优先级，分配绝对的时间片。这对公平性造成了很大的变数。

CFS的设计：摒弃绝对的时间片分配，而根据处理器使用比重分配。

3.3. CFS

允许每个进程运行一段时间并循环轮转，然后选择运行最少的进程作为下一个运行进程；
nice值在CFS中作为获得处理器运行比的权重，根据权重所占所有进程的比例获取时间片（总量称作“目标延迟”）；
引入“最小粒度”（时间片底线），防止任务过多造成时间片过短；
nice的相对值影响分配比例，而非绝对值。

4. Linux调度实现

4.1. 时间记账

CFS调度器实体结构struct sched_entity追踪记账（定义在<linux/shed.h>中，它被嵌入在task_struct中。当系统时钟节拍发生时，记账的时间片会递减，若到0，则会被未减到0的进程抢占。

4.2. 虚拟实时与进程选择

shed_entity的一个成员vruntime，存放进程虚拟运行时间，值被标准化（加权），单位为ns（与节拍器无关）。

CFS使用它来记录程序运行了多少时间，且应该还需要运行多久。记录通过update_curr()由系统定时器周期调用，无论进程处于什么状态。

CFS会挑选vruntime最小的进程，因此进程可运行队列使用红黑树（struct rbtree）实现（根据vruntime排序），快速找到这个进程。

通过缓存最左节点可加速查询

当进程进入可运行状态（被唤醒）或fork()时，向树中加入节点；

当进程阻塞或终止时，从树中移除节点。

4.3. 调度器入口

入口函数是schedule()，定义在kernel/shed.c中：选择哪个进程可以运行，何时运行。

它按照优先级遍历调度类，从最高优先级的调度类选择进程
优化（使用likely()）：绝大多数进程是普通进程，CFS是普通进程调度类，这样使用likely()优化和加速选择CFS提供的进程

4.4. 睡眠和唤醒

进程休眠会有2种状态：TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE，它们都位于同一个等待队列上，不能够运行。

4.4.1. 等待队列

wake_queue_head_t代表等待队列，通过DECLARE_WAIT()宏/init_waitqueue_head()创建
进程放入队列（add_to_queue()）
检查等待条件，进入循环，变更进程状态（prepare_to_wait()），有必要会将进程加回到等待队列
- 若状态是TASK_INTERRUPTIBLE，进程先信号唤醒（伪唤醒），会检查和处理信号
进程被唤醒后，会再次检查等待条件是否为真，若是，则跳出循环，否则调用schedule()，并依旧在循环内（此时移出了运行队列，开始等待）
跳出循环后（出现等待事件)，移出等待队列（finish_wait()），变更状态

DEFINE_WAIT(wait);
add_wait_queue(q, &wait);
while(!cond) { //等待的事件
    prepare_to_wait(&q, &wait, TASK_INTERRUPIBLE);
    if(signal_pending(current)) { 
      //处理信号
    } 
    schedule(); //调用deactivate_task()从运行队列删除任务
}
finish_wait(&q, &wait)

4.4.2. 唤醒

通过wake_up()进行，唤醒队列上所有进程。

有时存在虚假唤醒（不是因为等待条件达成），因此需要一个循环保证它的等待条件真正达成。

wake

5. 抢占与上下文切换

由context_switch()处理（定义在kernel/sched.c）：

调用switch_mm()（定义在<asm/mmu_context.h>），将虚拟内存切换到新进程
调用switch_to()，将处理器状态切换到新进程（保存、恢复栈信息和寄存器信息，以及其它体系结构相关的信息）

内核需要直到什么时候调用schedule()，因此每个进程会有need_resched标识（在thread_info用一个位表示），表明是否需要重新执行调度。它对内核意思是：有其它进程需要被运行，请尽快调度。

5.1. 用户抢占

发生在：

系统调用返回用户空间时
中断处理返回用户空间时

5.2. 内核抢占

只要重新调度是安全的，内核就可以在任何事件抢占任务。

对于安全的重新调度，只要没有锁，内核就可以抢占（锁是非强制区域的标识），因此：

每个thread_info引入preempt_count计数上锁次数，值是0时即可抢占
抢占还需要need_resched被设置

若显式调用schedule()，要确保自己可安全被抢占。

它可发生在：

中断程序正在执行，返回内核空间前
内核代码再一次具有可抢占性时
内核任务显式调用schedule()
内核任务阻塞（导致调用schedule()）

6. 实时调度策略

两类：

SCHED_FIFO(FIFO)
SCHED_RR(round-robin)

实现都以静态优先级（rtprio）。

软实时：调度进程，尽量使进程在它限定事件到来前运行，但不是总能满足要求。Linux实时调度是软实时。

任何实时进程都会比普通进程先得到调度。

普通进程的nice值共享了rtprio的取值空间，归一化后，nice的-20~+19会被映射到100~139；而实时进程优先级映射到0~99。

ps和top种PRI/PR代表优先级（可能是动态的），越小优先级越大；NI表示nice，仅对普通进程有用。（

Linux内核-进程调度