單核與多核的CPU調(diào)度算法

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

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

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

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

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

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

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

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