作業系統精髓與設計原理--多處理器和實時排程

概述

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

1 多處理器排程

    多處理器系統可以分為以下幾類：

• 松耦合、分布式處理器、叢集：有一系列相對自治的系統組成，每個處理器有自己的記憶體和I/O通道。
• 專門功能的處理器：I/O處理器時一個例子，此時有一個通用的主處理器，專門處理器受主處理器的控制，并給主處理器提供服務。
• 緊耦合多處理器：由一系列共享同一個記憶體并在作業系統完全控制的處理器組成，這裡詳細分析。

1.1 多處理器帶來的問題

    排程上需要考慮三種問題：

• 将程序配置設定到處理器。
• 在單個處理器上使用多道程式設計。
• 一個程序 的實際分派。

1.1.1将程序配置設定到處理器

    如果多處理器結構統一，即在記憶體、I/O裝置的通路時沒有特殊的優勢，最簡單的方法時将處理器看作一個資源池，然後按照要求配置設定到對應處理器。那麼要靜态還是動态配置設定呢？

    如果一個程序的生命周期都被配置設定到一個處理器上（靜态配置設定），則需要為每個處理器維護一個短程隊列，優點是開銷小（所有程序隻配置設定一次，使用專門處理器的一個政策時組排程），缺點時一個處理器可能一直處于空閑狀态，而另一個處理器積壓許多工作，避免此方法是使用一個公共隊是列，所有程序進入并配置設定到任意一個可用的處理器上。在緊密耦合的共享儲存器結構中，所有處理器可以得到任意程序的上下文環境資訊（排程程序的開銷與被排程到的處理器無關）。另一種配置設定方法是動态負載均衡（動态配置設定），線程可以在不同處理器所對應的隊列裡轉移，Linux使用此政策。

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

• 主從試：作業系統的主要核心功能在某個特定的處理器上運作，其他處理器可能僅僅用于執行使用者程序。主處理器負載排程作業，如果從處理器需要I/O調用等服務，則必須給主處理器發送請求，然後等待服務執行。由于主處理擁有對所有存儲器和I/O資源的控制，可以簡化沖突解決方案，是以幾乎不需要對單處理器多道程式作業系統程序增強。同時主處理器的失敗會導緻整個系統的失敗，主處理器可能為性能瓶頸。
• 對等式：作業系統可以在任何處理器上執行。每個處理器從進場池裡進行自排程。作業系統的穩定性和性能相對主從試較高，但同時增加了作業系統的複雜性：作業系統必須確定不能一個程序被多個處理器選擇，程序也不能在隊列裡丢失，是以要采用一些可以解決同步競争資源請求的技術。
• 當然還有在兩個極端之前的方法：可以提供處理器子集而非一個處理器，以專門用于核心的處理；基于優先級和執行曆史來管理核心程序和其他程序之前的需求差異。

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

    如果每個程序使用靜态配置設定，就會有一個新問題：此處理器支援多道程式嗎？如果綁定後因為等待I/O或考慮到并發/同步而被頻繁阻塞，則會有處理器的浪費。

1.1.3 程序分派

    這是關于選擇那個程序運作的政策，在多道單處理器上面，使用優先級或基于曆史的進階排程算法比簡單的FCFS政策性能更好。而在多處理器上，這些複雜性可能不必要，甚至有相反效果，而簡單的方法可能更有效。對于線程排程則有比優先級或執行曆史更重要的新問題。

1.2 程序排程

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

    在一個雙處理器和單處理器系統裡，多處理的每個處理器處理速度是單處理的一半。使用FCFS排程、輪轉法和最短剩餘時間法後進行比較，得到程序服務時間的對比，即一個程序的生命周期裡使用處理器的時間。輪轉法的時間片長度比上下文環境切換的開銷大，且比平均服務時間短。該執行結果取決于每個程序之間的服務時間變化，從每個服務時間的差異從0增加，可得到一個結論：對于雙處理器，不同排程算法的差距沒有單處理表現的大，當處理器增多時該結論更加确定。是以多處理器使用簡單的FCFS或靜态優先級方案的FCFS即可。（在多處理器的FCSF排程中，一個長程序很少被中斷，其他程序可以使用其他的處理器，是以相對單處理器短程序等待時間較少）

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

1.3 線程排程

    有4種比較突出的方法：

1.3.1 負載配置設定

    程序不是配置設定到固定的處理器，而是有系統維護一個就緒程序的全局隊列，當處理器空閑時就從隊列裡選擇一個程序。

    優點是：

• 負載均勻分布在各處理器上，有工作可做時，沒有處理器空閑。
• 不需要集中排程器。作業系統排程例程在空閑的處理器上運作以選擇就緒線程。
• 可以選擇單處理排程的方案組織和通路全局隊列，包括基于優先級和執行曆史或預處理請求的方案。 負載配置設定方案：
• FCFS：為空閑處理器選擇全局共享隊列末尾的就緒線程，直到完成或阻塞。
• 最少線程數優先：空閑就緒隊列被組織成優先級隊列，如果一個作業的位排程線程數目最少則優先級最高，優先級相同則優先執行先到達的作業，被排程的線程一直運作直到阻塞或結束。
• 可搶占最少線程數優先：如果一個新到的作業包含線程數少于目前正在執行的作業，則搶占執行。 通過實驗得出，FCFS的效果優于其他兩個排程政策。

    缺點是：

• 中心隊列占據了必須互斥通路的存儲器區域，當特别多的處理器同時查找工作時可能出現瓶頸。
• 被搶占的線程可能不在同一個處理器上恢複運作，如果每個處理器都配備一個本地高速緩存，則緩存效率較低。
• 如果所有線程看做公共的線程池，則一個程式的線程不能同時被多個處理器通路。如果一個程式的線程之間需要高度的合作，則涉及的程序切換可能會影響性能。

1.3.2 組排程

    一組相關程序基于一對一的原則，同時排程到一組處理器上運作。提高程式性能的顯著方式是使程序切換開銷最小，即讓有聯系的線程可以同時運作。可以按照每個應用程式的線程個數權重配置設定不同的組排程時間，以減少處理器浪費的時間。

    優點：

• 如果緊密相關的程序并行執行，則同步阻塞的可能會減少，并且程序切換也會變少，性能會提高。
• 排程開銷可能減少，因為一個決策可以影響到許多的處理器和程序。

1.3.3 專用處理器配置設定

    與負載配置設定的方法相反，指定線程運作到某個處理器。處理器數目與線程數相等，線程結束時處理器傳回到處理器池裡。

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

• 在高度并行的系統中，有幾十或幾百個處理器，每個處理器隻占用系統總代價的一笑部分，處理器使用率不是衡量有效性或性能的一個重要因素。
• 在一個程度的聲明周期裡要避免程序切換而加快程式的運作速度，類似作業系統的單處理器的存儲器配置設定問題，即一定時刻配置設定給一個程式多少處理器（一定時刻給程序配置設定多少頁框）。

    在其他方案裡提出一個類似虛拟記憶體的工作集術語--活動工作集：為了保證應用程式以可接受的速度運作，在處理器上必須同時排程的最少數目的線程。和存儲器管理方案一樣，排程活動工作集中所有元素是的失敗可能導緻處理器抖動：排程其他線程時，取消了未來将要排程執行的線程。類似記憶體碎片，處理器碎片指當一些處理器剩餘的數目和合适程度上不滿足正在等待的應用程式的需要。而組排程和專用處理器配置設定則有意避免這些問題。

1.3.4 動态排程

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

    将處理器配置設定給作業，每個作業将他的部分可以運作任務映射到線程，使用目前配置設定的處理器運作。而關于運作那個子集以及需要挂起那個線程的決策留個單個應用程式決定。

    排程政策：

• 有請求到來時：

1. 如果有空閑的處理器，則使用并執行。
2. 否則，如果是新到達的請求（不是未滿足配置設定需求而等待的請求），則選擇目前已配置設定的多個處理器的作業，分出處理器去執行新作業。
3. 如果配置設定不能得到滿足，則保持未完整狀态，直到滿足的處理器可用，或請求廢除。

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

2 實時排程

    實時任務或程序是指該程序的執行與計算機系統外部的某些程序、功能或事件集合有關，并且為了保證有效和正确的與外部環境互動，必須滿足一個或多個最後期限。

    實時作業系統是指能夠管理實時程序的作業系統。在實時的作業系統中，傳統的排程算法原則不适用，關鍵因素是滿足最後期限，很大程度上依靠搶占和對相對最後期限有反應的算法适合于這種上下文。

2.1 限期排程

    目标是盡可能快速啟動實時任務，是以強調快速中斷處理和任務分派。盡管存在動态資源請求和沖突、處理過載和軟硬體故障，實時應用程式不關注絕對速度，關注在最有價值的時間完成或啟動任務。

    關于實時任務排程的有效、合适的方法，都基于每個任務的額外資訊，常見資訊有：

• 就緒時間：任務開始準備執行時間，對于周期性或重複的任務，該時間序列提前可以知道。對于非周期性任務，或者事先知道，或者作業系統僅僅知道什麼時候任務就緒。
• 啟動最後時間：必須開始的時間。
• 完成最後時間：必須完成的時間，典型實時應用程式有啟動最後時間或完成最後時間的一個。
• 處理時間：開始執行到完成的時間，某些情況作業系統度量指數平均值而不是提供此時間。
• 資源需求：執行時需要的資源集合（除處理器）。
• 優先級：硬實時任務可能有絕對優先級，錯過則導緻系統失敗。如果系統無論如何都要運作，則硬、軟實時任務可以被指定相關的優先級以指導排程器。
• 子任務結構：一個任務可被分解為必須運作或可選的子任務。

    相關的政策有：

• 最早最後期限：選擇就緒任務裡有最近的最後期限任務。
• 有自願空閑時間的最早最後期限：隻優先調用最近的最後期限任務，即使要等待還沒有就緒的任務。

2.2 速率單調排程

    速率單調排程RMS是基于任務的周期給它們指定優先級，周期越短（速率越高）優先越高，周期與速率互為倒數。處理器使用率為執行時間/周期時間。

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

    選擇RMS的原因是：

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