• Read the fucking source code! --By 鲁迅

• A picture is worth a thousand words. --By 高尔基

1. Kernel版本：4.14

2. ARM64处理器，Contex-A53，双核

3. 使用工具：Source Insight 3.5， Visio

1. 概述

2. 概念

2.1 进程

• 从教科书上，我们都能知道：进程是资源分配的最小单位，而线程是CPU调度的的最小单位。

• 进程不仅包括可执行程序的代码段，还包括一系列的资源，比如：打开的文件、内存、CPU时间、信号量、多个执行线程流等等。而线程可以共享进程内的资源空间。

• 在Linux内核中，进程和线程都使用 struct task_struct 结构来进行抽象描述。

• 进程的虚拟地址空间分为用户虚拟地址空间和内核虚拟地址空间，所有进程共享内核虚拟地址空间，没有用户虚拟地址空间的进程称为内核线程。

struct task_struct {
  /* ... */
    
  /* 进程状态 */
  volatile long			state;

  /* 调度优先级相关，策略相关 */
	int				prio;
	int				static_prio;
	int				normal_prio;
	unsigned int			rt_priority;
  unsigned int			policy;
    
  /* 调度类，调度实体相关，任务组相关等 */
  const struct sched_class	*sched_class;
	struct sched_entity		se;
	struct sched_rt_entity		rt;
#ifdef CONFIG_CGROUP_SCHED
	struct task_group		*sched_task_group;
#endif
	struct sched_dl_entity		dl;
    
  /* 进程之间的关系相关 */
  /* Real parent process: */
	struct task_struct __rcu	*real_parent;

	/* Recipient of SIGCHLD, wait4() reports: */
	struct task_struct __rcu	*parent;

	/*
	 * Children/sibling form the list of natural children:
	 */
	struct list_head		children;
	struct list_head		sibling;
	struct task_struct		*group_leader;
    
   /* ... */
}

2.2 进程状态

• 上图中左侧为操作系统中通俗的进程三状态模型，右侧为 Linux 对应的进程状态切换。每一个标志描述了进程的当前状态，这些状态都是互斥的；

• Linux 中的就绪态和运行态对应的都是TASK_RUNNING标志位，就绪态表示进程正处在队列中，尚未被调度；运行态则表示进程正在 CPU 上运行；

/* Used in tsk->state: */
#define TASK_RUNNING			    0x0000
#define TASK_INTERRUPTIBLE		0x0001
#define TASK_UNINTERRUPTIBLE	0x0002

/* Used in tsk->exit_state: */
#define EXIT_DEAD			  0x0010
#define EXIT_ZOMBIE			0x0020
#define EXIT_TRACE			(EXIT_ZOMBIE | EXIT_DEAD)

/* Used in tsk->state again: */
#define TASK_PARKED			0x0040
#define TASK_DEAD			  0x0080
#define TASK_WAKEKILL		0x0100
#define TASK_WAKING			0x0200
#define TASK_NOLOAD			0x0400
#define TASK_NEW			  0x0800
#define TASK_STATE_MAX	0x1000

/* Convenience macros for the sake of set_current_state: */
#define TASK_KILLABLE			(TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED			(TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_TRACED			  (TASK_WAKEKILL | __TASK_TRACED)

#define TASK_IDLE			    (TASK_UNINTERRUPTIBLE | TASK_NOLOAD)

2.3 scheduler 调度器

• 所谓调度，就是按照某种调度的算法，从进程的就绪队列中选取进程并分配CPU，主要是协调CPU等的资源使用。进程调度的目标是最大限度利用CPU时间。

1. Stop调度器， stop_sched_class：优先级最高的调度类，可以抢占其他所有进程，不能被其他进程抢占；

2. Deadline调度器， dl_sched_class：使用红黑树，把进程按照绝对截止期限进行排序，选择最小进程进行调度运行；

3. RT调度器， rt_sched_class：实时调度器，为每个优先级维护一个队列；

4. CFS调度器， cfs_sched_class：完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念；

5. IDLE-Task调度器， idle_sched_class：空闲调度器，每个CPU都会有一个 idle 线程，当没有其他进程可以调度时，调度运行 idle 线程；

• SCHED_DEADLINE：限期进程调度策略，使 task 选择Deadline调度器来调度运行；

• SCHED_RR：实时进程调度策略，时间片轮转，进程用完时间片后加入优先级对应运行队列的尾部，把 CPU 让给同优先级的其他进程；

• SCHED_FIFO：实时进程调度策略，先进先出调度没有时间片，没有更高优先级的情况下，只能等待主动让出 CPU；

• SCHED_NORMAL：普通进程调度策略，使 task 选择CFS调度器来调度运行；

• SCHED_BATCH：普通进程调度策略，批量处理，使 task 选择CFS调度器来调度运行；

• SCHED_IDLE：普通进程调度策略，使 task 以最低优先级选择CFS调度器来调度运行；

2.4 runqueue 运行队列

• 每个 CPU 都有一个运行队列，每个调度器都作用于运行队列；

• 分配给 CPU 的 task，作为调度实体加入到运行队列中；

• task 首次运行时，如果可能，尽量将它加入到父 task 所在的运行队列中（分配给相同的CPU，缓存 affinity 会更高，性能会有改善）；

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
	/* runqueue lock: */
	raw_spinlock_t lock;

	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned int nr_running;

  /* 三个调度队列：CFS调度，RT调度，DL调度 */
	struct cfs_rq cfs;
	struct rt_rq rt;
	struct dl_rq dl;

  /* stop指向迁移内核线程， idle指向空闲内核线程 */
  struct task_struct *curr, *idle, *stop;

  /* ... */
}

2.5 task_group 任务分组

• 利用任务分组的机制，可以设置或限制任务组对 CPU 的利用率，比如将某些任务限制在某个区间内，从而不去影响其他任务的执行效率；

• 引入task_group后，调度器的调度对象不仅仅是进程了，Linux 内核抽象出了 sched_entity/sched_rt_entity/sched_dl_entity 描述调度实体，调度实体可以是 进程 或 task_group；

• 使用数据结构 struct task_group 来描述任务组，任务组在每个 CPU 上都会维护一个 CFS调度实体、CFS运行队列，RT调度实体，RT运行队列；

/* task group related information */
struct task_group {
  /* ... */

  /* 为每个CPU都分配一个CFS调度实体和CFS运行队列 */
#ifdef CONFIG_FAIR_GROUP_SCHED
	/* schedulable entities of this group on each cpu */
	struct sched_entity **se;
	/* runqueue "owned" by this group on each cpu */
	struct cfs_rq **cfs_rq;
	unsigned long shares;
#endif

  /* 为每个CPU都分配一个RT调度实体和RT运行队列 */
#ifdef CONFIG_RT_GROUP_SCHED
	struct sched_rt_entity **rt_se;
	struct rt_rq **rt_rq;

	struct rt_bandwidth rt_bandwidth;
#endif

  /* task_group之间的组织关系 */
	struct rcu_head rcu;
	struct list_head list;

	struct task_group *parent;
	struct list_head siblings;
	struct list_head children;

  /* ... */
};

3. 调度程序

1. 主动调度 - schedule()



• schedule()函数，是进程调度的核心函数，大体的流程如上图所示。
• 核心的逻辑：选择另外一个进程来替换掉当前运行的进程。
• 进程的选择是通过进程所使用的调度器中的 pick_next_task 函数来实现的，不同的调度器实现的方法不一样；
• 进程的替换是通过 context_switch() 来完成切换的，具体的细节后续的文章再深入分析。

2. 周期调度 - schedule_tick()



• 时钟中断处理程序中，调用 schedule_tick() 函数；
• 时钟中断是调度器的脉搏，内核依靠周期性的时钟来处理器CPU的控制权；
• 时钟中断处理程序，检查当前进程的执行时间是否超额，如果超额则设置重新调度标志(_TIF_NEED_RESCHED)；
• 时钟中断处理函数返回时，被中断的进程如果在用户模式下运行，需要检查是否有重新调度标志，设置了则调用schedule()调度；

3. 高精度时钟调度 - hrtick()



• 高精度时钟调度，与周期性调度类似，不同点在于周期调度的精度为 ms 级别，而高精度调度的精度为 ns 级别；
• 高精度时钟调度，需要有对应的硬件支持；

4. 进程唤醒时调度 - wake_up_process()



• 唤醒进程时调用wake_up_process()函数，被唤醒的进程可能抢占当前的进程；

参考文档