进程调度

调度程序复杂决定哪个进程投入运行，合适运行以及运行时长。调度程序可看做在可运行态进程之间分配有限的处理器时间资源内核子系统。只有通过调度程序的合理调度，系统资源才能最大程度地发挥作用，多进程才会有并发执行的效果。

1.多任务

多任务就是操作系统能同时并发地交互执行多个进程。实际上是使多个任务处于阻塞或睡眠状态，这些任务位于内存，但是并不处于可运行状态，知道某一时间发生。Linux系统中往往有多个程序在内存，但是仅有一个处于可运行状态。

多任务系统划分为两类：抢占式和非抢占式。Linux采用抢占式多任务模式，进程在被抢占之前能够运行一定时间，这个时间称为时间片(timeslice)。从全局角度来看，合理调整时间片可以优化系统资源的使用效率。

2.调度策略

调度策略决定进程何时运行以及处理器使用时间，因此调度器的策略往往决定系统的整体印象。

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

进程分为I/O消耗型，处理器消耗型，以及混合型。I/O消耗型大部分时间用于等待或提交I/O请求，因此这种类型特点就是频繁需要处于运行态，但是运行时间很短，例如用户图形界面；处理器消耗型，很少需要I/O，主要是占用大量CPU时间，用于计算，例如Matlab；混合型，例如字处理器，通常等待键盘输入，同时大量占用CPU进行拼写检查和宏计算。

针对不同类型的进程需要不同的调度策略，考虑进程的主要需求是响应迅速还是高吞吐量。

进程优先级

Linux采用两种不同的优先级范围：nice值和实时优先级。nice值越小表明优先级越高，实时优先级正好相反(值越大优先级越高)，同时实时性进程的优先级高于非实时性进程。

时间片

前面说了时间片是进程被抢占前所能持续运行的时间，在Linux中，时间片不是一个定值，而是根据nice值分配处理器的使用比例，所以时间片跟系统负载相关。nice值越大的进程，时间片就越小。

对于Linux中使用的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。若消耗的使用比比当前进程小，则抢占处理器立刻投入运行。否则，推迟其运行。

3.Linux调度的实现

Linux的CFS调度算法实现主要有4个组成部分：

• 时间记账
• 进程旋转
• 调度器入口
• 睡眠和唤醒

时间记账

所有调度器必须对运行时间记账，每次系统时钟节拍发生时，分配给进程的时间片减少一个节拍，当节拍为0时，则会被另一个时间片尚未减到0的进程抢占。Linux中使用一个调度器实体结构——sched_entity来记录，该实体嵌入在进程描述符task_struct内。同时CFS采用虚拟实时vruntime来度量进程的运行时间，实现记账功能。

进程选择

CFS在选择下一个运行进程时，会挑选一个vruntime最小的进程。CFS使用红黑树(请翻阅数据结构，或者直接看做一种高效的数据结构，查找和删除效率很高，O(log(n))的复杂度)来存储可运行进程队列，因此每次从红黑树中选择最左边的节点。

调度器入口

进程调度的主要入口是函数schedule()，它是内核其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。通常schedule()都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类——后者需要有自己的可运行队列，然后询问后者谁是下一个该运行的进程。

睡眠和唤醒

休眠(被阻塞)的进程处于特殊的不可执行状态，往往是等待某事件或者I/O资源。内核对其操作：进程标记自己为休眠状态，从可执行红黑树中移除，放入等待队列，然后调用schedule()选择和执行其他一个进程。

唤醒过程刚好相反：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

4.抢占和上下文切换

上下文切换，就是从一个可执行进程切换到另一个可执行进程，由context_switch()函数负责处理。每当一个新进程准备投入运行的时候，schedule()都会调用该函数，其主要完成两个工作：

• 调用switch_mm()，负责把虚拟内存从上一个进程映射切换到新进程中
• 调用switch_to()，负责从上一个进程的处理器状态切换到新进程的处理器状态。包括保存、恢复栈信息和寄存器信息，还有其他与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。

内核还必须知道何时调用schedule()，内核提供了一个need_resched标志来表明是否需要重新执行一次调度。在某个进程被抢占，优先级高的程序进入执行状态，返回用户空间以及中断返回时，内核会检查need_resched标志。每个进程都有need_resched标志，这是因为访问进程描述符内数值快于全局变量。

用户抢占

用户抢占发生在：从系统调用返回用户空间时和从中断处理程序返回用户空间时。

内核抢占

Linux支持内核抢占，在重新调度是安全的时候（没有持有锁，锁是非抢占区域的标志），内核就可以在任何时间抢占正在执行的任务。内核抢占发生在：

• 中断处理程序正在执行，且返回内核空间之前
• 内核代码再一次具有可抢占性的时候
• 内核中任务显示调用schedule()
• 内核中任务阻塞

5.实时调度策略

Linux提供两种实时调度策略：FIFO(先入先出)和RR(轮询)两种方式。FIFO是指先到来的任务占用处理器，直到其主动放弃，再让第二个到来的任务占用处理器。RR与FIFO类似，但是任务耗尽其时间片后，必须由下一个任务占用处理器。

小结

本节内容，其实对于本人而言可能更为简单一些(因为研究生期间接触了一些无线通信的调度算法)，因此省略了一些细节，我自己也是喜欢先了解大概流程，再回头细读的方式学习，不然容易被细节阻碍思路。