【操作系统 · 调度】多处理器 实时调度
1. 多處理器調度
多處理器系統(tǒng)分為以下幾類：
- 松耦合、分布式多處理器、集群 ： 由一些列相對自治的系統(tǒng)組成，每個處理器都有自身的內存和I/O通道。
- 專用處理器 ：I/O處理器最為經(jīng)典。此時，有一個通用的主處理器，專用處理器由主處理器控制 ，并為其服務。
- 緊耦合多處理器 ：由一系列共享同一個內存并受操作系統(tǒng)完全控制的處理器組成。
1.1 粒度
| 細 | 單指令流中固有的并行 | < 20 |
| 中等 | 一個單獨應用中的并行處理/多任務處理 | 20 ~ 200 |
| 粗 | 多道程序環(huán)境中并發(fā)進程的處理器 | 200 ~ 2000 |
| 極粗 | 在網(wǎng)絡節(jié)點上進行分布式處理，形成一個計算環(huán)境 | 2000 ~ 1M |
| 無約束 | 多個無關進程 | 不適用 |
無約束并行性
對于無約束并行（independent parallelism），進程間沒有顯式的同步。每個進程都代表獨立的應用/作業(yè)（典型為分時應用）。
粗粒度、極粗粒度并行性
粗粒度（coarse）、極粗粒度（very coarse）并行，指在進程間存在同步，但這種同步的級別極粗。可以簡單地處理為一組運行在多道程序單處理器上的并發(fā)進程。
中粒度并行性
典型情況下，為了達到中粒度并行性（medium-grain）的同步，在應用程序的線程之間，需要更高程度的合作、交互。
細粒度并行性
細粒度（fine-grain）并行性表示與線程中并行相比，更為復雜的使用情況。
1.2 設計問題
三個相互關聯(lián)的設計問題：把進程分配到處理器、在單處理器上使用多道程序設計、一個進程的實際分派。所用的方法，通常取決于應用程序的粒度級和可用處理器的數(shù)量。
把進程分配到處理器
若假設多處理器結構統(tǒng)一（各性能基本持平），最簡單的調度方法是把處理器視為一個資源池，并按照要求把進程分配到相應的處理器。
靜態(tài)分配 ：一個進程從被激活到完成，一直被分配給同一個處理器（需要為每個處理器維護一個專門的短程隊列）
動態(tài)負載平衡 ：該策略中，線程能在不同處理器對應的隊列間轉移
在單處理器上使用多道程序設計
如果每個進程在其生命周期中都被靜態(tài)地分配給一個處理器，就應考慮處理器是否支持都到程序。
進程分派
與多處理器調度相關的最后一個設計問題是選擇哪個進程運行。
1.3 進程調度
在大多傳統(tǒng)的多處理器系統(tǒng)中，進程并不指定到一個專用的處理器。并非所有處理器都只有一個隊列，或只使用某種類型的優(yōu)先級方案，而是有多個基于優(yōu)先級的隊列，都送入相同的處理器池中。在任何情況下，都可把系統(tǒng)視為多服務器排隊結構。
一般結論，對于雙處理器，調度原則的選擇不如在單處理器中重要。因此，在多處理器系統(tǒng)中使用簡單的FCFS原則，或在靜態(tài)優(yōu)先級方案中使用FCFS就已足夠。
1.4 線程調度
在多處理器線程調度和處理器分配的各種方案中，有四種重要方法：負載分配、組調度、專用處理器分配、動態(tài)調度 。
負載分配
進程不分配到某個特定的處理器。系統(tǒng)維護一個就緒隊列的全局隊列，每個處理器只要空閑就從隊列中選擇一個線程。
三種不同的負載分配方案：
-
先來先服務（FCFS）
-
最少線程數(shù)優(yōu)先
-
可搶占的最少線程數(shù)優(yōu)先
優(yōu)點：
- 負載在各處理器均勻分布，沒有處理器空閑。
- 無需集中調度程序，處理器可用，由操作系統(tǒng)為其選擇下一個線程。
缺點：
- 中心隊列必須占據(jù)互斥訪問的存儲器區(qū)域（成百上千個處理器可能出現(xiàn)瓶頸）
- 被搶占的線程可能不在同一個處理器上恢復執(zhí)行，每個處理器配置Cache時，Cache效率很低
- 如果所有處線程被視為公共的線程池，當一個程序的線程需要高度合作、無法同時訪問處理器時，會嚴重影響性能
組調度
一組相關的線程基于一對一的原則，同時調度到一組處理器上運行。
優(yōu)點：
- 組內的進程相關/大致平等時，同步阻塞減少、只需要很少的進程切換，性能提高
- 調度開銷減少，一個決策影響許多處理器、進程
組分配與 & 加權組分配：
專用處理器分配
它與負載分配相反，它通過把線程指定到處理器來定義隱式的調度。采用池化思想，維護處理器池，每個程序開始執(zhí)行時都分配給其與線程數(shù)等同數(shù)量的處理器，終止時，向處理器池交還資源。
一種極端形式的組調度：在一個應用程序執(zhí)行期間，把一組處理器專門分配給這個應用程序。即當每個線程都被分配給一個處理器，相應的處理器專門用于處理對應的線程，直到應用程序運行結束。
動態(tài)調度
在執(zhí)行期間，進程中線程數(shù)量可以改變。
當一個作業(yè)請求一個/多個處理器時：
釋放了一個/多個處理器時（包括作業(yè)離開）：
1.5 多核線程調度
隨著單個芯片上的內核數(shù)量的增加，最小化訪問片外存儲器比最大化處理器利用率更優(yōu)先。在最小化訪問片外存儲器方面，傳統(tǒng)且主流的方法是利用局部緩存。
例如，AMD推土機芯片，在這種芯片的架構中，每個內核擁有一個獨立的一級緩存，每對內核共享一個二級緩存，所有內核共享三級緩存。
當部分單非全部內核共享緩存時，調度期間線程分配給內核的方式對性能會有顯著的影響。
我們假定共享共享二級緩存的兩個內核相鄰。最好的情況是：
- 若兩個線程要 共享 內存資源，則應將其分配給 相鄰 的內核來 提高性能
- 若兩個線程 不共享 內存資源，則應將其分配到 不相鄰 內核以實現(xiàn) 負載均衡
緩存共享需要考慮兩方面的因素：
- 合作共享資源：使得多個線程可以訪問相同的內存區(qū)域（多線程應用、生產者-消費者線程交互）
- 資源搶占：線程在相鄰的內核上競爭緩存內存地址
2. 實時調度
兩種實時調度方法：
- 限時調度
- 速率單調調度
2.1 背景
硬實時任務（hard real-time task） ：必須滿足最后期限的任務，否則會給系統(tǒng)帶來不可接受的破壞 / 致命的錯誤。
軟實時任務（soft real-time task） ：有一個與之關聯(lián)的最后期限，希望能滿足這一期限，但并不強制。
非周期任務（aperiodic task） ：有一個必須結束/開始的最后期限，或有一個關于開始時間、結束時間的約束條件。
周期任務（periodic task） ：每隔周期T一次
2.2 特點
實時操作系統(tǒng)5方面需求表征：可確定性、可響應性、用戶控制、可靠性、故障弱化操作。
可確定性（deterministic）
在某種程度上是指它可以按照固定的、預先確定的時間/時間間隔執(zhí)行操作。多個進程競爭使用資源、處理器時間時，沒有哪個系統(tǒng)是完全可確定的。可確定性關注操作系統(tǒng)獲知有一個中斷之前的延遲。
可響應性（responsiveness）
可響應性關注在知道中斷之后，操作系統(tǒng)為中斷提供服務的時間。
用戶控制（user control）
在實時系統(tǒng)中，允許用戶細粒度地控制任務優(yōu)先級必不可少。用戶應能區(qū)分硬實時任務、軟實時任務，并在每類中確定相對優(yōu)先級。
可靠性（reliability）
在實時系統(tǒng)中比在非實時系統(tǒng)中更重要。實時系統(tǒng)是實時響應、控制事件的，性能的損失/降低可能產生災難性的后果。
故障弱化操作（fail-soft operation）
指系統(tǒng)在故障時盡可能多地保存其性能和數(shù)據(jù)的能力。
故障弱化運行的一個重要特征：穩(wěn)定性：
- 如果當它不可能滿足所有任務的最后期限時，及時總是不能滿足一些不太重要任務的最后期限，系統(tǒng)也將首先滿足最重要的、優(yōu)先級最高的任務的最后期限。
實時系統(tǒng) 常見功能：
- 使用更為嚴格的優(yōu)先級，以搶占式調度滿足實時性要求
- 中斷延遲（運行 → 中斷 時間）有界且相對較短
- 有更精確、更可預測的時序特征
實時系統(tǒng)的核心是短任務調度程序。在設計這種調度程序時，公平性、最小平均響應時間不是最重要的，最重要的是所有硬實時任務都能在最后期限內完成，且盡可能多的軟實時任務也能在最后期限內完成。
2.3 實時調度
靜態(tài)表調度法（static table-driven scheduling）
執(zhí)行關于可行調度的靜態(tài)分析。分析的結果是一個調度，它確定在運行時一個任務何時須開始執(zhí)行。
適用于周期性任務，輸入為周期性到達時間、執(zhí)行時間、周期性的最后結束期限、每個任務的相對優(yōu)先級。
靜態(tài)優(yōu)先級搶占調度法（static priority-driven preemptive scheduling）
執(zhí)行一個靜態(tài)分析，但未指定制度，而是通過給任務指定優(yōu)先級，使得可以使用傳統(tǒng)的基于優(yōu)先級的搶占式調度程序。
基于動態(tài)規(guī)劃的調度法（dynamic planning-based scheduling）
在運行時動態(tài)地確定可行性，而非開始運行前離線地確定。到達任務僅能滿足其他時間約束才能被接受、執(zhí)行。可行性分析結果是一個調度/規(guī)劃，用于確定何時分配任務。
動態(tài)盡力調度法（dynamic best effort scheduling）
不執(zhí)行可行性分析。系統(tǒng)試圖滿足最后期限，并終止已經(jīng)開始運行但錯過最后期限的進程。
當前許多商用實時系統(tǒng)使用的方法，一個任務到達時，根據(jù)任務特性賦予其優(yōu)先級，并通常使用某種形式的 時限調度（deadline scheduling），如最早最后期限調度。
2.4 限期調度
大多數(shù)當代實時操作系統(tǒng)的設計目標是盡快啟動實時任務，因此強調快速中斷處理、任務分派。實時應用程序本身并不關注絕對速度，二負按住在最優(yōu)價值的時間內完成任務，它按照優(yōu)先級來提供依據(jù)，而并不以最有價值的時間來完成需求。
實時任務調度的方法，所需最常見的信息：
- 就緒時間 ：任務開始準備執(zhí)行的時間。
- 啟動最后期限 ：任務必須開始的時間。
- 完成最后期限 ：任務必須完成的時間。
- 處理時間 ：從執(zhí)行任務直到完成任務所需的時間。
- 資源需求 ：任務在執(zhí)行過程中所需的資源集（處理器以外的資源）。
- 優(yōu)先級 ：度量任務的相對重要性。
- 子任務結構 ：一個任務可分解為一個必須執(zhí)行的子任務、一個可選執(zhí)行的子任務。
2.5 速率單調調度
速率單調調度（Rate Monotonic Scheduling, RMS），可解決周期性任務多任務調度沖突。
RMS基于任務的周期給它們指定優(yōu)先級。在RMS中，最短周期的任務具有最高優(yōu)先級，依次遞減。
若將任務優(yōu)先級視為速率的函數(shù)，則它是一個單調遞增函數(shù)，“速率單調調度” 因此得名。
2.6 優(yōu)先級反轉
**優(yōu)先級反轉（priority inversion）**是在任何基于優(yōu)先級的可搶占調度方案中都會出現(xiàn)的現(xiàn)象。
當一個低優(yōu)先級任務被某個資源（設備/信號量）所阻塞，且一個高優(yōu)先級的任務也要被同一個資源阻塞，就會發(fā)生優(yōu)先級反轉。高優(yōu)先級任務被置為阻塞態(tài)，低優(yōu)先級任務使用、釋放資源后，高優(yōu)先級任務才會被喚醒。
無界限優(yōu)先級反轉（unbounded priority inversion）：這種情況下，優(yōu)先級反轉的持續(xù)時間不僅取決于處理共享資源的時間，還卻決于其他不相關任務的不可預測行為。
優(yōu)先級繼承（priority inheritance）：優(yōu)先級較低的任務繼承任何與其共享同一個資源的優(yōu)先級較高的任務的優(yōu)先級。當高優(yōu)先級任務在資源上阻塞時，立即改變優(yōu)先級。資源被低優(yōu)先級任務釋放，這一改變結束。
優(yōu)先級置頂（priority ceililng）：優(yōu)先級與每個資源相關聯(lián)，資源的優(yōu)先級：比使用該資源的具有最高優(yōu)先級的用戶的優(yōu)先級
務也要被同一個資源阻塞，就會發(fā)生優(yōu)先級反轉。高優(yōu)先級任務被置為阻塞態(tài)，低優(yōu)先級任務使用、釋放資源后，高優(yōu)先級任務才會被喚醒。
無界限優(yōu)先級反轉（unbounded priority inversion）：這種情況下，優(yōu)先級反轉的持續(xù)時間不僅取決于處理共享資源的時間，還卻決于其他不相關任務的不可預測行為。
優(yōu)先級繼承（priority inheritance）：優(yōu)先級較低的任務繼承任何與其共享同一個資源的優(yōu)先級較高的任務的優(yōu)先級。當高優(yōu)先級任務在資源上阻塞時，立即改變優(yōu)先級。資源被低優(yōu)先級任務釋放，這一改變結束。
優(yōu)先級置頂（priority ceililng）：優(yōu)先級與每個資源相關聯(lián)，資源的優(yōu)先級：比使用該資源的具有最高優(yōu)先級的用戶的優(yōu)先級
總結
以上是生活随笔為你收集整理的【操作系统 · 调度】多处理器 实时调度的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于 Nios II 的串口打印和流水灯
- 下一篇： 概率分布 ---- 均匀分布