《Linux内核设计与实现》第四章读书笔记

第四章——进程调度

一、多任务

1.多任务系统分为两类：非抢占式多任务和抢占式

• Linux是抢占式的多任务模式。由调度程序来决定什么时候停止一个进程的运行。进程在被抢占之前的时间是预先设置好的，称为时间片。时间片就是分配给每个可运行进程的处理器时间段。

• 非抢占多任务模式下，除非进程自己主动停止运行，否则会一直执行。进程主动挂起自己的动作叫做让步。这种模式

二、Linux的进程调度

Linux2.5内核版本采用O(1)调度程序的新调度程序，对大服务器的工作负载很理想，但其缺少叫交互进程。

Linux2.6内核版本初期采用RSDL，反转楼梯最后期限调度算法。最终采用CFS，完全调度公平算法。

三、策略

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

（1）进程分为I/O消耗型和处理器消耗型

• I/O消耗型:进程的大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，但通常是短短一会儿。因为它在等待更多的I/O请求时最后总会阻塞。

• 处理器消耗型：把时间大多用在执行代码上。除非被抢占，否则一直不停地运行。对于这类，调度策略尽量降低他们的调度频率，而延长其运行时间。

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

（3）Unix系统更倾向于I/O消耗型程序，以提供更好的程序响应速度。

2. 进程优先级

在某些系统中，优先级高的进程使用的时间片也比较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。

Linux采用了两种不同的优先级范围——nice值和实时优先级值。

（1） nice值，范围是-20到19，数值越大优先级越低，默认值为0。Linux中，nice值则代表时间片的比例。可以通过ps-el命令查看系统中的进程列表，结果中标记NI的一列就是进程对应的nice值。

（2） 实时优先级值，默认0到99，数值越大优先级越高。任何实时进程的优先级都高于普通的进程。
查看进程列表以及对应的实时优先级：ps-eo state,uid,pid,ppid,rtprio,time,comm.

3.时间片

表明进程被抢占前所能持续运行的时间。长时间片导致系统交互表现欠佳。

关于Linux的CFS调度器：

（1）没有直接分配时间片到进程，而是将处理器的使用比划分给进程。nice值高、优先权低的进程被赋予低权重，丧失一小部分处理器使用比；nice值低、优先权高的进程被赋予高权重，抢得更多的处理器使用比。

（2）其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，立刻投入运行，抢占当前进程；否则推迟运行。

四、Linux调度算法

1.调度器类（模块化结构）

• Linux调度器以模块方式提供，允许不同类型的进程有针对性地选择调度算法。

• 每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类选择下一个要执行的程序。

• 完全公平调度（CFS）——针对普通进程的调度类，在Linux中称为SCHED_NORMAL（POSIX中称为SCHED_OTHER），其算法实现定义在kernel/sched_fair.c文件中。

2.Unix系统中的进程调度

Unix系统中，优先级以nice值形式输出给用户空间。产生如下问题：

(1) 将nice值对应给时间片，就必须nice单位值对应到处理器的绝对时间，导致进程切换无法最优化进行。给定高nice值
（低优先级）的进程往往是后台进程，且多是计算密集型；而普通优先级的进程多是前台用户任务，不合理。

(2) nice（通常使用相对nice值）系统调用实在原值上增加或者减少，不是在绝对值上操作。比如nice值减一的效果更多取决于其初始值。

(3) 如果执行nice值到时间片的映射，需要分配一个绝对时间片（必须在内核的测试范围内）。即时间片必须是定时器节拍的整数倍。

(4) 基于优先级的调度器为了优化交互任务，唤醒相关进程，即使时间片已经用尽。有时会给某些特殊的睡眠/唤醒用例一个玩弄调度器的后门，使得给定进程打破公平原则，获得更多处理器时间，损害其他进程利益。

总结：实质问题是分配绝对的时间片引发的固定的切换频率给公平性造成了很大变数。

3.公平调度

• 目标延迟：CFS为完美多任务中的无限小调度周期的近似值设立的一个目标。越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但必须承受更高的切换代价和更差的系统总吞吐能力。

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

CFS中，任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定。任何nice值对应的绝对时间是处理器的使用比。

五、Linux调度的实现

CFS相关代码四个组成部分：时间记账、进程选择、调度器入口和睡眠和唤醒。

1. 时间记账

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

调度器实体结构

CFS使用调度器实体结构（名为se的成员变量，嵌入在进程描述符struct task_struct内）进行追踪程序并记账：

虚拟实时

• vruntime变量存放进程的虚拟运行时间，纪录一个程序到底运行了多长时间以及还应该再运行多长时间。
• update_curr()函数计算当前进程执行时间，存放在变量delta_exec中；
• __update_curr()函数根据当前进程可运行总数对运行时间进行加权计算；
• 最终权重值和当前运行进程的vruntime相加。

注意：update_curr()是由系统定时器周期性调用的，无论进程出于何种状态。

2. 进程选择

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

挑选下一个任务

CFS进程选择算法——运行rbtree最左边叶子节点所代表的进程。__pick_next_entity()函数实现，定义在kernel/sched_fair.c文件中。

向树中加入进程

• 进程变为可执行状态（被唤醒）或者通过fork()调用第一次创建进程时，CFS将进程加入rbtree。
• enqueue_entity（）函数实现了将进程加入rbtree 中，以及如何缓存最左叶子节点。
• 该函数更新运行时间和其他一些统计数据，然后调用＿enqueue_entity（）进行繁重的插入操作，把数据项真正插入到红黑树中。
• 平衡二叉树的基本规则是，如果键值小于当前节点的键值，则需转向树的左分 支：相反如果大于当前节点的键值，则转向右分支。

从树中删除进程

删除动作发生在进程堵塞或者终止时，实际工作由辅助函数__dequeue_entity()完成。

3. 调度器入口

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

（2）schedule()会调用pick_next_task()——以优先级为序，从高到低，依次检查每一个调度类，并从最高优先级的调度类中选择最高优先级的进程:

注意：该函数的核心是for()循环；pick_next_task()实现会调用pick_next_entity()。

4. 睡眠和唤醒

• 休眠的进程处于一个特殊的不可执行状态。

• 休眠有两种进程状态：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。

     TASK_INTERRUPTIBLE接收到信号会提前被唤醒，并响应该信号；而TASK_UNINTERRUPTIBLE的进程会忽略信号。
  

等待队列

休眠通过等待队列进行处理。

进程加入到一个等待队列：

（1）调用宏DEFINE_WAIT()创建一个等待队列的项。

（2）调用 add_ wait_ queue（）把自己加入到队列中。

（3）调用 prepareto wait（）方法将进程的状态变更为TASK_ INTERRUPTIBLE 或TASK_ UNINTERRUPTIBLE。

（4）如果状态被设置为TASK_INTERRUPTIBLE，则信号唤醒进程。

（5）当进程被唤醒的时候，它会再次检查条件是否为真。

（6）当条件满足后，进程将自己设置为 TASK_ RUNNING 并调用 finish_ wait（）方法把自己移 出等待队列。

唤醒

唤醒操作由函数wake_up()进行

• 它会调用函数try_to wake_up()，将进程设置为TASK_RUNNING状态，调用enqueue_task()将进程放入红黑树中。如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置need resched标志。
• 有时存在虚假的唤醒。

六、抢占和上下文切换

由context_switch()函数（定义在kernel/sched.c中）负责处理。每当一个新的进程被选出来准备运行的时候，schedule()就会调用该函数，完成两项基本工作：

调用switch_mm()，负责把虚拟内存从上一个进程映射切换到新的进程中；
调用switch_to()，负责从上一个进程的处理器状态切换到新进程的处理器状态。以进程为对象进行管理和保存。

内核提供need_ resched标志表明是否需要重新执行一次调度。该标志对内核是一个信息，标识其他进程应当被运行了，要尽快调度程序。

1．用户抢占（会检查need_ resched标志）

发生时机：

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

2．内核抢占

（1）只要没有锁，内核就可以进程抢占；锁是非抢占区域的标志。

（2）为了支持抢占，每个进程的thread_info都加入了preempt_count计数器（初值为0，每当使用锁的时候就加1，释放锁的时候数值减1），当数值为0的时候，内核就可以抢占。

（3）如果内核中进程被阻塞或显示调用了schedule()，内核抢占也会显示发生。

总结——内核抢占发生在：

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

七、实时调度策略

linux 提供两种实时调度策略SCHED_FIFO和SCHED_RR。

• SCHED_FIFO实现了一种简单的、先入先出的调度算法：它不使用时间片．处于可运行状态的SCHED_FIFO 级的进程会比任何SCHED_NORMAL 级的进程都先得到调度。
• SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再继续执行了．即 SC阻止RR 是带有时闹片的SCHED_FIFO-这是一种实时轮流调度算挂。

这两种算法实现的都是静态优先级。Linux实时调度算法是软实时工作方式——内核调度进程，尽量使进程在它的限定时间到来前运行，但内核不能保证能够总能满足。

实时优先级范围是0到MAX_RT_PRIO减1。默认情况下，MAX_RT_PRIO为100，nice值从-20到19直接对应的是100到139的实时优先级范围。

八、与调度相关的系统调用

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

• sched_setscheduler()和 sched_getscheduler()分别用于设置和获取进程的调度策略和实时优先级。与其他的系统调用相似，它们的实现也是由许多参数检查、初始化和清理构成的。其实最重要的工作在于读取或改写进程task_struct的policy和rt_priority的值。

• sched_setscheduler()和 sched_getscheduler()分别用于设置和获取进程的实时优先级。这两个系统调用获取封装在sched_param特殊结构体的rt_priority中。实时调度策略的的最大优先级：是MAX_ USERRT_PRIO减1。最小优先级等于1。

• 对于―个普通的进程，nice函数可以将给定进程的静态优先级增加一个给定的量。只有超级用户才能在调用它时使用负值，从而提高进程的优先级。nice函数会调用内核的set_user_nice函数，这个函数会设置进程的的task_struct的static_prio值。

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

Linux调度程序提供强制的处理器绑定机制。也就是说，虽然它尽力通过一种软的（或者说自然的）亲和性试图使进程尽量在同一个处理器上运行，但它也允许用户强制指定“这个进程无论如何都必须在这些处理器上运行”。这种强制的亲和性保存在进程的一个位掩码标志中。该掩码标志的每一位对应一个系统可用的处理器，默认情况下，所有的位都被设置。

内核提供的强制处理器绑定的方法很简单：

• 首先，当处理进行第一次创建时，它继承了其父进程的相关掩码。由于父进程运行在指定处理器上， 子进程也运行在相应处理器上。
• 其次，当处理器绑定关系改变时，内核会采用“移植钱程”把任务推到合曲的处理器上。
• 最后，加载平衡器只把任务拉到允许的处理器上。

3．放弃处理器时间

Linux通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制，它是通过将进程从活动队列中（因为进程正在执行，所以它肯定位于此队列当中）移到过期队列中实现的。

内核代码为了方便，可以直接调用sched_yield()，先要确定给定进程确实处于可执行状态，然后再调用sched_yield(),用户空间的应用程序直接使用sched_yield()系统调用就可以 。

小结

进程调度程序是内核重要的组成部分，因为运行着的进程首先在使用计算机（至少在我们大多数人看来）。从Unix渐渐完善到Linux的CFS调度程序，逐步尽量满足各方面的需求，本章也主要的介绍了进程调度所遵循的基本原理、具体实现、调度算法以及目前Linux内核所使用的接口。通过这章的学习，对以前的知识比如第五章系统调用有了更加深刻的理解。