Linux进程调度

调度定义

wiki上的关于scheduler的定义:

   In computing, scheduling is the method by which work is assigned
   to resources that complete the work. The work may be virtual
   computation elements such as threads, processes or data flows,
   which are in turn scheduled onto hardware resources such as
   processors, network links or expansion cards.

在计算机领域里，调度是一种将任务分配给完成任务的资源的方法。
任务可能是虚拟计算元素，例如线程，进程或数据流，这些虚拟计算元素又被安排在硬件资源（例如处理器，网络链接或扩展卡）上。

任务的分类:

对于要调度的任务分类:

• 按照依赖资源：
  • CPU-bound: 任务处理效率受CPU处理速度的影响;
  • I/O-bound: 任务处理效率受I/O处理速度的影响;
• 按照执行特点:
  • Interactive: 交互式,如shell.
  • Batch: 后台服务式，不需要与用户交互的 ，如数据库引擎.
  • Real-Time: 及时响应式.

调度目标

• 所有系统
  • 公平: 给每个进程CPU资源
  • 策略强制执行: 保证规定的策略被执行
  • 平衡: 保持系统所有部分都忙碌
• 批处理系统
  • 吞吐量: 每小时最大作业数
  • 周转时间: 从提交到终止的最小时间
  • CPU利用率: 保持CPU时钟忙碌
• 交互式系统
  • 响应时间: 快速响应请求;
  • 均衡性: 满足用户期望
• 实时系统
  • 满足截止时间: 避免丢失数据
  • 可预测性: 在多媒体系统中避免品质降低

历史及发展

概述

wiki Scheduling(coputing)把Linux scheduler按照调度算法时间复杂度分为三个阶段：

O(n) -> O(1) -> O(logN)

调度器由最早版本比较原始的基于优先级和时间片的优先级队列调度策略,这个时期主要应用是单核处理器. 2.0版本逐步引入对多处理器(SMP)支持，通过big lock对整个系统访问进行序列化, 随着应用的规模逐步壮大，以及PC中多核的逐步普及. 2.4版本，各个版本中逐步完善调度策略、实时任务的支持，这个时期调度策略时间复杂度O(n). 2.5版本进一步完善交互式任务支持,对多处理器支持, 实时性方面的增强，在2.5开发版本中引入的O(1)调度器, 随后被加入到2.6发布版本中， O(1)是以其算法闻名; 之后出现了更加公平的调度算法 SD,RSDL，这启发了Ingo Molnár. CFS调度器产生, CFS– 完全公平调度器做为目前Linux调度器，一直使用到现在(V5.3)。

以下阶段主要参考M. Jones Inside the Linux 2.6 Completely Fair Scheduler文章中内核版本阶段划分

原始阶段；基于优先级队列的调度策略

V0.12 版本为例, 这个阶段Linux Kernel针对单核处理器设计的, 调度器简单高效, 主要是基于时间片和优先级队列方式实现调度。

大约是在 ~ v1.2之前,具体的版本可能不准确，那时的pc cpu还是单核

数据结构

• task_struct : 任务核心数据结构,进程相关信息
  • state
    Linux的进程状态：
  • TASK_RUNNING，相当于运行态和就绪态；
  • TASK_INTERRUPTIBLE 被挂起可中断;
  • TASK_UNINTERRUPTIBLE 被挂起不可中断;
  • TASK_STOPPED 用于SIGSTP等IPC信号响应;
  • TASK_ZOMBIE: 已退出但是暂时没有被父进程回收的僵尸进程;

  • priority
    用于给counter赋值,在 Linux 0.12 中这个初值为 15 个系统时钟周期时间

  • counter
    该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多）

  • signal
    字段是进程当前所收到信号的位图，共 32 个比特位，每个比特位代表一种信号，信号 值=位偏移值+1。因此 Linux 内核最多有 32 个信号。在每个系统调用处理过程的最后，系统会使用该信号位图对信号进行预处理。

  • blocked
    字段是进程当前不想处理的信号的阻塞位图。与 signal 字段类似，其每一比特位代 表一种被阻塞的信号。

  • timeout
    内核定时超时值

  • tss
    是进程的任务状态段 TSS（Task State Segment）信息结构。 在任务从执行中被 切换出时 tss_struct 结构保存了当前处理器的所有寄存器值

• task_union
  每个任务（进程）在内核态运行时都有自己的内核态堆栈。这里定义了任务的内核态堆栈结构。 这里定义任务联合（任务结构成员和 stack 字符数组成员）。因为一个任务的数据结构与其内核态堆栈放在同一内存页中，所以从堆栈段寄存器 ss 可以获得其数据段选择符

  union task_union {
    struct task_struct task;
    char stack[PAGE_SIZE];
  };
  

\linux-0.12\kernel\sched.c

定义了数组task[NR_TASKS]存放当前运行的任务

struct task_struct * task[NR_TASKS] = {&(init_task.task), };

\linux-0.12\kernel\sched.c

调度策略

通过时间片与优先级排队实现调度.

调度算法

调度程序扫描任务数组tasks唤醒收到信号,状态是TASK_INTERRUPTIBLE的任务，随后扫描数组counter最大的那个，调用switch_to进行切换.

如果所有任务时间片用完后使用，下面的公式在更新一下:

counter = counter / 2 + prority

如果没有任务可执行，将调用init_task任务这个0号进程，这个任务调用pause

相关源码

相关函数

V0.12版本调度函数主要使用 schedule(), sleep_on(), wake_up()等函数

调度程序 schedule()函数首先扫描任务数组。通过比较每个就绪态TASK_RUNNING任务的运行时间递减 滴答计数 counter 的值来确定当前哪个进程运行的时间最少。哪一个的值大，就表示运行时间还不长，于是就选中该进程，并使用任务切换宏函数切换到该进程运行。首先,调度处理之前要先唤醒已经得到信号的任务.

如果此时所有处于 TASK_RUNNING 状态进程的时间片都已经用完，系统就会根据每个进程的优先权值 priority，对系统中所有进程（包括正在睡眠的进程）重新计算每个任务需要运行的时间片值 counter 计算的公式是：

counter = counter / 2 + prority

void schedule(void)
{
  int i,next,c;
  struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

  for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
    if (*p) {
      if ((*p)->timeout && (*p)->timeout < jiffies) {
          (*p)->timeout = 0;
          if ((*p)->state == TASK_INTERRUPTIBLE)
              (*p)->state = TASK_RUNNING;
      }
      if ((*p)->alarm && (*p)->alarm < jiffies) {
          (*p)->signal |= (1<<(SIGALRM-1));
          (*p)->alarm = 0;
      }
      if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&\

      (*p)->state==TASK_INTERRUPTIBLE)
      (*p)->state=TASK_RUNNING;
   }

/* this is the scheduler proper: */

 while (1) {
    c = -1;
    next = 0;
    i = NR_TASKS;
    p = &task[NR_TASKS];
    while (--i) {
        if (!*--p)
        continue;
        if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
        c = (*p)->counter, next = i;
    }
   if (c) break;
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p)
        (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
 }
 switch_to(next);
}

\linux-0.12\kernel\sched.c

其中counter通过时钟中断触发的do_timer实现动态时间片设置

static void do_timer(int irq, struct pt_regs * regs)
{
  ...
  if ((--current->counter)>0) return;
  ...
}

另外，V0.12 中还有两个函数sleep_on,wake_up().

sleep_on()函数的主要功能是当一个任务所请求的资源正被占用或不在内存中时暂时先把该进程切换出去， 放在等待队列中等待一段时间。当切换回来后再继续运行。放入等待队列的方式利用了函数中的 tmp 指 针作为各个正在等待任务的联系。

static inline void __sleep_on(struct task_struct **p, int state)
{
    struct task_struct *tmp;
    if (!p)
        return;
    if (current == &(init_task.task))
        panic("task[0] trying to sleep");
    tmp = *p;
    *p = current;
    current->state = state;
repeat: schedule();
    if (*p && *p != current) {
        (**p).state = 0;
        current->state = TASK_UNINTERRUPTIBLE;
        goto repeat;
    }
    if (!*p)
        printk("Warning: *P = NULL\n\r");
    if (*p = tmp)
        tmp->state=0;
}

唤醒函数 wake_up()用于把正在等待可用资源的指定任务置为就绪状态. 可以看到这里也用了, (**p).state=0;而不是TASK_RUNNING,不是很优雅哦.:P

void wake_up(struct task_struct **p)
{
    if (p && *p) {
        if ((**p).state == TASK_STOPPED)
            printk("wake_up: TASK_STOPPED");
        if ((**p).state == TASK_ZOMBIE)
            printk("wake_up: TASK_ZOMBIE");
        (**p).state=0;
    }
}

个函数 interruptible_sleep_on()，它的结构与 sleep_on()的基本类似，只是在进行调度之前是把 当前任务置成了可中断等待状态，并在本任务被唤醒后还需要判断队列上是否有后来的等待任务

通过sleep_on堆栈上该临时指针 tmp 的链接作用，在几个进程为等待同一资源而多次调用该函数时，内核程 序就隐式地构筑出一个等待队列

一些细节:

• counter初始值为15 tickets

struct task_struct {
  long state;
  long counter;
  long priority;
  ...
};

#define INIT_TASK \
  { 0,15,15, \

\linux-0.12\include\sched.h

int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
        long ebx,long ecx,long edx, long orig_eax, 
        long fs,long es,long ds,
        long eip,long cs,long eflags,long esp,long ss)
{
  ...
  p->counter = p->priority;
  ...
}

\linux-0.12\kernel\fork.c

• init_task: 0 号进程的工作. pause()

void main(void)     
{   
/*
 *   NOTE!!   For any other task 'pause()' would mean we have to get a
 * signal to awaken, but task0 is the sole exception (see 'schedule()')
 * as task 0 gets activated at every idle moment (when no other tasks
 * can run). For task0 'pause()' just means we go check if some other
 * task can run, and if not we return here.
 */
  for(;;)
   __asm__("int $0x80"::"a" (__NR_pause):"ax");
}

\linux-0.12\kernel\fork.c

• tasks数组最大64个任务.

#define NR_TASKS   64

\linux-0.12\include\linux\fork.c

• current 变量的赋值

static union task_union init_task = {INIT_TASK,};
struct task_struct *current = &(init_task.task);

以上内容部分摘自赵炯<>
V1.2 版本中还可以看到引入中断的设置了,使用的task[NR_TASKS]比较V0.12也调整为循环列表

小结

这个时期的代码没有看到调度策略相关的设置，没有区分实时任务和普通任务

发展阶段：支持非实时与实时，非抢占任务的调度

V2.2.5 版本为例, Linux 版本 2.0 开始对进程调度进行了分类，允许针对实时任务、非抢占式任务、非实时任务的调度策略。 2.2.x 调度器还包括对称多处理 (SMP) 支持, 并逐步优化; 任务权重则通过goodness设置.

Preemption 这个阶段Linux用户态是可抢占的, 内核是非抢占式的, 也就是说任务进入内核态模式是无法终端的. 非抢占有他自身的有点, 可以使得内核设计变得简单,不需要考虑各种终端导致数据同步问题. 实时性不强, 如果一个cpu上有一个低优先级的任务已经进入内核态,那么即使这时,cpu任务队列上有高优先级的任务,无法取抢占他.

这部分是自己理解,后续需要更正和补充

数据结构

• task_struct : 任务核心数据结构,进程相关信息
  • need_resched
    布尔值，在调度器中用于表示该进程需要申请调度

  • state
    Linux的进程状态：

  • TASK_RUNNING，相当于运行态和就绪态；
  • TASK_INTERRUPTIBLE 被挂起可中断;
  • TASK_UNINTERRUPTIBLE 被挂起不可中断;
  • TASK_STOPPED 用于SIGSTP等IPC信号响应;
  • TASK_ZOMBIE: 已退出但是暂时没有被父进程回收的僵尸进程;

  • TASK_SWAPPING: 内存页面换入换出(未找到相关实现)

  • policy
    调度策略

  • SCHED_FIFO: 先进先出式调度
  • SCHED_RR: 轮转式调度

  • SCHED_OTHER:常规的分时调度策略

  • priority
    用于给counter赋值,在 Linux 0.12 中这个初值为 15 个系统时钟周期时间

  • counter
    该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多）

  • rt_priority
    实时进程的静态优先级
    The static priority of a real-time process. Conventional processes do not make use of this field

• schedule_data
  包含cpu正在运行进行信息， prev标识正在运行的任务， prevstate，该任务状态，last_schedule标识最后一个进程切换在cpu上进行时间戳.

static union {
  struct schedule_data {
    struct task_struct * prev;
      long prevstate;
      cycles_t last_schedule;
    } schedule_data;
  char __pad [SMP_CACHE_BYTES];
} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};

linux-2.2.5\linux\kernel\sched.c

prevstat 保存当前任务的状态,即将被切换的任务.

调度策略

这个时期已经开始区分实时和非实时调度策略

#define SCHED_OTHER   0
#define SCHED_FIFO    1
#define SCHED_RR      2

linux-2.2.5\linux\include\linux\sched.h

其中非SCHED_OTHER为普通进程，其他两种为实时进程

调度算法

Linux调度算法通过将CPU时间划分为多个epoch来工作, 每个进程有一个指定的 time quantum, 当进程完成他的time quantum时，这个进程被抢占，也可以多次被调用，比如再等待资源如I/O而挂起，再资源到位后可以再次被调用，如果一个epoch结束，所有进程重新计算time quantum.

进程优先级分为静态优先级和动态优先级,前者为实时进程设置范围1-99,后者为普通进程使用, 进程调度顺序实时进程调用完毕后,调用普通进程.

特别的,所有的任务都放在一个全局的runqueue中供调度

相关源码

从代码上可以看到, 调度的相关算法太大变化, 与0.12版本中比较counter不同, 2.2.5版本中单独抽取出一个函数goodness,来计算相关任务的权重,判断是否被调度,调度程序 schedule()函数首先扫描任务数组。通过比较每个就绪态TASK_RUNNING任务的权重weight的值, 确定当前哪个进程哪一个的weight值大，就表示需要进行调度运行,于是就选中该进程，并使用任务切换宏函数切换到该进程运行。

如果此时所有处于 TASK_RUNNING 状态进程的时间片都已经用完, weight值为0，系统就会根据每个进程的优先权值 priority，对系统中所有进程（包括正在睡眠的进程）重新计算每个任务需要运行的时间片值 counter 计算的公式是：

counter = counter / 2 + prority (这个公式也没有变化)

asmlinkage void schedule(void)
{
    struct schedule_data * sched_data;
    struct task_struct * prev, * next;
    int this_cpu;

    run_task_queue(&tq_scheduler);

    prev = current;
    this_cpu = prev->processor;

    sched_data = & aligned_data[this_cpu].schedule_data;

    if (in_interrupt())
        goto scheduling_in_interrupt;
    release_kernel_lock(prev, this_cpu);

    if (bh_active & bh_mask)
        do_bottom_half();

    spin_lock(&scheduler_lock);
    spin_lock_irq(&runqueue_lock);

    prev->need_resched = 0;

    if (!prev->counter && prev->policy == SCHED_RR) {
        prev->counter = prev->priority;
        move_last_runqueue(prev);
    }

    switch (prev->state) {
        case TASK_INTERRUPTIBLE:
            if (signal_pending(prev)) {
                prev->state = TASK_RUNNING;
                break;
            }
        default:
            del_from_runqueue(prev);
        case TASK_RUNNING:
    }

    sched_data->prevstate = prev->state;

    {
        struct task_struct * p = init_task.next_run;
        int c = -1000;

        next = idle_task;
        if (prev->state == TASK_RUNNING) {
            c = goodness(prev, prev, this_cpu);
            next = prev;
        }

        spin_unlock_irq(&runqueue_lock);

        while (p != &init_task) {
            if (can_schedule(p)) {
                int weight = goodness(p, prev, this_cpu);
                if (weight > c)
                    c = weight, next = p;
            }
            p = p->next_run;
        }

        if (!c) {
            struct task_struct *p;
            read_lock(&tasklist_lock);
            for_each_task(p)
                p->counter = (p->counter >> 1) + p->priority;
            read_unlock(&tasklist_lock);
        }
    }

#ifdef __SMP__
    {
        cycles_t t, this_slice;

        t = get_cycles();
        this_slice = t - sched_data->last_schedule;
        sched_data->last_schedule = t;

        prev->avg_slice = this_slice + prev->avg_slice;
        prev->avg_slice >>= 1;
    }

    next->processor = this_cpu;
    next->has_cpu = 1;
    spin_unlock(&scheduler_lock);
#endif 
    if (prev != next) {
#ifdef __SMP__
        sched_data->prev = prev;
#endif
        kstat.context_swtch++;
        get_mmu_context(next);
        switch_to(prev,next);

        __schedule_tail();
    }

    reacquire_kernel_lock(current);
    return;

scheduling_in_interrupt:
    printk("Scheduling in interrupt\n");
    *(int *)0 = 0;
}

linux-2.2.5\linux\kernel\sched.c

也可以看到一些变化:

• 软中断
  从这个版本的代码中可以看到调度代码中相关软中断延时处理. 这个版本主要还是 bottom half和 task queue来实现

  bottom half:

  if (bh_active & bh_mask)
      do_bottom_half();
  

  if (in_interrupt())
      goto scheduling_in_interrupt;
  

  #define in_interrupt() ({ int __cpu = smp_processor_id(); \
  (local_irq_count[__cpu] + local_bh_count[__cpu] != 0); })
  

  \linux\include\asm-i386\hardirq.h

  task queue:

  run_task_queue(&tq_scheduler)
  

• 锁:
  • 自旋锁, 可以看到有涉及runqueue的锁,因为就一个runqueue会导致资源竞争

  spin_lock(&scheduler_lock);
  spin_lock_irq(&runqueue_lock);
  

  • 读(写)锁

  read_lock(&tasklist_lock);
  read_unlock(&tasklist_lock);
  

  • 大内核锁

  release_kernel_lock(prev, this_cpu);
  reacquire_kernel_lock(current);
  

  使用的是kernel_flag自旋锁实现

  #define release_kernel_lock(task, cpu) \
  do { \
  if (task->lock_depth >= 0) \
  spin_unlock(&kernel_flag); \
  release_irqlock(cpu); \
  _sti(); \
  } while (0)
  
  #define reacquire_kernel_lock(task) \
  do { \
  if (task->lock_depth >= 0) \
  spin_lock(&kernel_flag); \
  } while (0)
  

  linux\include\asm-i386\smplock.h

• 调度策略

  针对SCHED_RR策略的任务时间片耗尽更新时间片，并将任务移动到队列队尾

• SMP的支持

  aligned_data table 包含的每个处理器的数据结构,用于快速获取每个处理器的描述符

  sched_data = & aligned_data[this_cpu].schedule_data;
  

  可以看到cpu最大支持32个

  #ifdef __SMP__
    #define NR_CPUS   32
  #else
    #define NR_CPUS 1
  #endif
  

  linux\include\linux\tasks.h

  考虑到任务切换到不同cpu上, 保持每个进程的“平均时间片”值。

  cycles_t t, this_slice;
  
  t = get_cycles();
  this_slice = t - sched_data->last_schedule;
  sched_data->last_schedule = t;
  
  prev->avg_slice = this_slice + prev->avg_slice;
  prev->avg_slice >>= 1;
  

• goodness:
  • 功能: 这是决定调度是否理想的功能。您可以相互权衡不同的任务, 他们最近在什么CPU上运行以尝试处理缓存和TLB失误处罚。
  • 返回值:
    -1000: 不会出现
    0: 时间片用完, 重新计算counter
    +ve: goodness值,越大越好
    +1000: 实时进程

  • 流程:
    如果已经释放CPU则返回0, 并清空SCHED_YIELD标识
    实时进程，weight值组成为 1000+ 其任务的实时优先级 rt_priority(0-99)
    非实时进程， weight值为任务的counter值,对以下两种情况优先:1.针对SMP运行同一个处理器上的进程;2. 当前运行的任务
    针对非实时进程增加 priority值,使得高优先级被优先调度

源代码:

static inline int goodness(struct task_struct * p, \
struct task_struct * prev, int this_cpu)
{
  int policy = p->policy;
  int weight;

  if (policy & SCHED_YIELD) {
    p->policy = policy & ~SCHED_YIELD;
    return 0;
  }

  if (policy != SCHED_OTHER)
    return 1000 + p->rt_priority;

  weight = p->counter;
  if (weight) {

#ifdef __SMP__
    if (p->processor == this_cpu)
        weight += PROC_CHANGE_PENALTY;
#endif
  if (p->mm == prev->mm)
    weight += 1;
 weight += p->priority;
 }
 return weight;
}

通过update_process_times更新counter

static void update_process_times(unsigned long ticks, \
unsigned long system)
{
   ...
    p->counter -= ticks;
    if (p->counter < 0) {
      p->counter = 0;
      p->need_resched = 1;
   }
   ...
}

一些细节:

• counter初始值为20 tickets ,大约210ms

struct task_struct {
  ...
  long counter;
  long priority;
  ...
};

#define DEF_PRIORITY   (20*HZ/100) /* 210 ms time slices */

#define INIT_TASK \
/* state etc */ { 0,0,0,KERNEL_DS,&default_exec_domain,0, \
/* counter */   DEF_PRIORITY,DEF_PRIORITY,0, 

• current 变量的赋值

在Linux中，在创建进程时分配了两个页8KB，并且将该进程的task_struct安排在栈顶。实际上这两个页是在分配task_struct时申请的，初始化完task_struct后即将esp预设为页尾作为进程的核心栈栈底，往task_struct方向延伸。

static inline struct task_struct * get_current(void)
{
  struct task_struct *current;
  __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
  return current;
 }
#define current get_current()

linux\include\asm-i386\current.h

小结

这个时期的逐步完善SMP支持,增加了对实时进程的支持

O(n) scheduler

以2.4.37版本为例

经过前几个版本的迭代，2.4 版本 O(n) scheduler 相关功能逐步完善.

数据结构

• task_struct : 任务核心数据结构,进程相关信息
  • state
    Linux的进程状态主要分为几类：
  • TASK_RUNNING，相当于运行态和就绪态；
  • TASK_INTERRUPTIBLE 被挂起可中断;
  • TASK_UNINTERRUPTIBLE 被挂起不可中断;
  • TASK_STOPPED 用于SIGSTP等IPC信号响应;
  • TASK_ZOMBIE: 已退出但是暂时没有被父进程回收的僵尸进程;

  • need_resched

    在调度器中用于表示该进程需要申请调度

  • policy

  调度策略

  • SCHED_FIFO: 先进先出式调度
  • SCHED_RR: 轮转式调度
  • SCHED_OTHER : 常规的分时调度策略
    另外，policy中还包含了一个SCHED_YIELD位，置位时表示主动放弃CPU。

  • rt_priority

  用于表征实时进程的优先级，从1-99取值，非实时进程该项应该为0。

  • counter

  该属性记录的是当前时间片内该进程还允许运行的时间

  • nice

    用户可支配的进程优先级

  • cpus_allowed

  以位向量的形式表示可用于该进程运行的CPU

  • cpus_runnable

  以位向量的形式表示当前运行该进程的CPU（相应位为1）。如果不在任何CPU上运行，则为全1。这一属性和cpus_allowed属性结合，可以迅速判断该进程是否能调度到某一CPU上运行（位”与”）。

  • processor

  本进程当前（或最近）所在CPU编号。

  • thread

  用于保存进程执行环境（各个寄存器的值以及IO操作许可权映射表），内容与TSS相近。因为TSS以CPU id为索引，而Linux无法预测被替换下来的进程下一次将在哪个CPU上运行，所以这些信息不能保存在TSS中。

  • current
    核心经常需要获知当前在某CPU上运行的进程的task_struct，在Linux中用current指针指向这一描述符。
• schedule_data: 对应cpu，可以利用它访问到某cpu上运行的进程

  static union {
   struct schedule_data {
     struct task_struct * curr;
     cycles_t last_schedule;
   } schedule_data;
   char __pad [SMP_CACHE_BYTES];
  } aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};
  

• init_tasks: 所有进程存放的双向链表

• runqueue_head: 双向链表，所有处于就绪状态TASK_RUNNING的进程

linux\kernel\sched.c

调度策略

无大变化

#define SCHED_OTHER   0
#define SCHED_FIFO    1
#define SCHED_RR      2

linux\include\linux\sched.h

调度算法

Linux调度算法通过将CPU时间划分为多个epoch来工作, 每个进程有一个指定的 time quantum, 当进程完成他的time quantum时，这个进程被抢占，也可以多次被调用，比如再等待资源如I/O而挂起，再资源到位后可以再次被调用，如果一个epoch结束，所有进程重新计算time quantum.

进程优先级分为静态优先级和动态优先级,前者为实时进程设置范围1-99,后者为普通进程使用, 进程调度顺序实时进程调用完毕后,调用普通进程.

特别的,所有的任务都放在一个全局的runqueue中供调度, 调度算法要遍历所有runqueue中任务, 时间复杂度与任务个数N有关 .

这个时期的调度器又被称作The O(n) scheduler

相关源码

调度算法与2.2 版本相差不大, 主要变化:
– 软中断: 没有了bottom half,task queue的软中断处理;
– SMP支持: cpus_allowed,cpus_runnable的使用;
– counter计算: 关于时间片的分配通过 NICE_TO_TICKS实现;j
– 内存处理: 2.4版本增加了内存属性处理active_mm,mm对于普通进程两个域值一样, 内核线程mm为NULL.内核线程设置active_mm, 设置TLBSTATE_LAZY,告诉内存不要刷新TLB, 否则通过switch_mm完成内存交换

内存这部分后续再学习补充

asmlinkage void schedule(void)
{
  struct schedule_data * sched_data;
  struct task_struct *prev, *next, *p;
  struct list_head *tmp;
  int this_cpu, c;

  spin_lock_prefetch(&runqueue_lock);

  if (!current->active_mm) BUG();
need_resched_back:
  prev = current;
  this_cpu = prev->processor;

  if (unlikely(in_interrupt())) {
    printk("Scheduling in interrupt\n");
    BUG();
  }

  release_kernel_lock(prev, this_cpu);

  sched_data = & aligned_data[this_cpu].schedule_data;

  spin_lock_irq(&runqueue_lock);

  if (unlikely(prev->policy == SCHED_RR))
    if (!prev->counter) {
      prev->counter = NICE_TO_TICKS(prev->nice);
      move_last_runqueue(prev);
  }

  switch (prev->state) {
    case TASK_INTERRUPTIBLE:
     if (signal_pending(prev)) {
        prev->state = TASK_RUNNING;
        break;
     }
    default:
      del_from_runqueue(prev);
    case TASK_RUNNING:;
  }
  prev->need_resched = 0;

repeat_schedule:
  next = idle_task(this_cpu);
  c = -1000;
  list_for_each(tmp, &runqueue_head) {
    p = list_entry(tmp, struct task_struct, run_list);
    if (can_schedule(p, this_cpu)) {
      int weight = goodness(p, this_cpu, prev->active_mm);
      if (weight > c)
         c = weight, next = p;
    }
 }

  if (unlikely(!c)) {
    struct task_struct *p;

    spin_unlock_irq(&runqueue_lock);
    read_lock(&tasklist_lock);
    for_each_task(p)
      p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
    read_unlock(&tasklist_lock);
    spin_lock_irq(&runqueue_lock);
    goto repeat_schedule;
 }

  sched_data->curr = next;
  task_set_cpu(next, this_cpu);
  spin_unlock_irq(&runqueue_lock);

  if (unlikely(prev == next)) {
    prev->policy &= ~SCHED_YIELD;
    goto same_process;
  }

#ifdef CONFIG_SMP
  sched_data->last_schedule = get_cycles();

#endif

  kstat.context_swtch++;
  prepare_to_switch();
  {
    struct mm_struct *mm = next->mm;
    struct mm_struct *oldmm = prev->active_mm;
   if (!mm) {
      if (next->active_mm) BUG();
      next->active_mm = oldmm;
      atomic_inc(&oldmm->mm_count);
      enter_lazy_tlb(oldmm, next, this_cpu);
   } else {
      if (next->active_mm != mm) BUG();
      switch_mm(oldmm, mm, next, this_cpu);
   }

   if (!prev->mm) {
      prev->active_mm = NULL;
      mmdrop(oldmm);
   }
  }

  switch_to(prev, next, prev);
  __schedule_tail(prev);

same_process:
  reacquire_kernel_lock(current);
  if (current->need_resched)
     goto need_resched_back;
     return;
}

针对SMP判断cpu是否可以调度

#ifdef CONFIG_SMP

#define idle_task(cpu) (init_tasks[cpu_number_map(cpu)])
#define can_schedule(p,cpu) \
    ((p)->cpus_runnable & (p)->cpus_allowed & (1UL << cpu))

#else

#define idle_task(cpu) (&init_task)
#define can_schedule(p,cpu) (1)

#endif

2.4版本时间片分配

/*
 * Scheduling quanta.
 *
 * NOTE! The unix "nice" value influences how long a process
 * gets. The nice value ranges from -20 to +19, where a -20
 * is a "high-priority" task, and a "+10" is a low-priority
 * task.
 *
 * We want the time-slice to be around 50ms or so, so this
 * calculation depends on the value of HZ.
 */
#if HZ < 200
#define TICK_SCALE(x)  ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x)  ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x)  (x)
#elif HZ < 1600
#define TICK_SCALE(x)  ((x) << 1)
#else
#define TICK_SCALE(x)  ((x) << 2)
#endif

#define NICE_TO_TICKS(nice)    (TICK_SCALE(20-(nice))+1)

一些细节:

• counter 初始化值 10

#define DEF_COUNTER    (10*HZ/100) /* 100 ms time slice */

#define INIT_TASK(tsk) \
{                                   \
    ...
    counter:        DEF_COUNTER,                    \
    ...

include\linux\sched.h

小结

这个阶段之前的调度器太大的变化

经过前几个版本的迭代，2.4 版本 O(n) scheduler 相关功能逐步完善. 由于都是放到一个runqueue里调度, 处理还是比较简单的.

但是由于其针对进程数量巨大的低效，预定义时间片过长，优先I/O密集型应用对用户交互型应用不是总是有效， 对实时性应用支持有限,仍然有很大要改进的空间.

• 调度器保证只有当所有 RUNNING 进程的时间片都被用完之后，才对所有进程重新分配时间片。这段时间被称为一个 epoch（调度周期）
• 每个epoch内，每个任务都可以运行一段时间, 调度器保证只有当所有 RUNNING 进程的时间片都被用完之后，才对所有进程重新分配时间片
• 调度器倾向提高交互进程优先级，普通进程优先级由进程counter确认，进程创建子进程,子进程counter减半.
• 优先级调整方式：调度器将重新计算所有进程的 counter 值，所有进程不仅包括 RUNNING 进程，也包括处于睡眠状态的进程。处于睡眠状态的进程的 counter 本来就没有用完，在重新计算时，他们的 counter 值会加上这些原来未用完的部分，从而提高了它们的优先级。

  缺点；

• 扩展性不好: 要遍历所有runqueue队列，counter计算随着进程数量增加代价增高
• 高负载系统调度性能比较低 :分配给进程时间片比较大，高负载情况下效率较低
• 交互式进程的优化不完善 :批量进程频繁的IO操作影响了交互式进程调度.
• 实时进程支持不够 内核是非抢占式的对于实时任务来说很弱

O(1) scheduler

O(1) scheduler从2.5 版本引入, 正式进入2.6正式版本, 调度器开销恒定, 更好支持实时性, 多处理器并行.
2.6引入了per-CPU变量,为每一个cpu配置了一个runqueue队列, 大家再也不用抢了

数据结构

• struct rq :
  per-CPU runqueue data structure.

  任务存放:

  • prio_array_t *active, *expired, arrays[2];
    active可被调度的队列, expired时间片用完的就绪队列, O(1)使用最关键部分

  #define DECLARE_BITMAP(name,bits) \
    unsigned long name[BITS_TO_LONGS(bits)
  
    struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); 
    struct list_head queue[MAX_PRIO];
    };
  

  同步(锁):

  • spinlock_t rq->lock
    自旋锁只针对一个cpu上的队列

  相关任务指针:

  • task_t *curr

  本CPU正在运行的进程。

  • tast_t *idle

  指向本 CPU 的 idle 进程

  内存相关:

  • struct mm_struct *prev_mm

  保存进程切换后被调度下来的进程（称之为 prev）的 active_mm 结构指针。

  负载相关:

  • int best_expired_prio

  记录 expired 就绪进程组中的最高优先级

  • unsigned long expired_timestamp

  expired 中就绪进程的最长等待时间

  • unsigned long nr_running

  本 CPU 上的就绪进程数

  • unsigned long nr_switches

  记录了本 CPU 上自调度器运行以来发生的进程切换的次数。

  • unsigned long nr_uninterruptible

  记录本 CPU 尚处于 TASK_UNINTERRUPTIBLE 状态的进程数

  • atomic_t nr_iowait

  记录本 CPU 因等待 IO 而处于休眠状态的进程数。

  • unsigned long timestamp_last_tick

  本就绪队列最近一次发生调度事件的时间

  • int prev_cpu_load[NR_CPUS]

  记录进行负载平衡时各个 CPU 上的负载状态

  • task_t *migration_thread

  指向本 CPU 的迁移进程。

  • struct list_head migration_queue

  需要进行迁移的进程列表

  NUMA相关:

  • atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]

  这两个属性仅在 NUMA 体系结构下有效，记录各个 NUMA 节点上的就绪进程数和上一次负载平衡操作时的负载情况

  • task_struct

  • state
    Linux的进程状态主要分为几类：

    • TASK_RUNNING，相当于运行态和就绪态；
    • TASK_INTERRUPTIBLE 被挂起可中断;
    • TASK_UNINTERRUPTIBLE 被挂起不可中断;
    • TASK_STOPPED 用于SIGSTP等IPC信号响应;
    • TASK_ZOMBIE: 已退出但是暂时没有被父进程回收的僵尸进程;
    • TASK_TRACED: 进程执行已由调试器停止。
    • TASK_NONINTERACTIVE: 不可交互睡眠状态;
    • TASK_DEAD :已经退出且不需要父进程来回收的进程;
  • timestamp
    单位是 nanosecond
  • prio
    优先级，普通进程 100- 139, 实时进程 1-99
  • static_prio
    静态优先级，与2.4 nice一致,转为新范围
  • activated
    表示进程因什么原因进入就绪态，这一原因会影响到调度优先级的计算。activated 有四个值：
    -1，进程从 TASK_UNINTERRUPTIBLE 状态被唤醒；
    0，缺省值，进程原本就处于就绪态；
    1，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且不在中断上下文中；
    2，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且在中断上下文中。
    与优先级优化有关

  • sleep_avg
    进程的平均等待时间（以 nanosecond 为单位），

  • interactive_credit
    这个变量记录了本进程的”交互程度”，用于精准确认交互式程序

  • nvcsw/nivcsw/cnvcsw/cnivcsw
    进程切换计数。

  • time_slice
    进程的时间片余额，相当于2.4中的counter

  • first_time_slice
    0 或 1，表示是否是第一次拥有时间片（刚创建的进程）

  • run_list
    优先级数组 prio_array 通过此信息找到相关任务信息

  • array
    记录当前 CPU 的活跃就绪队列

  • thread_info
    在 2.4 中，每个进程的 task_struct 都位于该进程核心栈的顶端
    通过栈寄存器 ESP 轻松访问到当前进程的 task_struct。
    在 2.6 中，进程核心栈顶保存的是其中的 thread_info 属性, 需要通过 thread_info->task指针访问一下.

调度策略

V2.6版本增加了SCHED_BATCH调度策略, 普通进程调度策略名称调整了一下, 细化成了SCHED_NORMAL, SCHED_BATCH

#define SCHED_NORMAL       0
#define SCHED_FIFO     1
#define SCHED_RR       2
#define SCHED_BATCH        3

调度算法

对于一个数据结构四种基本操作，访问，搜索，插入，删除，O(1)调度器使用了active，expired 数组， 数组中的元素着保存某一优先级的进程队列指针。系统一共有140个不同的优先级，因此这两个数组大小都是140。并在active，expired队列上各维护了一个bitmap, 在active bitmap 中.
通过公式计算动态优先级和区分交互进程
动态优先级计算公式：
C
dynamic priority = max (100, min ( static priority – bonus +5, 139))
其中bonus 取决于进程的平均睡眠时间。由此可以看出，在linux2.6中，
一个普通进程的优先级和平均睡眠时间的关系为：平均睡眠时间越长，其bonus越大，从而得到更高的优先级。
平均睡眠时间也被用来判断进程是否是一个交互式进程。如果满足下面的公式，进程就被认为是一个交互式进程：

Dynamic priority ≤ 3 x static priority /4 + 28

选择当前最高优先级的进程:
1. 在 active bitmap 里，寻找最高优先级的位置， 找到对应进程队列
2. 从队列中取出一个进程， 如果队列为空，将active bitmap中对应位设置为0；
3. 对于当前执行完的进程，重新计算其优先级，然后将进程放入对应的expired队列；
4. 将进程放入到 expired 相应的队里， 如果其优先级对应的 expired bitmap为0， 将其t置 1。
5. 如果 active bitmap全为零，将 active bitmap 和 expired bitmap交换一下。

为了提高交互式进程的响应时间，O(1)调度器不仅动态地提高该类进程的优先级,还采用一下方法：
1. 每次时钟tick中断中，进程的时间片(time_slice)被减1；
2. 当time_slice为0时，调度器判断当前进程的类型，如果是交互式进程或者实时进程，则重置其时间片并重新插入active数组；
3. 如果不是交互式进程则从active数组中移到expired数组。这样实时进程和交互式进程就总能优先获得CPU。

相关源码

调度相关的函数
scheduler_tick:维持当前最新时间 ;
try_to_wake_up:唤醒睡眠进程;
recalc_task_prio:更新进程动态优先级;
schedule: 选择要被执行的新进程;
load_balance:维持多处理器系统中的运行;

1. 禁用内核抢占, 并初始化current,将cpu本地队列赋值rq;
2. 释放大内核锁release_kernel_lock(prev);
3. sched_clock读取TSC将他转化为纳秒,存放now中,计算prev所用时间片;
4. run_time /= (CURRENT_BONUS(prev) ? : 1); 延时由于睡眠失去互动时间片;
5. spin_lock_irq(&rq->lock); 关掉本地中断,检查PF_DEAD 标识,检查prev是否被终止.
6. 如果是非阻塞状态挂起,将状态设置为TASK_RUNNING,否则从队列删除.
7. 检查运行队列中剩余的可运行进程数,没有可调用的进程, 调用idle_balance从另外的运行队列中迁移一些可运行的进程到本地队列.
8. 如果确实没有可运行任务, active, expired数组交换;
9. 搜索可运行进程, sched_find_first_bit调用bsfl返回32字节中最低位置的下标, 对应优先级最高的活动的进程链表,并获取第一个任务放到next
10. 如果next是普通进程, 如果是交互式进程被唤醒,调将进程插入运行队列开始经过的纳秒数加到进程的平均睡眠时间中.这里给了交互式进程更多的优先级.
11. 进行任务切换, 使用prefetch将CPU控制单元next的进程描述符第一部分字段内容装入硬件高速缓存,用于改善性能.
12. clear_tsk_need_resched清除 TIF_NEED_RESCHED标识,记录cpu正在经理的静止状态
    13.减少prev的平均睡眠时间,减去进程使用时间, 更新时间戳;
    14.如果prev,next不是一个进程,切换context_switch建立next地址空间,做完一系列处理后调用switch_to完成切换.

asmlinkage void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct prio_array *array;
    struct list_head *queue;
    unsigned long long now;
    unsigned long run_time;
    int cpu, idx, new_prio;
    long *switch_count;
    struct rq *rq;

    /*
     * Test if we are atomic.  Since do_exit() needs to call into
     * schedule() atomically, we ignore that path for now.
     * Otherwise, whine if we are scheduling when we should not be.
     */
    if (unlikely(in_atomic() && !current->exit_state)) {
        printk(KERN_ERR "BUG: scheduling while atomic: "
            "%s/0x%08x/%d\n",
            current->comm, preempt_count(), current->pid);
        debug_show_held_locks(current);
        if (irqs_disabled())
            print_irqtrace_events(current);
        dump_stack();
    }
    profile_hit(SCHED_PROFILING, __builtin_return_address(0));

need_resched:
    preempt_disable();
    prev = current;
    release_kernel_lock(prev);
need_resched_nonpreemptible:
    rq = this_rq();

    /*:
     * The idle thread is not allowed to schedule!
     * Remove this check after it has been exercised a bit.
     */
    if (unlikely(prev == rq->idle) && prev->state != TASK_RUNNING) {
        printk(KERN_ERR "bad: scheduling from the idle thread!\n");
        dump_stack();
    }

    schedstat_inc(rq, sched_cnt);
    now = sched_clock();
    if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
        run_time = now - prev->timestamp;
        if (unlikely((long long)(now - prev->timestamp) < 0))
            run_time = 0;
    } else
        run_time = NS_MAX_SLEEP_AVG;

    /*
     * Tasks charged proportionately less run_time at high sleep_avg to
     * delay them losing their interactive status
     */
    run_time /= (CURRENT_BONUS(prev) ? : 1);

    spin_lock_irq(&rq->lock);

    switch_count = &prev->nivcsw;
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        switch_count = &prev->nvcsw;
        if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
                unlikely(signal_pending(prev))))
            prev->state = TASK_RUNNING;
        else {
            if (prev->state == TASK_UNINTERRUPTIBLE)
                rq->nr_uninterruptible++;
            deactivate_task(prev, rq);
        }
    }

    cpu = smp_processor_id();
    if (unlikely(!rq->nr_running)) {
        idle_balance(cpu, rq);
        if (!rq->nr_running) {
            next = rq->idle;
            rq->expired_timestamp = 0;
            goto switch_tasks;
        }
    }

    array = rq->active;
    if (unlikely(!array->nr_active)) {
        /*
         * Switch the active and expired arrays.
         */
        schedstat_inc(rq, sched_switch);
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
    }

    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, struct task_struct, run_list);

    if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
        unsigned long long delta = now - next->timestamp;
        if (unlikely((long long)(now - next->timestamp) < 0))
            delta = 0;

        if (next->sleep_type == SLEEP_INTERACTIVE)
            delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

        array = next->array;
        new_prio = recalc_task_prio(next, next->timestamp + delta);

        if (unlikely(next->prio != new_prio)) {
            dequeue_task(next, array);
            next->prio = new_prio;
            enqueue_task(next, array);
        }
    }
    next->sleep_type = SLEEP_NORMAL;
switch_tasks:
    if (next == rq->idle)
        schedstat_inc(rq, sched_goidle);
    prefetch(next);
    prefetch_stack(next);
    clear_tsk_need_resched(prev);
    rcu_qsctr_inc(task_cpu(prev));

    update_cpu_clock(prev, rq, now);

    prev->sleep_avg -= run_time;
    if ((long)prev->sleep_avg <= 0)
        prev->sleep_avg = 0;
    prev->timestamp = prev->last_ran = now;

    sched_info_switch(prev, next);
    if (likely(prev != next)) {
        next->timestamp = next->last_ran = now;
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        prepare_task_switch(rq, next);
        prev = context_switch(rq, prev, next);
        barrier();
        /*
         * this_rq must be evaluated again because prev may have moved
         * CPUs since it called schedule(), thus the 'rq' on its stack
         * frame will be invalid.
         */
        finish_task_switch(this_rq(), prev);
    } else
        spin_unlock_irq(&rq->lock);

    prev = current;
    if (unlikely(reacquire_kernel_lock(prev) < 0))
        goto need_resched_nonpreemptible;
    preempt_enable_no_resched();
    if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
        goto need_resched;
}

static inline int interactive_sleep(enum sleep_type sleep_type)
{
    return (sleep_type == SLEEP_INTERACTIVE ||
        sleep_type == SLEEP_INTERRUPTED);
}

小细节

• 可以看到一些RCU的操作

    rcu_qsctr_inc(task_cpu(prev));

• 子进程退出时归还时间片

根据 first_time_slice 的值判断自己是否从未重新分配过时间片，如果是，则将自己的剩余时间片返还给父进程（保证不超过 MAX_TIMESLICE）。这个动作使进程不会因创建短期子进程而受到惩罚（与不至于因创建子进程而受到”奖励”相对应）。如果进程已经用完了从父进程那分得的时间片，就没有必要返还了

void release_task(struct task_struct * p)
{
  ...

  sched_exit(p);
  ...
}

void fastcall sched_exit(struct task_struct *p)
{
    unsigned long flags;
    struct rq *rq;

    /*
     * If the child was a (relative-) CPU hog then decrease
     * the sleep_avg of the parent as well.
     */
    rq = task_rq_lock(p->parent, &flags);
    if (p->first_time_slice && task_cpu(p) == task_cpu(p->parent)) {
        p->parent->time_slice += p->time_slice;
        if (unlikely(p->parent->time_slice > task_timeslice(p)))
            p->parent->time_slice = task_timeslice(p);
    }
    if (p->sleep_avg < p->parent->sleep_avg)
        p->parent->sleep_avg = p->parent->sleep_avg /
        (EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
        (EXIT_WEIGHT + 1);
    task_rq_unlock(rq, &flags);
}

小结

O(1)引入了平均等待时间,确定动态优先级,交互进程评价更加细致, 内核支持了抢占, 支持负载的,并支持NUMA结构下的调度.

O(1)里的经验公式比较多, 不能提炼出有效模型.对于后续分析和改进都存在很大障碍.

正如Ingo Monar 在接受采访时说，他设计的 O(1) 调度算法，基本上来自于个人的创意，没有参考市面上以及研究领域中已有的调度算法。从调度器设计上可以看出，2.6 调度系统考虑了很多细节，但总体上并没有清晰的主线，且无法（或者也无意于）在理论上对 O(1) 模型进行性能分析。

公平算法, CFS

数据结构

• sched_class
  const struct sched_class *sched_class;

  sched_class 执行时也是按照此顺序进行

  • stop_sched_class: 最高优先级;

  • dl_sched_class:对应deadline调度策略;

  • rt_sched_class:实时进程调度算法

  • fair_sched_class:普通进程调度策略

  • idle_sched_class:空闲进程调度算法

可以从pick_next_task中看到是从高优先级的调度类到低优先级的调度类依次调用的,保证高优先级任务先执行, 由于普通进程占大多数这里有针对fair_sched_class部分的优化*

调度类，这是一个可扩展的调度程序模块层次结构。这些模块封装了调度策略的详细信息，并由调度程序核心处理，而核心不需要关心他的实现细节。

调度类是通过sched_class结构实现的，该结构包含必须在发生相关事件时调用的函数的钩子。

• 部分hooks(功能实现)的列表：
  • enqueue_task(…)

  在任务进入可运行状态时调用。它将调度实体（任务）放入红黑树中并递增nr_running变量。

  • dequeue_task(…)

  当任务不再可运行时，将调用此函数以使相应的调度实体保持在红黑树之外。它递减nr_running变量。

  • yield_task(…)

  除非打开compat_yield，否则此函数基本上只是一个队列后出队列的队列; 在这种情况下，它将调度实体放在红黑树的最右端。

  • check_preempt_curr(…)

  该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前，CFS 调度程序模块将执行公平性测试。这将驱动唤醒式（wakeup）抢占。

  • pick_next_task(…)

  此功能选择最适合下次运行的任务。

  • set_curr_task(…)

  当任务更改其调度类或更改其任务组时，将调用此函数。

  • task_tick（…）

  该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占。

• task_struct

  • struct sched_entity : cfs调度实体,按照红黑树组织

  • struct sched_rt_entity : 实时调度实体

  • struct sched_dl_entity :dealline调度实体

• struct rq, cfs_rq, rt_rq

  存放所运行任务的队列

调度策略

在目前版本的Linux中进程分为一下两类:

• 实时进程: 需要尽快执行的任务。
  • 实时调度策略
  • SCHED_FIFO
  • SCHED_RR
  • SCHED_DEADLINE

  • 优先级

  • 范围 [0, 99]

• 普通进程:

  • 普通调度策略

  • SCHED_NORMAL

  • SCHED_BATCH

  • SCHED_IDLE

  • 优先级

  • 范围 [100, 139]

调度算法

SD/RSDL算法

• 楼梯调度算法 staircase scheduler: 楼梯算法(SD)在思路上和O(1)算法有很大不同，它抛弃了动态优先级的概念,还淘汰了expire数组，从而简化了代码。它最重要的意义在于证明了完全公平这个思想的可行性。

  • 普通进程：设任务本身优先级为P，当它从第N级台阶开始下楼梯并到达底部后，将回到第N+1级台阶。并且赋予该任务N+1倍的时间片.
  • 实时进程：FIFO, RR调度策略
• RSDL算法:(The Rotating Staircase Deadline Schedule): 重新引入了expire队列，每个优先级都分配一个组时间配置– Tg, 同一优先级的每一个进程都拥有同样的优先级时间配额 -Tp Tp小于进程时间片, 进程自身Tp用完后下降到下一个优先级进程组中。这个过程称 minor rotation, 与SD相同当优先级队列从N降到底部后，再回到N+1台阶开始, 与SD不同的是楼梯底部的低优先级进程必须等待所有的高优先级进程执行完才能获得CPU， RSDL中当高优先级进程用完Tg时，无论该组中是否有Tp尚未完成都会被强制降低到下一个优先级。这样低优先级任务就可以在一个可以预计的未来得到调度.
  当active数组为空或者所有进程将为最低优先级，发生major rotation，active数组与expire数组交换。

CFS调度算法

Completely Fair Scheduler
CFS通过设置vruntime维持某任务的时间量:
与之前调度器不同，它没有将任务维护到运行队列，CFS维护了一个以时间为顺序的红黑树

任务存储在以时间为顺序的红黑树中, 对处理器需求最多的任务 （最低虚拟运行时）存储在树的左侧,处理器需求少的放到右边，调度器选取最左侧的节点进行调整，以便保持公平性，任务通过将其运行时间通过权重计算方法添加到虚拟运行时间中,如果可运行再次插回树中。

C
vruntime + = 实际运行时间 delta_exec * NICE_0_LOAD/权重
这样树右侧的任务就迁移到左侧以保持公平。

相关源码

相关调度算法已经实现模块化, 可以编制指定的调度算法,这点很棒, BFS 调度器移植体验

下面是vruntime设置过程部分代码:

创建新进程会先将vruntime设置为当前进程一致，调用place_entity设置vruntime

vruntime初始化值为当前CPU cfs_rq队列的最小值，通过sched_vslice计算增量

这样即时切换到其他CPU也能保证相对的公平，因为大家的基数一样
如果是初次运行initial == 1并且START_DEBIT标识为1, 通过sched_vslice计算进程vruntime的增量值.

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    ...
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);
    ...
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

通过sched_vslice计算任务的vruntime增量,

/*
 * We calculate the vruntime slice of a to-be-inserted task.
 *
 * vs = s/w
 */
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

calc_delta_fair通过__calc_delta使用权重NICE_0_LOAD计算增加量

/*
 * delta /= w
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

    return delta;
}

计算队列所有任务运行一次的周期, 当前任务数大于sched_nr_latency,使用sched_min_granularity_ns*任务数,否则就使用系统配置的sysctl_sched_latency

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

计算cfs_rq队列上所有调度实体权重之和, 通过__calc_delta()函数计算虚拟时间

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load;

        if (unlikely(!se->on_rq)) {
            lw = cfs_rq->load;

            update_load_add(&lw, se->load.weight);
            load = &lw;
        }
        slice = __calc_delta(slice, se->load.weight, load);
    }
    return slice;
}

运行时间转化为虚拟时间

/*
 * delta_exec * weight / lw.weight
 *   OR
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
 * we're guaranteed shift stays positive because inv_weight is guaranteed to
 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
 *
 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
 * weight/lw.weight <= 1, and therefore our shift will also be positive.
 */
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = WMULT_SHIFT;

    __update_inv_weight(lw);

    if (unlikely(fact >> 32)) {
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }

    /* hint to use a 32x32->64 mul */
    fact = (u64)(u32)fact * lw->inv_weight;

    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }

    return mul_u64_u32_shr(delta_exec, fact, shift);
}

相关

相关OS调度算法

from wiki

应用级别的调度

erlang scheduler: erlang processes 到 threads 的映射;
nginx: HTTP/HTTPS 请求到 processes / application 的映射;
lMemory manager: virtual memory 到 physical memory 的映射;
hypervisor: VM 到硬件的映射;
Amazon Elastic Compute Cloud (EC2): VM 到 hypervisor 間的映射;
Apache Spark: map/reduce job 到计算节点间的映射;
go scheduler go语言调度器

多处理器

多处理器类型:

• Loosely coupled multiprocessor system
• Tightly coupled multiprocessor system
• Homogeneous multiprocessor system
• Heterogeneous multiprocessor system
• Shared memory multiprocessor system
• Distributed memory multiprocessor system
• Uniform memory access (UMA) system
• cc–NUMA system
• Hybrid system – shared system memory for global data and local memory for local data

其中常见有SMP Uniform memory access (UMA) system 和 NUMA:cc-NUMA system, SMP通过总线共享内存, NUMA有自己的本地内存

from wiki

软中断

软中断通常是硬中断服务程序对内核的中断, 在调度代码中可以看到机制:

• bottom half
• task queue
• tasklet

另外还有softirq, 不过作为一种底层机制，很少由内核程序员直接使用

参考/引用

Does /proc/sys/kernel/sched_child_runs_first work?
Kernel Tuning: kernel.sched_child_runs_first
Linus Torvalds 关于 Child-runs-first is now off 回复的邮件
当我谈 scheduling 时我在谈什么？
谈谈调度 – Linux O(1)
Linux 调度器发展简述
The Linux Scheduler
CFS调度器（1）-基本原理
The Linux Scheduler 2.4 vs 2.6
Inside the Linux scheduler
Linux 2.4.x内核软中断机制
Linux 2.4调度系统分析
Linux 2.6 调度系统分析
O(n)、O(1)和CFS调度器
Scheduling in Linux (webserver scheduling)
O(n)、O(1)和CFS调度器(这篇文章讲的很棒)
Linux 核心設計: 不只挑選任務的排程器
Scheduling (computing)
Multiprocessor system architecture
Linux 2.4.x内核软中断机制