多處理器調度是根據處理器調度策略每次取出一個任務，將任務分配到處理器上運行的方法。多處理器調度包括給處理器分配進程、在單個處理器上是否使用多道程式技術、實際分派進程三個相關的方面。多處理器系統中執行緒調度通常有負載共享、成組調度、專用處理器分配、動態調度四種方式。
基本介紹
- 中文名：多處理器調度
- 外文名：Multiprocessor scheduling
- 作用：將任務分配到處理器上運行
- 多處理器分類：鬆散、緊密耦合多處理器系統
- 調度方法：分配-是否使用多道程式-實際分派
- 所屬學科：信息科學
多處理器系統,多處理器調度方法,多處理器系統中執行緒調度方式,
多處理器系統
多處理器系統是包含兩個或更多處理器的計算機系統。與單處理器系統相比，在速度、性能、可靠性等方面都有很大提高，相應地，在結構和管理上也變得更為複雜。多處理器系統分為鬆散耦合多處理器系統（或稱集群系統）、緊密耦合多處理器系統。
1、鬆散耦合多處理器系統（或稱集群系統）
這是一組相對自主系統的集合體，每台處理器有自己的記憶體和I/O通道。每台處理器上有自己的作業系統。往往通過高速通信線路互連在一起。
2、緊密耦合多處理器系統
一組處理器共享一個記憶體，並且在一個作業系統的集中控制下工作。最常用的模式是對稱多處理器（Symmetric MultiProcessor, SMP）結構。該結構中所有處理器都是同構的。該系統的作業系統負責管理由各個處理器組成的集合體，其中任一成員都可控制 I/O設備或對記憶體單元進行訪問。作業系統是浮動的，可從一個處理器轉到另一個處理器上。當前負責管理系統表格和系統函式的處理器稱為“執行機”。任何時候擔當執行機的處理器只能有一個，這樣可預防對全局系統信息的競爭。
多處理器調度方法
多處理器調度包括如下三個相關的方面：
1、給處理器分配進程，即把進程加到某個處理器所對應的就緒佇列中。如果多處理器的體系結構是相同的，最簡單的調度方法就是把所有處理器看做一個資源池，根據要求把進程分配給處理器。常用的分配方式有靜態分配（即把一個進程固定地分給一個處理器）和動態分配（即把系統中所有就緒進程放入一個全局佇列，從中選出進程並分派到任何可用的處理器上）兩種。
2、在單個處理器上是否使用多道程式技術。在傳統的多處理器中，每個單一的處理器應在若干進程之間進行切換，以便獲得高利用率和良好性能。如果一個應用程式由多執行緒的單個進程實現，它運行在多處理器上，那么保持每個處理器儘可能地忙不再是最重要的因素。在這種情況下，一般考慮的焦點是為應用程式提供更好的性能。如果組成一個應用程式的所有執行緒同時運行，其性能最好。
3、實際分派進程。在多處理器系統中，方法越簡單，開銷越少，效率就越高。有統計資料表明，在雙CPU系統中，進程採用FCFS調度算法與採用輪轉法、最短剩餘時間優先法相比較，系統吞吐量的變化很小。所以，對於多處理器系統來說，採用簡單的FCFS算法或帶有靜態優先權的FCFS算法是合適的。
為了防止多個處理器同時從一個就緒佇列中選擇進程時出現的競爭問題，可以採用轉鎖（Spin Lock）方式實現互斥。但簡單的轉鎖方式存在“循環等待”問題—— 當一個進程占用轉鎖時，如果其他進程也要用該鎖，就得循環測試並等待，直至那個進程釋放該鎖。有些系統採用“靈巧”調度（Smart Scheduling），即得到轉鎖的進程設定一個全局標誌，聲明它當前占用該鎖。當它釋放該鎖時，就清除該標誌。調度程式不讓占有轉鎖的進程停止，而是多給它一點兒運行時間，使之儘快完成臨界區工作，從而釋放該鎖。
多處理器系統中執行緒調度方式
多處理器系統中執行緒調度通常有如下四種方式：
1、負載共享
它不把進程分給具體的處理器，系統維護一個全局的就緒執行緒佇列，當某個處理器空閒時，就從該佇列中選擇一個執行緒。
負載共享的方法有：
① FCFS，即按順序排隊，選隊首執行緒投入運行。
② 最少執行緒數優先（Smallest Number of Threads First），即共享就緒佇列按優先權構造，具有未調度執行緒個數最少的作業其執行緒的優先權最高。
③ 搶占式最少執行緒數優先，是對最少執行緒數優先法的改造。如果新到來的作業所擁有的執行緒個數比當前運行作業的還少，就發生搶占。
負載共享方式的優點是負載分布在不同的處理器上；不需要集中調度，作業系統的調度程式可以運行在不同的處理器上。同時它也有若干缺點：對該全局佇列占用的記憶體區必須互斥訪問，可能成為瓶頸問題；由於被搶占的執行緒未必能在相同的處理器上恢復執行，因而降低本地高速快取的效率；把所有執行緒看做公用執行緒池，一個進程的所有執行緒未必能同時獲得處理器，從而嚴重損害處理器性能。
2、成組調度
這種方法把一組相關執行緒作為一個單位同時調到一組處理器上運行，一一對應，所有成組執行緒一起開始和結束它們的時間片。
成組調度可使一個進程的所有執行緒一起運行，若其中一個執行緒向另一個發出請求，能立即得到該信息且能立即回答。因此在一個時間片中，同一個進程的各執行緒間可以傳送和接收大量的信息，大大方便了執行緒間的通信。
3、專用處理器分配
這是成組調度的極端形式。當一個進程被調度時，它的每個執行緒被分配到一個處理器上，在該進程完成之前，處理器由相應的執行緒專用。
這種方法會浪費處理器的時間。當一個執行緒為了與另一個執行緒同步而等待I/O時，該執行緒專用的處理器就閒置了。但是，在由幾十甚至上百個處理器組成的高度並行系統中，處理器的利用率不再是最重要的問題。此外，在一個應用程式的生存期中完全避免了進程切換，因而大大加速了程式的執行。
4、動態調度
這種方法允許在進程執行期間動態改變其執行緒的數目。作業系統的調度職責主要限 於處理器的分配，並且遵循以下原則：當一個作業請求一個或多個處理器時，如果有空閒的處理器，就使用它們，以滿足請求；否則，如果提出請求的作業是剛到來的，則從當前分得多個處理器的任何一個作業中拿出一個處理器分給該作業；如果任一部分請求都不能滿足，該作業就保持未完成狀態，直至有處理器可供它使用或該作業取消這個請求；當釋放一個或多個處理器時，掃描當前尚未處理過的請求處理器的作業佇列，且為佇列中尚未分到處理器的每個作業分配一個處理器，然後再次掃描該佇列，按FCFS方式分配其餘的處理器。動態調度方法優於成組調度或專用處理器分配方法，但是這種方法的開銷較大。
