基于Linux內(nèi)核的CFS調(diào)度算法研究.pdf

《基于Linux內(nèi)核的CFS調(diào)度算法研究.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、CFS隨著Linux內(nèi)核的／fi斷發(fā)展，Linux已經(jīng)被許多人視為是未來(lái)最彳j．前途的操作系統(tǒng)之一。進(jìn)程調(diào)度是Linux操作系統(tǒng)的核心功能，在Linux的發(fā)展史上二起著非常重要的作用，不同的算法對(duì)系統(tǒng)性能的影響也是不一樣的。2．4內(nèi)核的0(n)算法和早期2．6內(nèi)核的O(1)算法都是以往調(diào)度算法中的經(jīng)典算法，但是存在著一些缺點(diǎn)。2．6．23內(nèi)核發(fā)布的CFS算法將公平的理念用到調(diào)度算法中，具釘劃時(shí)代的意義。本文將在研究以往調(diào)度算法優(yōu)缺點(diǎn)的基礎(chǔ)上重點(diǎn)介紹CFS調(diào)度算法。2．Linux2．4與Linux2．6調(diào)度算法簡(jiǎn)介2．1Linux2．4內(nèi)核調(diào)度算法2．4內(nèi)

2、核采用的調(diào)度算法是基于優(yōu)先級(jí)的設(shè)計(jì)。它存每次進(jìn)程切換時(shí)，內(nèi)核掃描町運(yùn)行進(jìn)程的鏈表，計(jì)算進(jìn)程的優(yōu)先級(jí)，然后選擇“最佳”進(jìn)程來(lái)運(yùn)行?。通過(guò)對(duì)2．4調(diào)度算法研究，發(fā)現(xiàn)存在以下幾個(gè)缺點(diǎn)：(1)開(kāi)銷太大：選擇最佳進(jìn)程所要消耗的時(shí)『日J(rèn)與町運(yùn)行的進(jìn)程數(shù)量相關(guān)，兇此達(dá)不到實(shí)時(shí)性的要求。(2)內(nèi)核小支持搶占：當(dāng)進(jìn)程處于內(nèi)核態(tài)時(shí)不會(huì)發(fā)生搶占，這對(duì)真正的實(shí)時(shí)應(yīng)用是不能接受的。(3)SMP效率：在2．4內(nèi)核中，就緒進(jìn)程隊(duì)列是一。個(gè)全局?jǐn)?shù)據(jù)結(jié)構(gòu)，調(diào)度算法對(duì)它的所，fr操作都會(huì)

3、人l全局自旋鎖而導(dǎo)致系統(tǒng)各個(gè)處理機(jī)之間的等待，這將導(dǎo)致大部分的CPU處于空閑狀態(tài)，從而影響SMP效率[

4、21。2．2Linux2．6內(nèi)核調(diào)度算法針對(duì)2．4內(nèi)核的缺點(diǎn)，IngoMolnar設(shè)計(jì)并實(shí)現(xiàn)了早期2．6內(nèi)核的調(diào)度算法，它的算法復(fù)雜度為O(1)，所以又叫O(1)算法。它繼承和發(fā)揚(yáng)了2．4內(nèi)核調(diào)度算法的特點(diǎn)，極人地改善了0(n)調(diào)度算法的缺陷。首先，O(1)調(diào)度算法所花費(fèi)的時(shí)間為常數(shù)，與當(dāng)前系統(tǒng)中的進(jìn)程個(gè)數(shù)無(wú)關(guān)。其次，它支持內(nèi)核態(tài)搶占，更好地支持了實(shí)時(shí)進(jìn)程。最后，增強(qiáng)了SMP的可擴(kuò)展性，每個(gè)處理器擁有獨(dú)市的運(yùn)行隊(duì)列和自旋鎖，不會(huì)產(chǎn)生互斥13】，極大地提高了SMP效率。在O(1)算法中，每個(gè)CPU都有一個(gè)運(yùn)行隊(duì)列，每個(gè)運(yùn)行隊(duì)列是一個(gè)二元數(shù)組arrays，按

5、時(shí)間片是否J}}J完分為兩個(gè)隊(duì)列和兩個(gè)隊(duì)列指針14I，指針active指向時(shí)間片沒(méi)用完、當(dāng)前作者簡(jiǎn)介：劉婷，女，安徽蚌埠人，碩士研究生。間片之后，它就被移動(dòng)到expired隊(duì)列中。在移動(dòng)過(guò)程中，調(diào)度算法會(huì)對(duì)其時(shí)間片重新進(jìn)行計(jì)算。當(dāng)active隊(duì)列中沒(méi)有就緒進(jìn)程時(shí)，active和expired兩個(gè)指針將執(zhí)行互換操作。相比O(n)算法，O(1)算法在交互性方面有很大的改進(jìn)，它實(shí)現(xiàn)了基十進(jìn)程過(guò)去行為的啟發(fā)式算法，以確定進(jìn)程應(yīng)該被當(dāng)作交白：式進(jìn)程還是批處理進(jìn)程。fH是，它對(duì)于交瓦式應(yīng)用仍然存在響應(yīng)件差的^d題，對(duì)NUMA支持也不完善。為了解決這磐^d題，大苣代石

6、f5被加入調(diào)度算法中，雖然很多性能問(wèn)題得到了解決，但是代碼很復(fù)雜且難以維護(hù)和閱讀。3．CFS算法在Linux2．6．23內(nèi)核中發(fā)布了一種新的調(diào)度算法——CFS算法，CFS是“CompletelyFairScheduler”的縮寫(xiě)，它主要是改進(jìn)早期2．6內(nèi)核調(diào)度算法的代碼復(fù)雜度的^d題，使調(diào)度算法變得更加簡(jiǎn)單有效。它的出現(xiàn)徹底改變r(jià)內(nèi)核看待進(jìn)程調(diào)度的方式，不再依賴劃分時(shí)間片和增加搶占點(diǎn)。0(1)算法的事要復(fù)雜性來(lái)自動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算，調(diào)度算法根據(jù)甲均睡眠時(shí)間和一些很難理解的經(jīng)驗(yàn)公式來(lái)修正進(jìn)程的優(yōu)先級(jí)以區(qū)分交互式進(jìn)程和批處理進(jìn)程。這樣的代碼很難閱讀和維護(hù)。相比

7、O(1)算法，CFS算法思路簡(jiǎn)單，拋棄了時(shí)間片和復(fù)雜的算法，它總足試圖按照對(duì)CPU時(shí)間的最大需求運(yùn)行進(jìn)程，這彳r助于確保每個(gè)進(jìn)程町以獲得對(duì)CPU的公平共享。3．1CFS算法基本理論通過(guò)研究Linux2．6．23內(nèi)核發(fā)現(xiàn)，CFS算法從RSDL／SD中吸取了完全公平的思想，不再跟蹤進(jìn)程的睡眠時(shí)間，也不再企圖l叉：分交互式進(jìn)程。它將所有的進(jìn)程都統(tǒng)一對(duì)待，這就是公甲的含義。但足所謂的公平并不是絕對(duì)公平，而是相對(duì)公平。在以往的調(diào)度算法中，當(dāng)給一個(gè)進(jìn)程分配40ms的CPU計(jì)算時(shí)間時(shí)，它會(huì)一直占有CPU，其它進(jìn)程必須等待，這就產(chǎn)生不公平。但足對(duì)于CFS算法，它會(huì)將40

8、ms的CPU計(jì)算時(shí)間根據(jù)優(yōu)先級(jí)比例分配給不同的進(jìn)程，使每個(gè)進(jìn)程都能牛日對(duì)公平地獲得CPU的執(zhí)行時(shí)間。3．1．1CFS算法主要思想CFS算法的核心思想是圍繞著虛擬時(shí)鐘展開(kāi)的。虛擬時(shí)鐘區(qū)別十硬件的實(shí)際時(shí)鐘，虛擬時(shí)鐘町以根據(jù)權(quán)重調(diào)節(jié)步調(diào)，一6l一按照不同的步調(diào)前進(jìn)。而實(shí)際時(shí)鐘是按著同定的步調(diào)前進(jìn)，不能改變。每個(gè)處理器不儀維護(hù)實(shí)際的時(shí)鐘，還任對(duì)應(yīng)的運(yùn)行隊(duì)列維護(hù)著一個(gè)虛擬時(shí)鐘，它的前進(jìn)步伐與該處理器上的進(jìn)程總權(quán)重成反比?？倷?quán)重越大，虛擬時(shí)鐘前進(jìn)的步伐越慢。l司時(shí)，每個(gè)進(jìn)程也有自己的虛擬時(shí)鐘，它記錄著進(jìn)程已經(jīng)占用CPU的虛擬時(shí)間。它的前進(jìn)步伐與進(jìn)程的權(quán)重成反比。進(jìn)程

9、的權(quán)重對(duì)應(yīng)進(jìn)程的優(yōu)先級(jí)，對(duì)丁不同優(yōu)先級(jí)的迸程，一般來(lái)說(shuō)，優(yōu)先級(jí)低的進(jìn)程其虛擬時(shí)鐘