調度的目標

前面講過，在多進程，多線程并發的環境里，雖然從概念上看，有多個進程或線程在同時執行，但在單一CPU下，實際上在任何時刻只能有一個進程或線程處于執行狀態。而其他線程則處于非執行狀態。那么這就有一個需要解決的問題:我們是如何確定在任意時刻到底有哪個線程執行，哪些不執行呢?或者說，我們是如何進行線程調度的呢?

進程/線程的調度是操作系統進程管理的一個重要組成部分。其任務是怎么選擇下一個要運轉的進程。而要探明這一點，則首先需要確定操作系統進程調度的目標是什么。這樣，就知道選擇什么進程最合適。

那么操作系統進程調度的目標是什么呢？這需要對程序使用CPU的模式進行分析。那么程序在執行時有什么樣的模式呢？
一般來說，程序使用CPU的模式有三種：一種程序大部分時間在CPU上執行。另一種程序大部分時間在進行輸入輸出，還有一種程序則介于前兩種模式之間。

第一種程序運行的模式是在CPU上執行一陣較長時間，接著進行短暫的輸入，然后又在CPU上進行較長的運算，之后又進行一下短暫的輸入輸出操作。就這樣循環往復。這種程序由于使用CPU的時間大大多于其用于輸人輸出上的時間，因此稱為CPU導向( CPU-bound)或計算密集型程序。計算密集型程序通常是科學計算方面的程序。計算宇宙大爆炸各種參數的程序和矩陣乘法程序等就都是CPU bound 的程序。

第二種程序則與第一種相反，這種程序的大部分時間用來I/O，每次I/O后進行短暫的CPU執行,因此稱為I/О導向( I/O-bound)或輸入輸出密集型程序。一般來說，人機交互式程序均屬于這類程序。如游戲程序，講課時使用的PPT程序，就都屬于I/O bound的程序。

第三種程序自然介于二者之間，既有長時間的CPU執行部分，又有長時間的I/O部分。 或者說，這種程序使用CPU和I/O的時間相差不大。這種程序稱為平衡型程序。例如，網絡瀏覽或下載，網絡視頻等就屬于此類程序。

自然，對于不同性質的程序，調度所要達到的目的也有所不同。例如，對于I/O bound 的程序來說，響應時間非常重要，而對于CPU-bound的程序來說，則周轉時間( turn around )就比較重要，對于平衡型程序來說，則進行某種響應和周轉之間的平衡就顯得重要。

處理器調度的總體目標

CPU 調度就是要達到極小化平均響應時間，極大化系統吞吐率，保持系統各個功能部件均處于繁忙狀態和提供某種貌似公平的機制。

極小化平均響應時間就是要極小化用戶發出命令和看到某種結果之間所花費的時間，即減少做一件工作平均等待的時間；極大化系統吞吐率就是要在單位時間內完成盡可能多的程序，就是單位時間內能完成的工作數量，即整個系統運行效率高；保持系統各個功能部件繁忙就是要讓CPU和輸人輸出設備均處于忙碌狀態。因為CPU非常昂貴，讓其閑置顯然是―種浪費，因此保持CPU繁忙十分重要。就像人非常珍貴，因此要一直保持學習繁忙狀態，才能不浪費生命。提供公平就是要讓各個程序感到某種“平等”，即在CPU面前“人人平等”。公平是任何系統都應該努力達到的目標。因為,沒有公平,該系統對用戶的吸引力就會急劇下降。就像一個國家或者社會,如果缺乏公平,公民對該國家的認同度就會急劇下降一樣。

對于不同的系統來說，在調度目標方面也有一些細微的不同。例如，對于批處理系統來說，由于用戶并不坐在計算機前面等待結果，響應時間就顯得不太重要，但系統吞吐率，CPU利用率和周轉時間則很重要。對于交互式系統來說，因為用戶在等待計算機，因此響應時間要很快。但在這里要注意的是適度性( proportionality)。適度性就是響應時間要和期望值相匹配。 這里是說你不要超越用戶的期望。比如說，用戶期待1秒鐘的響應時間，你就給他1秒鐘的響應時間，而不必提供0.1秒的響應時間。這是因為，提供超出用戶期望的響應會增加系統設計的難度，而又不會提高用戶的滿意度(對于一個人來說，1秒鐘和0.1秒鐘的差別并不是很大)。對于實時系統來說，調度就是要達到在截止期前完成所應該完成的任務和提供性能可預測性。

先來先服務調度算法

先來先服務調度算法縮寫為FCFS( first come first serve)。就是誰先來，就先服務誰。 這個算法所有地球人都能想到。因為先來先到是人的本性中的一個公平觀念，而且生活實際中這種規則隨處可見。例如，我們排隊買東西或者辦理政務體現的就是先來先到原則。

先來先到的一個隱含條件就是不能搶占，一個程序一旦啟動就一直運行到結束或者受阻塞為止。這是因為一旦允許搶占，就破壞先來先到的原則了。這類似于我們生活中的干部終身制。先來先到的優點就是簡單，人人都能理解，實現起來容易。而缺點則是短的工作有可能變得很慢，因為其前面有很長的工作。這樣就造成用戶的交互式體驗也比較差。

例如，有兩個程序：A需要運行100秒，B需要運行1秒。A程序與B程序幾乎同時啟動，但B就是慢了一丁點，被排在A之后執行，則需要等100秒。這樣A的響應時間為100秒，而B的響應時間則為101秒，從而，平均響應時間100.5秒。響應時間非常慢。(用戶響應時間)

就像我們排隊辦理事情，你要辦理的事情只要幾分鐘就可辦好，而你前面的一個人辦理的事情因為復雜需要1個小時。這個時候你要等在他后面就十分不高興。這個時候你就想，要是每個人輪流辦理10分鐘事務的話，那多好呀。自然，研究處理器調度的人也想到了這點，而這種輪流辦理的調度方式就是時間片輪轉。

時間片輪轉

時間片輪轉算法是對FCFS 算法的一種改進，其主要目的是改善短程序的響應時間，其方法就是周期性地進行進程切換。

例如每1秒鐘進行一次進程輪換。這樣，短程序排在長程序后面也可以很快得到執行。因此長程序執行1秒后就得把CPU讓出來。這樣整個系統的響應時間就得到改善。以前面的A，B程序為例，A需要運行100秒，B需要運行1秒。使用FCFS時系統平均響應時間為100.5秒。而使用時間片輪轉，則A在執行1秒后，CPU切換到進程B，在執行1秒后，B結束，A接著執行99秒。這樣A的響應時間是101秒，而B的響應時間為2秒。系統的平均響應時間是51.5秒。顯然比FCFS強多了。

在此系統響應時間依賴于時間片的選擇。 我們因為選擇了1秒鐘的時間片，上述系統的響應時間是51.5秒。如果時間片是10秒鐘，則上述系統的平均響應時間將是65秒。如果選擇別的時間片，則響應時間還將不同。那我們自然想知道，到底選擇多大的時間片才合適呢?

顯然，如果時間片選擇過大，時間片輪轉將越來越像FCFS，當時間片的選擇超過任何一個程序所需要的執行時間長度時，則完全退化為FCFS。而時間片如果選擇過小，則進程切換所用的系統消耗將太多，使得系統的大部分時間花在進程的上下文切換上，而用來真正執行程序的有用時間很少，從而降低系統效率，并造成浪費。

那如何選擇一個合適的時間片呢？做研究。我們需要知道進行一次進程切換所用系統消耗和我們能夠承受的整個系統消耗，就可以得出合適的時間片。例如，如果每次進程切換需要消耗0.1毫秒的CPU時間，則選擇10毫秒的時間片將浪費約1%的CPU時間在上下文切換上；如果選擇5毫秒的時間片，浪費為2%；20毫秒的時間片浪費為0.5%。如果我們能夠承受的CPU浪費為1%,則選擇0毫秒的時間片就很合理。

時間片選擇還需考慮的一個因素是，有多少進程在系統里運行?如果運行的進程多，時間片就需要短一些，不然，用戶的交互體驗會很差。進程數量少，時間片就可以適當長一些。因此，時間片的選擇是一個綜合的考慮，需要權衡各方利益，進行適當的折中。

時間片輪轉看上去非常公平，響應時間非常好，每個進程周期性的獲得CPU時間。但時間片輪轉真的很公平嗎？時間片輪轉的系統響應時間總是比FCFS的響應時間短嗎?答案卻是不一定。

還用上面的例子，如果是B比A略微先到，如果用FCFS，B的響應時間為1秒，A的響應時間為101秒，這樣系統的平均響應時間為50.5秒。而這是最優的響應時間。如果使用時間片輪轉，除非時間片選擇的是1秒，否則時間片輪轉的系統響應時間將比FCFS慢(記住，進程切換是需耍消耗系統時間的)。

短任務優先

那么時間片輪轉真的那么公平嗎？當然不是。如果每個人的能力一樣，大家輪流坐莊當然比較公平，問題是并不是每個人的能力完全一樣。我們不是因為不滿大鍋飯而提出讓一部分人先富起來嗎？而時間片輪轉就是大鍋飯!

我們前面舉例說了，時間片輪轉改善了所謂的系統響應時間的論斷也不一定經得起推敲。更為重要的是，時間片輪轉所達到的系統響應時間并不是我們所能達到的響應時間下限。如果有30個用戶，其中一個用戶只需要1秒鐘時間執行，而其他29個用戶需要30秒鐘執行，如果因為某種原因，這個只要1秒鐘的程序排在另外29個程序的后面輪轉，則需要等待29秒鐘才能執行(假定時間片為1秒)。這個程序的響應時間和交互體驗變得非常差。

那要改善短任務排在長任務后面輪轉而造成響應時間和交互體驗下降的辦法就是短任務優先算法STCF( shorted time to completion first)。這種算法的核心是所有的程序并不都一樣，而是有優先級的不同。具體說來，就是短任務的優先級比長任務的高，而我們總是安排優先級高的程序先運轉。就像晚輩在公交汽車上遇到長輩時需要讓座一樣。

短任務優先算法有兩個變種：一種是非搶占，一種是搶占。非搶占短任務優先算法的原理是讓已經在CPU上運行的程序執行到結束或阻塞，然后在所有候選的程序中選擇需要執行時間最短的進程來執行。搶占式短任務優先算法則是在每進來一個新的進程就需要對所有進程(包括正在CPU上運行的進程)進行檢查，誰的時間短，就運行誰。

顯然，由于短任務優先總是運行需要執行時間最短的程序，其系統平均響應時間在我們目前已經討論過的幾種調度算法里面是最優的。這就是STCF的優點。事實上，在所有非搶占調度算法中，STCF的響應時間最優。而在所有搶占調度算法中，搶占式STCF的響應時間最優。

下面我們來看一個例子：假定有A，B，C三個進程，A，B均是純計算進程，分別需要使用CPU計算50和100毫秒，而C每計算1毫秒后進行9毫秒的輸入輸出操作,并這樣重復10次。(一般情況下，執行I/O不會占用CPU)

顯然，如果A，B單獨運行，則CPU利用率是100%，如果C單獨運行，則磁盤利用率為90%。如果我們將它們一起運行，結果會怎么樣呢？這里假定我們使用STCF調度算法。

要使用STCF算法，首先得搞清楚哪個工作是短工作，哪個是長工作。A，B，C三個進程相對來說，,C是短工作，因為其使用CPU的時間遠遠小于其花在I/O上面的時間。而A，B皆是長工作，但相對來說，A又是短工作，因為其使用CPU的時間小于B進程。這樣，STCF調度的優先級就是C，A，B。由此我們獲得如下圖所示的調度模式:(一個*代表1ms)

在STCF調度下，磁盤在90%的情況下保持繁忙，這與只運行C一個進程的結果相同。A進程在系統啟動后55毫秒結束，B進程在系統啟動后159毫秒結束，C進程在系統啟動后99毫秒結束。故整個系統的平均響應時間為104.3毫秒。

如果使用FCFS算法，如果A或者B在C之前達到，則磁盤將閑置150毫秒后才能第一次啟動，磁盤的利用率將大大低于STCF調度算法。而系統的響應時間(假定A在B前面)為A為50毫秒，B為150毫秒，C為250毫秒，平均響應時間為150毫秒。如果C在A、B前到達，由于C在執行1毫秒后就阻塞進行I/O，整個狀況與A、B先來的時候差不多。

如果使用時間片輪轉，假定時間片大小為10毫秒，按照C、A、B的順序輪轉，我們獲得下圖所示的調度情況。在時間片輪轉情況下，系統的響應時間是A為104毫秒，B為159毫秒，C為99毫秒，平均響應時間為120.67毫秒。

由此可見，STCF的響應時間確實最短。當然，在時間片輪轉的情況下，時間片大小選擇的不同，結果將有所不同，但其響應時間不會短于STCF的響應時間。
但STCF調度也有缺點。第一是可能造成長程序無法得到CPU時間而導致饑餓。除此之外，還有一個重大缺點，就是我們怎么知道每個進程還需要運轉多久 ?難道我們能夠預測將來不成?

這個時候就需要做研究！我們可以用一些啟發式（ heuristic）方法來進行估算。例如，根據程序大小來推測一個程序所需CPU執行時間。但這個方法并不可靠。另外一個辦法就是先將每個程序運行一遍，記錄其所用CPU時間，這樣在以后的運行中，即可根據這個實測數據來進行STCF調度了。

優先級調度

前面講過的STCF有一個缺點是可能造成長進程饑餓。但這個問題比較容易解決，使用優先級即可。優先級調度算法的原理是給每個進程賦予一個優先級，每次需要進程切換時，找一個優先級最高的進程進行調度。這樣，如果我們給長進程一個高優先級，則該進程就不會再有饑餓。事實上，STCF本身就是一種優先級調度，只不過它給予短進程高優先級而已。

優先級調度的優點是可以賦予重要的進程以高優先級以確保重要任務能夠得到CPU時間。其缺點則與STCF一樣，低優先級的進程可能會饑餓。不過，這個問題在優先級調度算法里比在STCF里好解決：只要動態的調節優先級即可。例如，我們在一個進程執行特定CPU時間后將其優先級降低一個級別，或者將處于等待進程的優先級提高一個級別。這樣，一個進程如果等待時間很長，其優先級將因持續提升而超越其他進程的優先級，從而得到CPU時間。這樣，饑餓現象就可以防止。

不過，優先級調度還有一個缺點，就是響應時間不能保證，除非將一個進程的優先級設為最高。即使將優先級設為最高，但如果每個人都將自己進程的優先級設為最高，響應時間還是無法保證。

混合調度算法

我們前面提到過的所有算法都存在缺點，我們自然想設計一個算法合并它們的優點，摒棄它們的缺點。這就是所謂的混合調度算法。該算法的原理是將所有進程分成不同的大類，每個大類為一個優先級。如果兩個進程處于不同的大類，則處于高優先級大類的進程優先執行;如果兩個進程處于同一個大類，則采用時間片輪轉來執行， 如圖所示。

其他調度算法

保證調度( Guaranteed scheduling)

其中保證調度算法的目標是保證每個進程享用CPU的時間完全一樣，即如果系統里一共有n 個進程，則每個進程占用CPU的時間為1/n。保障調度就是保障每個進程使用1/n的CPU時間。保障就是肯定1/n的時間運轉，而不是大概1/n時間運轉。那么保障調度和輪轉調度是一樣嗎？時間片輪轉能不能達到1/n的效果？關鍵就是達到1/n不一定要靠輪轉。輪轉是能夠達到1/n的，但是保障調度不一定要輪轉。每次給的時間片不一定要一樣。

彩票調度（Lottery scheduling)

彩票調度算法是一種概率調度算法。 你買過彩票就知道，你買的越多中獎的概率越大。在該算法里，給每個進程分發一定數量的彩票，而調度器則從所有彩票里隨機抽取一張彩票，持有該彩票的進程就獲得CPU。這樣，如果想讓某個進程獲得更多的CPU時間，我們可以給該進程多發幾張彩票。彩票算法的優越性是顯而易見的，通過給每個進程至少一張彩票就可以防止饑餓，因為該進程獲得CPU的概率將大于0。

用戶公平調度（Fair share schedulingper user)。

用戶公平調度算法則按照每個用戶，而不是每個進程來進行公平分配。前面講過的算法均以進程為單位。這樣一個貪婪的用戶可以通過啟動許多進程來奪占CPU時間。如果每個用戶都很貪婪，都試圖啟動很多進程，則將造成整個系統效率低下，甚至停頓。用戶公平調度算法就是將CPU時間按照用戶進行平均分配。如果一個用戶的進程多，則其所擁有的進程所獲得的CPU時間將短，反之則多。

實時調度算法

實時系統是一種必須提供時序可預測性的系統。由于其應用范圍廣和特性不同于一般計算機系統，其調度算法也別其一格，和我們前面講過的所有調度算法均有所不同。前面的算法主要考慮的是平均響應時間和系統吞吐率的問題，而實時系統則考慮每個具體任務的響應時間必須符合要求，即每個任務必須在什么時間之前完成，而無需考慮如何降低整個系統的響應時間或吞吐率。

比如計算來襲導彈軌跡的進程，其計算時間是非常有限的。如果進程不能在規定時間內計算出來襲導彈的軌跡，則結果毫無意義。但如果能夠在截止時間前完成，那提前多少則無關緊要。這就是說，只要達到一定響應時間后，再提升響應時間并不能獲得任何好處。比如，視頻輸出，在NTSC制式下（美國、日本、臺灣使用的電視視頻制式)，只要每33毫秒發出一個圖像幀，所看到的視頻就是連貫的。而如果發送得比這更快，也不會獲得任何額外的好處。其他實時系統還有物理控制系統，如核反應堆控制溫度的系統、汽車測速機制等。

我們只論述一下其最主要或者說最經典的兩種算法：動態優先級調度和靜態優先級調度。動態優先級調度又稱為最早截止任務優先算法（EDF，earliest deadline first)，而靜態優先級調度又稱為最短周期優先算法（RMS，ratemonotonic scheduling )。

最早截止任務優先算法（earliest deadline first)

該算法就是最早截止的任務先做。如果新的工作來了，比正在運行的程序的截止期更靠前，那么就搶占當前進程。 EDF 算法是實時調度里面的最優算法。如果一組任務可以被調度的話（指所有任務的截止時間在理論上能夠得到滿足)，則EDF可以滿足。一批任務如果不能全部滿足，那 EDF能滿足的任務數最多。這就是它最優的體現。

例如，任務A需要15毫秒執行時間，截止時間在進入到系統后的第20毫秒，B需要執行10毫秒，截止時間為進入系統后的第30毫秒，C需要5毫秒執行時間，截止時間為進入到系統后的第10毫秒。使用EDF調度的結果就是先運行C，再運行A。最后運行B，如圖所示。

EDF 就是STCF變化來的。如果將STCF的任務所需執行時間變為截止時間，則搶占式STCF就是 EDF。

最短周期優先算法（ratemonotonic scheduling )

EDF是一個動態調度算法。意思是該算法動態的計算每個任務的截止時間并動態調節優先級。如果需要，還會對當前進程進行搶占。雖然EDF在理論上是最優的，但動態計算截止時間和動態搶占CPU均要消耗系統資源，因此EDF實際效果比其理論效果要差一截。與EDF相對的是RMS調度。該算法在進行調度前先計算出所有任務的優先級，然后按照該計算出來的優先級進行調度，任務執行中間既不接收新的進程，也不進行優先級的調整或進行CPU搶占。因此這種機制的優點是系統消耗小，缺點是不靈活。一旦該系統的任務決定了，就不能再接受新的任務。

對于RMS 算法來說，一個重要的任務是判斷一個任務組能否被調度。而這個判斷并不是容易做到的。Liu和 Kayland 在1973年證明了如果一個系統里所有任務的CPU的利用率低于ln2，則這些任務的截止時間均可以得到滿足。具體說來，一個系統里所有任務的截止期如果想都得到滿足，則這些任務必須滿足下面的條件:

這里，n為任務的數量，ci為第i個任務的執行時間，pi為第i個任務的釋放周期，而當n趨向無窮時，U的值變為ln2。

根據上述公式，如果 CPU利用率在ln2以下時，所有任務的截止期均可滿足。因為 ln2約等于0.693147，此時系統還剩下約30%的CPU時間。這個時間可以用來處理一些非實時任務。

知識點

進程調度的目標---------充分利用系統資源，減少等待時間，單位時間完成的進程多

FCFS----非搶占----誰先來執行誰
時間片輪轉------非搶占---------平均給每個進程分配同樣大小的時間去執行—時間片大小的選擇很重要(平均真的好嗎？？)
短任務---------誰短執行誰------搶占/非搶占—(長的可能餓死，估算時間也算個問題)
優先級--------優先級高先執行-----------(動態優先級調整)

非搶占---------不夠靈活
搶占式缺點-----------響應時間無法保證

混合調度算法---------根據進程間的不同關系—選擇不同的調度算法
EDF-----搶占式--------誰截至時間早，先執行誰
RMS---------一組一組的執行進程(為每組進程計算優先級，按優先級來)------改組未執行完/不接受其他進程

總結

以上是生活随笔為你收集整理的进程调度.的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。