背景

Read the fucking source code! --By 魯迅
A picture is worth a thousand words. --By 高爾基

說明：

Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio

1. 概述

從這篇文章開始，將開始Linux調度器的系列研究了，
本文也會從一些基礎的概念及資料結構入手，先打造一個粗略的輪廓，后續的文章將逐漸深入，

2. 概念

2.1 行程

從教科書上，我們都能知道：行程是資源分配的最小單位，而執行緒是CPU調度的的最小單位，
行程不僅包括可執行程式的代碼段，還包括一系列的資源，比如：打開的檔案、記憶體、CPU時間、信號量、多個執行執行緒流等等，而執行緒可以共享行程內的資源空間，
在Linux內核中，行程和執行緒都使用struct task_struct結構來進行抽象描述，
行程的虛擬地址空間分為用戶虛擬地址空間和內核虛擬地址空間，所有行程共享內核虛擬地址空間，沒有用戶虛擬地址空間的行程稱為內核執行緒，

Linux內核使用task_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時間，

內核默認提供了5個調度器，Linux內核使用struct sched_class來對調度器進行抽象：

Stop調度器， stop_sched_class：優先級最高的調度類，可以搶占其他所有行程，不能被其他行程搶占；
Deadline調度器， dl_sched_class：使用紅黑樹，把行程按照絕對截止期限進行排序，選擇最小行程進行調度運行；
RT調度器， rt_sched_class：實時調度器，為每個優先級維護一個佇列；
CFS調度器， cfs_sched_class：完全公平調度器，采用完全公平調度演算法，引入虛擬運行時間概念；
IDLE-Task調度器， idle_sched_class：空閑調度器，每個CPU都會有一個idle執行緒，當沒有其他行程可以調度時，調度運行idle執行緒；

Linux內核提供了一些調度策略供用戶程式來選擇調度器，其中Stop調度器和IDLE-Task調度器，僅由內核使用，用戶無法進行選擇：

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會更高，性能會有改善）；

Linux內核使用struct rq結構來描述運行佇列，關鍵欄位如下：

/*
 * 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運行佇列；

Linux內核使用struct task_group來描述任務組，關鍵的欄位如下：

/* 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. 調度程式

調度程式依靠幾個函式來完成調度作業的，下邊將介紹幾個關鍵的函式，

主動調度 - schedule()

schedule()函式，是行程調度的核心函式，大體的流程如上圖所示，
核心的邏輯：選擇另外一個行程來替換掉當前運行的行程，行程的選擇是通過行程所使用的調度器中的pick_next_task函式來實作的，不同的調度器實作的方法不一樣；行程的替換是通過context_switch()來完成切換的，具體的細節后續的文章再深入分析，