單核與多核的CPU調度算法

1、多核CPU調度算法1.1全局隊列調度算法操作系統(tǒng)維護一個全局的任務等待隊列，每個進程在執(zhí)行階段可以使用全部 的處理器資源。當系統(tǒng)中有一個CPU核心空閑時，操作系統(tǒng)就從全局任務等待隊 列中選取Ready進程開始在此核心上執(zhí)行。優(yōu)點：CPU核心利用率較高，能保證全局資源的充分利用。缺點：多處理器同時查找工作時，可能會降低處理器效率。且同一進程可能 在不同內核上執(zhí)行，造成的進程遷移開銷較大。1.2局部隊列調度算法操作系統(tǒng)為每個CPU內核維護一個局部的任務等待隊列，將所有進程分配到 與處理器對應的進程隊列中。當系統(tǒng)中有一個CPU內核空閑時，便從該核心的任 務等待隊列中選取恰當的任務執(zhí)行。優(yōu)點：充分利用

2、局部緩存，降低了進程遷移的開銷。任務基本上無需在多個 CPU核心間切換，有利于提高CPU核心局部Cache命中率。目前多數多核CPU操 作系統(tǒng)采用的是基于全局隊列的任務調度算法。缺點：可能造成某些處理器超負荷，而某些處理器空閑，即資源分配不均衡 不充分，引起全局資源的不充分利用。簡單單核CPU調度算法2.1 先到先服務調度算法：FCFS (first-come,first-served )當一個進程進入到Ready隊列，其PCB就被鏈接到隊列的尾部。當CPU空閑 時，CPU被分配給位于隊列頭的進程(即當前Ready隊列中已等待時間最長的進 程)。接著，該運行進程從隊列中被刪除。缺點：對于一個進

3、程隊列，其總的周轉時間太長，且當進程的I/O較為密集 時，效率將會變得相當低，CPU利用率也會變得很低。優(yōu)點：實現方式簡單，適用于長程調度和處理器密集的進程調度。常與優(yōu)先 級策略結合提供一種更有效率的調度方法。2.2最短作業(yè)優(yōu)先調度算法：SJF (shortest-job-first)SJF是一種非搶占式的調度算法，其實現原則是取Ready隊列中處理時間最 短的進程加載入CPU，進入CPU執(zhí)行的進程執(zhí)行完后才釋放CPU，然后加載第二 個進程進入CPU執(zhí)行。缺點：忽視了作業(yè)等待時間，會出現starvation現象，且作業(yè)執(zhí)行時間無 法提前知道，也很難預估。優(yōu)點：算法實現簡單，能有效地降低作業(yè)的平

4、均等待時間，提高系統(tǒng)吞吐量， 是理論上的最優(yōu)調度算法。2.3最短剩余時間優(yōu)先調度算法：SRTF (Shortest Remaining Time First)SRTF調度算法是搶占式的SJF調度算法，調度程序總是首先選擇預期剩余 時間最短的進程加載進入CPU執(zhí)行。缺點：總是選擇預期剩余時間最短的進程，會造成starvation現象。有處 理時間預估，效率不足夠高。優(yōu)點：不偏向長進程，沒有額外的中斷，因此開銷較低。且對于一個進程隊 列，總的周轉時間較短，執(zhí)行效率較高，對短進程的響應較快。2.4優(yōu)先級調度算法每個進程都有一個自己的優(yōu)先級，Ready隊列采用優(yōu)先級隊列實現，CPU每 次取Ready隊

5、列隊首的進程。通常情況，當兩個進程的優(yōu)先級相同時，我們在相 同優(yōu)先級的進程之間采用FCFS調度算法。優(yōu)先級可以通過內部或外部方式來定 義。缺點：會出現starvation現象（也稱無窮阻塞），且不適用于分時系統(tǒng)或交 互式事務處理環(huán)境。優(yōu)點：主要用于批處理系統(tǒng)中，也可用于某些對實時性要求不嚴的實時系統(tǒng) 中?？梢圆捎美匣夹g，每個進程執(zhí)行以后其優(yōu)先級降低，以此來克服 starvation 的缺點。2.5輪轉法調度算法輪轉法（RR）調度算法是專門為分時系統(tǒng)設計的，是一種基于時鐘的搶占策 略。定義一個小時間單元，稱為時間量或時間片。時間片通常為10ms到100ms。 將Ready隊列作為循環(huán)隊列處理。

6、CPU調度程序循環(huán)就需隊列，為每個進程分配 不超過一個時間片間隔的CPU。如果上下文切換時間約為時間片的10%，那么約 10%的CPU時間會浪費在上下文切換上。缺點：時間片長度設計較難，當時間片長度過大時，會退化成FCFS調度算 法。調度I/O密集型進程時效率較低。由于輪詢調度在調度過程中不考慮瞬時信 道條件，因此它將導致較低的整體系統(tǒng)性能。優(yōu)點：對不同的分組業(yè)務流隊列進行同樣的無差別的循環(huán)調度服務，對于等 長業(yè)務流隊列是公平的，不存在starvation現象。2.6最高響應比優(yōu)先調度算法首先需要理解一個概念，叫作響應比。響應比的計算表達式為其中R為響應比，w為等待處理器的時間，s為預計服務的

7、時間。當進程被立即 調用時，R等于歸一化周轉時間。調度算法的過程是，當進程完成執(zhí)行或被阻塞時，選擇R值最大的Ready 進程加載進入CPU執(zhí)行。缺點：需要預估服務時間s，效率不太高。優(yōu)點：能克服starvation現象。復雜單核CPU調度算法3.1多級隊列調度算法 （multilevel queue-scheduling algorithm）將Ready隊列分成多個獨立的隊列，對Ready隊列和每個獨立的隊列采用不 同的調度算法進行執(zhí)行。常用的方式是，Ready隊列采用優(yōu)先級調度算法，不同 隊列根據實際情況采用合適的調度算法即可。優(yōu)點：綜合了多種調度算法，避免了 starvation現象，最大

8、限度地提高了 調度效率，也提高了 CPU利用率。3.2多級反饋隊列調度算法UNIX OS采用的調度算法。其詳細過程如下：進程在進入待調度的隊列等待時，首先進入優(yōu)先級最高的Q1等待。首先調度優(yōu)先級高的隊列中的進程。若高優(yōu)先級中隊列中已沒有調度的進程， 則調度次優(yōu)先級隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進 程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。對于同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間 片為N，那么Q1中的作業(yè)在經歷了 N個時間片后若還沒有完成，則進入Q2隊列 等待，若Q2的時間片用完后作業(yè)還不能完成，一直進入下一級隊列，直至完成。在低優(yōu)先級的隊列中的進程在運行時，又有新到達的作業(yè)，那么在運行完這 個時間片后，CPU馬上分配給新到達的作業(yè)（搶占式）。優(yōu)點：既能使高優(yōu)先級的作業(yè)得到響應又能使短作業(yè)（進程）迅速完成。多核CPU調度算法與單核CPU調度算法對比從上面的不同CPU調度算法，我們不難發(fā)現，單核CPU調度算法是多核CPU 調度算法的基礎，多核CPU調度算法是單核CPU調度算法的延伸和綜合使用。我 以大篇幅介紹了單核CPU的調度算法，而以少量的篇幅介紹了多核CPU調度算