|
最近幾天結(jié)合源碼看了很多l(xiāng)inux進(jìn)程調(diào)度的文章，雖然掌握了個(gè)大概，但是越看，細(xì)節(jié)越多，寫這篇文章的信心也就越不足，曾有系列文章叫鼠眼看linux進(jìn)程調(diào)度，很符合我現(xiàn)在的心境，就像盲人摸象，學(xué)到一些東西，很驚喜，但是總有一種力不從心的惶恐。但是好久沒寫博文了，還是寫一篇。寫的不對的地方，請大家批評指正。 CPU是一種寶貴的資源，Linux是多任務(wù)的OS，這種多任務(wù)要求，對于每個(gè)任務(wù)或者說進(jìn)程來說，就好像它獨(dú)占了CPU。想想如果只有一個(gè)CPU，但是有80個(gè)處于TASK_RUNNING狀態(tài)的進(jìn)程，在這八十個(gè)進(jìn)程選擇進(jìn)程，切換進(jìn)程是多么困難。如果你理解不了這種難度，你可以想想如果你同時(shí)有80個(gè)女朋友，性格迥異，愛好不同，要做到每個(gè)女朋友都認(rèn)為她自己是你唯一的女友是多么的困難。 劉明在《Linux 調(diào)度器BFS簡介》中有個(gè)很有意思的比喻，linux 內(nèi)核調(diào)度器就像處境尷尬的主婦，滿足孩子對晚餐的要求便有可能傷害到老人的食欲，做出一桌讓男女老少都滿意的飯菜實(shí)在是太難了。Linux是一個(gè)通用的操作系統(tǒng)，無法預(yù)測運(yùn)行其上的進(jìn)程有什么樣的特點(diǎn)，就像一家人的口味各不相同，孩子喜歡吃甜，爸爸喜歡吃咸，老人喜歡口味清淡，所以調(diào)度器也很為難。 一般來說根據(jù)進(jìn)程的特點(diǎn)，可以將進(jìn)程分成幾類 1 交互式進(jìn)程 這個(gè)比較簡單了，想想你你使用vi編輯文本，大量的人機(jī)交互，進(jìn)程不斷的進(jìn)入睡眠狀態(tài)等待你的輸入，CPU占用不高但是要求響應(yīng)迅速，比如你敲了鍵盤，過了10秒鐘才在編輯器上顯示出來，這用戶體驗(yàn)是多么的糟糕。 2 批處理進(jìn)程 最典型的就是編譯工程這種進(jìn)程了，如果我們編譯一個(gè)大型的工程，我們敲了個(gè)make，也許1個(gè)小時(shí)才能編譯成功，但是沒有人會(huì)兩個(gè)眼睛盯著屏幕看編譯的過程，我們更關(guān)心的是編譯的結(jié)果。對于這種進(jìn)程就是屬于姥姥不疼舅舅不愛的進(jìn)程，這要他在跑就行了，不必給他太多的關(guān)注和資源。 3 實(shí)時(shí)進(jìn)程 實(shí)時(shí)進(jìn)程原本的含義是給定的工作要在指定的時(shí)間內(nèi)完成，不要求你多快，但是一定要在指定的時(shí)間前完成指定的任務(wù)，多用在火箭 導(dǎo)彈類似的精密系統(tǒng)中。這種實(shí)時(shí)叫做硬實(shí)時(shí)，對于Linux 這種通用的OS來講，完全做到硬實(shí)時(shí)有點(diǎn)強(qiáng)人所難了，中斷，磁盤尋道，總線征用 鎖，等很多的機(jī)制帶來了太多的不確定性，很難做到硬實(shí)時(shí)。 linux所說的實(shí)時(shí)進(jìn)程是軟實(shí)時(shí)，就是盡量的實(shí)時(shí)，如果做不到，也不會(huì)出現(xiàn)毀滅性的后果。比如視頻播放器，解碼速度有點(diǎn)慢，頂多是視頻播放有點(diǎn)卡，用戶體驗(yàn)不好，但是不會(huì)機(jī)毀人亡。 不同的進(jìn)程，就用不同的調(diào)度策略伺候之，對于實(shí)時(shí)進(jìn)程，我們就采用實(shí)時(shí)調(diào)度策略：FIFO or Round Robin（時(shí)間片輪轉(zhuǎn)）。對于批處理進(jìn)程和交互進(jìn)程，我們采用CFS調(diào)度器。在之前的版本，Linux采用O(1)調(diào)度器的時(shí)候，有復(fù)雜的方法識別交互性進(jìn)程，獎(jiǎng)勵(lì)交互性進(jìn)程，算法比較復(fù)雜，現(xiàn)在采用CFS調(diào)度器后，核心思想比較簡單“完全公平”，降低了代碼復(fù)雜度，很好地滿足了各種需求。 先說說實(shí)時(shí)調(diào)度，實(shí)時(shí)調(diào)度有兩個(gè)維度1 優(yōu)先級2 調(diào)度策略。linux用戶程序可以通過調(diào)用sched_setscheduler系統(tǒng)調(diào)用來設(shè)置進(jìn)程的優(yōu)先級和調(diào)度策略。 實(shí)時(shí)進(jìn)程共有0~99共100種不同的優(yōu)先級，0優(yōu)先級最高，99優(yōu)先級最低，對應(yīng)100個(gè)隊(duì)列。對于實(shí)時(shí)進(jìn)程來說，高優(yōu)先級實(shí)時(shí)進(jìn)程存在，低優(yōu)先級的實(shí)時(shí)進(jìn)程就撈不著CPU資源，普通進(jìn)程更撈不著CPU資源。  接下來就是調(diào)度策略，一種是FIFO，先進(jìn)先出，如果最高優(yōu)先級的進(jìn)程是FIFO類型，那么他就一直執(zhí)行，一條路跑到黑，直到進(jìn)程退出，或者它調(diào)用sched_yield主動(dòng)讓出資源，或者突然出現(xiàn)更高優(yōu)先級的進(jìn)程橫空出世，搶占了它的CPU。另外一種是時(shí)間片輪轉(zhuǎn)，假如說最高優(yōu)先級實(shí)時(shí)進(jìn)程隊(duì)列存在多個(gè)進(jìn)程，當(dāng)前進(jìn)程耗盡自己時(shí)間片后自動(dòng)排到隊(duì)尾，選擇同一個(gè)隊(duì)列的隊(duì)列頭部的進(jìn)程去執(zhí)行。這些事情是在task_tick_rt函數(shù)做的。 前面提到實(shí)時(shí)進(jìn)程存在，普通進(jìn)程完全撈不到CPU資源也不完全對，后來LINUX增加組調(diào)度策略后，有/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us兩個(gè)參數(shù)，這兩個(gè)參數(shù)表示的含義是：在sched_rt_peroid_us的周期內(nèi)，所有的實(shí)時(shí)進(jìn)程運(yùn)行時(shí)間之和不得超過sched_rt_runtime_us。 默認(rèn)值為1秒和0.95秒換句話說，在1秒的周期以內(nèi)，所有實(shí)時(shí)進(jìn)程運(yùn)行時(shí)間之和不得超過0.95秒，剩下的0.5秒鐘留給普通進(jìn)程。 對于普通進(jìn)程的CFS調(diào)度器，內(nèi)容相對比較獨(dú)立，如果有時(shí)間，后面會(huì)有專門的博文總結(jié)。 2 SMP時(shí)代的進(jìn)程調(diào)度 更要命的是現(xiàn)在進(jìn)入了多核的時(shí)代，縱然不談服務(wù)器的高配置，我的筆記本配置不高，也已經(jīng)是四核，可見多核計(jì)算機(jī)已經(jīng)是滿大街了。對于負(fù)載的SMP，就引入了新的問題。單核的時(shí)候，只有一個(gè)CPU，不需要考慮選擇幾個(gè)運(yùn)行隊(duì)列，就是一個(gè)run queue。但是多核的時(shí)候，是建立一個(gè)run queue，所有的CPU去run queue上選擇摘取可執(zhí)行的進(jìn)程，還是每個(gè)CPU一個(gè)run queue？其實(shí)都是可以的。 1 per cpu run queue 目前l(fā)inux 內(nèi)核采用的是per cpu run queue，每個(gè)CPU去自己的run queue 去選擇可執(zhí)行的進(jìn)程，這樣減少 了競爭。其實(shí)除了這個(gè)好處，還有另外一個(gè)甚至更重要的好處，緩存重利用。進(jìn)程落在這個(gè)CPU的運(yùn)行隊(duì)列上，經(jīng)過多次調(diào)度后（暫不考慮多CPU的load balance），仍然是同一顆CPU運(yùn)行這個(gè)進(jìn)程，也許上次運(yùn)行時(shí)的變量 內(nèi)存還在cache中，如果只有一個(gè)運(yùn)行隊(duì)列，多個(gè)CPU的話，上次執(zhí)行所在的CPU和這次執(zhí)行所在的CPU很可能不是同一顆CPU，那么上次執(zhí)行調(diào)入的緩存就完全用不上了。 2 single run queue 所有的CPU使用同一個(gè)隊(duì)列，這也是可以的，有些人覺著太土，因?yàn)槿绻粋€(gè)CPU 訪問run queue的時(shí)候，其他的CPU 就不能訪問run queue了，一把大鎖降低了性能，尤其是當(dāng)CPU特別多的時(shí)候，想想如果你有1024個(gè)CPU，然而只有一個(gè)運(yùn)行隊(duì)列，run queue這個(gè)瓶頸就是顯而易見的了。 介紹到這里，很多筒子可能就會(huì)說了，那還有啥好糾結(jié)的，肯定是per cpu run queue 更優(yōu)越。但是實(shí)際情況要比理論復(fù)雜的多。BFS（Brain Fuck Scheduler ，又稱腦殘調(diào)度器）就是一種單一隊(duì)列的調(diào)度器，這種調(diào)度器對于桌面應(yīng)用來說，效果非常的好。感興趣的筒子可以閱讀《Linux調(diào)度器BFS簡介》和《BFS，Linux桌面的極速未來》 per cpu run queue也不是完全沒有缺點(diǎn)。既然是多個(gè)隊(duì)列，就會(huì)有可能不均衡，比如一個(gè)CPU忙的要死，另一個(gè)CPU無事可做，這種情景本身也是對CPU資源的浪費(fèi)。內(nèi)核為了解決這個(gè)問題就必須要發(fā)起CPU間的負(fù)載均衡load balance，兩個(gè)CPU之間負(fù)載均衡，要獲取兩個(gè)run queue的鎖，會(huì)傷害并發(fā)，除此以外，負(fù)載均衡本身也消耗CPU資源。 我們按照我們的硬件常識，如果我有兩顆物理CPU，每顆物理CPU有兩個(gè)核，那么我的CPU就是4核的，每個(gè)核又可以通過SMT（Simultaneous Multi-Threading）類似的技術(shù)實(shí)現(xiàn)多個(gè)硬件線程或者叫做Virtual CPU，比如Intel的超線程技術(shù)，如果每個(gè)核可以實(shí)現(xiàn)2個(gè)Virtual CPU，那么我的硬件就有8個(gè)Virtual CPU。這些Virtual CPU 之間的親緣關(guān)系是不同的。 為了應(yīng)對多核多CPU，Linux引進(jìn)了調(diào)度域的概念，其實(shí)就是根據(jù)的親緣關(guān)系的遠(yuǎn)近，劃分不同的范圍。根據(jù)親緣關(guān)系的遠(yuǎn)近從近到遠(yuǎn)分成四個(gè)層次： 1 超線程 同一個(gè)核利用超線程技術(shù)演化出來的Virtual CPU。我們知道CPU的速度要比內(nèi)存訪問的速度快，如果cache沒有命中，CPU在等待內(nèi)存的時(shí)間里面無事可做，這是一種浪費(fèi)，就切換到其他線程。這樣多個(gè)線程分時(shí)復(fù)用一個(gè)核。說實(shí)話，這個(gè)超線程技術(shù)我其實(shí)并不是特別理解，改天研究下Intel手冊看個(gè)究竟。 2 同一個(gè)物理CPU的不同Core 3 同一個(gè)NUMA結(jié)點(diǎn)上的不同物理CPU 4 不同NUMA節(jié)點(diǎn)上的物理CPU。  NUMA（非一致性內(nèi)存系統(tǒng)），CPU和RAM是以結(jié)點(diǎn)為單位分組的，同一個(gè)CPU訪問本結(jié)點(diǎn)內(nèi)的本地RAM代價(jià)要比訪問其他節(jié)點(diǎn)的RAM代價(jià)低。CPU親緣關(guān)系越近，他們之間進(jìn)程遷移的代價(jià)越低。比如說，將進(jìn)程在同一個(gè)物理CPU下的兩個(gè)Core之間遷移，代價(jià)要低于不同物理CPU之間的遷移，原因就是一部分cache可以繼續(xù)使用。 load balance，就是將進(jìn)程從一個(gè)CPU(廣義的CPU)遷移到另一個(gè)CPU，如果將進(jìn)程從一個(gè)核的一個(gè)超線程域搬到另一個(gè)超線程域，沒啥關(guān)系，因?yàn)榇鷥r(jià)不高，就好像讓我從辦公樓4樓搬到辦公樓3樓，代價(jià)很低，但是CPU親緣關(guān)系越遠(yuǎn)，代價(jià)越高，就好像上午還在南京上班，下午讓我搬到烏魯木齊上班，所以這種搬家盡量要少。事實(shí)上linux 內(nèi)核也是這么做的。 OK，繼續(xù)我們的調(diào)度域：假如我們有兩個(gè)物理CPU，每個(gè)物理CPU有兩個(gè)Core，每個(gè)Core有通過超線程演化出兩個(gè)Virtual CPU，那么我們看下下面這個(gè)圖（這個(gè)圖是從Linux內(nèi)核SMP負(fù)載均衡淺析中拷貝的）  對于每個(gè)virtual CPU，屬于一組調(diào)度域sched_domain，就像我是位于雨花區(qū)的，同時(shí)我也是位于南京，我還是江蘇的，我還是位于中國的，我隸屬的不同區(qū)域反應(yīng)的不過是不同層次看我所處的位置。每個(gè)調(diào)度域分成多個(gè)組，就好像中國分成30多個(gè)省級行政單位，每個(gè)省級行政單位又分成不同的市，每個(gè)市又分成不同的區(qū)。 這還只是普通進(jìn)程的SMP 調(diào)度，想想實(shí)時(shí)進(jìn)程，我們每個(gè)CPU都有隊(duì)列，也許CPU-a的最高優(yōu)先級的實(shí)時(shí)進(jìn)程尚不如 CPU-b第二高優(yōu)先級的實(shí)時(shí)進(jìn)程，這時(shí)候，需要將CPU-b中的實(shí)時(shí)進(jìn)程拽到CPU-a上面執(zhí)行，不然，會(huì)出現(xiàn)低優(yōu)先級的實(shí)時(shí)進(jìn)程先執(zhí)行的異常情況，這個(gè)拽的過程是有pull_rt_task 實(shí)現(xiàn)的。 參考文獻(xiàn) 1 Linux內(nèi)核SMP負(fù)載均衡淺析 2 Linux 進(jìn)程調(diào)度淺析 3 鼠眼看Linux調(diào)度器 4 Linux調(diào)度器BFS簡介 5 BFS，Linux桌面的極速未來 |
|
|
