溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
對于多處理器調度，此處概述了多個處理器可能帶來的問題和設計上的一些問題；對于實時調度，概述了兩種調度方法：限時調度和速率單調調度。
多處理器系統可以分為以下幾類：
松耦合、分布式處理器、集群：有一系列相對自治的系統組成，每個處理器有自己的內存和I/O通道。
專門功能的處理器：I/O處理器時一個例子，此時有一個通用的主處理器，專門處理器受主處理器的控制，并給主處理器提供服務。
緊耦合多處理器：由一系列共享同一個內存并在操作系統完全控制的處理器組成，這里詳細分析。
調度上需要考慮三種問題：
將進程分配到處理器。
在單個處理器上使用多道程序設計。
一個進程 的實際分派。
如果多處理器結構統一，即在內存、I/O設備的訪問時沒有特殊的優勢，最簡單的方法時將處理器看作一個資源池，然后按照要求分配到對應處理器。那么要靜態還是動態分配呢？
如果一個進程的生命周期都被分配到一個處理器上（靜態分配），則需要為每個處理器維護一個短程隊列，優點是開銷小（所有進程只分配一次，使用專門處理器的一個策略時組調度），缺點時一個處理器可能一直處于空閑狀態，而另一個處理器積壓許多工作，避免此方法是使用一個公共隊是列，所有進程進入并分配到任意一個可用的處理器上。在緊密耦合的共享儲存器結構中，所有處理器可以得到任意進程的上下文環境信息（調度進程的開銷與被調度到的處理器無關）。另一種分配方法是動態負載均衡（動態分配），線程可以在不同處理器所對應的隊列里轉移，Linux使用此策略。
在分配到處理器的過程中，主要有兩種方法：主從式、對等式。
主從試：操作系統的主要核心功能在某個特定的處理器上運行，其他處理器可能僅僅用于執行用戶進程。主處理器負載調度作業，如果從處理器需要I/O調用等服務，則必須給主處理器發送請求，然后等待服務執行。由于主處理擁有對所有存儲器和I/O資源的控制，可以簡化沖突解決方案，所以幾乎不需要對單處理器多道程序操作系統進程增強。同時主處理器的失敗會導致整個系統的失敗，主處理器可能為性能瓶頸。
對等式：操作系統可以在任何處理器上執行。每個處理器從進場池里進行自調度。操作系統的穩定性和性能相對主從試較高，但同時增加了操作系統的復雜性：操作系統必須確保不能一個進程被多個處理器選擇，進程也不能在隊列里丟失，所以要采用一些可以解決同步競爭資源請求的技術。
當然還有在兩個極端之前的方法：可以提供處理器子集而非一個處理器，以專門用于內核的處理；基于優先級和執行歷史來管理內核進程和其他進程之前的需求差異。
如果每個進程使用靜態分配，就會有一個新問題：此處理器支持多道程序嗎？如果綁定后因為等待I/O或考慮到并發/同步而被頻繁阻塞，則會有處理器的浪費。
這是關于選擇那個進程運行的策略，在多道單處理器上面，使用優先級或基于歷史的高級調度算法比簡單的FCFS策略性能更好。而在多處理器上，這些復雜性可能不必要，甚至有相反效果，而簡單的方法可能更有效。對于線程調度則有比優先級或執行歷史更重要的新問題。
實際大多數傳統處理器系統，使用多條基于優先級的隊列，且都在相同的處理池中執行。并非指定專門處理器或一個處理器使用一個隊列。
在一個雙處理器和單處理器系統里，多處理的每個處理器處理速度是單處理的一半。使用FCFS調度、輪轉法和最短剩余時間法后進行比較，得到進程服務時間的對比，即一個進程的生命周期里使用處理器的時間。輪轉法的時間片長度比上下文環境切換的開銷大，且比平均服務時間短。該執行結果取決于每個進程之間的服務時間變化，從每個服務時間的差異從0增加，可得到一個結論：對于雙處理器，不同調度算法的差距沒有單處理表現的大，當處理器增多時該結論更加確定。因此多處理器使用簡單的FCFS或靜態優先級方案的FCFS即可。（在多處理器的FCSF調度中，一個長進程很少被中斷，其他進程可以使用其他的處理器，因此相對單處理器短進程等待時間較少）
(見文獻Sauer, C. and Chandy, K. Computer Systems Performance Mondling. Englewood Cliffs, NJ:Prentice Hall, 1981)
有4種比較突出的方法：
進程不是分配到固定的處理器，而是有系統維護一個就緒進程的全局隊列，當處理器空閑時就從隊列里選擇一個進程。
優點是：
負載均勻分布在各處理器上，有工作可做時，沒有處理器空閑。
不需要集中調度器。操作系統調度例程在空閑的處理器上運行以選擇就緒線程。
可以選擇單處理調度的方案組織和訪問全局隊列，包括基于優先級和執行歷史或預處理請求的方案。 負載分配方案：
FCFS：為空閑處理器選擇全局共享隊列末尾的就緒線程，直到完成或阻塞。
最少線程數優先：空閑就緒隊列被組織成優先級隊列，如果一個作業的位調度線程數目最少則優先級最高，優先級相同則優先執行先到達的作業，被調度的線程一直運行直到阻塞或結束。
可搶占最少線程數優先：如果一個新到的作業包含線程數少于當前正在執行的作業，則搶占執行。 通過實驗得出，FCFS的效果優于其他兩個調度策略。
缺點是：
中心隊列占據了必須互斥訪問的存儲器區域，當特別多的處理器同時查找工作時可能出現瓶頸。
被搶占的線程可能不在同一個處理器上恢復運行，如果每個處理器都配備一個本地高速緩存，則緩存效率較低。
如果所有線程看做公共的線程池，則一個程序的線程不能同時被多個處理器訪問。如果一個程序的線程之間需要高度的合作，則涉及的進程切換可能會影響性能。
一組相關進程基于一對一的原則，同時調度到一組處理器上運行。提高程序性能的顯著方式是使進程切換開銷最小，即讓有聯系的線程可以同時運行。可以按照每個應用程序的線程個數加權分配不同的組調度時間，以減少處理器浪費的時間。
優點：
如果緊密相關的進程并行執行，則同步阻塞的可能會減少，并且進程切換也會變少，性能會提高。
調度開銷可能減少，因為一個決策可以影響到許多的處理器和進程。
與負載分配的方法相反，指定線程運行到某個處理器。處理器數目與線程數相等，線程結束時處理器返回到處理器池里。
看上去會浪費處理器時間，即應用程序一個線程被阻塞且等待I/O或與其他線程的同步，則該處理會一直空閑，屬于非多道程序設計。但有以下兩點的情況可以解釋使用此策略的原因：
在高度并行的系統中，有幾十或幾百個處理器，每個處理器只占用系統總代價的一笑部分，處理器利用率不是衡量有效性或性能的一個重要因素。
在一個程度的聲明周期里要避免進程切換而加快程序的運行速度，類似操作系統的單處理器的存儲器分配問題，即一定時刻分配給一個程序多少處理器（一定時刻給進程分配多少頁框）。
在其他方案里提出一個類似虛擬內存的工作集術語--活動工作集：為了保證應用程序以可接受的速度運行，在處理器上必須同時調度的最少數目的線程。和存儲器管理方案一樣，調度活動工作集中所有元素是的失敗可能導致處理器抖動：調度其他線程時，取消了未來將要調度執行的線程。類似內存碎片，處理器碎片指當一些處理器剩余的數目和合適程度上不滿足正在等待的應用程序的需要。而組調度和專用處理器分配則有意避免這些問題。
線程數可變，通過調整負載提高利用率。
將處理器分配給作業，每個作業將他的部分可以運行任務映射到線程，使用當前分配的處理器運行。而關于運行那個子集以及需要掛起那個線程的決策留個單個應用程序決定。
調度策略：
有請求到來時：
如果有空閑的處理器，則使用并執行。
否則，如果是新到達的請求（不是未滿足分配需求而等待的請求），則選擇當前已分配的多個處理器的作業，分出處理器去執行新作業。
如果分配不能得到滿足，則保持未完整狀態，直到滿足的處理器可用，或請求廢除。
處理器被釋放時： 掃描未滿足分配而等待的請求隊列，按照FCFS分配處理器資源。
實時任務或進程是指該進程的執行與計算機系統外部的某些進程、功能或事件集合有關，并且為了保證有效和正確的與外部環境交互，必須滿足一個或多個最后期限。
實時操作系統是指能夠管理實時進程的操作系統。在實時的操作系統中，傳統的調度算法原則不適用，關鍵因素是滿足最后期限，很大程度上依靠搶占和對相對最后期限有反應的算法適合于這種上下文。
目標是盡可能快速啟動實時任務，因此強調快速中斷處理和任務分派。盡管存在動態資源請求和沖突、處理過載和軟硬件故障，實時應用程序不關注絕對速度，關注在最有價值的時間完成或啟動任務。
關于實時任務調度的有效、合適的方法，都基于每個任務的額外信息，常見信息有：
就緒時間：任務開始準備執行時間，對于周期性或重復的任務，該時間序列提前可以知道。對于非周期性任務，或者事先知道，或者操作系統僅僅知道什么時候任務就緒。
啟動最后時間：必須開始的時間。
完成最后時間：必須完成的時間，典型實時應用程序有啟動最后時間或完成最后時間的一個。
處理時間：開始執行到完成的時間，某些情況操作系統度量指數平均值而不是提供此時間。
資源需求：執行時需要的資源集合（除處理器）。
優先級：硬實時任務可能有絕對優先級，錯過則導致系統失敗。如果系統無論如何都要運行，則硬、軟實時任務可以被指定相關的優先級以指導調度器。
子任務結構：一個任務可被分解為必須運行或可選的子任務。
相關的策略有：
最早最后期限：選擇就緒任務里有最近的最后期限任務。
有自愿空閑時間的最早最后期限：只優先調用最近的最后期限任務，即使要等待還沒有就緒的任務。
速率單調調度RMS是基于任務的周期給它們指定優先級，周期越短（速率越高）優先越高，周期與速率互為倒數。處理器利用率為執行時間/周期時間。
由于每個任務的處理器利用率和不大于1，所以可以通過計算總處理器利用率以判斷是否所以任務可以實時執行完畢。而RMS對于以下不等式成立：n個任務的總利用率和不大于n*(2^(1/n) -1)。
選擇RMS的原因是：
該公式是保守值，實際上通常能到達90%。
大多數硬實時系統也有軟時間部件，如非關鍵性的顯示與內置的自測試，可以在低優先上執行，占用硬實時任務的RMS調度中沒有使用的處理器時間。
RMS易于實現穩定性。當由于超載和瞬時錯誤而不能滿足最后期限時，原則上對一些基本任務只要是可調度的，其最后期限就應該被保證。如果使用靜態優先級分配方法，只需要確保基本任務具有相對較高的優先級；如果使用RMA，可以讓基本任務有較短的周期，或通過修改RMS優先級以說明基本任務實現；對于最早最后期限調度，周期性任務的優先級從一個周期到另一個周期是不斷變化的，使得基本任務的最后期限難以滿足。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
