Posted on 2009-06-28 13:28
dennis 閱讀(8707)
評論(1) 編輯 收藏 所屬分類:
數據結構與算法 、
計算機科學與基礎
在多進程、多線程并發的環境里，從概念上看，有多個進程或者多個線程在同時執行，具體到單個CPU級別，實際上任何時刻只能有一個進程或者線程處于執行狀態；因此OS需要決定哪個進程執行，哪些進程等待，也就是進程的調度。
一、調度的目標
1、首先要區分程序使用CPU的三種模式：IO密集型、計算密集型和平衡型。對于IO密集型程序來說，響應時間非常重要；對于CPU密集型來說，CPU的周轉時間就比較重要；對于平衡型程序來說，響應和周轉之間的平衡是最重要的。
2、CPU的調度就是要達到極小化平均響應時間、極大化系統吞吐率、保持系統各個功能部件均處于繁忙狀態和提供某種公平的機制。
3、對于實時系統來說，調度的目標就是要達到截止時間前完成所應該完成的任務和提供性能的可預測性。
二、調度算法
1、FCFS（First come first serve)，或者稱為FIFO算法，先來先處理。這個算法的優點是簡單，實現容易，并且似乎公平；缺點在于短的任務有可能變的非常慢，因為其前面的任務占用很長時間，造成了平均響應時間非常慢。
2、時間片輪詢算法，這是對FIFO算法的改進，目的是改善短程序（運行時間短）的響應時間，其方法就是周期性地進行進程切換。這個算法的關鍵點在于時間片的選擇，時間片過大，那么輪轉就越接近FIFO，如果太小，進程切換的開銷大于執行程序的開銷，從而降低了系統效率。因此選擇合適的時間片就非常重要。選擇時間片的兩個需要考慮的因素：一次進程切換所使用的系統消耗以及我們能接受的整個系統消耗、系統運行的進程數。
時間片輪詢看上起非常公平，并且響應時間非常好，然而時間片輪轉并不能保證系統的響應時間總是比FIFO短，這很大程度上取決于時間片大小的選擇，以及這個大小與進程運行時間的相互關系。
3、STCF算法（Short time to complete first)，顧名思義就是短任務優先算法。這種算法的核心就是所有的程序都有一個優先級，短任務的優先級比長任務的高，而OS總是安排優先級高的進程運行。
STCF又分為兩類：非搶占式和搶占式。非搶占式STCF就是讓已經在CPU上運行的程序執行到結束或者阻塞，然后在所有的就緒進程中選擇執行時間最短的來執行；而搶占式STCF就不是這樣，在每進來一個新的進程時，就對所有進程（包括正在CPU上執行的進程）進行檢查，誰的執行時間短，就運行誰。
STCF總是能提供最優的響應時間，然而它也有缺點，第一可能造成長任務的程序無法得到CPU時間而饑餓，因為OS總是優先執行短任務；其次，關鍵問題在于我們怎么知道程序的運行時間，怎么預測某個進程需要的執行時間？通常有兩個辦法：使用啟發式方法估算（例如根據程序大小估算），或者將程序執行一遍后記錄其所用的CPU時間，在以后的執行過程中就可以根據這個測量數據來進行STCF調度。
4、優先級調度，STCF遇到的問題是長任務的程序可能饑餓，那么優先級調度算法可以通過給長任務的進程更高的優先級來解決這個問題；優先級調度遇到的問題可能是短任務的進程饑餓，這個可以通過動態調整優先級來解決。實際上動態調整優先級（稱為權值）+時間片輪詢的策略正是linux的進程調度策略之一的 SCHED_OTHER分時調度策略,它的調度過程如下：
（1）創建任務指定采用分時調度策略，并指定優先級nice值(-20~19)。
（2）將根據每個任務的nice值確定在cpu上的執行時間(counter)。
（3）如果沒有等待資源，則將該任務加入到就緒隊列中。
（4）調度程序遍歷就緒隊列中的任務，通過對每個任務動態優先級的計算(counter+20-nice)結果，選擇計算結果最大的一個去運行，當這個時間片用完后(counter減至0)或者主動放棄cpu時，該任務將被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。
（5）此時調度程序重復上面計算過程，轉到第4步。
（6）當調度程序發現所有就緒任務計算所得的權值都為不大于0時，重復第2步。
linux還有兩個實時進程的調度策略：FIFO和RR,實時進程會立即搶占非實時進程。
5、顯然，沒有什么調度算法是毫無缺點的，因此現代OS通常都會采用混合調度算法。例如將不同的進程分為幾個大類，每個大類有不同的優先級，不同大類的進程的調度取決于大類的優先級，同一個大類的進程采用時間片輪詢來保證公平性。
6、其他調度算法，保證調度算法保證每個進程享用的CPU時間完全一樣；彩票調度算法是一種概率調度算法，通過給進程“發彩票”的多少，來賦予不同進程不同的調用時間，彩票調度算法的優點是非常靈活，如果你給短任務發更多“彩票”，那么就類似STCF調度，如果給每個進程一樣多的“彩票”，那么就類似保證調度；用戶公平調度算法，是按照每個用戶，而不是按照每個進程來進行公平分配CPU時間，這是為了防止貪婪用戶啟用了過多進程導致系統效率降低甚至停頓。
7、實時系統的調度算法，實時系統需要考慮每個具體任務的響應時間必須符合要求，在截止時間前完成。
（1）EDF調度算法，就是最早截止任務優先（Earliest deadline first)算法，也就是讓最早截止的任務先做。當新的任務過來時，如果它的截止時間更靠前，那么就讓新任務搶占正在執行的任務。EDF算法其實是貪心算法的一種體現。如果一組任務可以被調度（也就是所有任務的截止時間在理論上都可以得到滿足），那么EDF可以滿足。如果一批任務不能全部滿足（全部在各自的截止時間前完成），那EDF滿足的任務數最多，這就是它最優的體現。EDF其實就是搶占式的STCF，只不過將程序的執行時間換成了截止時間。EDF的缺點在于需要對每個任務的截止時間做計算并動態調整優先級，并且搶占任務也需要消耗系統資源。因此它的實際效果比理論效果差一點。
（2）RMS調度算法，EDF是動態調度算法，而RMS（rate monotonic scheduling)算法是一種靜態最優算法；該算法在進行調度前先計算出所有任務的優先級，然后按照計算出來的優先級進行調度，任務執行中間既不接收新任務，也不進行優先級調整或者CPU搶占。因此它的優點是系統消耗小，缺點就是不靈活了。對于RMS算法，關鍵點在于判斷一個任務組是否能被調度，這里有一個定律，如果一個系統的所有任務的CPU利用率都低于ln2，那么這些任務的截止時間均可以得到滿足，ln2約等于0.693147，也就是此時系統還剩下有30%的CPU時間。這個證明是Liu和Kayland在1973年給出的。
三、優先級反轉
1、什么是優先級反轉？
優先級反轉是指一個低優先級的任務持有一個被高優先級任務所需要的共享資源。高優先任務由于因資源缺乏而處于受阻狀態，一直等到低優先級任務釋放資源為止。而低優先級獲得的CPU時間少，如果此時有優先級處于兩者之間的任務，并且不需要那個共享資源，則該中優先級的任務反而超過這兩個任務而獲得CPU時間。如果高優先級等待資源時不是阻塞等待，而是忙循環，則可能永遠無法獲得資源，因為此時低優先級進程無法與高優先級進程爭奪CPU時間，從而無法執行，進而無法釋放資源，造成的后果就是高優先級任務無法獲得資源而繼續推進。
2、解決方案：
（1）設置優先級上限，給臨界區一個高優先級，進入臨界區的進程都將獲得這個高優先級，如果其他試圖進入臨界區的進程的優先級都低于這個高優先級，那么優先級反轉就不會發生。
（2）優先級繼承，當一個高優先級進程等待一個低優先級進程持有的資源時，低優先級進程將暫時獲得高優先級進程的優先級別，在釋放共享資源后，低優先級進程回到原來的優先級別。嵌入式系統VxWorks就是采用這種策略。
這里還有一個八卦，1997年的美國的火星探測器（使用的就是vxworks)就遇到一個優先級反轉問題引起的故障。簡單說下，火星探測器有一個信息總線，有一個高優先級的總線任務負責總線數據的存取，訪問總線都需要通過一個互斥鎖（共享資源出現了）；還有一個低優先級的，運行不是很頻繁的氣象搜集任務，它需要對總線寫數據，也就同樣需要訪問互斥鎖；最后還有一個中優先級的通信任務，它的運行時間比較長。平常這個系統運行毫無問題，但是有一天，在氣象任務獲得互斥鎖往總線寫數據的時候，一個中斷發生導致通信任務被調度就緒，通信任務搶占了低優先級的氣象任務，而無巧不成書的是，此時高優先級的總線任務正在等待氣象任務寫完數據歸還互斥鎖，但是由于通信任務搶占了CPU并且運行時間比較長，導致氣象任務得不到CPU時間也無法釋放互斥鎖，本來是高優先級的總線任務也無法執行，總線任務無法及時執行的后果被探路者認為是一個嚴重錯誤，最后就是整個系統被重啟。Vxworks允許優先級繼承，然而遺憾的工程師們將這個選項關閉了。
（3）第三種方法就是使用中斷禁止，通過禁止中斷來保護臨界區，采用此種策略的系統只有兩種優先級：可搶占優先級和中斷禁止優先級。前者為一般進程運行時的優先級，后者為運行于臨界區的優先級?；鹦翘铰氛哒怯捎谠谂R界區中運行的氣象任務被中斷發生的通信任務所搶占才導致故障，如果有臨界區的禁止中斷保護，此一問題也不會發生。