操作系統(tǒng)精髓與設(shè)計(jì)原理--多處理器和實(shí)時(shí)調(diào)度

概述

    對(duì)于多處理器調(diào)度，此處概述了多個(gè)處理器可能帶來(lái)的問(wèn)題和設(shè)計(jì)上的一些問(wèn)題；對(duì)于實(shí)時(shí)調(diào)度，概述了兩種調(diào)度方法：限時(shí)調(diào)度和速率單調(diào)調(diào)度。

1 多處理器調(diào)度

    多處理器系統(tǒng)可以分為以下幾類：

• 松耦合、分布式處理器、集群：有一系列相對(duì)自治的系統(tǒng)組成，每個(gè)處理器有自己的內(nèi)存和I/O通道。

• 專門功能的處理器：I/O處理器時(shí)一個(gè)例子，此時(shí)有一個(gè)通用的主處理器，專門處理器受主處理器的控制，并給主處理器提供服務(wù)。

• 緊耦合多處理器：由一系列共享同一個(gè)內(nèi)存并在操作系統(tǒng)完全控制的處理器組成，這里詳細(xì)分析。

1.1 多處理器帶來(lái)的問(wèn)題

    調(diào)度上需要考慮三種問(wèn)題：

• 將進(jìn)程分配到處理器。

• 在單個(gè)處理器上使用多道程序設(shè)計(jì)。

• 一個(gè)進(jìn)程 的實(shí)際分派。

1.1.1將進(jìn)程分配到處理器

    如果多處理器結(jié)構(gòu)統(tǒng)一，即在內(nèi)存、I/O設(shè)備的訪問(wèn)時(shí)沒(méi)有特殊的優(yōu)勢(shì)，最簡(jiǎn)單的方法時(shí)將處理器看作一個(gè)資源池，然后按照要求分配到對(duì)應(yīng)處理器。那么要靜態(tài)還是動(dòng)態(tài)分配呢？

    如果一個(gè)進(jìn)程的生命周期都被分配到一個(gè)處理器上（靜態(tài)分配），則需要為每個(gè)處理器維護(hù)一個(gè)短程隊(duì)列，優(yōu)點(diǎn)是開(kāi)銷?。ㄋ羞M(jìn)程只分配一次，使用專門處理器的一個(gè)策略時(shí)組調(diào)度），缺點(diǎn)時(shí)一個(gè)處理器可能一直處于空閑狀態(tài)，而另一個(gè)處理器積壓許多工作，避免此方法是使用一個(gè)公共隊(duì)是列，所有進(jìn)程進(jìn)入并分配到任意一個(gè)可用的處理器上。在緊密耦合的共享儲(chǔ)存器結(jié)構(gòu)中，所有處理器可以得到任意進(jìn)程的上下文環(huán)境信息（調(diào)度進(jìn)程的開(kāi)銷與被調(diào)度到的處理器無(wú)關(guān)）。另一種分配方法是動(dòng)態(tài)負(fù)載均衡（動(dòng)態(tài)分配），線程可以在不同處理器所對(duì)應(yīng)的隊(duì)列里轉(zhuǎn)移，Linux使用此策略。

    在分配到處理器的過(guò)程中，主要有兩種方法：主從式、對(duì)等式。

• 主從試：操作系統(tǒng)的主要核心功能在某個(gè)特定的處理器上運(yùn)行，其他處理器可能僅僅用于執(zhí)行用戶進(jìn)程。主處理器負(fù)載調(diào)度作業(yè)，如果從處理器需要I/O調(diào)用等服務(wù)，則必須給主處理器發(fā)送請(qǐng)求，然后等待服務(wù)執(zhí)行。由于主處理?yè)碛袑?duì)所有存儲(chǔ)器和I/O資源的控制，可以簡(jiǎn)化沖突解決方案，所以幾乎不需要對(duì)單處理器多道程序操作系統(tǒng)進(jìn)程增強(qiáng)。同時(shí)主處理器的失敗會(huì)導(dǎo)致整個(gè)系統(tǒng)的失敗，主處理器可能為性能瓶頸。

• 對(duì)等式：操作系統(tǒng)可以在任何處理器上執(zhí)行。每個(gè)處理器從進(jìn)場(chǎng)池里進(jìn)行自調(diào)度。操作系統(tǒng)的穩(wěn)定性和性能相對(duì)主從試較高，但同時(shí)增加了操作系統(tǒng)的復(fù)雜性：操作系統(tǒng)必須確保不能一個(gè)進(jìn)程被多個(gè)處理器選擇，進(jìn)程也不能在隊(duì)列里丟失，所以要采用一些可以解決同步競(jìng)爭(zhēng)資源請(qǐng)求的技術(shù)。

• 當(dāng)然還有在兩個(gè)極端之前的方法：可以提供處理器子集而非一個(gè)處理器，以專門用于內(nèi)核的處理；基于優(yōu)先級(jí)和執(zhí)行歷史來(lái)管理內(nèi)核進(jìn)程和其他進(jìn)程之前的需求差異。

1.1.2 在單處理器上使用多道程序設(shè)計(jì)

    如果每個(gè)進(jìn)程使用靜態(tài)分配，就會(huì)有一個(gè)新問(wèn)題：此處理器支持多道程序嗎？如果綁定后因?yàn)榈却齀/O或考慮到并發(fā)/同步而被頻繁阻塞，則會(huì)有處理器的浪費(fèi)。

1.1.3 進(jìn)程分派

    這是關(guān)于選擇那個(gè)進(jìn)程運(yùn)行的策略，在多道單處理器上面，使用優(yōu)先級(jí)或基于歷史的高級(jí)調(diào)度算法比簡(jiǎn)單的FCFS策略性能更好。而在多處理器上，這些復(fù)雜性可能不必要，甚至有相反效果，而簡(jiǎn)單的方法可能更有效。對(duì)于線程調(diào)度則有比優(yōu)先級(jí)或執(zhí)行歷史更重要的新問(wèn)題。

1.2 進(jìn)程調(diào)度

    實(shí)際大多數(shù)傳統(tǒng)處理器系統(tǒng)，使用多條基于優(yōu)先級(jí)的隊(duì)列，且都在相同的處理池中執(zhí)行。并非指定專門處理器或一個(gè)處理器使用一個(gè)隊(duì)列。

    在一個(gè)雙處理器和單處理器系統(tǒng)里，多處理的每個(gè)處理器處理速度是單處理的一半。使用FCFS調(diào)度、輪轉(zhuǎn)法和最短剩余時(shí)間法后進(jìn)行比較，得到進(jìn)程服務(wù)時(shí)間的對(duì)比，即一個(gè)進(jìn)程的生命周期里使用處理器的時(shí)間。輪轉(zhuǎn)法的時(shí)間片長(zhǎng)度比上下文環(huán)境切換的開(kāi)銷大，且比平均服務(wù)時(shí)間短。該執(zhí)行結(jié)果取決于每個(gè)進(jìn)程之間的服務(wù)時(shí)間變化，從每個(gè)服務(wù)時(shí)間的差異從0增加，可得到一個(gè)結(jié)論：對(duì)于雙處理器，不同調(diào)度算法的差距沒(méi)有單處理表現(xiàn)的大，當(dāng)處理器增多時(shí)該結(jié)論更加確定。因此多處理器使用簡(jiǎn)單的FCFS或靜態(tài)優(yōu)先級(jí)方案的FCFS即可。（在多處理器的FCSF調(diào)度中，一個(gè)長(zhǎng)進(jìn)程很少被中斷，其他進(jìn)程可以使用其他的處理器，因此相對(duì)單處理器短進(jìn)程等待時(shí)間較少）

(見(jiàn)文獻(xiàn)Sauer, C. and Chandy, K. Computer Systems Performance Mondling. Englewood Cliffs, NJ:Prentice Hall, 1981)

1.3 線程調(diào)度

    有4種比較突出的方法：

1.3.1 負(fù)載分配

    進(jìn)程不是分配到固定的處理器，而是有系統(tǒng)維護(hù)一個(gè)就緒進(jìn)程的全局隊(duì)列，當(dāng)處理器空閑時(shí)就從隊(duì)列里選擇一個(gè)進(jìn)程。

    優(yōu)點(diǎn)是：

• 負(fù)載均勻分布在各處理器上，有工作可做時(shí)，沒(méi)有處理器空閑。

• 不需要集中調(diào)度器。操作系統(tǒng)調(diào)度例程在空閑的處理器上運(yùn)行以選擇就緒線程。

• 可以選擇單處理調(diào)度的方案組織和訪問(wèn)全局隊(duì)列，包括基于優(yōu)先級(jí)和執(zhí)行歷史或預(yù)處理請(qǐng)求的方案。 負(fù)載分配方案：

• FCFS：為空閑處理器選擇全局共享隊(duì)列末尾的就緒線程，直到完成或阻塞。

• 最少線程數(shù)優(yōu)先：空閑就緒隊(duì)列被組織成優(yōu)先級(jí)隊(duì)列，如果一個(gè)作業(yè)的位調(diào)度線程數(shù)目最少則優(yōu)先級(jí)最高，優(yōu)先級(jí)相同則優(yōu)先執(zhí)行先到達(dá)的作業(yè)，被調(diào)度的線程一直運(yùn)行直到阻塞或結(jié)束。

• 可搶占最少線程數(shù)優(yōu)先：如果一個(gè)新到的作業(yè)包含線程數(shù)少于當(dāng)前正在執(zhí)行的作業(yè)，則搶占執(zhí)行。 通過(guò)實(shí)驗(yàn)得出，F(xiàn)CFS的效果優(yōu)于其他兩個(gè)調(diào)度策略。

    缺點(diǎn)是：

• 中心隊(duì)列占據(jù)了必須互斥訪問(wèn)的存儲(chǔ)器區(qū)域，當(dāng)特別多的處理器同時(shí)查找工作時(shí)可能出現(xiàn)瓶頸。

• 被搶占的線程可能不在同一個(gè)處理器上恢復(fù)運(yùn)行，如果每個(gè)處理器都配備一個(gè)本地高速緩存，則緩存效率較低。

• 如果所有線程看做公共的線程池，則一個(gè)程序的線程不能同時(shí)被多個(gè)處理器訪問(wèn)。如果一個(gè)程序的線程之間需要高度的合作，則涉及的進(jìn)程切換可能會(huì)影響性能。

1.3.2 組調(diào)度

    一組相關(guān)進(jìn)程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處理器上運(yùn)行。提高程序性能的顯著方式是使進(jìn)程切換開(kāi)銷最小，即讓有聯(lián)系的線程可以同時(shí)運(yùn)行?？梢园凑彰總€(gè)應(yīng)用程序的線程個(gè)數(shù)加權(quán)分配不同的組調(diào)度時(shí)間，以減少處理器浪費(fèi)的時(shí)間。

    優(yōu)點(diǎn)：

• 如果緊密相關(guān)的進(jìn)程并行執(zhí)行，則同步阻塞的可能會(huì)減少，并且進(jìn)程切換也會(huì)變少，性能會(huì)提高。

• 調(diào)度開(kāi)銷可能減少，因?yàn)橐粋€(gè)決策可以影響到許多的處理器和進(jìn)程。

1.3.3 專用處理器分配

    與負(fù)載分配的方法相反，指定線程運(yùn)行到某個(gè)處理器。處理器數(shù)目與線程數(shù)相等，線程結(jié)束時(shí)處理器返回到處理器池里。

    看上去會(huì)浪費(fèi)處理器時(shí)間，即應(yīng)用程序一個(gè)線程被阻塞且等待I/O或與其他線程的同步，則該處理會(huì)一直空閑，屬于非多道程序設(shè)計(jì)。但有以下兩點(diǎn)的情況可以解釋使用此策略的原因：

• 在高度并行的系統(tǒng)中，有幾十或幾百個(gè)處理器，每個(gè)處理器只占用系統(tǒng)總代價(jià)的一笑部分，處理器利用率不是衡量有效性或性能的一個(gè)重要因素。

• 在一個(gè)程度的聲明周期里要避免進(jìn)程切換而加快程序的運(yùn)行速度，類似操作系統(tǒng)的單處理器的存儲(chǔ)器分配問(wèn)題，即一定時(shí)刻分配給一個(gè)程序多少處理器（一定時(shí)刻給進(jìn)程分配多少頁(yè)框）。

    在其他方案里提出一個(gè)類似虛擬內(nèi)存的工作集術(shù)語(yǔ)--活動(dòng)工作集：為了保證應(yīng)用程序以可接受的速度運(yùn)行，在處理器上必須同時(shí)調(diào)度的最少數(shù)目的線程。和存儲(chǔ)器管理方案一樣，調(diào)度活動(dòng)工作集中所有元素是的失敗可能導(dǎo)致處理器抖動(dòng)：調(diào)度其他線程時(shí)，取消了未來(lái)將要調(diào)度執(zhí)行的線程。類似內(nèi)存碎片，處理器碎片指當(dāng)一些處理器剩余的數(shù)目和合適程度上不滿足正在等待的應(yīng)用程序的需要。而組調(diào)度和專用處理器分配則有意避免這些問(wèn)題。

1.3.4 動(dòng)態(tài)調(diào)度

    線程數(shù)可變，通過(guò)調(diào)整負(fù)載提高利用率。

    將處理器分配給作業(yè)，每個(gè)作業(yè)將他的部分可以運(yùn)行任務(wù)映射到線程，使用當(dāng)前分配的處理器運(yùn)行。而關(guān)于運(yùn)行那個(gè)子集以及需要掛起那個(gè)線程的決策留個(gè)單個(gè)應(yīng)用程序決定。

    調(diào)度策略：

• 有請(qǐng)求到來(lái)時(shí)：

1. 如果有空閑的處理器，則使用并執(zhí)行。

2. 否則，如果是新到達(dá)的請(qǐng)求（不是未滿足分配需求而等待的請(qǐng)求），則選擇當(dāng)前已分配的多個(gè)處理器的作業(yè)，分出處理器去執(zhí)行新作業(yè)。

3. 如果分配不能得到滿足，則保持未完整狀態(tài)，直到滿足的處理器可用，或請(qǐng)求廢除。

• 處理器被釋放時(shí)： 掃描未滿足分配而等待的請(qǐng)求隊(duì)列，按照FCFS分配處理器資源。

2 實(shí)時(shí)調(diào)度

    實(shí)時(shí)任務(wù)或進(jìn)程是指該進(jìn)程的執(zhí)行與計(jì)算機(jī)系統(tǒng)外部的某些進(jìn)程、功能或事件集合有關(guān)，并且為了保證有效和正確的與外部環(huán)境交互，必須滿足一個(gè)或多個(gè)最后期限。

    實(shí)時(shí)操作系統(tǒng)是指能夠管理實(shí)時(shí)進(jìn)程的操作系統(tǒng)。在實(shí)時(shí)的操作系統(tǒng)中，傳統(tǒng)的調(diào)度算法原則不適用，關(guān)鍵因素是滿足最后期限，很大程度上依靠搶占和對(duì)相對(duì)最后期限有反應(yīng)的算法適合于這種上下文。

2.1 限期調(diào)度

    目標(biāo)是盡可能快速啟動(dòng)實(shí)時(shí)任務(wù)，因此強(qiáng)調(diào)快速中斷處理和任務(wù)分派。盡管存在動(dòng)態(tài)資源請(qǐng)求和沖突、處理過(guò)載和軟硬件故障，實(shí)時(shí)應(yīng)用程序不關(guān)注絕對(duì)速度，關(guān)注在最有價(jià)值的時(shí)間完成或啟動(dòng)任務(wù)。

    關(guān)于實(shí)時(shí)任務(wù)調(diào)度的有效、合適的方法，都基于每個(gè)任務(wù)的額外信息，常見(jiàn)信息有：

• 就緒時(shí)間：任務(wù)開(kāi)始準(zhǔn)備執(zhí)行時(shí)間，對(duì)于周期性或重復(fù)的任務(wù)，該時(shí)間序列提前可以知道。對(duì)于非周期性任務(wù)，或者事先知道，或者操作系統(tǒng)僅僅知道什么時(shí)候任務(wù)就緒。

• 啟動(dòng)最后時(shí)間：必須開(kāi)始的時(shí)間。

• 完成最后時(shí)間：必須完成的時(shí)間，典型實(shí)時(shí)應(yīng)用程序有啟動(dòng)最后時(shí)間或完成最后時(shí)間的一個(gè)。

• 處理時(shí)間：開(kāi)始執(zhí)行到完成的時(shí)間，某些情況操作系統(tǒng)度量指數(shù)平均值而不是提供此時(shí)間。

• 資源需求：執(zhí)行時(shí)需要的資源集合（除處理器）。

• 優(yōu)先級(jí)：硬實(shí)時(shí)任務(wù)可能有絕對(duì)優(yōu)先級(jí)，錯(cuò)過(guò)則導(dǎo)致系統(tǒng)失敗。如果系統(tǒng)無(wú)論如何都要運(yùn)行，則硬、軟實(shí)時(shí)任務(wù)可以被指定相關(guān)的優(yōu)先級(jí)以指導(dǎo)調(diào)度器。

• 子任務(wù)結(jié)構(gòu)：一個(gè)任務(wù)可被分解為必須運(yùn)行或可選的子任務(wù)。

    相關(guān)的策略有：

• 最早最后期限：選擇就緒任務(wù)里有最近的最后期限任務(wù)。

• 有自愿空閑時(shí)間的最早最后期限：只優(yōu)先調(diào)用最近的最后期限任務(wù)，即使要等待還沒(méi)有就緒的任務(wù)。

2.2 速率單調(diào)調(diào)度

    速率單調(diào)調(diào)度RMS是基于任務(wù)的周期給它們指定優(yōu)先級(jí)，周期越短（速率越高）優(yōu)先越高，周期與速率互為倒數(shù)。處理器利用率為執(zhí)行時(shí)間/周期時(shí)間。

    由于每個(gè)任務(wù)的處理器利用率和不大于1，所以可以通過(guò)計(jì)算總處理器利用率以判斷是否所以任務(wù)可以實(shí)時(shí)執(zhí)行完畢。而RMS對(duì)于以下不等式成立：n個(gè)任務(wù)的總利用率和不大于n*(2^(1/n) -1)。

    選擇RMS的原因是：

• 該公式是保守值，實(shí)際上通常能到達(dá)90%。

• 大多數(shù)硬實(shí)時(shí)系統(tǒng)也有軟時(shí)間部件，如非關(guān)鍵性的顯示與內(nèi)置的自測(cè)試，可以在低優(yōu)先上執(zhí)行，占用硬實(shí)時(shí)任務(wù)的RMS調(diào)度中沒(méi)有使用的處理器時(shí)間。

• RMS易于實(shí)現(xiàn)穩(wěn)定性。當(dāng)由于超載和瞬時(shí)錯(cuò)誤而不能滿足最后期限時(shí)，原則上對(duì)一些基本任務(wù)只要是可調(diào)度的，其最后期限就應(yīng)該被保證。如果使用靜態(tài)優(yōu)先級(jí)分配方法，只需要確?；救蝿?wù)具有相對(duì)較高的優(yōu)先級(jí)；如果使用RMA，可以讓基本任務(wù)有較短的周期，或通過(guò)修改RMS優(yōu)先級(jí)以說(shuō)明基本任務(wù)實(shí)現(xiàn)；對(duì)于最早最后期限調(diào)度，周期性任務(wù)的優(yōu)先級(jí)從一個(gè)周期到另一個(gè)周期是不斷變化的，使得基本任務(wù)的最后期限難以滿足。