概述

    對于多處理器調度，此處概述了多個處理器可能帶來的問題和設計上的一些問題；對于實時調度，概述了兩種調度方法：限時調度和速率單調調度。

海寧ssl適用于網站、小程序/APP、API接口等需要進行數據傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

1 多處理器調度

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

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

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

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

1.1 多處理器帶來的問題

    調度上需要考慮三種問題：

• 將進程分配到處理器。

• 在單個處理器上使用多道程序設計。

• 一個進程 的實際分派。

1.1.1將進程分配到處理器

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

    如果一個進程的生命周期都被分配到一個處理器上（靜態(tài)分配），則需要為每個處理器維護一個短程隊列，優(yōu)點是開銷小（所有進程只分配一次，使用專門處理器的一個策略時組調度），缺點時一個處理器可能一直處于空閑狀態(tài)，而另一個處理器積壓許多工作，避免此方法是使用一個公共隊是列，所有進程進入并分配到任意一個可用的處理器上。在緊密耦合的共享儲存器結構中，所有處理器可以得到任意進程的上下文環(huán)境信息（調度進程的開銷與被調度到的處理器無關）。另一種分配方法是動態(tài)負載均衡（動態(tài)分配），線程可以在不同處理器所對應的隊列里轉移，Linux使用此策略。

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

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

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

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

1.1.2 在單處理器上使用多道程序設計

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

1.1.3 進程分派

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

1.2 進程調度

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

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

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

1.3 線程調度

    有4種比較突出的方法：

1.3.1 負載分配

    進程不是分配到固定的處理器，而是有系統(tǒng)維護一個就緒進程的全局隊列，當處理器空閑時就從隊列里選擇一個進程。

    優(yōu)點是：

• 負載均勻分布在各處理器上，有工作可做時，沒有處理器空閑。

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

• 可以選擇單處理調度的方案組織和訪問全局隊列，包括基于優(yōu)先級和執(zhí)行歷史或預處理請求的方案。 負載分配方案：

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

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

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

    缺點是：

• 中心隊列占據了必須互斥訪問的存儲器區(qū)域，當特別多的處理器同時查找工作時可能出現(xiàn)瓶頸。

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

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

1.3.2 組調度

    一組相關進程基于一對一的原則，同時調度到一組處理器上運行。提高程序性能的顯著方式是使進程切換開銷最小，即讓有聯(lián)系的線程可以同時運行。可以按照每個應用程序的線程個數加權分配不同的組調度時間，以減少處理器浪費的時間。

    優(yōu)點：

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

• 調度開銷可能減少，因為一個決策可以影響到許多的處理器和進程。

1.3.3 專用處理器分配

    與負載分配的方法相反，指定線程運行到某個處理器。處理器數目與線程數相等，線程結束時處理器返回到處理器池里。

    看上去會浪費處理器時間，即應用程序一個線程被阻塞且等待I/O或與其他線程的同步，則該處理會一直空閑，屬于非多道程序設計。但有以下兩點的情況可以解釋使用此策略的原因：

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

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

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

1.3.4 動態(tài)調度

    線程數可變，通過調整負載提高利用率。

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

    調度策略：

• 有請求到來時：

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

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

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

• 處理器被釋放時： 掃描未滿足分配而等待的請求隊列，按照FCFS分配處理器資源。

2 實時調度

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

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

2.1 限期調度

    目標是盡可能快速啟動實時任務，因此強調快速中斷處理和任務分派。盡管存在動態(tài)資源請求和沖突、處理過載和軟硬件故障，實時應用程序不關注絕對速度，關注在最有價值的時間完成或啟動任務。

    關于實時任務調度的有效、合適的方法，都基于每個任務的額外信息，常見信息有：

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

• 啟動最后時間：必須開始的時間。

• 完成最后時間：必須完成的時間，典型實時應用程序有啟動最后時間或完成最后時間的一個。

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

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

• 優(yōu)先級：硬實時任務可能有絕對優(yōu)先級，錯過則導致系統(tǒng)失敗。如果系統(tǒng)無論如何都要運行，則硬、軟實時任務可以被指定相關的優(yōu)先級以指導調度器。

• 子任務結構：一個任務可被分解為必須運行或可選的子任務。

    相關的策略有：

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

• 有自愿空閑時間的最早最后期限：只優(yōu)先調用最近的最后期限任務，即使要等待還沒有就緒的任務。

2.2 速率單調調度

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

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

    選擇RMS的原因是：

• 該公式是保守值，實際上通常能到達90%。

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

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

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

新聞標題：操作系統(tǒng)精髓與設計原理--多處理器和實時調度-創(chuàng)新互聯(lián)
網站鏈接：http://www.chinadenli.net/article8/ccphip.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供商城網站、網站營銷、電子商務、網站排名、服務器托管、手機網站建設

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)