自Linux 2.6以來(嚴(yán)格說應(yīng)該是2.5)，O(n)調(diào)度器被人們認(rèn)為是一種千年之前就應(yīng)該拋棄的東西被重重的甩開了，此后出現(xiàn)了O(1)，CFS等，再也沒人提起O(n)了。說實(shí)話，Linux的調(diào)度器遠(yuǎn)比標(biāo)準(zhǔn)Unix的來得復(fù)雜，因?yàn)長inux被用于不同的場合，從手機(jī)一直到大型服務(wù)器，跨度如此之大就需要兼各種情況，你既要使網(wǎng)絡(luò)服務(wù)器的吞吐量達(dá)到最大，又要使交互體驗(yàn)更佳，然而有時(shí)候吞吐量和延遲卻是魚與熊掌的關(guān)系...
??????? O(n)被徹底遺忘，某種程度上反映了人們的思維誤區(qū)，那就是“解決問題的方案隨著問題的復(fù)雜化而復(fù)雜，殊不知方案復(fù)雜度的增加很多在于方案本身而不是問題”。走了這么多年，人們已然忘記了一樣?xùn)|西在剛出現(xiàn)時(shí)是什么樣子了，隨著時(shí)間的流逝，任何事物都會面目全非，于是人們“站在巨人的肩上”使其越來越復(fù)雜，最終崩潰...在路上，或者在崩潰前夕，如果能停下來尋找一下本源，返璞歸真的東西也許更好，Con Kolivas研發(fā)了BFS調(diào)度器，正是循著這樣的思路進(jìn)行的，于是他為自己的調(diào)度器起了一個(gè)十分具有諷刺意義的名字：Brain Fuck ...

0.小手段

計(jì)算機(jī)操作系統(tǒng)不是神，它們沒有靈魂，然而作為一款通用操作系統(tǒng)，很多設(shè)計(jì)者都希望其兼顧所有的情況，既要滿足桌面交互的低延遲需求，又要滿足大吞吐量，同時(shí)又要支持N多個(gè)處理器，因此就需要做負(fù)載均衡...作為一個(gè)通用的調(diào)度器的設(shè)計(jì)，為了照顧這么多種情況，你不得不引入一些小巧的手段來專門照顧這些另類的需求。

1.調(diào)度器回顧

O(n)調(diào)度器

Linux的初始版本使用的是O(n)調(diào)度器，它采用單一鏈表，用遍歷比較的方式，采用冒泡算法進(jìn)行pick-next，下課的原因在于：
a.O(n)中的n嚇倒了很多人，大家都不喜歡這個(gè)n，因?yàn)樗臅r(shí)間復(fù)雜度會隨著進(jìn)程數(shù)量的增加而增加
b.單一的隊(duì)列，進(jìn)程等待時(shí)間可能過長，造成饑餓
c.多處理器的出現(xiàn)，為了避免頻繁鎖定
d.它太簡單了？玩弄高深的人不喜歡簡單的東西？?

O(1)調(diào)度器

2.6內(nèi)核采用了O(1)調(diào)度器，該調(diào)度器引入了每CPU的優(yōu)先級隊(duì)列組，每組隊(duì)列包含active和expire兩個(gè)隊(duì)列，采用啟發(fā)式算法動態(tài)調(diào)整優(yōu)先級，盡可能的進(jìn)行時(shí)間片補(bǔ)償和懲罰等動態(tài)計(jì)算，多CPU之間的優(yōu)先級隊(duì)列負(fù)載均衡。下課的原因有兩點(diǎn)：1.啟發(fā)式算法，補(bǔ)償/懲罰機(jī)制過于復(fù)雜，導(dǎo)致算法本身消耗巨大；2.有了更好的CFS調(diào)度器。

類“多級反饋隊(duì)列”調(diào)度器

此調(diào)度器只以patch的形式存在，在并入mainline之前即被CFS取代。采用類似4.4BSD的傳統(tǒng)UNIX調(diào)度算法，其優(yōu)點(diǎn)在于免饑餓以及大吞吐量，這也正是UNIX的特點(diǎn)，缺點(diǎn)在于延遲不穩(wěn)定，仍然需要一些“小手段”來“玷污”良好的設(shè)計(jì)。

CFS調(diào)度器

該調(diào)度器于2.6.23被并入，旨在消除一切的“小手段”，采用完全公平的策略進(jìn)行調(diào)度，引入了虛擬時(shí)鐘的概念，進(jìn)程的優(yōu)先級以及性別(IO?Calc?交互性?)完全映射到虛擬時(shí)鐘的速率上，基于虛擬時(shí)鐘的補(bǔ)償性調(diào)度。理論很美，然而為了支持SMP以及交互進(jìn)程要求日益提高，仍然引入了“小手段”-睡眠補(bǔ)償，調(diào)度域負(fù)載均衡等。

接下來的調(diào)度器

一定要以一種徹底的方式消除那些“小手段”，“小手段”的引入完全是“兼顧所有情況”這種“魚與熊掌可兼得”的思想造成的。如果我們回顧上述的調(diào)度器，就會發(fā)現(xiàn)從O(1)開始，基本都是拆東墻補(bǔ)西墻的方式，解決一個(gè)問題從而引入另一個(gè)問題。照此以往，事情會越來越復(fù)雜的。如果嘗試在O(n)調(diào)度器的基礎(chǔ)上優(yōu)化，可能會更好，因?yàn)镺(n)調(diào)度器最純粹。

2.BFS調(diào)度器的引入

給出一個(gè)圖片

前些天突然在網(wǎng)上看到了下面的圖片

后來發(fā)現(xiàn)該圖片是BFS調(diào)度器的引子，太具有諷刺意義了。

可配置型調(diào)度器的需求

為了避免小手段，那就要徹底拋棄“魚與熊掌可兼得”的思想，采用“一種調(diào)度器只適用于一種場景”的新思路。如此我們可以設(shè)計(jì)多種調(diào)度器，在安裝操作系統(tǒng)的時(shí)候可以由管理員進(jìn)行配置，比如我們將其用于桌面，那么就使用“交互調(diào)度器”，如果用于路由器，那就使用“大吞吐調(diào)度器”...消除了兼顧的要求，調(diào)度器設(shè)計(jì)起來就更佳簡單和純粹了。
??????? 面對需要大吞吐量的網(wǎng)絡(luò)操作系統(tǒng)，我們有傳統(tǒng)的UNIX調(diào)度器，然而面對日益桌面化的操作系統(tǒng)比如Android手機(jī)，我們是否能摒棄那種大而全的調(diào)度策略呢？Con Kolivas老大設(shè)計(jì)出的BFS調(diào)度器就是為桌面交互式應(yīng)用量身打造的。

問題在哪？

Linux 2.6內(nèi)核實(shí)現(xiàn)了那么多的調(diào)度器，然而其效果總是有美中不足的地方，到底問題出在哪里？事實(shí)上，Linux 2.6的各種調(diào)度器的實(shí)現(xiàn)都不是完全按照理論完成的，其中都添加了一些小手段。比如雖然CFS號稱支持大于2048的CPU個(gè)數(shù)，然而實(shí)際應(yīng)用中，效果未必好，因?yàn)镃FS調(diào)度器繼承了O(1)調(diào)度器的load_balance特性，因此在那么多處理器之間進(jìn)行基于調(diào)度域的load_balance，鎖定以及獨(dú)占的代價(jià)將會十分大，從而抵消了每CPU隊(duì)列帶來的消除鎖定的優(yōu)勢。
??????? 總之，這些調(diào)度器太復(fù)雜了，而且越來越復(fù)雜，將80%的精力消耗在了20%的場景中。實(shí)際上，做設(shè)計(jì)不要聯(lián)想，完全依照我們目前所知道的和所遇到的來，在可用性和效率上被證明是明智的，當(dāng)然不考慮太多的可擴(kuò)展性。

回到O(n)調(diào)度器

BFS調(diào)度器用一句話來總結(jié)就是“回到了O(n)調(diào)度器”，它在O(n)調(diào)度器的基礎(chǔ)上進(jìn)行了優(yōu)化，而沒有引入看起來很好的O(1)調(diào)度器，這就是其實(shí)質(zhì)。O(n)調(diào)度器有什么不好么？有的。大不了就是遍歷的時(shí)間太長，BFS根據(jù)實(shí)際的測試數(shù)據(jù)忽略之；每個(gè)處理器都要鎖定整個(gè)隊(duì)列，BFS改之，做到這些既可，這才叫基于O(n)調(diào)度器的優(yōu)化而不是徹底顛覆O(n)調(diào)度器而引入O(1)調(diào)度器-當(dāng)然前提是桌面環(huán)境。如果說能回到原始的O(n)調(diào)度器進(jìn)行修改使之重新發(fā)揮其作用而不是徹底拋棄它，這才是最佳的做法，反之，如果我們把問題的解決方案搞的越來越復(fù)雜，最終就是陷入一個(gè)泥潭而不可自拔。要知道方案復(fù)雜性的積累是一個(gè)笛卡兒積式的積累，你必須考慮到每一種排列組合才能，當(dāng)你做不到這一點(diǎn)的時(shí)候，你就需要返璞歸真。

BFS調(diào)度器的原理

BFS的原理十分簡單，其實(shí)質(zhì)正是使用了O(1)調(diào)度器中的位圖的概念，所有進(jìn)程被安排到103個(gè)queue中，各個(gè)進(jìn)程不是按照優(yōu)先級而是按照優(yōu)先級區(qū)間被排列到各自所在的區(qū)間，每一個(gè)區(qū)間擁有一個(gè)queue，如下圖所示：

內(nèi)核在pick-next的時(shí)候，按照O(1)調(diào)度器的方式首先查找位圖中不為0的那個(gè)queue，然后在該queue中執(zhí)行O(n)查找，查找到virtual deadline(如下所述)最小的那個(gè)進(jìn)程投入執(zhí)行。過程很簡單，就像流水一樣。之所以規(guī)劃103個(gè)隊(duì)列而不是一個(gè)完全是為了進(jìn)程按照其性質(zhì)而分類，這個(gè)和每CPU沒有任何關(guān)系，將進(jìn)程按照其性質(zhì)(RT?優(yōu)先級?)分類而不是按照CPU分類是明智之舉。內(nèi)核中只有一個(gè)“103隊(duì)列”，m個(gè)CPU和“103隊(duì)列”完全是一個(gè)“消費(fèi)者-生產(chǎn)者”的關(guān)系。O(1)調(diào)度器，內(nèi)核中擁有m(CPU個(gè)數(shù))個(gè)“消費(fèi)者-生產(chǎn)者”的關(guān)系，每一個(gè)CPU附帶一個(gè)“生產(chǎn)者(140隊(duì)列組)”。
????????只有統(tǒng)一的，單一的“消費(fèi)者-生產(chǎn)者”的關(guān)系才能做到調(diào)度的公平，避免了多個(gè)關(guān)系之間踢皮球現(xiàn)象，這是事實(shí)。在結(jié)構(gòu)單一，功能確定且硬件簡單的系統(tǒng)中，正確的調(diào)度器架構(gòu)如下圖所示：

在結(jié)構(gòu)單一，功能確定且硬件簡單的系統(tǒng)中，不正確的調(diào)度器架構(gòu)如下圖所示：

BFS調(diào)度器初始版本的鏈表的非O(n)遍歷

BFS調(diào)度器的發(fā)展歷程中也經(jīng)歷了一個(gè)為了優(yōu)化性能而引入“小手段”的時(shí)期，該“小手段”是如此合理，以至于每一個(gè)細(xì)節(jié)都值得品味，現(xiàn)表述如下：
大家都知道，遍歷一個(gè)鏈表的時(shí)間復(fù)雜度是O(n)，然而這只是遍歷的開銷，在BFS調(diào)度器中，遍歷的目的其實(shí)就是pick-next，如果該鏈表某種意義上是預(yù)排序的，那么pick-next的開銷可以減少到接近O(1)。BFS如何做到的呢？我們首先看一下virtual deadline的概念
virtual deadline(VD)
VD=jiffies + (prio_ratio * rr_interval)
其中prio_ratio為進(jìn)程優(yōu)先級，rr_interval為一個(gè)Deadline，表示該進(jìn)程在最多多久內(nèi)被調(diào)度，鏈表中的每一個(gè)entry代表一個(gè)進(jìn)程，都有一個(gè)VD與之相關(guān)。VD的存在使得entry在鏈表的位置得以預(yù)排序，這里的預(yù)排序指的是vitrual deadline expire的影響下的預(yù)排序，BFS和O(n)的差別就在于這個(gè)expire，由于這個(gè)expire在，一般都會在遍歷的途中遇到VD expire，進(jìn)而不需要O(n)。基于VD的O(n)和基于優(yōu)先級的O(n)是不同的，其區(qū)別在于根據(jù)上述的計(jì)算公式，VD是單調(diào)向前的，而優(yōu)先級幾乎是不怎么變化的，因此基于VD的O(n)調(diào)度器某種程度上和基于紅黑樹的CFS是一樣的，VD也正類似于CFS中的虛擬時(shí)鐘，只是數(shù)據(jù)結(jié)構(gòu)不同而已，BFS用鏈表實(shí)現(xiàn)，CFS用紅黑樹實(shí)現(xiàn)。
??????? 其實(shí)，O(n)并沒有那么可怕，特別是在桌面環(huán)境中，你倒是有多少進(jìn)程需要調(diào)度呢？理論上O(n)會隨著進(jìn)程數(shù)量的增加而效率降低，然而桌面環(huán)境下實(shí)際上沒有太多的進(jìn)程需要被調(diào)度，所以采用了BFS而拋棄了諸多小手段的調(diào)度器效果會更好些。理論上，CFS或者O(1)可以支持SMP下的諸多進(jìn)程調(diào)度的高效性，然而，桌面環(huán)境下，第一，SMP也只是2到4個(gè)處理器，進(jìn)程數(shù)也大多不超過1000個(gè)，進(jìn)程在CPU之間蹦來蹦去，很累，何必殺雞用牛刀呢？瓶頸不是雞，而是殺雞的刀，是吧！

pick-next算法

BFS的pick-next算法對于SCHED_ISO進(jìn)程依照以下的原則進(jìn)行：
a.依照FIFO原則進(jìn)行，不再遍歷鏈表
BFS的pick-next算法對于SCHED_NORMAL或者SCHED_IDLEPRIO進(jìn)程依照以下的原則進(jìn)行：
a.遍歷運(yùn)行鏈表，比較每一個(gè)entry的VD，找出最小的entry，從鏈表中刪除，投入運(yùn)行
b.如果發(fā)現(xiàn)有entry的VD小于當(dāng)前的jiffers，則停止遍歷，取出該entry，投入運(yùn)行--小手段
以上的原則可以總結(jié)為“最小最負(fù)最優(yōu)先”原則。作者一席話如下：
BFS has 103 priority queues. 100 of these are dedicated to the static priority
of realtime tasks, and the remaining 3 are, in order of best to worst priority,
SCHED_ISO (isochronous), SCHED_NORMAL, and SCHED_IDLEPRIO (idle priority
scheduling). When a task of these priorities is queued, a bitmap of running
priorities is set showing which of these priorities has tasks waiting for CPU
time. When a CPU is made to reschedule, the lookup for the next task to get
CPU time is performed in the following way:

First the bitmap is checked to see what static priority tasks are queued. If
any realtime priorities are found, the corresponding queue is checked and the
first task listed there is taken (provided CPU affinity is suitable) and lookup
is complete. If the priority corresponds to a SCHED_ISO task, they are also
taken in FIFO order (as they behave like SCHED_RR). If the priority corresponds
to either SCHED_NORMAL or SCHED_IDLEPRIO, then the lookup becomes O(n). At this
stage, every task in the runlist that corresponds to that priority is checked
to see which has the earliest set deadline, and (provided it has suitable CPU
affinity) it is taken off the runqueue and given the CPU. If a task has an
expired deadline, it is taken and the rest of the lookup aborted (as they are
chosen in FIFO order).

Thus, the lookup is O(n) in the worst case only, where n is as described
earlier, as tasks may be chosen before the whole task list is looked over.
使用virtual deadline，類似于CFS的virtual runtime的概念，然而不要紅黑樹，而采用了雙向鏈表來實(shí)現(xiàn)，因?yàn)榧t黑樹的插入效率不如鏈表插入效率，在pick-next算法上雖然紅黑樹占優(yōu)勢，然而由于VD expire的存在也使得pick-next不再是O(n)了。
??????? BFS初始版本的小手段的意義在于減少O(n)遍歷比較時(shí)間復(fù)雜度帶來的恐懼。

去除了小手段的BFS調(diào)度器

最終將小手段去除是重要的，否則BFS最終還是會陷入類似O(1)，CFS等復(fù)雜化的泥潭里面不可自拔，因此在后續(xù)的patch中，BFS去除了上述的小手段，用統(tǒng)一的O(n)復(fù)雜度來pick-next，畢竟前面已經(jīng)說了O(n)在特定環(huán)境下并不是問題的關(guān)鍵，該patch在2.6.31.14-bfs318-330test.patch中體現(xiàn)。

隊(duì)列外部執(zhí)行

BFS調(diào)度器和CFS是一樣的，都是隊(duì)列外執(zhí)行進(jìn)程的，這樣可以減少鎖爭用帶來的性能問題。再列出作者的一席話：
BFS has one single lock protecting the process local data of every task in the
global queue. Thus every insertion, removal and modification of task data in the
global runqueue needs to grab the global lock. However, once a task is taken by
a CPU, the CPU has its own local data copy of the running process' accounting
information which only that CPU accesses and modifies (such as during a
timer tick) thus allowing the accounting data to be updated lockless. Once a
CPU has taken a task to run, it removes it from the global queue. Thus the
global queue only ever has, at most,

????(number of tasks requesting cpu time) - (number of logical CPUs) + 1

tasks in the global queue. This value is relevant for the time taken to look up
tasks during scheduling. This will increase if many tasks with CPU affinity set
in their policy to limit which CPUs they're allowed to run on if they outnumber
the number of CPUs. The +1 is because when rescheduling a task, the CPU's
currently running task is put back on the queue. Lookup will be described after
the virtual deadline mechanism is explained.
??????? 在schedule核心函數(shù)中，使用return_task來把prev進(jìn)程重新入隊(duì)，在earliest_deadline_task這個(gè)pick-next中，使用take_task將選中的next從隊(duì)列取出，從而實(shí)現(xiàn)隊(duì)列外執(zhí)行。

綜上的結(jié)論

從上面的論述，我們絲毫沒有看到有任何的諸如“SMP負(fù)載均衡”，“CPU親和力”，“補(bǔ)償”，“懲罰”之類的字眼，是的，這些字眼在BFS中完全不需要，BFS也正是摒棄了這些字眼才獲得成功的，畢竟在一個(gè)一般人使用的桌面操作系統(tǒng)中，沒有這么多的套套，大多數(shù)人使用的就是一個(gè)只有一個(gè)到兩個(gè)處理器核心的系統(tǒng)，難道有必要搞什么調(diào)度域么？難道有必要搞什么NUMA么？需求決定一切，面對大型服務(wù)器，有UNIX的機(jī)制站在那里，而如果我們想把Linux推廣到每一個(gè)掌上設(shè)備，那就沒必要復(fù)制UNIX的那套了，BFS完全可以完美的搞定一切。小手段的去除，說明BFS調(diào)度器的發(fā)展方向起碼是正確的。
??????? BFS對SMP的支持如何呢？答案是它僅僅支持少量CPU的SMP體系，別忘了BFS的應(yīng)用場合。因?yàn)樵谡{(diào)度過程中需要一個(gè)遍歷所有CPU的O(m)復(fù)雜度的計(jì)算，這就明確告訴人們，別指望BFS使用在擁有4096個(gè)CPU的系統(tǒng)上，正如沒人用這種系統(tǒng)看視頻一樣，那樣的話，還是乖乖使用CFS吧。

展示一些代碼

BFS調(diào)度器思想很簡單：集中精力做好一件事，適應(yīng)一種場景，代碼同樣十分簡單，因此即使貼上代碼整個(gè)文章也不會顯得過于冗長，你再也看不到諸如load_balance或者for_each_domain之類的東西了，至于CPU cache的親和力智能判斷，如果你非要做，那么就自己調(diào)用sched_setaffinity系統(tǒng)調(diào)用設(shè)置吧，把一個(gè)線程或者一組相關(guān)的進(jìn)程設(shè)置到一個(gè)或者一組共享Cache的CPU上，讓內(nèi)核這些，在進(jìn)程不那么多，CPU個(gè)數(shù)不那么多，沒有NUMA的系統(tǒng)上，真的太累了。

a.進(jìn)程插入

當(dāng)有一個(gè)進(jìn)程要插入運(yùn)行隊(duì)列的時(shí)候，調(diào)度器要遍歷所有的CPU，看一下是否能搶占某個(gè)CPU上正在運(yùn)行的進(jìn)程，這種策略是十分合理的。BFS調(diào)度器將所有的CPU作為一個(gè)執(zhí)行者，其執(zhí)行的資源就是唯一的運(yùn)行隊(duì)列。如果不能搶占任何進(jìn)程，那就將喚醒的進(jìn)程相插入到相應(yīng)隊(duì)列的末尾位置，等待deadline的調(diào)度：
static inline void enqueue_task(struct task_struct *p) { if (idleprio_task(p) && !rt_task(p)) { if (idleprio_suitable(p)) p->prio = p->normal_prio; else p->prio = NORMAL_PRIO; } if (iso_task(p) && !rt_task(p)) { if (isoprio_suitable()) p->prio = p->normal_prio; else p->prio = NORMAL_PRIO; } __set_bit(p->prio, grq.prio_bitmap); list_add_tail(&p->run_list, grq.queue + p->prio); sched_info_queued(p); }

b.進(jìn)程喚醒

BFS省略了復(fù)雜的負(fù)載均衡機(jī)制，因此try_to_wake_up瘦身了很多很多。BFS不做調(diào)度域負(fù)載均衡，其理由是“在決定將進(jìn)程投入運(yùn)行的時(shí)候，消耗一點(diǎn)點(diǎn)計(jì)算來讓其自選CPU”。全局的看待整個(gè)CPU集合才是王道，所謂的負(fù)載均衡并不是說每個(gè)CPU上排隊(duì)待運(yùn)行進(jìn)程數(shù)量的均衡，而是讓每個(gè)CPU都動起來。因此唯一需要均衡的地方就是搶占，如果不能搶占任何CPU上的當(dāng)前進(jìn)程，那么就排入到全局的BFS隊(duì)列中，這是個(gè)全局的隊(duì)列而不是每CPU隊(duì)列，因此對各個(gè)CPU機(jī)會是均等的，當(dāng)CPU需要運(yùn)行一個(gè)進(jìn)程的時(shí)候，讓其自己來這個(gè)全局隊(duì)列中挑選一個(gè)最值得運(yùn)行的，而在這里，所有的CPU的挑選策略是相同的！
static int try_to_wake_up(struct task_struct *p, unsigned int state) { unsigned long flags; int success = 0; long old_state; struct rq *rq; rq = time_task_grq_lock(p, &flags); old_state = p->state; if (!(old_state & state)) goto out_unlock; if (queued_or_running(p)) goto out_running; activate_task(p, rq); //調(diào)用enqueue_task try_preempt(p, rq); //這里有一個(gè)O(m)時(shí)間復(fù)雜度的計(jì)算，m為cpu的個(gè)數(shù) success = 1; out_running: trace_sched_wakeup(rq, p, success); p->state = TASK_RUNNING; out_unlock: task_grq_unlock(&flags); return success; } 我們沒有看到關(guān)于任何關(guān)于CPU親和力的“小手段”，在不多于16個(gè)CPU的系統(tǒng)上，完全沒有必要考慮CPU親和力帶來的巨大性能影響，如今的處理器都是微封裝的，大多數(shù)的桌面處理器都使用共享Cache，因此為了榨取那么一點(diǎn)點(diǎn)“一級緩存命中”所帶來的性能提升而增加如此復(fù)雜的針對于CPU親和力的負(fù)載均衡代碼，得不償失！

c.進(jìn)程調(diào)度的pick-next

在BFS中，首先要調(diào)度的是搶占的進(jìn)程，如果有進(jìn)程搶占其它正在運(yùn)行的進(jìn)程，那么將它投入運(yùn)行：
static inline struct task_struct *earliest_deadline_task(struct rq *rq, struct task_struct *idle) { unsigned long long_deadline, shortest_deadline; struct task_struct *edt, *p; unsigned int cpu = rq->cpu; struct list_head *queue; int idx = 0; if (rq->preempt_next) { //rq->preempt_next在try_preempt中設(shè)置 if (likely(task_queued(rq->preempt_next) && cpu_isset(cpu, rq->preempt_next->cpus_allowed))) { edt = rq->preempt_next; goto out_take; } } retry: idx = find_next_bit(grq.prio_bitmap, PRIO_LIMIT, idx); queue = &grq.queue[idx]; if (idx < MAX_RT_PRIO) { /* We found rt tasks */ list_for_each_entry(p, queue, run_list) { if (cpu_isset(cpu, p->cpus_allowed)) { edt = p; goto out_take; } } /* More rt tasks, we couldn't take the lower prio ones */ ++idx; goto retry; } /* No rt tasks, find earliest deadline task */ edt = idle; if (unlikely(idx >= PRIO_LIMIT)) { /* All rt tasks but none suitable for this cpu */ goto out; } long_deadline = shortest_deadline = longest_deadline() * 2 + 1; list_for_each_entry(p, queue, run_list) { unsigned long deadline_diff; /* Make sure cpu affinity is ok */ if (!cpu_isset(cpu, p->cpus_allowed)) continue; deadline_diff = p->deadline - jiffies; /* Normalise all old deadlines and cope with jiffy wrap. */ if (deadline_diff > long_deadline) deadline_diff = 0; /* Select the earliest deadline task now */ //簡單的冒泡比較 if (edt == idle || deadline_diff < shortest_deadline) { shortest_deadline = deadline_diff; edt = p; } } if (edt == idle) { if (idx < IDLE_PRIO) { /* Haven't checked for SCHED_IDLEPRIO tasks yet */ idx++; goto retry; } goto out; } out_take: take_task(rq, edt); out: return edt; }

d.時(shí)間片用盡

略......

自己的體驗(yàn)

費(fèi)了九牛二虎之力，編譯好了帶有BFS的內(nèi)核(實(shí)際上只是在2.6.32內(nèi)核上打上了一個(gè)patch，然后重新編譯內(nèi)核而已，然而這個(gè)工作量不小，你可以試試...)，基于Debian的桌面版本，硬件是在垃圾場淘的巨老無比的P4，效果十分可觀，起碼和Mac OS一樣了，由此我再也不把Redhat的桌面看作可有可無的部分了。以前我總是編輯/etc/inittab文件將其啟動到level 3，然后用ssh登錄操作之，現(xiàn)在我也可以直接進(jìn)level 5了，這就是BFS的效果。順帶說一句，如果你使用很高檔或者比較高檔的硬件，那么這個(gè)效果就不明顯了，學(xué)子們注意了，別較真兒
??????? 聽說Android使用了該調(diào)度器，我還沒有嘗試，因?yàn)槲覜]有預(yù)算買設(shè)備。

3.更多的寓意

寫這篇文章的目的在于引出一些寓意，而不是介紹BFS調(diào)度器本身。該寓意在于，歷史得看問題或許會更好。埋沒在歷史深處的事務(wù)并不一定是過時(shí)的，它可能是最能反映問題本質(zhì)的，不要將其置之不顧，時(shí)不時(shí)地回頭看一眼，有的時(shí)候，它會給你更多的思路。

?? ? ?? 所謂的操作系統(tǒng)進(jìn)程調(diào)度就是為了讓所有的CPU都動起來，這是一門藝術(shù)而不僅僅是一門技術(shù)。你既不能讓CPU空閑，又不能讓某些進(jìn)程排隊(duì)等待時(shí)間過長，這是一個(gè)CPU利用率和對待進(jìn)程公平性的游戲。這才是問題的本質(zhì)，而這個(gè)問題的本質(zhì)在不同的硬件配置以及使用場景下又有不同的表現(xiàn)，因此調(diào)度器為了迎合這種差異巨大的不同的表現(xiàn)不可能做成一個(gè)統(tǒng)一的，只有具體問題具體分析才能得到良好的表現(xiàn)

?本文轉(zhuǎn)自 dog250 51CTO博客，原文鏈接:http://blog.51cto.com/dog250/1268976

總結(jié)

以上是生活随笔為你收集整理的返璞归真的Linux BFS调度器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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