Linux進程調度算法分析

1、計 算 機 與 現 代 化 2009年第 6期J I S UANJ I Y U X I A NDA I HUA總第 166期文章編號 :100622475(2009 0620013203收稿日期 :2008211225作者簡介 :馮宇 (19832 , 男 , 四川成都人 , 電子科技大學計算機科學與工程學院碩士研究生 , 研究方向 :軟件工程 。L inux 進程調度算法分析馮 宇 , 左志宏(電子科技大學計算機科學與工程學院 , 四川 成都 610054摘要 :在 L inux 系統(tǒng)中 , 進程作為實體自始至終運行在系統(tǒng)之中 , 進程使用系統(tǒng)的資源 , 而進程的調度更是影響系統(tǒng)的性 能 :

2、進程響應時間盡可能快 , 后臺進程的吞吐量盡可能高 , 進程 “ 餓死 ” 現象盡可能避免 , 低優(yōu)先級和高優(yōu)先級進程需要盡 可能調和 。 本文從 L inux 2. 4. 0內核角度分析影響進程調度的各個因素和調度處理流程 , 以及在 S M P (Sy mmetric M ultiPr ocessing 的進程調度處理 。關鍵詞 :L inux 操作系統(tǒng) ; 進程 ; 進程調度 ; 性能 ; 對稱多處理器 中圖分類號 :TP311 文獻標識碼 :AA lgor ith m Ana lysis of L i n ux Process Scheduli n gFENG Yu, Z UO Zhi

3、 2hong(College of Computer Science and Engineering, University of Electr onic and ogy Chengdu 610054, China Abstract:I n L inux syste m, p r ocess runs all the way as entity . p r the p r ocess scheduling af 2fect the perf or mance of the system:p r ocess res ponse ti m backgr ound p r ocess thr oug

4、hput should be as large as possible, the phenomenon Starve t be avoid as far as possible, l ow p ri or level needs t o rec 2oncile with high p ri or as analyses many fact or which influenced by p r ocess scheduling fr o m L inux 2. 4. 0in S MP (Sy mmetric M ulti Pr ocessing .Key words:L inux syste m

5、; p r ocess; p r ocess scheduling; perf or mance; S M P (Sy mmetric Multi Pr ocessing 0 引 言自 1991年 L inux 操作系統(tǒng)出現以來 , L inux 操作系統(tǒng)以令人驚異的速度迅速在服務器和桌面系統(tǒng)中 獲得了成功 。 它已經被業(yè)界認為是未來最有前途的 操作系統(tǒng)之一 , 并且在嵌入式領域 , 由于 L inux 操作 系統(tǒng)具有開放源代碼 、 良好的可移植性 、 豐富的代碼 資源以及異常的健壯 , 使得它獲得越來越多的關注 。 本文從進程的角度來分析 L inux 進程調度算法 。1 影響調度的因素L

6、inux 的調度是基于分時技術的 , 給每個可運行 進程分配一個時間片 , 當進程運行結束或時間片到期 時 , 進程就發(fā)生切換 。在 L inux 調度算法中 , 每次進 程切換 , 內核掃描可運行進程鏈表 , 計算進程的優(yōu)先 級 , 有時會用復雜的算法求出進程的當前優(yōu)先級 , 選 擇 “ 最適合 ” 的進程運行 (在未說明 S MP 時 , 默認為單處理器系統(tǒng) , 即每個進程都有一個值與之相關 聯(lián) , 這個值用來表示進程如何適當地分配給 CP U, 也 就是進程的優(yōu)先級 。 1. 1優(yōu)先級優(yōu)先級可分為靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級 。(1 靜態(tài)優(yōu)先級 。每個進程都有它的靜態(tài)優(yōu)先級 , 新進程總是繼承

7、父進程的靜態(tài)優(yōu)先級 , 不過也可以通過 nice 等系統(tǒng)調用來改變靜態(tài) 優(yōu)先級 。 靜態(tài)優(yōu)先級的值是與進程的類型有關的 。 對進程進 行如下分類 : 交互式進程 (interactive p r ocess 。這類進程經常和用戶交互 , 要花很多的時間等待鍵盤和 鼠標的操作 。 當接受輸入后 , 進程必須很快被喚醒 , 否則用戶 就會發(fā)現 系 統(tǒng) 反 應 遲 鈍 。典 型 情 況 是 , 平 均 延 遲 是 50150m s 。 常見的交互式命令有 shell 、 文本編輯程序和圖形應用 程序等 。 批處理進程 (batch p r ocess 。與交互式進程相反 , 這類進程不需要與用戶交互

8、 , 因此經 14 計 算 機 與 現 代 化 2009年第 6期常在后臺運行 , 所以這類進程不必很快被 CP U 喚醒 , 經常被 調度程序延遲 。 常見的批處理進程有編譯程序 、 數據庫搜索 引擎等 。 實時進程 (real 2ti m e p r ocess 。很強的調度需要 , 不能被低優(yōu)先級的進程阻塞 , 必須在一 個很短的時間內響應 。 常見的實時進程有視頻和音頻應用程 序 、 工業(yè)控制程序等 。不同類型進程的靜態(tài)優(yōu)先級也不一樣 。 實時進程的優(yōu)先 級是從 1(最高優(yōu)先級 99(最低優(yōu)先級 的值 ; 普通進程的 優(yōu)先級是從 100(最高優(yōu)先級 139(最低優(yōu)先級 , 值越小 優(yōu)先

9、級越高 。 在 L inux 中 , 進程的優(yōu)先級是動態(tài)的 , 調度程序 跟蹤進程的行為 , 并周期性地動態(tài)調整進程的優(yōu)先級 。比如 , 在較長的時間沒有被 CP U 使用的進程 , 提高它的優(yōu)先級 ; 已 經在 CP U 上運行較長時間的進程 , 則降低它的優(yōu)先級 。(2 動態(tài)優(yōu)先級 。普通進程除了靜態(tài)優(yōu)先級 , 還有動態(tài)優(yōu)先級 , 其值的范圍 是 100(最高優(yōu)先級 139(最低優(yōu)先級 。它與靜態(tài)優(yōu)先級 的關系使用下面的經驗公式表示 :動態(tài)優(yōu)先級 =max(100, m in (靜態(tài)優(yōu)先級 2bonus+5, 139 其中 bonus 是從范圍 010的值 , 值小于 5表示降低動態(tài) 優(yōu)先

10、級 , 值大于 5表示提高動態(tài)優(yōu)先級 。 bonus 的值與進程的 平均睡眠時間有關 (如表 1所示 。 眠狀態(tài)所消耗的平均納秒數 。表 1 bonus bonus 粒度 大于或等于 005120大于或等于 100小于 200m s 12560大于或等于 200小于 300m s 21280大于或等于 300小于 400m s 3640大于或等于 400小于 500m s 4320大于或等于 500小于 600m s 5160大于或等于 600小于 700m s 680大于或等于 700小于 800m s 740大于或等于 800小于 900m s 820大于或等于 900小于 1000m s

11、910大于 1s1010 平均睡眠時間也被調度程序用來確定一個給定 進程是交互式進程還是批處理進程 。如果一個進程 滿足下面的公式 , 就被看作是交互式進程 :動態(tài)優(yōu)先級 <=33靜態(tài)優(yōu)先級 /4+28有了進程的優(yōu)先級 , 就可以對進程進行調度 。每 個 L inux 進程總是按照一定的調度策略類型被調 度的 。1. 2進程的調度策略(1 SCHE D_FI F O 調度策略 。先進先出的實時進程 。當調度程序把 CP U 分配給進程的時候 , 它把該進程描述符保留在運行隊列鏈表的隊列頭位 置 , 如果沒有其他可運行的更高優(yōu)先級的實時進程 , 進程就繼續(xù)使用 CP U, 想用多久就可以用

12、多久 , 直到該實時進程運行結束 , 即使還有其他的具有相同優(yōu)先級的實時進程處于可運行 狀態(tài) 。(2 SCHE D_RR調度策略 。時間片輪轉的實時進程 。當調度程序把 CP U 分配給進 程的時候 , 它把該進程的描述符放在運行隊列鏈表的末尾 。 這種調度策略可以保證對所有具有相同優(yōu)先級的實時進程公 平地分配 CP U 時間 。(3 SCHE D_NORMAL 調度策略 。普通的分時進程 。當調度程序把 CP U 分配給進程的時 候 , 它檢查進程的時間片是否用完 , 如果沒有則繼續(xù)運行該進 程 ; 如果用完 , 把該進程的描述符放在運行隊列鏈表的末尾 , 調度運行隊列鏈表的下一個進程 。

13、如果所有的進程時間片都 用完 , 則賦予所有進程新的時間片 , 然后進行新一輪的調用 。2 進程調度程序由內核函數 schedule ( 實現調度程序。 首先對所 有進程進行檢測 , 喚醒任何一個已經得到信號的進程。 根據進程的時間片和優(yōu)先級調度機制 , 來選擇要執(zhí)行 的進程 , 并隨后將 CP U , 然后調用宏 s witch_to rev, 由 p rev 變 , s _schedul_tail來收尾 , 這 next 之前進程 p rev 的信息 。進程切換發(fā)生在 s witch ( 函數中 。切換主要包 括用戶空間 (pgd 和運行上下文 (hardware context 和 堆棧

14、等 的切換 。這里要談的宏 s witch_t o 就是實現 運行上下文的切換的 。 s witch (p rev, next, last 函數的 處理流程如圖 1所示 。圖 1 s witch (p rev, next, last 函數處理兩個進程上下文的切換 , 代碼如下 :#defines witch_to (p rev, next, last do unsigned l ong ebx, ecx, edx, esi, edi; as m volatile (" pushflnt" " pushl %ebp nt""movl %es p,

15、 %p rev_sp nt" "movl %next_sp , %es p nt" "movl $1f, %p rev_ip nt" " pushl %next_ip nt" 2009年第 6期 馮宇等 :L inux 進程調度算法分析 15" j m p _switch_to n"" 1:t"" pop l %ebp nt"" popfln":p rev_sp " =m"(p rev 2>thread . s p ,p

16、 rev_ip " =m"(p rev 2>thread . i p ," =a" (last ," =b" (ebx ," =c" (ecx ," =d" (edx ," =S" (esi ," =D"(edi :next_sp "m" (next 2>thread . s p ,next_ip "m" (next 2>thread . i p ,p rev" a" (p re

17、v ,next" d" (next ;while (0將 next 的 i p 壓入堆棧 , 然后調用 j m p, 而在 _ s witch_to 中采用 ret 返回 , 則返回地址就變成 next_ i p , 也就是進程 next 的標號為 1處 , 進入 next 執(zhí)行 。 調用 schedule ( 函數后 , 進程就實現了切換 , 將 CP U 賦給另一個進程 (或原進程 使用 。當沒有可運 行的進程時 , 去執(zhí)行 idle 進程 ,進程 , 就跳轉過去執(zhí)行 。3L inux , 如果進程處于 T ASK_ RUNN I N G 狀態(tài) , 內核檢查它的優(yōu)先級是

18、否大于當前 正運行進程的優(yōu)先級 。如果是 , current 的執(zhí)行被中 斷 , 并調用調度程序選擇另一個進程運行 (通常情況 下是剛剛成為 T ASK_RUNNI N G 狀態(tài)的進程 。當 然 , 進程在它的時間片到期時也可以被搶占 , 此時設 置進程的 need_resched域 , 以便定時中斷處理程序中 止時調度程序 。要注意的是 , 被搶占的進程仍處于 T ASK_RUNNI N G 狀態(tài) , 只是不能使用 CP U, 而并沒有 被掛起 。而 L inux 操作系統(tǒng)是非內核搶占式 , 只有進程運 行在用戶態(tài)時 , 才可能發(fā)生進程搶占 。 如果進程進入 了內核 , 即使此時有更高優(yōu)先級

19、的進程處于 T ASK_ RUNN I N G 狀態(tài) , 也不能被搶占 。所以 , L inux 這樣設 計是 簡 化 了 內 核 代 碼 , 但 L inux 操 作 系 統(tǒng) 實 時 性 不高 。4 S MP 的進程調度(1 S M P 。由于 L inux 一直堅持采用對稱多處理模型 (S M P , 這意味 著在多處理器下 , 與其他 CP U 相比 , 內核不應該對其中的某 一個 CP U 有任何的偏向 , 而且多處理器具有很多不同的風 格 , 所以相對單處理的調度程序有所不同 。下面介紹兩種典型的不同類型的多處理器系統(tǒng) : 標準的多處理器體系結構 。這是多處理器機器中最普通的體系結構

20、 , 所共有的 RAM 被所有 CP U 共享 。 超線程 。超線程芯片是一個可以同時執(zhí)行幾個線程的微處理器 。 一個超線程的物理 CP U 可以被 L inux 看成幾個不同的邏 輯 CP U 。(2 S MP 的進程調度 。在單處理器結構中 , schedule ( 函數從本地 CP U 的運行 隊列中挑選新進程進行運行 。 因此 , 一個指定的 CP U 只能執(zhí) 行其相應的運行隊列的可運行進程 。另外 , 一個可運行進程 總是存放在某一個運行隊列中 , 即任何一個可運行進程都不 可能同時出現在兩個或兩個以上的運行隊列中 。因此 , 一個 保持可運行狀態(tài)的進程通常被限制在一個固定的 CP

21、U 上 。 在正常情況下 , 這種設計有益于系統(tǒng)的性能 , 因為 , 運行隊列 中的可運行進程擁有的數據 , 可能會添滿每個 CP U 的高速緩 存 。 但是 , 在有些情況下 , 把可運行進程限制在一個指定的 CP U 上可能引起嚴重的性能損失 。比如 , 頻繁使用 CP U 的批 處理進程 , CP U 的可運行隊列上 , 那 CP U , 其他的 CP U 幾乎處, , 并 , 把一些進程從一個運行隊列上轉移到另一個 。L inux 提出了一種基于“ 調度域 ” 的概念的復雜運行隊列 平衡算法 。調度域 (scheduling domain 實際上一個 CP U 集合 , 由內 核來保持

22、它們工作量的平衡 。調度域采用分層的組織形式 :最上層的調度域 (包括系統(tǒng)中所有的 CP U 包括多個子調度 域 , 每個子調度域包括一個 CP U 子集 。每個調度域被依次劃 分成一個或多個組 , 每個組代表調度域的一個 CP U 子集 。工 作量的平衡總是在調度域的組之間來完成 , 即只有在某個調 度域的某個組的總工作量遠遠低于同一個調度域的另一組的 工作量時 , 才把進程從一個 CP U 遷移到另一個 CP U 。5 結束語新內核對 S MP 的調度算法已經進行了改進和簡 化 。 只要一個新的進程變?yōu)榭蛇\行的 , 內核檢查原來 運行該進程的 CP U 是否為空 , 如果為空 , 則內核把

23、進 程分配給該 CP U; 否則 , 內核把進程分配給另一個空 閑的 CP U, 如果所有的 CP U 都忙 , 則進行進程搶占 。參考文獻 :1 Daniel P Bovel,Marco Cesati . Understanding the L inux Ker 2 nel M.北京 :中國電力出版社 , 2001.2 Maurice J Bach . The Design of the Unix Operati on Syste m M.北京 :機械工業(yè)出版社 , 2005.3 毛德操 , 胡希明 . L inux 內核源代碼情景分析 M.杭 州 :浙江大學出版社 , 2001. (下轉第

24、 20頁 20 計 算 機 與 現 代 化 2009年第 6期表 6 R2006的關系模型房號 D 管理費0501South200601, 200605, 380 200606, 200612, 400表 7 R2007的關系模型房號 D 管理費0501South 200701, 200703, 400 200704, Now , 430 由表 5、 表 6、 表 7可以看到 , 分解后關系的屬性 集和元組集保持不變 , 三個關系的屬性生命周期分別 為 200501, 200512、 200601, 200612、 200701, Now , 同一元組各個關系的屬性生命周期無間隙 、 無 重疊

25、 , 其 集 合 結 果 等 于 關 系 R2的 屬 性 生 命 周 期 200501, Now , 滿足生命周期分解的時態(tài)聯(lián)接性約 束要求 。5 結束語HRDB 在傳統(tǒng) RDB 的基礎上引入時變屬性 , 使 數據 庫 成 為 一 種 具 有 時 態(tài) 特 性 的 三 維 結 Te mpS QL 模型是在 HRDB型 , 規(guī)定 HRDB , 同一 , 即要滿足同 時性條件 ?；?Te mpS QL 模型的 HRDB 可能存在冗余和數 據膨脹 , 解決辦法是根據時態(tài)關系規(guī)范化進行模式分 解 。 HRDB 分解時除了消除不合理的數據依賴 , 還必 須遵守時態(tài)數據庫所特有的時態(tài)約束 。 HRDB 在

26、時 態(tài)約束下像 RDB 一樣根據 3NF 或 BCNF 對關系進行 模式分解 , 這個過程稱為時態(tài)關系規(guī)范化 。消除 HRDB 冗余可以采用投影分解 , 把一個關 系分解為多個具有較小屬性集的關系 。分解時各個 屬性的時間區(qū)間不變 , 屬于生命周期不分解的模式分 解 。 此時 , 除了要消除不合理的數據依賴 , 滿足無損 聯(lián)接和函數依賴保持 , 還要遵守元組同時性約束的時 態(tài)約束 , 即分解后的各個關系中來自同一個元組各個 屬性的生命周期必須是一致的 。解決 HRDB 數據膨脹可以按時間區(qū)間分解 , 把 一個關系分解為多個較小時間跨度的關系 。分解后 每個關系的屬性集和元組與分解前是一樣的 ,

27、 只是按 屬性生命周期進行分解 , 屬于生命周期分解的模式分 解 。 分解時要遵守時態(tài)聯(lián)接性約束的時態(tài)約束 , 即分 解后的各個關系中來自同一個元組的屬性生命周期 必須是無間隙 、 無重疊的 。參考文獻 :1 湯庸 . 時態(tài)數據庫導論 M.北京 :北京大學出版社 , 2004:13263.2 , 等 . M.北京 :科學出版社 , 214.Johannes Gehrke . 數據庫管理系統(tǒng) (M.北京 :清華大學出版社 , 2002:3172336. 馬玉華 . 關系數據庫模式分解方法分析 J .漯河職業(yè) 技術學院學報 , 2007(2 :37238.5 孫睿 , 劉磊 , 邵明珠 . 數據庫的規(guī)范化理論與非規(guī)范化 設計 J .電腦知識與技術 , 2006(11 :23225, 107. 6 馬雪英 , 馮睿 . 基于函數依賴的模式分解方法 J .計