CPU是如何調(diào)度任務(wù)的？

前言

你清楚下面這幾個(gè)問題嗎？

有了內(nèi)存，為什么還需要 CPU Cache？

CPU 是怎么讀寫數(shù)據(jù)的？

如何讓 CPU 能讀取數(shù)據(jù)更快一些？

CPU 偽共享是如何發(fā)生的？又該如何避免？

CPU 是如何調(diào)度任務(wù)的？如果你的任務(wù)對響應(yīng)要求很高，你希望它總是能被先調(diào)度，這該怎么辦？

…

這篇，我們就來回答這些問題。

正文

CPU 如何讀寫數(shù)據(jù)的？

先來認(rèn)識 CPU 的架構(gòu)，只有理解了 CPU 的 架構(gòu)，才能更好地理解 CPU 是如何讀寫數(shù)據(jù)的，對于現(xiàn)代 CPU 的架構(gòu)圖如下：

可以看到，一個(gè) CPU 里通常會有多個(gè) CPU 核心，比如上圖中的 1 號和 2 號 CPU 核心，并且每個(gè) CPU 核心都有自己的 L1 Cache 和 L2 Cache，而 L1 Cache 通常分為 dCache（數(shù)據(jù)緩存） 和 iCache（指令緩存），L3 Cache 則是多個(gè)核心共享的，這就是 CPU 典型的緩存層次。

上面提到的都是 CPU 內(nèi)部的 Cache，放眼外部的話，還會有內(nèi)存和硬盤，這些存儲設(shè)備共同構(gòu)成了金字塔存儲層次。如下圖所示：

從上圖也可以看到，從上往下，存儲設(shè)備的容量會越大，而訪問速度會越慢。至于每個(gè)存儲設(shè)備的訪問延時(shí)，你可以看下圖的表格：

你可以看到， CPU 訪問 L1 Cache 速度比訪問內(nèi)存快 100 倍，這就是為什么 CPU 里會有 L1~L3 Cache 的原因，目的就是把 Cache 作為 CPU 與內(nèi)存之間的緩存層，以減少對內(nèi)存的訪問頻率。

CPU 從內(nèi)存中讀取數(shù)據(jù)到 Cache 的時(shí)候，并不是一個(gè)字節(jié)一個(gè)字節(jié)讀取，而是一塊一塊的方式來讀取數(shù)據(jù)的，這一塊一塊的數(shù)據(jù)被稱為 CPU Line（緩存行），所以CPU Line 是 CPU 從內(nèi)存讀取數(shù)據(jù)到 Cache 的單位。

至于 CPU Line 大小，在 Linux 系統(tǒng)可以用下面的方式查看到，你可以看我服務(wù)器的 L1 Cache Line 大小是 64 字節(jié)，也就意味著L1 Cache 一次載入數(shù)據(jù)的大小是 64 字節(jié)。

那么對數(shù)組的加載， CPU 就會加載數(shù)組里面連續(xù)的多個(gè)數(shù)據(jù)到 Cache 里，因此我們應(yīng)該按照物理內(nèi)存地址分布的順序去訪問元素，這樣訪問數(shù)組元素的時(shí)候，Cache 命中率就會很高，于是就能減少從內(nèi)存讀取數(shù)據(jù)的頻率， 從而可提高程序的性能。

但是，在我們不使用數(shù)組，而是使用單獨(dú)的變量的時(shí)候，則會有 Cache 偽共享的問題，Cache 偽共享問題上是一個(gè)性能殺手，我們應(yīng)該要規(guī)避它。

接下來，就來看看 Cache 偽共享是什么？又如何避免這個(gè)問題？

現(xiàn)在假設(shè)有一個(gè)雙核心的 CPU，這兩個(gè) CPU 核心并行運(yùn)行著兩個(gè)不同的線程，它們同時(shí)從內(nèi)存中讀取兩個(gè)不同的數(shù)據(jù)，分別是類型為long的變量 A 和 B，這個(gè)兩個(gè)數(shù)據(jù)的地址在物理內(nèi)存上是連續(xù)的，如果 Cahce Line 的大小是 64 字節(jié)，并且變量 A 在 Cahce Line 的開頭位置，那么這兩個(gè)數(shù)據(jù)是位于同一個(gè) Cache Line 中，又因?yàn)?CPU Line 是 CPU 從內(nèi)存讀取數(shù)據(jù)到 Cache 的單位，所以這兩個(gè)數(shù)據(jù)會被同時(shí)讀入到了兩個(gè) CPU 核心中各自 Cache 中。

我們來思考一個(gè)問題，如果這兩個(gè)不同核心的線程分別修改不同的數(shù)據(jù)，比如 1 號 CPU 核心的線程只修改了 變量 A，或 2 號 CPU 核心的線程的線程只修改了變量 B，會發(fā)生什么呢？

分析偽共享的問題

現(xiàn)在我們結(jié)合保證多核緩存一致的 MESI 協(xié)議，來說明這一整個(gè)的過程，如果你還不知道 MESI 協(xié)議，你可以看我這篇文章「10 張圖打開 CPU 緩存一致性的大門」。

①. 最開始變量 A 和 B 都還不在 Cache 里面，假設(shè) 1 號核心綁定了線程 A，2 號核心綁定了線程 B，線程 A 只會讀寫變量 A，線程 B 只會讀寫變量 B。

②. 1 號核心讀取變量 A，由于 CPU 從內(nèi)存讀取數(shù)據(jù)到 Cache 的單位是 Cache Line，也正好變量 A 和 變量 B 的數(shù)據(jù)歸屬于同一個(gè) Cache Line，所以 A 和 B 的數(shù)據(jù)都會被加載到 Cache，并將此 Cache Line 標(biāo)記為「獨(dú)占」?fàn)顟B(tài)。

③. 接著，2 號核心開始從內(nèi)存里讀取變量 B，同樣的也是讀取 Cache Line 大小的數(shù)據(jù)到 Cache 中，此 Cache Line 中的數(shù)據(jù)也包含了變量 A 和 變量 B，此時(shí) 1 號和 2 號核心的 Cache Line 狀態(tài)變?yōu)椤腹蚕怼範(fàn)顟B(tài)。

④. 1 號核心需要修改變量 A，發(fā)現(xiàn)此 Cache Line 的狀態(tài)是「共享」?fàn)顟B(tài)，所以先需要通過總線發(fā)送消息給 2 號核心，通知 2 號核心把 Cache 中對應(yīng)的 Cache Line 標(biāo)記為「已失效」?fàn)顟B(tài)，然后 1 號核心對應(yīng)的 Cache Line 狀態(tài)變成「已修改」?fàn)顟B(tài)，并且修改變量 A。

⑤. 之后，2 號核心需要修改變量 B，此時(shí) 2 號核心的 Cache 中對應(yīng)的 Cache Line 是已失效狀態(tài)，另外由于 1 號核心的 Cache 也有此相同的數(shù)據(jù)，且狀態(tài)為「已修改」?fàn)顟B(tài)，所以要先把 1 號核心的 Cache 對應(yīng)的 Cache Line 寫回到內(nèi)存，然后 2 號核心再從內(nèi)存讀取 Cache Line 大小的數(shù)據(jù)到 Cache 中，最后把變量 B 修改到 2 號核心的 Cache 中，并將狀態(tài)標(biāo)記為「已修改」?fàn)顟B(tài)。

所以，可以發(fā)現(xiàn)如果 1 號和 2 號 CPU 核心這樣持續(xù)交替的分別修改變量 A 和 B，就會重復(fù) ④ 和 ⑤ 這兩個(gè)步驟，Cache 并沒有起到緩存的效果，雖然變量 A 和 B 之間其實(shí)并沒有任何的關(guān)系，但是因?yàn)橥瑫r(shí)歸屬于一個(gè) Cache Line ，這個(gè) Cache Line 中的任意數(shù)據(jù)被修改后，都會相互影響，從而出現(xiàn) ④ 和 ⑤ 這兩個(gè)步驟。

因此，這種因?yàn)槎鄠€(gè)線程同時(shí)讀寫同一個(gè) Cache Line 的不同變量時(shí)，而導(dǎo)致 CPU Cache 失效的現(xiàn)象稱為偽共享（False Sharing）。

避免偽共享的方法

因此，對于多個(gè)線程共享的熱點(diǎn)數(shù)據(jù)，即經(jīng)常會修改的數(shù)據(jù)，應(yīng)該避免這些數(shù)據(jù)剛好在同一個(gè) Cache Line 中，否則就會出現(xiàn)為偽共享的問題。

接下來，看看在實(shí)際項(xiàng)目中是用什么方式來避免偽共享的問題的。

在 Linux 內(nèi)核中存在__cacheline_aligned_in_smp宏定義，是用于解決偽共享的問題。

從上面的宏定義，我們可以看到：

如果在多核（MP）系統(tǒng)里，該宏定義是__cacheline_aligned，也就是 Cache Line 的大?。?/p>

而如果在單核系統(tǒng)里，該宏定義是空的；

因此，針對在同一個(gè) Cache Line 中的共享的數(shù)據(jù)，如果在多核之間競爭比較嚴(yán)重，為了防止偽共享現(xiàn)象的發(fā)生，可以采用上面的宏定義使得變量在 Cache Line 里是對齊的。

舉個(gè)例子，有下面這個(gè)結(jié)構(gòu)體：

結(jié)構(gòu)體里的兩個(gè)成員變量 a 和 b 在物理內(nèi)存地址上是連續(xù)的，于是它們可能會位于同一個(gè) Cache Line 中，如下圖：

所以，為了防止前面提到的 Cache 偽共享問題，我們可以使用上面介紹的宏定義，將 b 的地址設(shè)置為 Cache Line 對齊地址，如下：

這樣 a 和 b 變量就不會在同一個(gè) Cache Line 中了，如下圖：

所以，避免 Cache 偽共享實(shí)際上是用空間換時(shí)間的思想，浪費(fèi)一部分 Cache 空間，從而換來性能的提升。

我們再來看一個(gè)應(yīng)用層面的規(guī)避方案，有一個(gè) Java 并發(fā)框架 Disruptor 使用「字節(jié)填充 + 繼承」的方式，來避免偽共享的問題。

Disruptor 中有一個(gè) RingBuffer 類會經(jīng)常被多個(gè)線程使用，代碼如下：

你可能會覺得 RingBufferPad 類里 7 個(gè) long 類型的名字很奇怪，但事實(shí)上，它們雖然看起來毫無作用，但卻對性能的提升起到了至關(guān)重要的作用。

我們都知道，CPU Cache 從內(nèi)存讀取數(shù)據(jù)的單位是 CPU Line，一般 64 位 CPU 的 CPU Line 的大小是 64 個(gè)字節(jié)，一個(gè) long 類型的數(shù)據(jù)是 8 個(gè)字節(jié)，所以 CPU 一下會加載 8 個(gè) long 類型的數(shù)據(jù)。

根據(jù) JVM 對象繼承關(guān)系中父類成員和子類成員，內(nèi)存地址是連續(xù)排列布局的，因此 RingBufferPad 中的 7 個(gè) long 類型數(shù)據(jù)作為 Cache Line前置填充，而 RingBuffer 中的 7 個(gè) long 類型數(shù)據(jù)則作為 Cache Line后置填充，這 14 個(gè) long 變量沒有任何實(shí)際用途，更不會對它們進(jìn)行讀寫操作。

另外，RingBufferFelds 里面定義的這些變量都是final修飾的，意味著第一次加載之后不會再修改， 又由于「前后」各填充了 7 個(gè)不會被讀寫的 long 類型變量，所以無論怎么加載 Cache Line，這整個(gè) Cache Line 里都沒有會發(fā)生更新操作的數(shù)據(jù)，于是只要數(shù)據(jù)被頻繁地讀取訪問，就自然沒有數(shù)據(jù)被換出 Cache 的可能，也因此不會產(chǎn)生偽共享的問題。

CPU 如何選擇線程的？

了解完 CPU 讀取數(shù)據(jù)的過程后，我們再來看看 CPU 是根據(jù)什么來選擇當(dāng)前要執(zhí)行的線程。

在 Linux 內(nèi)核中，進(jìn)程和線程都是用tark_struct結(jié)構(gòu)體表示的，區(qū)別在于線程的 tark_struct 結(jié)構(gòu)體里部分資源是共享了進(jìn)程已創(chuàng)建的資源，比如內(nèi)存地址空間、代碼段、文件描述符等，所以 Linux 中的線程也被稱為輕量級進(jìn)程，因?yàn)榫€程的 tark_struct 相比進(jìn)程的 tark_struct 承載的 資源比較少，因此以「輕」得名。

一般來說，沒有創(chuàng)建線程的進(jìn)程，是只有單個(gè)執(zhí)行流，它被稱為是主線程。如果想讓進(jìn)程處理更多的事情，可以創(chuàng)建多個(gè)線程分別去處理，但不管怎么樣，它們對應(yīng)到內(nèi)核里都是tark_struct。

所以，Linux 內(nèi)核里的調(diào)度器，調(diào)度的對象就是tark_struct，接下來我們就把這個(gè)數(shù)據(jù)結(jié)構(gòu)統(tǒng)稱為任務(wù)。

在 Linux 系統(tǒng)中，根據(jù)任務(wù)的優(yōu)先級以及響應(yīng)要求，主要分為兩種，其中優(yōu)先級的數(shù)值越小，優(yōu)先級越高：

實(shí)時(shí)任務(wù)，對系統(tǒng)的響應(yīng)時(shí)間要求很高，也就是要盡可能快的執(zhí)行實(shí)時(shí)任務(wù)，優(yōu)先級在0~99范圍內(nèi)的就算實(shí)時(shí)任務(wù)；

普通任務(wù)，響應(yīng)時(shí)間沒有很高的要求，優(yōu)先級在100~139范圍內(nèi)都是普通任務(wù)級別；

調(diào)度類

由于任務(wù)有優(yōu)先級之分，Linux 系統(tǒng)為了保障高優(yōu)先級的任務(wù)能夠盡可能早的被執(zhí)行，于是分為了這幾種調(diào)度類，如下圖：

Deadline 和 Realtime 這兩個(gè)調(diào)度類，都是應(yīng)用于實(shí)時(shí)任務(wù)的，這兩個(gè)調(diào)度類的調(diào)度策略合起來共有這三種，它們的作用如下：

SCHED_DEADLINE：是按照 deadline 進(jìn)行調(diào)度的，距離當(dāng)前時(shí)間點(diǎn)最近的 deadline 的任務(wù)會被優(yōu)先調(diào)度；

SCHED_FIFO：對于相同優(yōu)先級的任務(wù)，按先來先服務(wù)的原則，但是優(yōu)先級更高的任務(wù)，可以搶占低優(yōu)先級的任務(wù)，也就是優(yōu)先級高的可以「插隊(duì)」；

SCHED_RR：對于相同優(yōu)先級的任務(wù)，輪流著運(yùn)行，每個(gè)任務(wù)都有一定的時(shí)間片，當(dāng)用完時(shí)間片的任務(wù)會被放到隊(duì)列尾部，以保證相同優(yōu)先級任務(wù)的公平性，但是高優(yōu)先級的任務(wù)依然可以搶占低優(yōu)先級的任務(wù)；

而 Fair 調(diào)度類是應(yīng)用于普通任務(wù)，都是由 CFS 調(diào)度器管理的，分為兩種調(diào)度策略：

SCHED_NORMAL：普通任務(wù)使用的調(diào)度策略；

SCHED_BATCH：后臺任務(wù)的調(diào)度策略，不和終端進(jìn)行交互，因此在不影響其他需要交互的任務(wù)，可以適當(dāng)降低它的優(yōu)先級。

完全公平調(diào)度

我們平日里遇到的基本都是普通任務(wù)，對于普通任務(wù)來說，公平性最重要，在 Linux 里面，實(shí)現(xiàn)了一個(gè)基于 CFS 的調(diào)度算法，也就是完全公平調(diào)度（Completely Fair Scheduling）。

這個(gè)算法的理念是想讓分配給每個(gè)任務(wù)的 CPU 時(shí)間是一樣，于是它為每個(gè)任務(wù)安排一個(gè)虛擬運(yùn)行時(shí)間 vruntime，如果一個(gè)任務(wù)在運(yùn)行，其運(yùn)行的越久，該任務(wù)的 vruntime 自然就會越大，而沒有被運(yùn)行的任務(wù)，vruntime 是不會變化的。

那么，在 CFS 算法調(diào)度的時(shí)候，會優(yōu)先選擇 vruntime 少的任務(wù)，以保證每個(gè)任務(wù)的公平性。

這就好比，讓你把一桶的奶茶平均分到 10 杯奶茶杯里，你看著哪杯奶茶少，就多倒一些；哪個(gè)多了，就先不倒，這樣經(jīng)過多輪操作，雖然不能保證每杯奶茶完全一樣多，但至少是公平的。

當(dāng)然，上面提到的例子沒有考慮到優(yōu)先級的問題，雖然是普通任務(wù)，但是普通任務(wù)之間還是有優(yōu)先級區(qū)分的，所以在計(jì)算虛擬運(yùn)行時(shí)間 vruntime 還要考慮普通任務(wù)的權(quán)重值，注意權(quán)重值并不是優(yōu)先級的值，內(nèi)核中會有一個(gè) nice 級別與權(quán)重值的轉(zhuǎn)換表，nice 級別越低的權(quán)重值就越大，至于 nice 值是什么，我們后面會提到。
于是就有了以下這個(gè)公式：

你可以不用管 NICE_0_LOAD 是什么，你就認(rèn)為它是一個(gè)常量，那么在「同樣的實(shí)際運(yùn)行時(shí)間」里，高權(quán)重任務(wù)的 vruntime 比低權(quán)重任務(wù)的 vruntime少，你可能會奇怪為什么是少的？你還記得 CFS 調(diào)度嗎，它是會優(yōu)先選擇 vruntime 少的任務(wù)進(jìn)行調(diào)度，所以高權(quán)重的任務(wù)就會被優(yōu)先調(diào)度了，于是高權(quán)重的獲得的實(shí)際運(yùn)行時(shí)間自然就多了。

CPU 運(yùn)行隊(duì)列

一個(gè)系統(tǒng)通常都會運(yùn)行著很多任務(wù)，多任務(wù)的數(shù)量基本都是遠(yuǎn)超 CPU 核心數(shù)量，因此這時(shí)候就需要排隊(duì)。

事實(shí)上，每個(gè) CPU 都有自己的運(yùn)行隊(duì)列（Run Queue, rq），用于描述在此 CPU 上所運(yùn)行的所有進(jìn)程，其隊(duì)列包含三個(gè)運(yùn)行隊(duì)列，Deadline 運(yùn)行隊(duì)列 dl_rq、實(shí)時(shí)任務(wù)運(yùn)行隊(duì)列 rt_rq 和 CFS 運(yùn)行隊(duì)列 csf_rq，其中 csf_rq 是用紅黑樹來描述的，按 vruntime 大小來排序的，最左側(cè)的葉子節(jié)點(diǎn)，就是下次會被調(diào)度的任務(wù)。

這幾種調(diào)度類是有優(yōu)先級的，優(yōu)先級如下：Deadline > Realtime > Fair，這意味著 Linux 選擇下一個(gè)任務(wù)執(zhí)行的時(shí)候，會按照此優(yōu)先級順序進(jìn)行選擇，也就是說先從dl_rq里選擇任務(wù)，然后從rt_rq里選擇任務(wù)，最后從csf_rq里選擇任務(wù)。因此，實(shí)時(shí)任務(wù)總是會比普通任務(wù)優(yōu)先被執(zhí)行。

調(diào)整優(yōu)先級

如果我們啟動任務(wù)的時(shí)候，沒有特意去指定優(yōu)先級的話，默認(rèn)情況下都是普通任務(wù)，普通任務(wù)的調(diào)度類是 Fail，由 CFS 調(diào)度器來進(jìn)行管理。CFS 調(diào)度器的目的是實(shí)現(xiàn)任務(wù)運(yùn)行的公平性，也就是保障每個(gè)任務(wù)的運(yùn)行的時(shí)間是差不多的。

如果你想讓某個(gè)普通任務(wù)有更多的執(zhí)行時(shí)間，可以調(diào)整任務(wù)的nice值，從而讓優(yōu)先級高一些的任務(wù)執(zhí)行更多時(shí)間。nice 的值能設(shè)置的范圍是-20～19， 值越低，表明優(yōu)先級越高，因此 -20 是最高優(yōu)先級，19 則是最低優(yōu)先級，默認(rèn)優(yōu)先級是 0。

是不是覺得 nice 值的范圍很詭異？事實(shí)上，nice 值并不是表示優(yōu)先級，而是表示優(yōu)先級的修正數(shù)值，它與優(yōu)先級（priority）的關(guān)系是這樣的：priority(new) = priority(old) + nice。內(nèi)核中，priority 的范圍是 0~139，值越低，優(yōu)先級越高，其中前面的 0~99 范圍是提供給實(shí)時(shí)任務(wù)使用的，而 nice 值是映射到 100~139，這個(gè)范圍是提供給普通任務(wù)用的，因此 nice 值調(diào)整的是普通任務(wù)的優(yōu)先級。

在前面我們提到了，權(quán)重值與 nice 值的關(guān)系的，nice 值越低，權(quán)重值就越大，計(jì)算出來的 vruntime 就會越少，由于 CFS 算法調(diào)度的時(shí)候，就會優(yōu)先選擇 vruntime 少的任務(wù)進(jìn)行執(zhí)行，所以 nice 值越低，任務(wù)的優(yōu)先級就越高。

我們可以在啟動任務(wù)的時(shí)候，可以指定 nice 的值，比如將 mysqld 以 -3 優(yōu)先級：

如果想修改已經(jīng)運(yùn)行中的任務(wù)的優(yōu)先級，則可以使用renice來調(diào)整 nice 值：

nice 調(diào)整的是普通任務(wù)的優(yōu)先級，所以不管怎么縮小 nice 值，任務(wù)永遠(yuǎn)都是普通任務(wù)，如果某些任務(wù)要求實(shí)時(shí)性比較高，那么你可以考慮改變?nèi)蝿?wù)的優(yōu)先級以及調(diào)度策略，使得它變成實(shí)時(shí)任務(wù)，比如：

總結(jié)

理解 CPU 是如何讀寫數(shù)據(jù)的前提，是要理解 CPU 的架構(gòu)，CPU 內(nèi)部的多個(gè) Cache + 外部的內(nèi)存和磁盤都就構(gòu)成了金字塔的存儲器結(jié)構(gòu)，在這個(gè)金字塔中，越往下，存儲器的容量就越大，但訪問速度就會小。

CPU 讀寫數(shù)據(jù)的時(shí)候，并不是按一個(gè)一個(gè)字節(jié)為單位來進(jìn)行讀寫，而是以 CPU Line 大小為單位，CPU Line 大小一般是 64 個(gè)字節(jié)，也就意味著 CPU 讀寫數(shù)據(jù)的時(shí)候，每一次都是以 64 字節(jié)大小為一塊進(jìn)行操作。

因此，如果我們操作的數(shù)據(jù)是數(shù)組，那么訪問數(shù)組元素的時(shí)候，按內(nèi)存分布的地址順序進(jìn)行訪問，這樣能充分利用到 Cache，程序的性能得到提升。但如果操作的數(shù)據(jù)不是數(shù)組，而是普通的變量，并在多核 CPU 的情況下，我們還需要避免 Cache Line 偽共享的問題。

所謂的 Cache Line 偽共享問題就是，多個(gè)線程同時(shí)讀寫同一個(gè) Cache Line 的不同變量時(shí)，而導(dǎo)致 CPU Cache 失效的現(xiàn)象。那么對于多個(gè)線程共享的熱點(diǎn)數(shù)據(jù)，即經(jīng)常會修改的數(shù)據(jù)，應(yīng)該避免這些數(shù)據(jù)剛好在同一個(gè) Cache Line 中，避免的方式一般有 Cache Line 大小字節(jié)對齊，以及字節(jié)填充等方法。

系統(tǒng)中需要運(yùn)行的多線程數(shù)一般都會大于 CPU 核心，這樣就會導(dǎo)致線程排隊(duì)等待 CPU，這可能會產(chǎn)生一定的延時(shí)，如果我們的任務(wù)對延時(shí)容忍度很低，則可以通過一些人為手段干預(yù) Linux 的默認(rèn)調(diào)度策略和優(yōu)先級。

責(zé)任編輯：lq