第4章　进程调度

4.1　多任务

多任务系统可以划分为：非抢占式多任务和抢占式多任务。 
Linux 提供了抢占式的多任务模式。

• 在抢占式多任务模式下，由调度程序来决定什么时候停止一个进程的运行。这个强制的挂起动作就叫做抢占。
• 在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步 。

4.2　Linux 的进程调度

1、O(1）调度器调度算法对于调度那些响应时间敏感的程序有先天不足。

响应时间敏感的程序称其为交互进程。

2、O(1）调度程序性能比较：

优点：对于大服务器的工作负载很理想 
缺点：在有交互程序要运行的桌面系统上则表现不佳，因为其缺少交互进程

3、“完全公平调度算法”(简称 CFS)

该算法吸取了队列理论，将公平调度的概念引入了Linux调度程序。后来又被称为“完全公平调度算撞”，或者简称 CFS.

4.3　策略

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

1、进程可以被分为I/O消耗型和处理器消耗型。

2、调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短〉和最大系统利用率（高吞吐量）。

4.3.2　进程优先级

1、Linux 采用了两种不同的优先级范围。

第一种是用 nice 值，范围是从－20 到＋19，默认值为 0 ：越大的 nice 值意味着更低的优先级。

• Mac OS X，进程的 nice 值代表分配给进程的时间片的绝对值
• Linux 系统中， nice 值则代表时间片的比例
• 可以通过ps-el 命令查看系统中的进程列衰，结果中标记NI 的一列就是进程对应的 nice 值．

第二种范围是实时优先级，其值是可配置的，默认情况下它的变化范围是从0 到 99。 越高的实时优先级数值意味着进程优先级越高。

2、查看到你系统中的进程列表,以及它们对应的实时优先级：

ps- eo state, uid,pi d,ppid,rtpri o,time,comm.

• 如果有进程对应列显示“·”，则说明它不是实时进程。

4.3.3　时间片

1、时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。

• 时间片过长会导致系统对交互的响应表现欠佳
• 时间片太短会明显增大进程切换带来的处理器耗时

2、是否要将一个进程立刻投入运行，是完全由进程优先级和是否有时间片决定的。

4.3.4　调度策略的活动

一个系统，它拥有两个可运行的进程： 一个文字编辑程序和一个视频编码 程序,对此我们有两个目标。

• 第一是我们希望系统给文字编辑程序更多的处理器时间
• 第二是我们希望文本编辑器能在其被唤醒时抢占视频解码程序。

上述目标的达成是要依靠系统分配给文本编辑器比视频解码程序更高的优先级和更多的时间片。

4.4　Linux调度算法

4.4.1　调度器类

1、Linux 调度器是以模块方式提供的。

• 这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。
• 每个调度器都有－个优先级，基础的调度器代码定义在kernel/scbed.c 文件中。

2、完全公平调度（CFS）是一个针对普通进程的调度类,CFS 算法实现定义在文件kemel/scbed_ fair. c 中。

• 在Linux 中称为 SCHED_NORMAL
• 在 POSIX 中称为 SCHED_OTHER

4.4.2　Unix 系统中的进程调度

1、现代进程调度器有两个通用的概念：进程优先级和时间片。

• 时间片是指进程运行多少时间，进程一旦启动就会有一个默认时间片。
• 具有更高优先级的进程将运行得更频繁，而且也会被赋予更多的时间片。

2、相关的问题

• 第一个问题，若要将 nice 值映射到时间片，就必然需要将nice 单位值对应到处理器的绝对时间。但这样做将导致进程切换无法最优化进行。

事实上，给定高nice 值（低优先级）的进程往往是后台进程， 且多是计算密集型：而普通优先级的进程则更多是前台用户任务。所以这种时间片分配方式显然是和初衷背道而弛的。

• 第二个问题涉及相对nice值，同时和前面的nice值到时间片映射关系也有关系。

解决方式：将nice值呈几何增加而非算数增加

• 第三个问题，如果执行nice值到时间片的映射，我们需要能分配一个绝对时间片，而且这个绝对时间片必须能在内核的测试范围内。

解决方式：采用一个新的度量机制将从nice 值到时间片的映射与定时器节拍分离开来.

• 第四个问题是关于基于优先级的调度器为了优化交互任务而唤醒相关进程的问题。

3、实质问题一一即分配绝对的时闽片引发的固定的切换频率，给公平性造成了很大变数。

4、CFS 采用的方法是对时间片分配方式进行根本性的重新设计——完全摒弃时间片而是分配给进程一个处理器使用比重。

通过这种方式， CFS 确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。

4.4.3　公平调度

1、CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice 值来计算时间片。 nice 值在 CFS 中被作为进程获得的处理器运行比的权重。

2、CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。

“目标延迟”——越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但必须承受更高的切换代价和更差的系统总吞吐能力。

3、最小粒度：CFS引人每个进程获得的时间片底线，这个底线称为最小粒度。

4、只有相对值才会影响处理器时间的分配比例。

5、任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。

CFS称为公平调度器是因为它确保给每个进程公平的处理器使用比。它在多进程环境下，降低了调度延迟带来的不公平性。

4.5　Linux调度的实现

CFS的相关代码位于文件 kernel/sched_fair.c中。其四个组成部分：

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

4.5.1　时间记账

1、调度器实体结构 
CFS 使用调度器实体结构来追踪进程运行记，定义在文件＜linux/sched.h＞的 struct_ sched_ entity 中。

2、虚拟实时 
vruntime变量存放进程的虚拟运行时间。CFS 使用 vruntime 变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

• 定义在kemel/sched_ fair.c 文件中的 update_ curr(）函数实现了该记账功能。
• update_ currO 计算了当前进程的执行时间，并且将其存放在变量delta_ exec 中。
• update_ curr（）是由系统定时器周期性调用的，根据这种方式，vruntime可以准确地测量给定进程的运行时间，而且可知道谁应该是下一个被运行的进程。

4.5.2　进程选择

1、CFS 调度算法的核心：选择具有最小vruntime的任务。

CFS 使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。

2、具体步骤;

1、 挑选下一个任务

• CFS 的进程选择算法可简单总结为“运行rbtree树中最左边叶子节点所代表的那个 进程”。实现这一过程的函数是_ pick_ next_ entity() ，它定义在文件kemel/sched_ fair.c中。

2、 向树中加入进程

• enqueue_entity（）函数实现了将进程加入rbtree 中，以及如何缓存最左叶子节点。
• 该函数更新运行时间和其他一些统计数据，然后调用＿enqueue_entity（）进行繁重的插入操作，把数据项真正插入到红黑树中。

• 平衡二叉树的基本规则是，如果键值小于当前节点的键值，则需转向树的左分 支：相反如果大于当前节点的键值，则转向右分支。

• 从树中则除进程 删除动作发生在进程堵塞或者终止时，实际工作是由辅助函数＿dequeue_entity()完成的。

4.5.3　调度器入口

1、进程调度的主要入口点是函数schedule（），它定义在文件 kernel/sched.c中。

• 它正是内核其他部分用子调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。
• Schedule（）通常都需要和一个具体的调度类相关联。
• 该函数中唯一重要的事情是它会调用pick_ next_ task()也定义在文件 kernel/sched.c中）

2、pick_ next_task（）会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程。

4.5.4　睡眠和唤醒

1、休眠的一个常见原因就是文件I/O。

2、内核的操作都相同：

• 进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用 schedule（）选择和执行一个其他进程。
• 唤醒的过程刚好相反——进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

3、休眠有两种相关的进程状态： TASK_ INTERRUPTIBLE 和 TASK_ UNINTERRUPTIBLE。

它们的唯一区别是处于TASK_ UNINTERRUPTIBLE 的进程会忽略信号， 而处于 TASK_ INTERRUPTIBLE 状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。

4、等待队列 
休眠通过等待队列进行处理。 
进程通过执行下面几个步骤将自己加入到一个等待队列中：

• 1、调用宏 DEFINE_ WAIT（）创建一个等待队列的项。
• 2、调用 add_ wait_ queue（）把自己加入到队列中。
• 3、调用 prepareto wait（）方法将进程的状态变更为TASK_ INTERRUPTIBLE 或TASK_ UNINTERRUPTIBLE。
• 4、如果状态被设置为TASK_INTERRUPTIBLE，则信号唤醒进程。
• 5、当进程被唤醒的时候，它会再次检查条件是否为真。
• 6、当条件满足后，进程将自己设置为 TASK_ RUNNING 并调用 finish_ wait（）方法把自己移 出等待队列。

5、唤醒 
唤醒操作通过函数wake_ up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_ to_ wake_ up()，该函数负责将进程设置为TASK_ RUNNING 状态。

通常哪段代码促使等待条件达成，它就要负责随后调用wake_up(）函数。

4.6　抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在 kernel/ sched.c 中的 context_switch（）函数负责处理。

1、schedule()会调用该函数，完成了两项基本的工作：

• 用声明在 ＜asm/mmu_ context.h＞中的 switch_ mm(), 该函数负责把虚拟内存从上一个进程映射切换到新进程中。
• 调用声明在 <asm/system.h> 中的 switch_to() ，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。

2、need_ resched标志：表明是否需要重新执行一次调度。

• 当某个进程应该被抢占时， scheduler_ tick()就会设置这个标志
• 当一个优先级高的进程进入可执行状态的时候，try_ to_ wake_ up（）也会设置这个标志。

4.6.1　用户抢占

用户抢占在以下情况时产生：

• 从系统调返回用户空间时
• 从中断处理程序返回用户空间时

4.6.2　内核抢占

内核抢占会发生在:

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

4.7　实时调度策略

1、Linux 提供了两种实时调度策略： SCHED_ FIFO 和 SCHED_ RR。普通的、非实时的调度策略是SCHED_ NORMAL。具体的实现定义在文件 kemel/sched_rt.c. 中。

2、SCHED_FIFO 实现了一种简单的、先入先出的调度算法：它不使用时间片。

只有更高优先级的 SCHEDFIFO 或者 SCHEDRR任务才能抢占 SCHED_FIFO 任务。是静态优先级。

3、SCHED_ RR 是带有时间片的 SCHED_FIFO-这是一种实时轮流调度算法。是静态优先级。

4、Linux 的实时调度算挂提供了一种软实时工作方式．软实时的含义是，内核调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求．相反，硬实时系统保证在一定条件下，可以满足任何调度的要求。

4.8　与调度相关的系统调用

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

• sched_ setscheduler() 和 sched_ getscheduler()分别用于设置和获取进程的调度策略和实时优先级。

最重要的工作在于读取或改写进程taststruct的policy和rt priority 的值。

• sched_ setparam（）和sched_ getparam（）分别用于设置和获取进程的实时优先级。

这两个系统调用获取封装在sched_ param特殊结构体的rt_ priority中。

• sched_ get_ priority_ max() 和 sched_ get_ priority_ min（）分别用于返回给定调度策略的最大和最小优先级。

实时调度策略的最大优先级是MAX_ USER_ RT_ PRIO减1，最小优先级等于1。

• nice（）函数调用内核的 set_ user_ nice（）函数， 这个函数会设置进程的 task_ struct 的 static_ prio 和 prio 值。

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

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

• 当处理进行第一次创建时，它继承了其父进程的相关掩码。由于父进程运行在指定处理器上，子进程也运行在相应处理器上。
• 当处理器绑定关系改变时，内核会采用“移植线程”把任务推到合曲的处理器上。
• 加载平衡器只把任务拉到允许的处理器上,因此,进程只运行在指定处理器上,对处理器的指定是由该进程描述符的 cpus_ allowed 域设置的。

4.8.3　放弃处理器时间

Linux通过sched_ yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。它是通过将进程从活动队列中移到过期队列中实现的。

• 内核代码为了方便，可以直接调用 yield（）
• 用户空间的应用程序直接使用 sched_ yield（）系统调用就可以了。

4.9　小结

本章则考察了

• 进程调度所遵循的基本原理
• 具体实现
• 调度算法
• 目前Linux内核所使用的接口

原文：http://www.cnblogs.com/java-stx/p/5371789.html