背景

• 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調(diào)度器的系列研究了。本文也會從一些基礎(chǔ)的概念及數(shù)據(jù)結(jié)構(gòu)入手，先打造一個粗略的輪廓，后續(xù)的文章將逐漸深入。

2. 概念

2.1 進程

• 從教科書上，我們都能知道：進程是資源分配的最小單位，而線程是CPU調(diào)度的的最小單位。

• 進程不僅包括可執(zhí)行程序的代碼段，還包括一系列的資源，比如：打開的文件、內(nèi)存、CPU時間、信號量、多個執(zhí)行線程流等等。而線程可以共享進程內(nèi)的資源空間。

• 在Linux內(nèi)核中，進程和線程都使用struct task_struct結(jié)構(gòu)來進行抽象描述。

• 進程的虛擬地址空間分為用戶虛擬地址空間和內(nèi)核虛擬地址空間，所有進程共享內(nèi)核虛擬地址空間，沒有用戶虛擬地址空間的進程稱為內(nèi)核線程。

Linux內(nèi)核使用task_struct結(jié)構(gòu)來抽象，該結(jié)構(gòu)包含了進程的各類信息及所擁有的資源，比如進程的狀態(tài)、打開的文件、地址空間信息、信號資源等等。task_struct結(jié)構(gòu)很復(fù)雜，下邊只針對與調(diào)度相關(guān)的某些字段進行介紹。

struct task_struct {/* ... *//* 進程狀態(tài) */volatile long state;/* 調(diào)度優(yōu)先級相關(guān)，策略相關(guān) */int prio;int static_prio;int normal_prio;unsigned int rt_priority;unsigned int policy;/* 調(diào)度類，調(diào)度實體相關(guān)，任務(wù)組相關(guān)等 */const struct sched_class *sched_class;struct sched_entity se;struct sched_rt_entity rt; #ifdef CONFIG_CGROUP_SCHEDstruct task_group *sched_task_group; #endifstruct sched_dl_entity dl;/* 進程之間的關(guān)系相關(guān) *//* 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 進程狀態(tài)

• 上圖中左側(cè)為操作系統(tǒng)中通俗的進程三狀態(tài)模型，右側(cè)為Linux對應(yīng)的進程狀態(tài)切換。每一個標(biāo)志描述了進程的當(dāng)前狀態(tài)，這些狀態(tài)都是互斥的；

• Linux中的就緒態(tài)和運行態(tài)對應(yīng)的都是TASK_RUNNING標(biāo)志位，就緒態(tài)表示進程正處在隊列中，尚未被調(diào)度；運行態(tài)則表示進程正在CPU上運行；

內(nèi)核中主要的狀態(tài)字段定義如下

/* 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 調(diào)度器

• 所謂調(diào)度，就是按照某種調(diào)度的算法，從進程的就緒隊列中選取進程分配CPU，主要是協(xié)調(diào)對CPU等的資源使用。進程調(diào)度的目標(biāo)是最大限度利用CPU時間。

內(nèi)核默認(rèn)提供了5個調(diào)度器，Linux內(nèi)核使用struct sched_class來對調(diào)度器進行抽象：

Stop調(diào)度器， stop_sched_class：優(yōu)先級最高的調(diào)度類，可以搶占其他所有進程，不能被其他進程搶占；

Deadline調(diào)度器， dl_sched_class：使用紅黑樹，把進程按照絕對截止期限進行排序，選擇最小進程進行調(diào)度運行；

RT調(diào)度器， rt_sched_class：實時調(diào)度器，為每個優(yōu)先級維護一個隊列；

CFS調(diào)度器， cfs_sched_class：完全公平調(diào)度器，采用完全公平調(diào)度算法，引入虛擬運行時間概念；

IDLE-Task調(diào)度器， idle_sched_class：空閑調(diào)度器，每個CPU都會有一個idle線程，當(dāng)沒有其他進程可以調(diào)度時，調(diào)度運行idle線程；

Linux內(nèi)核提供了一些調(diào)度策略供用戶程序來選擇調(diào)度器，其中Stop調(diào)度器和IDLE-Task調(diào)度器，僅由內(nèi)核使用，用戶無法進行選擇：

• SCHED_DEADLINE：限期進程調(diào)度策略，使task選擇Deadline調(diào)度器來調(diào)度運行；

• SCHED_RR：實時進程調(diào)度策略，時間片輪轉(zhuǎn)，進程用完時間片后加入優(yōu)先級對應(yīng)運行隊列的尾部，把CPU讓給同優(yōu)先級的其他進程；

• SCHED_FIFO：實時進程調(diào)度策略，先進先出調(diào)度沒有時間片，沒有更高優(yōu)先級的情況下，只能等待主動讓出CPU；

• SCHED_NORMAL：普通進程調(diào)度策略，使task選擇CFS調(diào)度器來調(diào)度運行；

• SCHED_BATCH：普通進程調(diào)度策略，批量處理，使task選擇CFS調(diào)度器來調(diào)度運行；

• SCHED_IDLE：普通進程調(diào)度策略，使task以最低優(yōu)先級選擇CFS調(diào)度器來調(diào)度運行；

2.4 runqueue 運行隊列

• 每個CPU都有一個運行隊列，每個調(diào)度器都作用于運行隊列；

• 分配給CPU的task，作為調(diào)度實體加入到運行隊列中；

• task首次運行時，如果可能，盡量將它加入到父task所在的運行隊列中（分配給相同的CPU，緩存affinity會更高，性能會有改善）；

Linux內(nèi)核使用struct rq結(jié)構(gòu)來描述運行隊列，關(guān)鍵字段如下：

/** 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;/* 三個調(diào)度隊列：CFS調(diào)度，RT調(diào)度，DL調(diào)度 */struct cfs_rq cfs;struct rt_rq rt;struct dl_rq dl;/* stop指向遷移內(nèi)核線程， idle指向空閑內(nèi)核線程 */struct task_struct *curr, *idle, *stop;/* ... */ }

2.5 task_group 任務(wù)分組

• 利用任務(wù)分組的機制，可以設(shè)置或限制任務(wù)組對CPU的利用率，比如將某些任務(wù)限制在某個區(qū)間內(nèi)，從而不去影響其他任務(wù)的執(zhí)行效率；

• 引入task_group后，調(diào)度器的調(diào)度對象不僅僅是進程了，Linux內(nèi)核抽象出了sched_entity/sched_rt_entity/sched_dl_entity描述調(diào)度實體，調(diào)度實體可以是進程或task_group；

• 使用數(shù)據(jù)結(jié)構(gòu)struct task_group來描述任務(wù)組，任務(wù)組在每個CPU上都會維護一個CFS調(diào)度實體、CFS運行隊列，RT調(diào)度實體，RT運行隊列；

Linux內(nèi)核使用struct task_group來描述任務(wù)組，關(guān)鍵的字段如下：

/* task group related information */ struct task_group {/* ... *//* 為每個CPU都分配一個CFS調(diào)度實體和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調(diào)度實體和RT運行隊列 */ #ifdef CONFIG_RT_GROUP_SCHEDstruct sched_rt_entity **rt_se;struct rt_rq **rt_rq;struct rt_bandwidth rt_bandwidth; #endif/* task_group之間的組織關(guān)系 */struct rcu_head rcu;struct list_head list;struct task_group *parent;struct list_head siblings;struct list_head children;/* ... */ };

3. 調(diào)度程序

調(diào)度程序依靠幾個函數(shù)來完成調(diào)度工作的，下邊將介紹幾個關(guān)鍵的函數(shù)。

主動調(diào)度 - schedule()

• schedule()函數(shù)，是進程調(diào)度的核心函數(shù)，大體的流程如上圖所示。

• 核心的邏輯：選擇另外一個進程來替換掉當(dāng)前運行的進程。進程的選擇是通過進程所使用的調(diào)度器中的pick_next_task函數(shù)來實現(xiàn)的，不同的調(diào)度器實現(xiàn)的方法不一樣；進程的替換是通過context_switch()來完成切換的，具體的細(xì)節(jié)后續(xù)的文章再深入分析。

周期調(diào)度 - schedule_tick()

• 時鐘中斷處理程序中，調(diào)用schedule_tick()函數(shù)；

• 時鐘中斷是調(diào)度器的脈搏，內(nèi)核依靠周期性的時鐘來處理器CPU的控制權(quán)；

• 時鐘中斷處理程序，檢查當(dāng)前進程的執(zhí)行時間是否超額，如果超額則設(shè)置重新調(diào)度標(biāo)志(_TIF_NEED_RESCHED)；

• 時鐘中斷處理函數(shù)返回時，被中斷的進程如果在用戶模式下運行，需要檢查是否有重新調(diào)度標(biāo)志，設(shè)置了則調(diào)用schedule()調(diào)度；

高精度時鐘調(diào)度 - hrtick()

• 高精度時鐘調(diào)度，與周期性調(diào)度類似，不同點在于周期調(diào)度的精度為ms級別，而高精度調(diào)度的精度為ns級別；

• 高精度時鐘調(diào)度，需要有對應(yīng)的硬件支持；

進程喚醒時調(diào)度 - wake_up_process()

• 喚醒進程時調(diào)用wake_up_process()函數(shù)，被喚醒的進程可能搶占當(dāng)前的進程；

上述講到的幾個函數(shù)都是常用于調(diào)度時調(diào)用。此外，在創(chuàng)建新進程時，或是在內(nèi)核搶占時，也會出現(xiàn)一些調(diào)度點。

本文只是粗略的介紹了一個大概，后續(xù)將針對某些模塊進行更加深入的分析，敬請期待。

---

推薦閱讀：

專輯|Linux文章匯總

專輯|程序人生

嵌入式Linux

微信掃描二維碼，關(guān)注我的公眾號

總結(jié)

以上是生活随笔為你收集整理的Linux进程调度器-基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。