多處理機的任務分配和進程調(diào)度

多處理機的任務分配和進程調(diào)度

目錄多處理機的相關介紹多處理機的任務分配（簡）處理機的進程調(diào)度多處理機的進程調(diào)度多處理機概念：

兩個或兩個以上處理機，通過高速互聯(lián)網(wǎng)絡連接起來，在統(tǒng)一的操作系統(tǒng)管理下，實現(xiàn)指令及以上級（任務級、作業(yè)級）并行。特點:a.結(jié)構(gòu)靈活b.程序并行:屬于操作一級的并行，性能比指令高c.進程同步:不需要同步控制（并行處理機需要）d.多處理機工作時，根據(jù)多種條件分配資源，所以所需要的資源變化復雜。多處理機分類：

按照處理機間的連接程度:緊密耦合MP和松散耦合MP

按照是否共享主存儲器:共享存儲器MP和分布式存儲器MP

按照處理機類型:同構(gòu)MP和異構(gòu)MP

按照處理機的個數(shù)：大規(guī)模并行處理機MPP和對稱多處理機SMP

另外，多向量處理機和機群系統(tǒng)也是多處理機多處理機-互連方式總線形式環(huán)形互連形式交叉開關形式多端口存儲器形式開關樞紐結(jié)構(gòu)形式多處理機-互連方式1.總線形式多個處理機、存儲器模塊和外圍設備通過接口與公用總線相連，采用分時或多路轉(zhuǎn)接技術(shù)傳送。結(jié)構(gòu)簡單，成本低，增減模塊方便，但對總線的失效敏感。

提高總線的系統(tǒng)效率：采用優(yōu)質(zhì)高頻同軸電纜，用光纖采用多總線方式減少沖突概率多處理機-互連方式總線仲裁算法：a.靜態(tài)優(yōu)先級算法：為每一個連到總線的部件分配固定的優(yōu)先級b.固定時間片算法：把總線按固定大小時間片，輪流提供給部件使用c.動態(tài)優(yōu)先級算法：讓總線上各部件優(yōu)先級可根據(jù)情況按一定規(guī)則動態(tài)地改變d.先來先服務算法：按接受到訪問總線請求先后順序來響應多處理機-互連方式2.環(huán)形互連形式總線形成環(huán)形互連；令牌（Token）；點點連接，物理參數(shù)容易控制；適合于高帶寬的光纖

多處理機-互連方式P6P7P5P4P0P1P3P2級間采用環(huán)形互連的多處理機多處理機-互連方式3.交叉開關形式包含一組縱橫開關陣列；

是總線方式的極端；

交叉開關陣列復雜；

總線數(shù)=m+I+n,m:存儲器模塊數(shù)

n:處理機數(shù)I:I/o設備數(shù)

一般:M>=I+N多處理機-互連方式PnPnM1M2M3I/O1I/O2交叉開關形式多處理機-互連方式4.多端口存儲器形式如果每個存儲器模塊有多個訪問端口，且將分布在交叉開關矩陣中的控制、轉(zhuǎn)換和優(yōu)先級仲裁邏輯分別移到相應存儲器模塊的接口中。

I/O1I/O1M1M1M4M3M2P1P2四端口存儲器形式的結(jié)構(gòu)多處理機-互連方式5.開關樞紐結(jié)構(gòu)形式把互連結(jié)構(gòu)的開關設置在各個處理機或其接口內(nèi)部，組成分布式結(jié)構(gòu)。美國加州大學伯克利分校設計的樹形多處理機X-TREE

多處理機與并行處理機的比較方

面并行處理機SIMD多處理機

結(jié)構(gòu)靈活性針對向量、數(shù)組處理而設計的，有專用性，雖然處理單元數(shù)多16384個，但設置有限的、固定的實現(xiàn)作業(yè)、任務、程序段的并行，適應算法，結(jié)構(gòu)靈活多變，實現(xiàn)復雜的機間互連，避免爭用共享的硬件資源程序并行性實現(xiàn)操作級并行，并行性存在指令內(nèi)部并行性還存在于指令外部，表現(xiàn)于多個任務間的并行

并行任務派生通過指令來反映數(shù)據(jù)間是否并行計算，并由指令直接啟動多個處理單元并行工作需要專門的指令或語句指明程序中各程序段的并發(fā)關系，并控制并發(fā)執(zhí)行進程同步實現(xiàn)指令內(nèi)部對數(shù)據(jù)操作的并行實現(xiàn)指令、任務作業(yè)級的并行資源分配和任務調(diào)度處理單元數(shù)目固定，可利用屏蔽手段，改變數(shù)目處理機數(shù)目不固定，復雜多處理機的任務分配（任務調(diào)度）NP問題分布式內(nèi)存多處理機上并行任務靜態(tài)調(diào)度一種基于A*算法的多處理機任務調(diào)度算法一種多處理機任務分配的啟發(fā)式算法一種有優(yōu)先約束的多處理機系統(tǒng)的任務分配方法處理機的進程調(diào)度（線程調(diào)度）處理機調(diào)度的基本概念What---按什么原則分配CPU---進程調(diào)度算法When---何時分配CPU---進程調(diào)度時機How---如何分配CPU---進程調(diào)度過程處理機調(diào)度目的：分配CPU處理機調(diào)度方式：一級調(diào)度或二級調(diào)度調(diào)度算法：FCFS、SPF(SJF)、時間片輪轉(zhuǎn)、優(yōu)先權(quán)高者優(yōu)先、多級反饋隊列等不同的調(diào)度算法。處理機的進程調(diào)度進程調(diào)度分類

按調(diào)度層次，分為按OS的類型，分為高級調(diào)度中級調(diào)度低級調(diào)度批處理調(diào)度分時調(diào)度實時調(diào)度多處理機調(diào)度處理機的進程調(diào)度選擇調(diào)度方式和調(diào)度算法的若干準則1.面向用戶的準則a.周轉(zhuǎn)時間短：是批處理系統(tǒng)中衡量性能的一個重要指標。分為兩個具體指標：作業(yè)周轉(zhuǎn)時間和進程周轉(zhuǎn)時間。b.響應時間快：是分時系統(tǒng)中衡量性能的重要指標。從提交一個請求開始到首次產(chǎn)生響應為止(顯示出結(jié)果)的一段時間間隔。c.截至時間的保證：是實時系統(tǒng)中衡量性能的一個重要指標。是指某任務必須從開始執(zhí)行的最近時間，或必須完成的最遲時間。d.優(yōu)先權(quán)準則：它是緊急作業(yè)得到及時處理的重要保證。處理機的進程調(diào)度2.面向系統(tǒng)的準則a.系統(tǒng)吞吐量大：是用于評價批處理系統(tǒng)的重要指標，因而它是選擇批處理系統(tǒng)的重要準則。b.處理機利用率高：是大、中型計算機系統(tǒng)選擇調(diào)度算法的重要依據(jù)。但對單用戶或?qū)崟r系統(tǒng)，它不是十分重要的準則了。c.各類資源的平衡利用：也是大、中型計算機系統(tǒng)選擇調(diào)度算法的重要依據(jù)。對單用戶或?qū)崟r系統(tǒng)，它不是十分重要的準則了。處理機的進程調(diào)度調(diào)度算法1.先來先服務算法（FCFS）

該算法總是把處理機分配給最先進入就緒隊列的進程，即：就緒隊列按進入的先后順序排隊。

優(yōu)點：實現(xiàn)簡單

缺點：沒有考慮進程的優(yōu)先級

屬于不可搶占策略

此算法是有利于長(大)作業(yè)(進程)，不利于短(小)作業(yè)(進程)；有利于CPU繁忙的作業(yè)(進程)，不利于I/O繁忙的作業(yè)(進程)。處理機的進程調(diào)度2.短作業(yè)（進程）優(yōu)先調(diào)度算法（SJF/SPF）

是指對短作業(yè)或者短進程優(yōu)先調(diào)度的算法。

屬于不可搶占策略短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。處理機的進程調(diào)度優(yōu)點：該算法相對FCFS來說調(diào)度性能要好些，且能滿足大多數(shù)作業(yè)(均是短作業(yè))用戶的要求。缺點：a.該算法對長作業(yè)不利b.該算法未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進程）及時得到處理。c.該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。處理機的進程調(diào)度3.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（1）優(yōu)先權(quán)調(diào)度算法的類型

基本原理是：對于進程調(diào)度，它總是把處理機分配給就緒隊列中具有最高優(yōu)先權(quán)的進程；對于作業(yè)調(diào)度，它總選擇后備隊列中若干具有高優(yōu)先權(quán)的作業(yè)進入內(nèi)存。優(yōu)先級調(diào)度算法又可分為：非搶占的優(yōu)先級調(diào)度法可搶占的優(yōu)先級調(diào)度法處理機的進程調(diào)度（2）優(yōu)先權(quán)的類型a.靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，在整個運行期間不再發(fā)生改變。

確定靜態(tài)優(yōu)先權(quán)的依據(jù)：

進程類型；進程對資源的需求；用戶要求的優(yōu)先權(quán)

靜態(tài)優(yōu)先權(quán)簡單易行，系統(tǒng)開銷小，但不精確。b.動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)是基于某種原則，使進程的優(yōu)先權(quán)隨時間而改變。

處理機的進程調(diào)度（3）高響應比優(yōu)先調(diào)度算法

HRN原理：就是在每調(diào)度一個作業(yè)投入運行時，先計算后備作業(yè)隊列中每個作業(yè)的響應比，然后挑選響應比最高者投入運行。優(yōu)點：該算法既照顧了短作業(yè)用戶，同時也避免了長作業(yè)用戶無限期的等待，是FCFS和SJ(P)F兩種算法的較好折衷方案。

缺點：算法較為復雜，增加了系統(tǒng)開銷(計算響應比)。處理機的進程調(diào)度4.基于時間片的輪轉(zhuǎn)調(diào)度算法

（1）基本原理：輪轉(zhuǎn)法是最簡單又最公平的進程調(diào)度算法。主要用于分時系統(tǒng)中作為其主調(diào)度算法。

屬于可搶占策略輪轉(zhuǎn)法分配給每一進程在CPU上運行的時間長度，稱之為時間片。其基本原理是：諸進程以此時間片為限制，輪流使用CPU。如果時間片到期時，進程尚未完成運行，調(diào)度程序?qū)儕Z它正在使用的CPU，轉(zhuǎn)讓給另一進程使用；如果進程在使用完它的某一時間片之前已經(jīng)完成運行或已阻塞，CPU也立即轉(zhuǎn)讓給另一進程使用。處理機的進程調(diào)度（2）時間片大小的確定輪轉(zhuǎn)法的性能取決于時間片大小的選擇。例：若一次切換時間為5毫秒，時間片長度選擇為20毫秒，則20％的CPU時間花費于進程調(diào)度程序。為了改善CPU的利用率，可以增大時間片，比如說為500毫秒，此時CPU利用率達99％之多，但每一進程的響應時間也因之增大。若就緒隊列中共有10個進程，則每一進程需要等待5秒鐘，才能在CPU上服務一次。

通常來說，選擇時間片為100毫秒左右比較適宜。時間片選擇有：固定時間片和可變時間片；與時間片大小有關的因素有：系統(tǒng)響應時間、就緒進程個數(shù)和CPU處理能力三個。

處理機的進程調(diào)度5.多級反饋隊列調(diào)度算法

（1）思路如下：把進程按優(yōu)先級分組，優(yōu)先級最高的進程組中的進程每次在CPU上運行一個時間片t長度；優(yōu)先級次之的進程組的進程每次運行二個時間片2t長度；優(yōu)先級再次之的進程組的進程每次運行4個時間片4t長度，以此類推，進程每次運行完它的時間片后便降低一個優(yōu)先級別，移至另一優(yōu)先級的進程組中。處理機的進程調(diào)度最高優(yōu)先權(quán)隊列時間片次高優(yōu)先權(quán)隊列時間片最低優(yōu)先權(quán)隊列時間片新進程進入s1s2s3sn至CPU至CPU至CPU至CPU(時間片：s1<s2<s3<…)再次高優(yōu)先權(quán)隊列時間片處理機的進程調(diào)度（2）多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法具有較好的性能，能滿足各種類型用戶的需要。

1.終端型用戶：作業(yè)較小，可在第一隊列的時間片內(nèi)完成。

2.短批處理型作業(yè)用戶：大多數(shù)作業(yè)可在第一隊列的時間片內(nèi)完成，稍長的也可在第二隊列的時間片內(nèi)完成。

3.長批處理型作業(yè)用戶：可依次在第一、二、…、n隊列的時間片內(nèi)完成。多處理機的進程調(diào)度（線程調(diào)度）

前面所討論的是單CPU下的進程調(diào)度，對于多CPU，一方面由于有多臺處理機，可采用的調(diào)度策略也隨之增多，另一方面在調(diào)度目標上，要求的是整個系統(tǒng)的運行效率的提高，即不能只保證單CPU忙，而且在引入線程后，調(diào)度的基本單位已經(jīng)是線程了。因此，在多CPU的OS中，廣泛采用了線程調(diào)度機制，接下來主要介紹對線程的調(diào)度問題。多處理機的進程調(diào)度（線程調(diào)度）多處理機系統(tǒng)（MPS）的類型1.緊密耦合MPS和松散耦合MPS(1)緊密耦合MPS結(jié)構(gòu)（同構(gòu)型）高速交叉開關M1M2M3MnI/O2I/O1……...P1P2P3Pn特點：通過高速總線或高速交叉開關進行處理機之間的

互連，并共享存儲器。一般說，該結(jié)構(gòu)里的所有

處理機都是相同的。多處理機的進程調(diào)度（線程調(diào)度）(2)松散耦合MPS結(jié)構(gòu)（異構(gòu)型）P1P2PnMnM2M1I/O2I/O1I/On……特點：各個處理機有自己的存儲器和OS，它們之間通過通道或通信線路實現(xiàn)互連。一般說，該結(jié)構(gòu)里的所有處理機可以不相同。在多處理機系統(tǒng)中，進程調(diào)度與系統(tǒng)結(jié)構(gòu)和OS的工作模式均相關。多處理機的進程調(diào)度（線程調(diào)度）2.對稱多處理機系統(tǒng)和非對稱多處理機系統(tǒng)(1)對稱多處理機系統(tǒng)SMPS(SymmetricMultiProcessorSystem)

在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是相同的，當前的絕大多數(shù)MPS都屬于SMPS。例如，IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構(gòu)成的。(2)非對稱多處理機系統(tǒng)AMPS(AsymmetricalMultiProcessorSystem)

在系統(tǒng)中有多種類型的處理單元，它們的功能和結(jié)構(gòu)各不相同，其中只有一個主處理器，有多個從處理器。多處理機的進程調(diào)度（線程調(diào)度）進程分配方式1.對稱多處理機系統(tǒng)中的進程分配方式在SMP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個處理器池(Processorpool)，由調(diào)度程序或基于處理器的請求，將任何一個進程分配給池中的任何一個處理器去處理。在進行進程分配時，可采用以下兩種方式之一。多處理機的進程調(diào)度（線程調(diào)度）（1）靜態(tài)分配：是指一個進程從開始執(zhí)行直到完成，都被固定分配到一臺處理機上去執(zhí)行。采用該分配，需為每個處理機設置一個專用的就緒進程隊列，該隊列中的諸進程先后都被分配到該處理機上。在進程阻塞后再次就緒時，仍被掛在原來這個就緒隊列中。

優(yōu)點：進程調(diào)度的開銷小。

缺點：會使各CPU的忙、閑不均。多處理機的進程調(diào)度（線程調(diào)度）（2）動態(tài)分配：是指一個進程從開始執(zhí)行直到完成，可以隨機的被分配到任意一臺空閑處理機上去執(zhí)行。采用該分配，只需為系統(tǒng)設置一個公共的就緒隊列，所有就緒進程均放在此隊列中。在進程阻塞后再次被執(zhí)行時，分配給它的處理機可能已經(jīng)不是它原來分配給的處理機。

優(yōu)點：消除了各CPU的忙、閑不均的現(xiàn)象。缺點：進程調(diào)度的開銷較大。多處理機的進程調(diào)度（線程調(diào)度）2.非對稱對處理機系統(tǒng)中的進程分配對于異構(gòu)型多處理機系統(tǒng)，OS大多采用主—從式(Master/Slave)式OS，即OS的核心部分駐留在主機上，而從機只是執(zhí)行用戶程序，進程調(diào)度只由主機執(zhí)行。每當從機空閑時，便向主機發(fā)送一要求進程的信號，主機便從隊首摘下一進程分配給發(fā)出請求信號的從機。從機執(zhí)行完畢后又向主機發(fā)送一要求進程的信號，如此繼續(xù)，直到任務完成。

優(yōu)點：系統(tǒng)易于實現(xiàn)，系統(tǒng)開銷較小。

缺點：資源利用率低，可靠性差，缺乏靈活性。多處理機的進程調(diào)度（線程調(diào)度）進程（線程）調(diào)度方式1.自調(diào)度(Self-Scheduling)方式（1）自調(diào)度機制在多處理機系統(tǒng)中，自調(diào)度方式是最簡單的一種調(diào)度方式。它是直接由單處理機環(huán)境下的調(diào)度方式演變而來的。在系統(tǒng)中設置有一個公共的進程或線程就緒隊列，所有的處理機在空閑時，都可自己到該隊列中取得一進程(線程)來運行。在自調(diào)度方式中，可采用在單處理機環(huán)境下所用的調(diào)度算法，如先來先服務調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等。多處理機的進程調(diào)度（線程調(diào)度）（2）自調(diào)度方式的優(yōu)點

a.只要系統(tǒng)中有工作可做，或說只要就緒隊列不空，就不會出現(xiàn)處理機空閑的情況。

b.系統(tǒng)中沒有集中的調(diào)度機制，任何處理機都可以利用OS的調(diào)度例程去選擇一線程。

c.對就緒隊列可按單處理機所采用的各種方式加以組織，其調(diào)度算法可沿用單處理機所用的算法。多處理機的進程調(diào)度（線程調(diào)度）（3）自調(diào)度方式的缺點a.瓶頸問題。這個問題在多處理機系統(tǒng)中當處理機個數(shù)不多時，表現(xiàn)得并不嚴重，但當處理機數(shù)目增大到數(shù)十乃至數(shù)百個時，就會產(chǎn)生嚴重的瓶頸問題了。

b.低效性。由于一個線程在整個生命期中可能要多次更換處理機，保存在原來（上一次）處理機高速緩存中的該線程數(shù)據(jù)需要在新處理機上重新建立拷貝，使得高速緩存的使用效率很低。

c.對線程切換頻繁。一個應用程序的若干線程在自調(diào)度方式中很難同時獲得處理機而同時運行，使得該應用程序中的某些線程會因其合作線程未獲得處理機而被阻塞，進而被切換下來。多處理機的進程調(diào)度（線程調(diào)度）2.成組調(diào)度(GangScheduling)方式為了解決自調(diào)度方式中線程切換頻繁的問題，提出了成組調(diào)度。它的調(diào)度性能通常優(yōu)于自調(diào)度，目前已得到廣泛認可。所謂成組調(diào)度，是將一個進程的若干線程分配到一組處理機上去執(zhí)行。這樣分配有如下好處：

a.

如果一組相互合作的線（進）程，能并行執(zhí)行，則可有效地減少線（進）程的阻塞情況的發(fā)生，從而可以減少線程的切換，使系統(tǒng)性能得到改善。

b.因為每次調(diào)度都可以解決一組線程的處理機分配問題，因而可以顯著地減少調(diào)度頻率，從而也就減少了調(diào)度開銷。多處理機的進程調(diào)度（線程調(diào)度）在成組調(diào)度中分配處理機可以