Linux組調(diào)度是什么？Linux組調(diào)度原理圖你知道嗎？Linux組調(diào)度是如何實(shí)現(xiàn)的？

在介紹 組調(diào)度 前，我們先來(lái)重溫下什么是 進(jìn)程調(diào)度。

　　本文基于 Linux-2.6.26 版本

　　什么是進(jìn)程調(diào)度

　　一般來(lái)說(shuō)，在操作系統(tǒng)中會(huì)運(yùn)行多個(gè)進(jìn)程（幾個(gè)到幾千個(gè)不等），但一臺(tái)計(jì)算機(jī)的 CPU 資源是有限的，如 8 核的 CPU 只能同時(shí)運(yùn)行 8 個(gè)進(jìn)程。那么當(dāng)進(jìn)程數(shù)大于 CPU 核心數(shù)時(shí)，操作系統(tǒng)是如何同時(shí)運(yùn)行這些進(jìn)程的呢？

　　這里就涉及 進(jìn)程調(diào)度 問(wèn)題。

　　操作系統(tǒng)運(yùn)行進(jìn)程的時(shí)候，是按 時(shí)間片 來(lái)運(yùn)行的。時(shí)間片 是指一段很短的時(shí)間段（如20毫秒），操作系統(tǒng)會(huì)為每個(gè)進(jìn)程分配一些時(shí)間片。當(dāng)進(jìn)程的時(shí)間片用完后，操作系統(tǒng)將會(huì)把當(dāng)前運(yùn)行的進(jìn)程切換出去，然后從進(jìn)程隊(duì)列中選擇一個(gè)合適的進(jìn)程運(yùn)行，這就是所謂的 進(jìn)程調(diào)度。如下圖所示：

　　什么是組調(diào)度

　　一般來(lái)說(shuō)，操作系統(tǒng)調(diào)度的實(shí)體是 進(jìn)程，也就是說(shuō)按進(jìn)程作為單位來(lái)調(diào)度。但如果按進(jìn)程作為調(diào)度實(shí)體，就會(huì)出現(xiàn)以下情況：

　　Linux 是一個(gè)支持多用戶的操作系統(tǒng)，如果 A 用戶運(yùn)行了 10 個(gè)進(jìn)程，而 B 用戶只運(yùn)行了 2 個(gè)進(jìn)程，那么就會(huì)出現(xiàn) A 用戶使用的 CPU 時(shí)間是 B 用戶的 5 倍。如果 A 用戶和 B 用戶都是花同樣的錢(qián)來(lái)買(mǎi)的虛擬主機(jī)，那么對(duì) B 用戶來(lái)說(shuō)是非常不公平的。

　　為了解決這個(gè)問(wèn)題，Linux 實(shí)現(xiàn)了 組調(diào)度 這個(gè)功能。那么什么是 組調(diào)度 呢？

　　組調(diào)度 的實(shí)質(zhì)是：調(diào)度時(shí)候不再以進(jìn)程作為調(diào)度實(shí)體，而是以 進(jìn)程組 作為調(diào)度實(shí)體。比如上面的例子，可以把 A 用戶運(yùn)行的進(jìn)程劃分為 進(jìn)程組A，而 B 用戶運(yùn)行的進(jìn)程劃分為 進(jìn)程組B。

　　調(diào)度的時(shí)候，進(jìn)程組A 和 進(jìn)程組B 分配到相同的可運(yùn)行 時(shí)間片，如 進(jìn)程組A 和 進(jìn)程組B 各分配到 100 毫秒的可運(yùn)行時(shí)間片。由于 進(jìn)程組A 有 10 個(gè)進(jìn)程，所以每個(gè)進(jìn)程分配到的可運(yùn)行時(shí)間片為 10 毫秒。而 進(jìn)程組B 只有 2 個(gè)進(jìn)程，所以每個(gè)進(jìn)程分配到的可運(yùn)行時(shí)間片為 50 毫秒。

　　下圖是 組調(diào)度 的原理：

　　如上圖所示，當(dāng)內(nèi)核進(jìn)行調(diào)度時(shí)，首先以 進(jìn)程組 作為調(diào)度實(shí)體。當(dāng)選擇出最優(yōu)的 進(jìn)程組 后，再?gòu)?進(jìn)程組 中選擇出最優(yōu)的進(jìn)程進(jìn)行運(yùn)行，而被切換出來(lái)的進(jìn)程將會(huì)放置回原來(lái)的 進(jìn)程組。

　　由于 組調(diào)度 是建立在 cgroup 機(jī)制之上的，而 cgroup 又是基于 虛擬文件系統(tǒng)，所以 進(jìn)程組 是以樹(shù)結(jié)構(gòu)存在的。也就是說(shuō)，進(jìn)程組 除了可以包含進(jìn)程，還可以包含進(jìn)程組。如下圖所示：

　　cgroup 相關(guān)的知識(shí)點(diǎn)可以參考文章：《cgroup介紹》 和 《cgroup實(shí)現(xiàn)原理》

　　Linux 在調(diào)度的時(shí)候，首先會(huì)根據(jù) 完全公平調(diào)度算法 從根進(jìn)程組中篩選出一個(gè)最優(yōu)的進(jìn)程或者進(jìn)程組進(jìn)行調(diào)度。

　　如果篩選出來(lái)的是進(jìn)程，那么可以直接把當(dāng)前運(yùn)行的進(jìn)程切換到篩選出來(lái)的進(jìn)程運(yùn)行即可。

　　如果篩選出來(lái)的是進(jìn)程組，那么就繼續(xù)根據(jù) 完全公平調(diào)度算法 從進(jìn)程組中篩選出一個(gè)最優(yōu)的進(jìn)程或者進(jìn)程組進(jìn)行調(diào)度（重復(fù)進(jìn)行第一步操作），如此類推。

　　組調(diào)度實(shí)現(xiàn)

　　接下來(lái)，我們將介紹 組調(diào)度 是如何實(shí)現(xiàn)的。在分析之前，為了對(duì) 完全公平調(diào)度算法 有個(gè)大體了解，建議先看看這篇文章：《Linux完全公平調(diào)度算法 》。

　　1. 進(jìn)程組

　　在 Linux 內(nèi)核中，使用 task_group 結(jié)構(gòu)表示一個(gè)進(jìn)程組。其定義如下：

　　下面介紹一下 task_group 結(jié)構(gòu)各個(gè)字段的作用：

　　se：完全公平調(diào)度算法 是以 sched_entity 結(jié)構(gòu)作為調(diào)度實(shí)體（也就是說(shuō)運(yùn)行隊(duì)列中的元素都是 sched_entity 結(jié)構(gòu)），而 sched_entity 結(jié)構(gòu)既能代表一個(gè)進(jìn)程，也能代表一個(gè)進(jìn)程組。這個(gè)字段主要作用是，將進(jìn)程組放置到運(yùn)行隊(duì)列中進(jìn)行調(diào)度。由于進(jìn)程組中的進(jìn)程可能會(huì)在不同的 CPU 上運(yùn)行，所以這里為每個(gè) CPU 分配一個(gè) sched_entity 結(jié)構(gòu)。

　　cfs_rq：完全公平調(diào)度算法 的運(yùn)行隊(duì)列。完全公平調(diào)度算法 在調(diào)度時(shí)是通過(guò) cfs_rq 結(jié)構(gòu)完成的，cfs_rq 結(jié)構(gòu)使用一棵紅黑樹(shù)將需要調(diào)度的進(jìn)程或者進(jìn)程組組織起來(lái)，然后選擇最左端的節(jié)點(diǎn)作為要運(yùn)行的進(jìn)程或進(jìn)程組，詳情可以參考文章：《Linux完全公平調(diào)度算法》。由于進(jìn)程組可能在不同的 CPU 上調(diào)度，所以進(jìn)程組也為每個(gè) CPU 分配一個(gè)運(yùn)行隊(duì)列。

　　shares：進(jìn)程組的權(quán)重，用于計(jì)算當(dāng)前進(jìn)程組的可運(yùn)行時(shí)間片。

　　parent、siblings、children：用于將系統(tǒng)中所有的進(jìn)程組組成一棵親屬關(guān)系樹(shù)。

　　task_group、sched_entity 和 cfs_rq 這三個(gè)結(jié)構(gòu)的關(guān)系如下圖所示：

　　從上圖可以看出，每個(gè)進(jìn)程組都為每個(gè) CPU 分配一個(gè)可運(yùn)行隊(duì)列，可運(yùn)行隊(duì)列中保存著可運(yùn)行的進(jìn)程和進(jìn)程組。Linux 調(diào)度的時(shí)候，就是從上而下（從根進(jìn)程組開(kāi)始）地篩選出最優(yōu)的進(jìn)程進(jìn)行運(yùn)行。

　　2. 調(diào)度過(guò)程

　　當(dāng) Linux 需要進(jìn)行進(jìn)程調(diào)度時(shí)，會(huì)調(diào)用 schedule() 函數(shù)來(lái)完成，其實(shí)現(xiàn)如下（經(jīng)精簡(jiǎn)后）：

　　schedule() 函數(shù)會(huì)調(diào)用 pick_next_task() 函數(shù)來(lái)篩選最優(yōu)的可運(yùn)行進(jìn)程，我們來(lái)看看 pick_next_task() 函數(shù)的實(shí)現(xiàn)過(guò)程：

　　從 pick_next_task() 函數(shù)的實(shí)現(xiàn)來(lái)看，其最終會(huì)調(diào)用 完全公平調(diào)度算法 的 pick_next_task() 方法來(lái)完成篩選工作，我們來(lái)看看這個(gè)方法的實(shí)現(xiàn)：

　　我們來(lái)分析下 pick_next_task_fair() 函數(shù)到流程：

　　從根進(jìn)程組中篩選出最優(yōu)的可運(yùn)行實(shí)體（進(jìn)程或進(jìn)程組）。

　　如果篩選出來(lái)的實(shí)體是進(jìn)程，那么直接返回這個(gè)進(jìn)程。

　　如果篩選出來(lái)的實(shí)體是進(jìn)程組，那么將會(huì)繼續(xù)對(duì)這個(gè)進(jìn)程組中的可運(yùn)行隊(duì)列進(jìn)行篩選，直至篩選出一個(gè)可運(yùn)行的進(jìn)程。

　　怎么區(qū)分 sched_entity 實(shí)體是進(jìn)程或者進(jìn)程組？sched_entity 結(jié)構(gòu)中有個(gè) my_q 的字段，當(dāng)這個(gè)字段設(shè)置為 NULL 時(shí)，說(shuō)明這個(gè)實(shí)體是一個(gè)進(jìn)程。如果這個(gè)字段指向一個(gè)可運(yùn)行隊(duì)列時(shí)，說(shuō)明這個(gè)實(shí)體是一個(gè)進(jìn)程組。

　更多信息可以來(lái)這里獲取==>>電子技術(shù)應(yīng)用-AET<<