进程调度（一）

调度程序负责决定将哪个进程投入运行，何时运行，以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。

（一）：多任务

多任务操作系统就是能并发的交互执行多个进程的操作系统，多任务系统可以分为两类：非抢占式多任务和抢占式多任务。Linux提供了抢占式多任务，在这个模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会，这个强制挂起的动作就叫做抢占。进程的时间片是分配给每个可运行进程的处理器时间段。

在非抢占式多任务模式下，除非进程自己主动停止运行，否则他会一直执行下去。进程主动挂起自己的操作成为让步。

（二）：策略

​1：IO消耗型和处理器消耗型进程

进程可以被分为IO消耗型和处理器消耗型，前者指进程的大部分时间用来提交IO请求或是等待IO请求。这样的进程通常处于可运行状态，但通常是运行短短一会儿，因为他在等待更多的IO请求的时候，最终会阻塞。
处理器消耗型进程通常把时间大多用在执行代码上，除非被抢占，否则他们通常都一直不停的运行，他们没有太多的IO请求。

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

​2：进程优先级

调度算法中最基本的一类就是基于优先级的调度。通常的做法是高优先级的先运行，低优先级的后运行，相同优先级的以轮转的方式运行。
Linux采用了两种不同的优先级范围：第一种是nice值，他的值的范围是-20—-+19,默认为0。nice值越大，优先级越低。相比高nice值的进程，低nice值的进程可以获得更多的处理器时间。由于不同的操作系统的调度算法不同，nice 值的意义也就不一样。Mac os x中的nice是分配给进程的时间片的绝对值，而在Linux中，nice代表时间片的比例。
​第二类是实时优先级，他的值是可配置的，默认情况下他的变化范围是[0,99],实时优先级越大，进程的优先级越高。nice优先级和实时优先级处于两个互不相交的范畴。

3：时间片

​时间片是一个数值，他表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片。

（三）：Linux调度算法

​1：调度器类

Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性的选择调度算法。 这种模块化结构被称作调度器类，他允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，他会按照优先级顺序遍历调度器类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

完全公平调度（CFS）是一个针对普通进程的调度类，在Linux中成为SCHED_NORMAL，该调度器定义在kernel/sched_fair.c中。

2：公平调度

CFS的出发点基于一个简单的概念：进程调度的效果应该如同系统具备一个理想的完美多任务处理器。在这种系统中，每个进程将能获取1/n的处理器时间-n是指可运行进程的数量。CFS的做法是允许每个进程运行一段时间，循环轮转，选择运行最少的进程作为下一个运行进程。而不采用分配给每个进程时间片的做法了。CFS在所有可运行进程总数的基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值（越低的优先级）进程获得更低的处理器使用权重。

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

假如说：目标延迟是20ms，如果有两个同样优先级的可运行任务，每个任务在被其他进程抢占前运行10ms。

最小粒度：CFS引入的每个进程获得的时间片的底线，默认情况下最小粒度是1ms。

任何进程所获得的处理器时间是由他自己和其他所有可运行进程nice值的相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS称为公平调度器是因为他确保给每个进程公平的处理器使用比。

（四）：Linux调度的实现

Linux调度的实现重点在于下面四个重要的组成部分：
​1：时间记账
​2：进程选择
​3：调度器入口
​4：睡眠和唤醒

1：时间记账

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

1）：调度器的实体结构

​CFS不再有时间片的概念，但是他也必须维护一个每个进程运行时间的时间记账，因为他需要确保每个进程只在公平分配给他的处理器时间内运行。CFS使用调度器实体结构（定义在文件linux/sched.h的struct sched_entity中）来追踪时间记账。

下面我们来看一下代码：

struct sched_entity {
    struct load_weight  load;       /* for load-balancing */
    struct rb_node      run_node;
    struct list_head    group_node;
    unsigned int        on_rq;
    u64         exec_start;
    u64         sum_exec_runtime;
    u64         vruntime;  //记录程序到底运行了多长时间
    u64         prev_sum_exec_runtime;
    u64         last_wakeup;
    u64         avg_overlap;
    u64         nr_migrations;
    u64         start_runtime;
    u64         avg_wakeup;
 / * 省略代码，只有在设置了CONFIG_SCHEDSTATS时才启用这些变量*/
};

在进程描述符中，调度器实体结构作为一个名为se的成员变量存在。
​
​2：虚拟实时

vruntime变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算经过了所有可运行进程总数的标准化。虚拟运行时间是以ns为单位，所以vruntime和定时器节拍不再相关。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及他还应该再运行多久。

我们来看一下记账功能的实现。（定义在kernel/sched_fair.c中的update_curr()函数）

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock;
    unsigned long delta_exec;
    if (unlikely(!curr))
        return;
    /*
     * Get the amount of time the current task was running
     * since the last time we changed load (this cannot
     * overflow on 32 bits):
     *
     * 获得当前任务从上一次修改负载之后，运行的总时间
     * （在32位系统上不会溢出）
     *
     */
    delta_exec = (unsigned long)(now - curr->exec_start);
    if (!delta_exec)  //如果运行时间为0,则表示没有运行，不用修改vruntime，直接返回
        return;
    __update_curr(cfs_rq, curr, delta_exec);
    curr->exec_start = now;  //重新设置当前任务的开始时间。
    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);
        trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
        cpuacct_charge(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }
}

该函数即update_curr()计算出了当前进程的执行时间，将该时间存放在delta_exec变量中。然后将该变量传递给__update_curr()函数，该函数根据当前可运行进程总数对运行时间进程加权计算。最终将算出的权值与当前运行进程的vruntime相加。

下面是__update_curr()函数：

/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 * 
 * 更新当前任务的运行时的统计数据，跳过不在调度器类中的当前任务。
 *
 */
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
          unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;
    schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
    //更新运行时统计，更新当前进程的总运行时间
    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq, exec_clock, delta_exec);
    //计算出差值的权重
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);
    //更新当前进程的vruntime变量
    curr->vruntime += delta_exec_weighted;
    //更新cfs队列中的最小的vruntime
    update_min_vruntime(cfs_rq);
}

其中，需要说明的是函数update_curr()是由系统定时器周期性调用的，无论进程处于可运行状态还是处于堵塞状态。根据这种方式，vruntime可以准确的测量给定进程的运行时间，而且可以知道谁应该是下一个被运行的进程。