文章轉(zhuǎn)自公眾號(hào)“人人都是極客”

但凡懂Linux內(nèi)核的，都知道Linux內(nèi)核的CFS進(jìn)程調(diào)度算法，無論是從2.6.23將其初引入時(shí)的論文，還是各類源碼分析，文章，以及Linux內(nèi)核專門的圖書，都給人這樣一種感覺，即?CFS調(diào)度器是革命性的，它將徹底改變進(jìn)程調(diào)度算法。?預(yù)期中，人們期待它會(huì)帶來令人驚艷的效果。然而這是錯(cuò)覺。人們希望CFS速勝，但是分析來分析去，卻只是在某些方面比O(1)調(diào)度器稍微好一點(diǎn)點(diǎn)。甚至在某些方面比不上古老的4.4BSD調(diào)度器。可是人們卻依然對(duì)其趨之若鶩，特別是源碼分析，汗牛塞屋！為什么CFS對(duì)別的調(diào)度算法沒有帶來碾壓的效果呢？首先，在真實(shí)世界，碾壓是不存在的，人與人，事與事既然被放在了同一個(gè)重量級(jí)梯隊(duì)比較，其之間的差別沒有想象的那么大，根本就不在誰碾壓誰。不能被小說電視劇電影蒙蔽了，此外，徐曉冬大擺拳暴打雷雷也不算數(shù)，因?yàn)樗麄儽揪筒皇且粋€(gè)梯隊(duì)。

任何領(lǐng)域，革命性的碾壓式推陳出新并不是沒有，但是概率極低，人們普遍的狂妄在于，總是認(rèn)為自己所置身的環(huán)境正在發(fā)生著某種碾壓式的變革，但其實(shí)，最終大概率不過是一場(chǎng)平庸。

最終就出現(xiàn)了角力，僵持。其次，我們應(yīng)該看到，CFS調(diào)度器聲稱它會(huì)給交互式進(jìn)程帶來福音，在這方面CFS確實(shí)比O(1)做得好，但是驚艷的效果來自于粉絲的認(rèn)同。Linux系統(tǒng)交互進(jìn)程本來就不多，Linux更多地被裝在服務(wù)器，而在服務(wù)器看來，吞吐是要比交互響應(yīng)更加重要的。那么以交互為主的Android系統(tǒng)呢？我們知道，Android也是采用了CFS調(diào)度器，也有一些是BFS，為什么同樣沒有帶來驚艷的效果呢？我承認(rèn)，2008年前后出現(xiàn)CFS時(shí)還沒有Android，等到Android出現(xiàn)時(shí)，其采用的Linux內(nèi)核已經(jīng)默認(rèn)了CFS調(diào)度器，我們看下Android版本，Linux內(nèi)核版本以及發(fā)行時(shí)間的關(guān)系：Linux內(nèi)核在2.6.23就采用了CFS調(diào)度器。所以一個(gè)原因就是沒有比較。Android系統(tǒng)上，CFS沒有機(jī)會(huì)和O(1)做比較。另外，即便回移一個(gè)O(1)調(diào)度器到Android系統(tǒng)去和CFS做AB，在我看來，CFS同樣不會(huì)驚艷，原因很簡(jiǎn)單，Android系統(tǒng)幾乎都是交互進(jìn)程，前臺(tái)進(jìn)程卻永遠(yuǎn)只有一個(gè)，你幾乎感受不到進(jìn)程的切換卡頓，換句話說，即便CFS對(duì)待交互式進(jìn)程比O(1)好太多，你也感受不到，因?yàn)閷?duì)于手機(jī)，平板而言，你切換APP的時(shí)間遠(yuǎn)遠(yuǎn)大于進(jìn)程切換的時(shí)間粒度。那么，CFS到底好在哪里？簡(jiǎn)單點(diǎn)說，CFS的意義在于，?在一個(gè)混雜著大量計(jì)算型進(jìn)程和IO交互進(jìn)程的系統(tǒng)中，CFS調(diào)度器對(duì)待IO交互進(jìn)程要比O(1)調(diào)度器更加友善和公平。理解這一點(diǎn)至關(guān)重要。其實(shí)，CFS調(diào)度器的理念非常古老，就說在業(yè)界，CFS的思想早就被應(yīng)用在了磁盤IO調(diào)度，數(shù)據(jù)包調(diào)度等領(lǐng)域，甚至最最古老的SRV3以及4.3BSD UNIX系統(tǒng)的進(jìn)程調(diào)度中早就有了CFS的身影，可以說，Linux只是使用CFS調(diào)度器，而不是設(shè)計(jì)了CFS調(diào)度器！就以4.3BSD調(diào)度器為例，我們看一下其調(diào)度原理。4.3BSD采用了1秒搶占制，每間隔1秒，會(huì)對(duì)整個(gè)系統(tǒng)進(jìn)程進(jìn)行優(yōu)先級(jí)排序，然后找到優(yōu)先級(jí)最高的投入運(yùn)行，非常簡(jiǎn)單的一個(gè)思想，現(xiàn)在看看它是如何計(jì)算優(yōu)先級(jí)的。首先，每一個(gè)進(jìn)程j均擁有一個(gè)CPU滴答的度量值Cj，每一個(gè)時(shí)鐘滴答，當(dāng)前在運(yùn)行的進(jìn)程的CPU度量值C會(huì)遞增：

當(dāng)一個(gè)1秒的時(shí)間區(qū)間i過去之后，Cj被重置，該進(jìn)程j的優(yōu)先級(jí)采用下面的公式計(jì)算：

可以計(jì)算，在一個(gè)足夠長(zhǎng)的時(shí)間段內(nèi)，兩個(gè)進(jìn)程運(yùn)行的總時(shí)間比例，將和它們的Base_PrioBase_Prio優(yōu)先級(jí)的比例相等。4.3BSD的優(yōu)先級(jí)公平調(diào)度是CPU滴答驅(qū)動(dòng)的?，F(xiàn)在看Linux的CFS，CFS采用隨時(shí)搶占制。每一個(gè)進(jìn)程j均攜帶一個(gè)?虛擬時(shí)鐘VCj，每一個(gè)時(shí)鐘滴答，當(dāng)前進(jìn)程k的VCk會(huì)重新計(jì)算，同時(shí)調(diào)度器選擇VC最小的進(jìn)程運(yùn)行，計(jì)算方法非常簡(jiǎn)單：可見， Linux的CFS簡(jiǎn)直就是4.3BSD進(jìn)程調(diào)度的自驅(qū)無級(jí)變速版本！如果你想了解CFS的精髓，上面的就是了。換成語言描述，CFS的精髓就是 “n個(gè)進(jìn)程的系統(tǒng)，任意長(zhǎng)的時(shí)間周期T，每一個(gè)進(jìn)程運(yùn)行T/n的時(shí)間！”當(dāng)然，在現(xiàn)實(shí)和實(shí)現(xiàn)中，會(huì)有80%的代碼處理20%的剩余問題，比如如何獎(jiǎng)勵(lì)睡眠太久的進(jìn)程等等，但是這些都不是精髓。綜上，我們總結(jié)了：

• 現(xiàn)實(shí)世界很難碾壓同級(jí)別的人或事。

• 大量的Linux服務(wù)器不需要照顧交互進(jìn)程，CFS優(yōu)勢(shì)無法凸顯。

• 大量的Android系統(tǒng)沒有和O(1)同臺(tái)競(jìng)技的機(jī)會(huì)。

• 大量的Android系統(tǒng)交互進(jìn)程很難感知進(jìn)程調(diào)度這件事。

• CFS調(diào)度思想古已有之。

所以無論從概念還是從效果，Linux CFS調(diào)度器均沒有帶來令人眼前一亮的哇塞效果。但是還缺點(diǎn)什么。嗯，技術(shù)上的解釋。分析和解釋任何一個(gè)機(jī)制之前，必然要先問，這個(gè)機(jī)制的目標(biāo)是什么，它要解決什么問題，這樣才有意義。而不能僅僅是明白了它是怎么工作的。那么Linux CFS調(diào)度器被采用，它的目標(biāo)是解決什么問題的呢？它肯定是針對(duì)O(1)算法的一個(gè)問題而被引入并取代O(1)，該問題也許并非什么臭名昭著，但是確實(shí)是一枚釘子，必須拔除。O(1)調(diào)度器的本質(zhì)問題在于?進(jìn)程的優(yōu)先級(jí)和進(jìn)程可運(yùn)行的時(shí)間片進(jìn)行了強(qiáng)映射！

也就是說，給定一個(gè)進(jìn)程優(yōu)先級(jí)，就會(huì)計(jì)算出一個(gè)時(shí)間片與之對(duì)應(yīng)，我們忽略獎(jiǎng)懲相關(guān)的動(dòng)態(tài)優(yōu)先級(jí)，看一下原始O(1)算法中一個(gè)進(jìn)程時(shí)間片的計(jì)算：

#define?BASE_TIMESLICE(p)?(MIN_TIMESLICE?+?/
((MAX_TIMESLICE?-?MIN_TIMESLICE)?*?/
(MAX_PRIO-1?-?(p)->static_prio)?/?(MAX_USER_PRIO-1)))static?inline?unsigned?int?task_timeslice(task_t?*p){return?BASE_TIMESLICE(p);
}

直觀點(diǎn)顯示：

針對(duì)上述問題，2.6內(nèi)核的O(1)引入了雙斜率來解決：

static?unsigned?int?task_timeslice(task_t?*p){if?(p->static_prio?0))return?SCALE_PRIO(DEF_TIMESLICE*4,?p->static_prio);elsereturn?SCALE_PRIO(DEF_TIMESLICE,?p->static_prio);
}

直觀圖示如下：

貌似問題解決了，但是如果單單揪住上圖的某一個(gè)優(yōu)先級(jí)子區(qū)間來看，還是會(huì)有問題，這就是相對(duì)優(yōu)先級(jí)的問題。我們看到，高優(yōu)先級(jí)的時(shí)間片是緩慢增減的，而低優(yōu)先級(jí)的時(shí)間片卻是陡然增減，同樣都是相差同樣優(yōu)先級(jí)的進(jìn)程，其優(yōu)先級(jí)分布影響了它們的時(shí)間片分配。本來是治瘸子，結(jié)果腿好了，但是胳臂壞了。本質(zhì)上來講，這都源自于下面兩個(gè)原因：固定的優(yōu)先級(jí)映射到固定的時(shí)間片。相對(duì)優(yōu)先級(jí)和絕對(duì)優(yōu)先級(jí)混雜。那么這個(gè)問題如何解決？優(yōu)先級(jí)和時(shí)間片本來就是兩個(gè)概念，二者中間還得有個(gè)變量溝通才可以。優(yōu)先級(jí)高只是說明該進(jìn)程能運(yùn)行的久一些，但是到底久多少，并不是僅僅優(yōu)先級(jí)就能決定的，還要綜合考慮，換句話距離來說，如果只有一個(gè)進(jìn)程，那么即便它優(yōu)先級(jí)再低，它也可以永久運(yùn)行，如果系統(tǒng)中有很多的進(jìn)程，即便再高優(yōu)先級(jí)的進(jìn)程也要讓出一些時(shí)間給其它進(jìn)程。所以，考慮到系統(tǒng)中總體的進(jìn)程情況，將優(yōu)先級(jí)轉(zhuǎn)換為權(quán)重，將時(shí)間片轉(zhuǎn)換為份額，CFS就是了。最終的坐標(biāo)系應(yīng)該是權(quán)重占比/時(shí)間片坐標(biāo)系而不是權(quán)重(或者優(yōu)先級(jí))/時(shí)間片。應(yīng)該是這個(gè)平滑的樣子：

看來，Linux CFS只是為了解決O(1)中一個(gè)“靜態(tài)優(yōu)先級(jí)/時(shí)間片映射”問題的，那么可想而知，它又能帶來什么驚艷效果呢？這里還有個(gè)“但是”，這個(gè)O(1)調(diào)度器的問題其實(shí)在計(jì)算密集型的守護(hù)進(jìn)程看來，并不是問題，反而是好事，畢竟高優(yōu)先級(jí)進(jìn)程可以無條件持續(xù)運(yùn)行很久而不切換。這對(duì)于吞吐率的提高，cache利用都是有好處的。無非也就侵?jǐn)_了交互進(jìn)程唄，又有何妨。當(dāng)然，使用調(diào)優(yōu)CFS的時(shí)候，難免也要遇到IO睡眠獎(jiǎng)懲等剩余的事情去設(shè)計(jì)一些trick算法，這破費(fèi)精力。對(duì)了，還要設(shè)置你的內(nèi)核為HZ1000哦，這樣更能體現(xiàn)CFS的平滑性，就像它宣稱的那樣。我難以想象，除了Ubuntu，Suse等花哨的桌面發(fā)行版之外，還有哪個(gè)Linux需要打開HZ1000，服務(wù)器用HZ250不挺好嗎？關(guān)于調(diào)度的話題基本就說完了，但是在進(jìn)入下一步固有的噴子環(huán)節(jié)之前，還有兩點(diǎn)要強(qiáng)調(diào)：

CFS的時(shí)間片是動(dòng)態(tài)的，是系統(tǒng)負(fù)載均衡以及其優(yōu)先級(jí)的函數(shù)，這便可以把進(jìn)程調(diào)度動(dòng)態(tài)適應(yīng)到系統(tǒng)最佳，以節(jié)省切換開銷。

即便是到了多核時(shí)代，對(duì)于實(shí)時(shí)進(jìn)程依然像單核時(shí)代那般嚴(yán)格遵循最優(yōu)先調(diào)度。

我還是想說，在調(diào)度器設(shè)計(jì)方面，大部分的人們關(guān)注點(diǎn)錯(cuò)了！

在CPU核數(shù)越來越多的時(shí)代，人們更應(yīng)該關(guān)心把進(jìn)程調(diào)度到哪里CPU核上而不是某個(gè)CPU核要運(yùn)行哪個(gè)進(jìn)程。

單核時(shí)代一路走過來的Linux，發(fā)展迅猛，這無可厚非，但是成就一個(gè)操作系統(tǒng)內(nèi)核的并不單單是技術(shù)，還有別的。這些當(dāng)然程序員們很不愛聽，程序員最煩非技術(shù)方面的東西了，程序員跟誰都比寫代碼，程序員特別喜歡噴領(lǐng)導(dǎo)不會(huì)寫代碼云云。Linux在純技術(shù)方面并不優(yōu)秀，Linux總體上優(yōu)秀的原因是因?yàn)橛幸蝗悍谴a不明志的程序員在讓它變得越來越優(yōu)秀，另一方面還要?dú)w功于開源和社區(qū)。Linux的學(xué)習(xí)門檻極低，如果一個(gè)公司能不費(fèi)吹灰之力招聘到一個(gè)Linux程序員的話，那它干嘛還要費(fèi)勁九牛二虎之力去招聘什么高端的BSD程序員呢？最終的結(jié)果就是，Linux用的人極多，想換也換不掉了。但無論如何也沒法彌補(bǔ)Linux內(nèi)核上的一些原則性錯(cuò)誤。Linux內(nèi)核還是以原始的主線為base，以講Linux內(nèi)核的書為例，經(jīng)典的Robert Love的《Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)》，以及《深入理解Linux內(nèi)核》，在講進(jìn)程調(diào)度的時(shí)候，關(guān)于多核負(fù)載均衡的筆墨都是少之又少甚至沒有，如此經(jīng)典的著作把很多同行引向了那萬劫不復(fù)的代碼深淵。于是乎，鋪天蓋地的CFS源碼分析紛至沓來。但其實(shí)，拋開這么一個(gè)再普通不過的Linux內(nèi)核，現(xiàn)代操作系統(tǒng)進(jìn)入了多核時(shí)代，其核心正是在cache利用上的革新，帶來的轉(zhuǎn)變就是進(jìn)程調(diào)度和內(nèi)存管理的革新。review一下Linux內(nèi)核源碼，這些改變?cè)缇鸵呀?jīng)表現(xiàn)了出來?？杀氖?#xff0c;關(guān)于Linux內(nèi)核的經(jīng)典書籍卻再也沒有更新，所有的從傳統(tǒng)學(xué)校出來的喜歡看書學(xué)習(xí)的，依然是抱著10年前的大部頭在啃。當(dāng)然了，Linux內(nèi)核作為一個(gè)代碼來講，它是普適的，所以社區(qū)很難看到且關(guān)注單單是多核的問題，社區(qū)關(guān)注的最多的是可維護(hù)性，而不是性能。Linux新特性在128MB內(nèi)存的i386機(jī)器上跑沒有問題，那就是OK的。只要不是80%以上的人遭遇的新問題，社區(qū)是從不care的，同時(shí)，正因?yàn)槿绱?#xff0c;社區(qū)還會(huì)引入bug，這也是令人想嘆息都不能嘆息。我的看法吧，社區(qū)只是一個(gè)一切以代碼為準(zhǔn)繩的程序員社區(qū)，社區(qū)不會(huì)過于關(guān)注體系結(jié)構(gòu)的發(fā)展和新特性，這些都是廠商的事情?；氐竭M(jìn)程調(diào)度的話題，正因?yàn)長(zhǎng)inux一直在關(guān)注調(diào)度算法本身以及其實(shí)現(xiàn)的代碼，才會(huì)出現(xiàn)The Linux Scheduler: a Decade of Wasted Cores，這篇十分中肯的paper：http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf同樣，我一向噴的TCP也是如此，人們關(guān)注TCP的實(shí)現(xiàn)代碼本身，才會(huì)讓它越來越復(fù)雜，然后越來越脆弱，也許你會(huì)說這就是進(jìn)化，但是趁著萬劫不復(fù)前，不是還有回爐的機(jī)會(huì)嗎？還沒有進(jìn)化到必須繼續(xù)進(jìn)化的地步吧。如果站在外面看且具有強(qiáng)制措施，估計(jì)早就沒有垃圾TCP了吧。浙江溫州皮鞋濕，下雨進(jìn)水不會(huì)胖。

總結(jié)

以上是生活随笔為你收集整理的用c语言实现对n个进程采用“短进程优先”算法的进程调度_为什么Linux CFS调度器没有带来惊艳的碾压效果？...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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