OS-04處理機調(diào)度1.ppt

1、第4章 處理機調(diào)度,處理器調(diào)度的類型 調(diào)度算法 傳統(tǒng)的UNIX調(diào)度 多處理器調(diào)度 實時調(diào)度 Windows 2000調(diào)度 UNIX SVR4調(diào)度 Linux調(diào)度,第4章 處理機調(diào)度,操作系統(tǒng)必須為多個進程可能有競爭的請求分配計算機資源。對處理器而言，可分配的資源是在處理器上的執(zhí)行時間，分配途徑是調(diào)度 調(diào)度功能必須設(shè)計成可以滿足多個目標，例如公平、任何進程都不會餓死、有效地使用處理器時間和低開銷等 調(diào)度功能還需要為某些進程的啟動或結(jié)束考慮不同的優(yōu)先級和實時最后期限 調(diào)度已經(jīng)實現(xiàn)了許多不同的算法。如今，調(diào)度研究的重點是開發(fā)多處理器系統(tǒng)，特別是用于多線程應(yīng)用的調(diào)度和實時調(diào)度,4 處理器調(diào)度的類型,多

2、道程序的關(guān)鍵是調(diào)度。典型的調(diào)度類型有： 長程調(diào)度(作業(yè)調(diào)度,高級調(diào)度）決定加入到待執(zhí)行的進程池中 中程調(diào)度（交換調(diào)度,中級調(diào)度）將進程調(diào)入內(nèi)存,或者將進程交換到硬盤 短程調(diào)度（進程調(diào)度，低級調(diào)度）決定哪一個就緒進程將被處理器執(zhí)行 線程調(diào)度,P86圖,就緒/掛起,新建,就緒,運行,退出,阻塞,短程調(diào)度,阻塞/掛起,中程調(diào)度,長程調(diào)度,長程調(diào)度,中程調(diào)度,處理器,就緒隊列,就緒、掛起隊列,釋放,超時,阻塞、掛起隊列,阻塞隊列,事件等待,交互用戶,批作業(yè),事件 發(fā)生,用于調(diào)度的隊列圖,長程調(diào)度程序決定哪一個程序可以進入系統(tǒng)中處理。一旦允許進入，一個作業(yè)或用戶程序成為一個進程，并被添加到供短程調(diào)度程序

3、使用的隊列中 在某些系統(tǒng)中，一個新創(chuàng)建的進程從一個換出條件開始，在這種情況下，它被添加到供中程調(diào)度程序使用的隊列中,長程調(diào)度,在批處理系統(tǒng)中，新提交的作業(yè)被發(fā)送到磁盤，保存在一個批處理隊列中。長程調(diào)度程序在可以時，從隊列中創(chuàng)建一個進程 調(diào)度程序必須決定可以接納一個進程還是多個進程 調(diào)度程序必須決定接受哪個或哪些作業(yè)，并轉(zhuǎn)變成進程,長程調(diào)度,何時創(chuàng)建一個新進程的決策通常由期望的多道程序的程度驅(qū)動。創(chuàng)建的進程越多，每個進程可以執(zhí)行的時間百分比就越小 為了給當前進程集提供滿意的服務(wù)，長程調(diào)度程序可能限制多道程序的程度 每當一個作業(yè)終止時，調(diào)度程序可能會決定增加一個或多個新作業(yè) 如果處理器的空閑時間片

4、超過了一定的閾值，可能會調(diào)用長程調(diào)度程序,長程調(diào)度,下一次允許哪一個進程進入的決策可以基于簡單的先來先服務(wù)原則，或者也可以基于管理系統(tǒng)性能的工具 使用的原則包括優(yōu)先級、期待執(zhí)行時間和I/O需求 同樣，可以根據(jù)請求哪個I/O資源和試圖平衡I/O使用的目的進行決策,長程調(diào)度,中程調(diào)度是交換功能的一部分，換入決策基于管理多道程序程度的要求 對不使用虛存的系統(tǒng)，存儲器管理也是一個問題。因此，換入決策將考慮換出進程的存儲需求,中程調(diào)度,從執(zhí)行的頻率看 長程調(diào)度程序的執(zhí)行頻率相對低些，并且僅僅是粗略地決定是否接受新進程以及接受哪一個 為進行交換決策，中程調(diào)度程序執(zhí)行得略微頻繁一些 短程調(diào)度程序，即分派程序

5、執(zhí)行得最頻繁，并且精確地決定下一次執(zhí)行哪一個進程,短程調(diào)度,4 調(diào)度算法,進程調(diào)度的主要問題就是采用某種算法合理有效地把處理機分配給進程 調(diào)度算法的設(shè)計原則： 盡可能提高資源的利用率，減少處理機的空閑時間 對于用戶作業(yè)采用較合理的平均響應(yīng)時間 盡可能地增強處理機的處理能力，避免有些進程長期不能投入運行,短程調(diào)度的主要目標是按照可以優(yōu)化系統(tǒng)行為的方式分配處理器時間。通常，需要相對于可能評估的各種調(diào)度策略建立一組準則 使用的準則可以按兩維來分類 面向用戶的準則 面向系統(tǒng)的準則,短程調(diào)度準則,面向用戶的準則 與單個用戶或進程感知到的系統(tǒng)的行為有關(guān) 例如交互式系統(tǒng)中的響應(yīng)時間。響應(yīng)時，這個時間數(shù)量對用

6、戶是可見的，也是用戶感興趣的 希望調(diào)度策略能給各種用戶提供“好”的服務(wù)。對于響應(yīng)時間，可能定義了一個閾值，如2秒。那么調(diào)度機制的目標是使平均響應(yīng)時間為2秒或小于2秒的用戶數(shù)最大,短程調(diào)度準則,面向系統(tǒng)的準則 面向系統(tǒng)的準則重點是有效和高效地利用處理器。例如吞吐量，也就是進程完成的速度 但面向系統(tǒng)準則的重點是系統(tǒng)性能，而不是提供給用戶的服務(wù)。因此，這是系統(tǒng)管理員所關(guān)注的，而不是普通用戶所關(guān)注的 面向用戶準則在所有系統(tǒng)中都是非常重要的，而面向系統(tǒng)原則在單用戶系統(tǒng)中的重要性低一些，只要系統(tǒng)對用戶應(yīng)用程序的響應(yīng)時間是可以接受的，則實現(xiàn)處理器高利用率或高吞吐量可能并不是很重要,短程調(diào)度準則,面向用戶準則

7、所關(guān)心的性能指標 周轉(zhuǎn)時間 指一個進程從提交到完成之間的時間間隔，包括實際執(zhí)行時間時間加上等待資源 (包括處理器資源) 的時間。對批處理作業(yè)來說，這是一種很適宜的度量 響應(yīng)時間 對一個交互進程，這是從提交一個請求到開始接收響應(yīng)之間的時間。該調(diào)度原則將試圖達到較低的響應(yīng)時間，并且在響應(yīng)時間可接受的范圍內(nèi)，交互用戶的數(shù)目最多 最后期限 當可以指定進程完成的最后期限時，調(diào)度原則將服從于其他目標，使得距最后期限最近,短程調(diào)度準則,其它： 帶權(quán)的周轉(zhuǎn)時間：周轉(zhuǎn)時間與執(zhí)行時間的比值 可預(yù)測性 無論系統(tǒng)的負載如何，一個給定的工作運行的總時間量和總代價是相同的。用戶不希望響應(yīng)時間或周轉(zhuǎn)時間的變化太大,短程調(diào)度

8、準則,面向系統(tǒng)準則所關(guān)心的性能指標 吞吐量 調(diào)度策略將試圖使得每個時間單位完成的進程數(shù)目最大。它取決于一個進程的平均長度，也受調(diào)度策略的影響，調(diào)度策略會影響使用率 處理器使用率 這是處理器忙的時間百分比。對昂貴的共享系統(tǒng)來說，這是一個重要的準則。在單用戶系統(tǒng)和一些別的系統(tǒng)如實時系統(tǒng)中，這個準則與其他相比顯得不太重要,短程調(diào)度準則,其它： 公平 在沒有來自用戶的指導或其他系統(tǒng)提供的指導時，進程應(yīng)該被平等對待，沒有一個進程會被餓死 強制優(yōu)先級 當進程被指定了優(yōu)先級，調(diào)度策略會先選擇高優(yōu)先級的進程 平衡資源 調(diào)度策略將保持系統(tǒng)中所有資源忙，對負擔較重的資源使用較少的進程更受歡迎。這個準則也可用于中程

9、調(diào)度和長程調(diào)度,短程調(diào)度準則,這些重要的調(diào)度準則是互相依賴的，不可能同時使它們都達到最優(yōu) 例如，提供較好的響應(yīng)時間可能需要調(diào)度算法在進程間頻繁地切換，這就增加了系統(tǒng)開銷，降低了吞吐量 設(shè)計一個調(diào)度策略涉及到在互相競爭的各種要求之間進行折衷，根據(jù)系統(tǒng)的本質(zhì)和使用情況，給各種要求設(shè)定相對權(quán)值 在大多數(shù)交互式操作系統(tǒng)中，不論是單用戶系統(tǒng)還是分時系統(tǒng)，適當?shù)捻憫?yīng)時間是最重要的要求,短程調(diào)度準則,作業(yè)調(diào)度性能評價（p90） 平均周轉(zhuǎn)時間 帶權(quán)的平均周轉(zhuǎn)時間 進程調(diào)度性能評價（p93） 可靠性 簡潔性 CPU利用率 進程在就緒隊列的等待時間和執(zhí)行時間比,進程調(diào)度,根據(jù)已占有處理機的進程是否可被剝奪這一原則

10、，調(diào)度方式（策略）可分為： 非剝奪方式：一旦某個就緒進程分得處理機之后，只要不是其自身的原因被阻塞 (如要求I/O操作) 而不能繼續(xù)運行時，就一直運行下去，直至運行結(jié)束 缺點：緊急進程無法立即運行，實時性差； 短進程周轉(zhuǎn)時間長，公平性差。,進程調(diào)度方式,剝奪方式：當一個正在運行的進程沒有運行完時，系統(tǒng)采取某種手段強行剝奪已分配給該進程的處理器資源。而被剝奪的進程重新回到就緒隊列中等待 在剝奪方式下，可以通過剝奪處理器所有權(quán)的方式，暫停當前進程的運行，已滿足更緊急進程的處理要求。,進程調(diào)度方式,進程調(diào)度方式,有三個進程p1，p2，p3到達時間為：0，3，4，優(yōu)先級依次增高，運行所需的時間分別為2

11、0，4，2，假設(shè)現(xiàn)按優(yōu)先級策略調(diào)度執(zhí)行，并且不采用時間片原則，請分別求出非剝奪方式和剝奪方式下各個進程的周轉(zhuǎn)時間。,周轉(zhuǎn)時間：p120；p223；p318,周轉(zhuǎn)時間：p126；p26；p32,當時間片為5時，采用優(yōu)先級策略，問非剝奪和剝 奪方式下，求各進程的周轉(zhuǎn)時間和響應(yīng)時間,先來先服務(wù) (FCFS First Come First Service) 按照進程就緒的先后順序來調(diào)度進程，到達的越早，其優(yōu)先級越高 獲得處理機的進程，在未遇到其他情況時一直運行下去采用的是非剝奪方式 系統(tǒng)只需具備一個先進先出的隊列，在管理優(yōu)先級的就緒隊列時，這種方法是一種最常見策略，并且在沒有其他信息時，也是一種最合

12、理的策略,調(diào)度算法,p93,輪轉(zhuǎn)調(diào)度 (簡單輪轉(zhuǎn)法RR) 系統(tǒng)把所有就緒進程按先后次序排隊，處理機總是優(yōu)先分配給就緒隊列中的第一個就緒進程，并分配它一個固定的時間片 (如50毫秒) 當該運行進程用完規(guī)定的時間片時，被迫釋放處理機給下一個處于就緒隊列中的第一個進程,自己回到就緒隊列的尾部，并等待下次調(diào)度 當某個正在運行的進程的時間片尚未用完，但進程需要 I/O時，該進程被送到相應(yīng)阻塞隊列，等I/O完成重新返回到就緒隊列尾部，等待調(diào)度。,調(diào)度算法,簡單輪轉(zhuǎn)法RR,處理器,就緒隊列,阻塞隊列,分派,釋放,超時,等待事件,事件發(fā)生,輪轉(zhuǎn)調(diào)度 簡單輪轉(zhuǎn)法是以就緒隊列中的所有進程均以相同的速度往前推進為其

13、特征。其時間片的長短，影響著進程的進展速度 當就緒進程很多時，如果時間片很長，就會影響一些需要“緊急”運行的作業(yè)。同樣這對短作業(yè)和要求 I/O 操作多的作業(yè)顯然是不利的 因而，在簡單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級輪轉(zhuǎn)法,調(diào)度算法,分級輪轉(zhuǎn)法 將一個就緒隊列根據(jù)進程的優(yōu)先級不同，劃分二個或二個以上的就緒隊列，并賦給每個隊列不同的優(yōu)先級 一般情況下，調(diào)度算法把相同的時間片分配給優(yōu)先級高的就緒隊列中的隊首進程 只有當優(yōu)先級高的就緒隊列中的所有進程全部運行完畢或等待I/O操作而沒有進程運行時，才把處理機分配給低優(yōu)先級就緒隊列中的進程,調(diào)度算法,高優(yōu)先級就緒隊列,低優(yōu)先級就緒隊列,處理器,分級輪轉(zhuǎn)調(diào)度,分派

14、,超時,阻塞隊列,釋放,調(diào)度算法,分級輪轉(zhuǎn)法 為了公平性，低優(yōu)先級就緒隊列的進程如果獲得調(diào)度，將得到比高優(yōu)先級就緒隊列進程更多的時間片，加以彌補 這樣能大大降低長作業(yè)的交換頻率，減少系統(tǒng)在交換作業(yè)時的時間消耗，又給了短作業(yè)較高的優(yōu)先級 兩個優(yōu)先級隊列特例：前臺和后臺進程。,優(yōu)先級調(diào)度算法：按進程的優(yōu)先級調(diào)度 非搶占的優(yōu)先級調(diào)度法：一旦一個高優(yōu)先級的進程占有了處理器，就一直運行下去，直到因等待某事被阻塞或執(zhí)行結(jié)束，才選擇就緒隊列中優(yōu)先級最高的進程來執(zhí)行。 可搶占的優(yōu)先級調(diào)度法：任何時刻都按照高優(yōu)先級進程在處理器上運行的原則進行進程調(diào)度。當一高優(yōu)先級進程運行時，若有一更高優(yōu)先級進程到達就緒隊列，則

15、當前運行進程立刻將處理器讓給更高優(yōu)先級的進程（即使未處理完，也無遇到阻塞情況）,調(diào)度算法,動態(tài)優(yōu)先級法 指進程的優(yōu)先級在該進程的生存期間可以改變 大多數(shù)動態(tài)優(yōu)先級設(shè)計方案 把交互式和I/O頻繁的進程移到優(yōu)先級隊列的頂端，而讓計算量大的進程移到較低的優(yōu)先級上 對與優(yōu)先級相同的進程，按先來先服務(wù)或輪轉(zhuǎn)法則分配處理機 對于一給定時間周期，一個正在運行的進程，每請求一次I/O操作后其優(yōu)先級就自動加 1，直接反映出I/O請求的頻率，從而使I/O設(shè)備具有很高的利用率,調(diào)度算法,最短進程SPN（短進程優(yōu)先調(diào)度算法） 減少FCFS固有的對長進程的偏愛的另一種方法是最短進程 (SPN) 策略，這是一種非剝奪的策

16、略，其原則是下一次選擇所需處理時間最短的進程，因此，短進程將會越過長進程，跳到隊列頭 SPN策略的難點在于需要知道或至少需要估計每個進程所需要的處理時間 長進程可能被“餓死”,調(diào)度算法,最短剩余時間優(yōu)先調(diào)度算法 (SRT) 對SPN增加剝奪機制。當一個時鐘中斷周期到后，調(diào)度程序總是選擇預(yù)期剩余時間最短的進程 當一個新進程加入就緒隊列時，它可能比當前運行的進程具有更短的剩余時間，因此，調(diào)度程序?qū)儕Z當前程序，將處理器分配給新進程。 和SPN一樣，調(diào)度程序必須有關(guān)于處理時間的估計，并且存在長進程被餓死的危險,調(diào)度算法,最高響應(yīng)比優(yōu)先調(diào)度算法（HRRN） 響應(yīng)比： R=(w+s)/s=1+w/s w

17、表示等待時間；s表示執(zhí)行所需時間 最高響應(yīng)比也是對最短進程法的一種改進，當當前進程完成或被阻塞時，選擇響應(yīng)比最大的進程先執(zhí)行，是一種非剝奪的策略。 響應(yīng)比R，代表了進程的年齡，算法在保證短進程優(yōu)先的同時又兼顧了長進程折中,調(diào)度算法,最高響應(yīng)比優(yōu)先調(diào)度算法（HRRN） R=(w+s)/s=1+w/s 當一系列進程同時進入系統(tǒng)時，由于短作業(yè)s值小，R值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。 但隨著長作業(yè)等待的時間(w)增長，R值不斷增大，到達一定的等待時間，長進程最終將憑借年齡的增長戰(zhàn)勝短進程，從而獲得處理器。 可見，在HRRN算法中，長作業(yè)不會被餓死,調(diào)度算法,反饋FB（多級反饋隊列調(diào)度算法） 分級輪

18、轉(zhuǎn)調(diào)度和動態(tài)優(yōu)先級算法的結(jié)合，采用剝奪策略 劃分多個就緒隊列，優(yōu)先級逐步降低。 新建進程進入優(yōu)先級最高的隊列中，每當進程規(guī)定的時間片用完，被剝奪時，就送往低一級的就緒隊列。 進程調(diào)度時總是先執(zhí)行高優(yōu)先級隊列中的進程。高優(yōu)先級隊列為空后，才轉(zhuǎn)去處理低一級優(yōu)先級隊列中的進程。 同一優(yōu)先級隊列（除最低）的進程，按FIFO機制調(diào)度。最低優(yōu)先級隊列，按時間片輪轉(zhuǎn)調(diào)度算法執(zhí)行,調(diào)度算法,允許進入,CPU,RQ0,RQ1,RQ2,RQn,釋放,CPU,釋放,CPU,釋放,CPU,釋放,反饋調(diào)度,不同優(yōu)先級的就緒隊列可以給予相同的時間片，也可以不同。,調(diào)度算法,反饋FB 在反饋調(diào)度算法中，長進程也存在餓死的現(xiàn)

19、象 當比運行進程更高優(yōu)先級隊列到來一個新進程時，則應(yīng)該處理高優(yōu)先級隊列的進程。有兩種方案： 搶占方式：即當高優(yōu)先級進程到來時，立即搶占處理進程的處理器，被搶占進程回到原來就緒隊列的末尾。 非搶占方式：當前進程用完規(guī)定的時間片后，再調(diào)度高優(yōu)先級的進程。,調(diào)度算法,反饋FB 對于被阻塞的進程，當阻塞取消后的處理方法： 進入低一級的就緒隊列 回到原就緒隊列 放入高一級的就緒隊列中,時間片的長短由如下四個因素決定： 系統(tǒng)的響應(yīng)時間 當進程數(shù)目一定時，時間片的長短直接影響系統(tǒng)的響應(yīng)時間 就緒隊列中進程的數(shù)目 當系統(tǒng)對響應(yīng)時間要求一定時，就緒隊列中進程數(shù)少則時間片長，反之亦然 進程狀態(tài)轉(zhuǎn)換 (即進程由就緒

20、態(tài)到運行，或反之) 的時間開銷 計算機本身的處理能力 執(zhí)行速度和可運行作業(yè)的道數(shù),調(diào)度算法,調(diào)度算法例題,現(xiàn)有5各進程，到達就緒隊列的時間和所需的服務(wù)時間如下表所示 求 ：FCFS, RR (q=1、4) , SPN, SRT, HRRN, FB(q=1、2i ),先來先服務(wù) (FCFS),調(diào)度算法例題,循環(huán) (RR) q = 1,調(diào)度算法例題,循環(huán) (RR) q = 4,調(diào)度算法例題,最短進程 Next (SPN),調(diào)度算法例題,最短剩余 時間 (SPT),調(diào)度算法例題,最高響應(yīng)比 (HRRN),調(diào)度算法例題,反饋(隊列有2個） q = 1,調(diào)度算法例題,反饋（采用剝奪方式） q = 2i,

21、調(diào)度算法例題,各種調(diào)度算法各有其特點，但分級輪轉(zhuǎn)法和反饋法較為理想 除了從就緒進程中選取一合理的進程投入運行外，進程調(diào)度程序還必須給該進程分配運行時間片 為了保證終端用戶提供服務(wù)請求之后，能及時得到響應(yīng)，一般規(guī)定的時間片在幾十毫秒到幾百毫秒之間不等,調(diào)度算法,可以有針對性地確定時間片的長短，讓運行時間長的進程在不太頻繁的時間間隔里獲得較大的時間片 讓經(jīng)常相互制約的進程有更多的機會獲得處理機，但每次獲得的時間片應(yīng)較短 系統(tǒng)優(yōu)先考慮那些短的、相互制約的進程，而要求時間片長的進程雖然不經(jīng)常運行，但其運行周期較長，能減少處理機分配所造成的開銷 進程調(diào)度算法有許多種，在具體實施中，是將幾種算法結(jié)合起來使

22、用，這樣效率更高,選擇調(diào)度策略,因等待 I/O而堵塞,運行,高優(yōu)先級 就緒,低優(yōu)先級 就緒,調(diào)度時的進程狀態(tài)變遷圖,分析其使用的調(diào)度策略與調(diào)度算法 分析這一調(diào)度策略的設(shè)計出發(fā)點,調(diào)度算法分析： 將就緒進程分成高和低優(yōu)先級兩個隊列。如果進程運行中超過了規(guī)定的時間片就進入低優(yōu)先級隊列，而I/O操作完成的進程，即由阻塞狀態(tài)進入高優(yōu)先級就緒隊列 調(diào)度算法是: 首先從高優(yōu)先就緒隊列中選擇一個進程來運行，如果在高優(yōu)先級就緒隊列中沒有進程，則從低優(yōu)先級就緒隊列中選擇一個進程運行,調(diào)度時的進程狀態(tài)圖,此算法對于要求 I/O 量大的就緒進程有利 (高優(yōu)先級) ，而對于那些計算量大的就緒進程不利 (未計算完畢就進

23、入低優(yōu)先級就緒隊列) 由于外部設(shè)備的運行速度大大低于主機的運行速度，所以為了保持I/O通道和設(shè)備處于忙碌狀態(tài)，受I/O限制的進程優(yōu)先于受CPU限制的進程運行。只有當所有的受I/O限制的進程全部被阻塞，才選取某個受CPU限制的低優(yōu)先級就緒進程在處理機上運行 對交互式用戶來說，這個策略提供了良好的響應(yīng)，也保持了I/O和中央處理機之間的高度并行,調(diào)度時的進程狀態(tài)圖,4 傳統(tǒng)的UNIX調(diào)度,傳統(tǒng)的UNIX調(diào)度的基本目標是分時交互環(huán)境 調(diào)度算法設(shè)計成為交互用戶提供好的響應(yīng)時間，同時保證低優(yōu)先級的后臺作業(yè)不會餓死。是分時調(diào)度算法的代表 傳統(tǒng)的UNIX調(diào)度程序在每個優(yōu)先級隊列中采用使用循環(huán)法的多級反饋。該系

24、統(tǒng)使用1秒剝奪，也就是說，如果一個正在運行的進程在1秒內(nèi)沒有阻塞或完成，它將被剝奪。優(yōu)先級基于進程類型和執(zhí)行歷史,4 傳統(tǒng)的UNIX調(diào)度,每秒都重新計算每個進程的優(yōu)先級，并進行一次新的調(diào)度決策 基本優(yōu)先級的目的是把所有的進程劃分成固定的優(yōu)先級。這些區(qū)用于優(yōu)化訪問塊設(shè)備 (如磁盤) 和允許操作系統(tǒng)迅速響應(yīng)系統(tǒng)調(diào)用 按優(yōu)先級的順序，這些區(qū)如下 交換程序 塊I/O設(shè)備控制 文件操作,字符I/O設(shè)備控制 用戶進程, 4 多處理器調(diào)度,當系統(tǒng)包含多個處理器時，在設(shè)計調(diào)度功能時就會產(chǎn)生一些新問題 多處理器系統(tǒng)可以劃分為以下幾類 松耦合、分布式多處理器、集群：由一組相對自治的系統(tǒng)組成，每個處理器有自己的主存

25、和I/O通道 專門功能的處理器：例如I/O處理器。在這種情況下，有一個通用的主處理器，專用處理器受主處理器的控制，并給主處理器提供服務(wù) 緊耦合多處理器：由一組共享同一個主存并在操作系統(tǒng)完全控制下的處理器組成 關(guān)注最后一類系統(tǒng)，特別是與調(diào)度有關(guān)的問題,粒度 刻畫多處理器的一種比較好的方法，是考慮系統(tǒng)中進程之間的同步粒度，或者說同步頻率 可以根據(jù)粒度區(qū)分5類并行度 獨立：多個無關(guān)進程 非常粗：在網(wǎng)絡(luò)節(jié)點上進行分布處理，以形成一個計算環(huán)境 粗：在多道程序環(huán)境中并發(fā)進程的多處理 中等：在一個應(yīng)用程序中的并行處理或多任務(wù)處理(線程) 細：指令流中固有的并行,4 多處理器調(diào)度,獨立并行度 進程間沒有顯式的

26、同步。每個進程都代表各自獨立的應(yīng)用或作業(yè)。這類并行度的一個典型應(yīng)用是分時系統(tǒng)。每個用戶都執(zhí)行一個特定的應(yīng)用，如字處理或使用電子表格。多處理器和多道程序單處理器一樣提供相同的服務(wù)。由于有多個處理器可用，因而用戶的平均響應(yīng)時間非常短 有可能達到這樣的性能：每個用戶都如同在使用個人計算機或工作站。如果任何一個文件或信息被共享，則單個系統(tǒng)必須連接在一個有網(wǎng)絡(luò)支持的分布式系統(tǒng)中 在許多實例中，多處理器共享系統(tǒng)比分布式系統(tǒng)的成本效益更合算，它允許節(jié)約使用磁盤和其他外圍設(shè)備,粒度,粗粒度和非常粗粒度的并行度 是指進程之間在一個非常粗的級別上存在著同步。這種情況可以簡單地處理成一組運行在多道程序單處理器上的并

27、發(fā)進程，在多處理器上對用戶軟件進行很少的改動或者不進行改動就可以提供支持 一般來說，使用多處理器體系結(jié)構(gòu)，對所有需要通信或同步的并發(fā)進程集合都有好處。當進程間存在非常頻繁的交互時，分布式系統(tǒng)可以提供好的支持。但是，當交互更加頻繁時，分布式系統(tǒng)中的網(wǎng)絡(luò)通信開銷會抵消一部分潛在的加速，在這種情況下，多處理器組織能提供最有效的支持,粒度,中等粒度的并行度 應(yīng)用程序可以作為進程中的一組線程被有效地實現(xiàn)。在這種情況下，可以由程序員顯式地指定應(yīng)用程序潛在的并行性。典型地，在應(yīng)用程序的線程之間，需要更高程度的合作與交互，從而導致中等粒度級的同步 盡管多處理器和多道程序單處理器都支持獨立、非常粗和粗粒度的并行

28、度，并對調(diào)度功能產(chǎn)生少許影響或沒有影響，但是在處理線程調(diào)度時，我們?nèi)匀恍枰匦路治稣{(diào)度。由于應(yīng)用程序中各個線程間的交互是如此地頻繁，關(guān)于線程調(diào)度的決策可能會影響整個應(yīng)用的性能,粒度,細粒度的并行度 代表著比線程中的并行更加復雜的使用。盡管在高度并行的應(yīng)用中已經(jīng)完成了大量的工作，迄今為止，這仍然是一個特殊的、被分割的領(lǐng)域,粒度,多處理器中的調(diào)度涉及到以下三個相關(guān)問題 把進程分配到處理器 在單個處理器上使用多道程序 一個進程的實際分派 在討論這三個問題時，必須記住所采用的方法通常取決于應(yīng)用程序的粒度等級和可用的處理器的數(shù)目,設(shè)計問題,把進程分配到處理器 假設(shè)多處理器結(jié)構(gòu)中各個處理器在訪問主存和I/

29、O設(shè)備時沒有特別優(yōu)勢，那么最簡單的調(diào)度方法是把處理器看作是一個資源池，并按照要求把進程分配到相應(yīng)的處理器。帶來的問題是：分配應(yīng)該是靜態(tài)的還是動態(tài)的,設(shè)計問題,靜態(tài)：一個進程從被激活到完成，被永久地分配到一個處理器，則需要為每個處理器維護一個專門的短程隊列。 其優(yōu)點是調(diào)度的開銷比較小，因為所有進程關(guān)于處理器的分配只進行一次 靜態(tài)分配的缺點是某個處理器可能空閑，這時它的隊列為空，而另一個處理器卻積壓了許多工作,設(shè)計問題,設(shè)計問題,動態(tài)：為防止靜態(tài)分配浪費CPU資源的情況，需要使用一個公共隊列。所有進程都進入一個全局隊列，然后調(diào)度到任何一個可用的處理器中。這樣，在一個進程的生命周期中，它可以在不同的

30、時間在不同的處理器上執(zhí)行,把進程分配到處理器處理器結(jié)構(gòu) 主從式結(jié)構(gòu)：操作系統(tǒng)的主要核心功能總是在某個特定的處理器上運行，其他處理器可能僅用于執(zhí)行用戶程序 主處理器負責調(diào)度作業(yè)。當一個進程被激活時，如果從處理器需要服務(wù) (例如一次I/O調(diào)用) ，它必須給主處理器發(fā)送一個請求，然后等待服務(wù)的執(zhí)行 這種方法簡單，由于處理器擁有對所有存儲器和I/O資源的控制，因而可以簡化沖突解決方案 缺點是: 主處理器的失敗導致整個系統(tǒng)失敗; 主處理器可能成為性能瓶頸,設(shè)計問題,把進程分配到處理器處理器結(jié)構(gòu) 對等式結(jié)構(gòu)：操作系統(tǒng)可以在任何一個處理器中執(zhí)行。每個處理器從可用進程池中進行自調(diào)度。這種方法增加了操作系統(tǒng)的復

31、雜性，必須確保兩個處理器不會選擇同一個進程，進程也不會從隊列中丟失 也可以提供一個處理器子集專門用于內(nèi)核處理，或者是基于優(yōu)先級和執(zhí)行歷史來管理內(nèi)核進程和其他進程之間的差別等,設(shè)計問題,在單個處理器上使用多道程序 傳統(tǒng)的多處理器處理是粗粒度或獨立同步粒度，顯然單個處理器能夠在許多進程間切換，以達到較高的使用率和更好的性能。 但是，對于運行在有許多處理器的多處理器系統(tǒng)中的中等粒度(線程)應(yīng)用程序，當多個處理器可用時，要求每個處理器盡可能地忙就不再那么重要了。相反，我們更加關(guān)注如何能為應(yīng)用提供最好的平均性能。,設(shè)計問題,進程分派 選擇哪一個進程運行？ 在多道程序單處理器上，與簡單的先來先服務(wù)策略相比

32、較，使用優(yōu)先級或者基于過去的使用歷史的高級調(diào)度算法可以提高性能 當考慮多處理器時，這些復雜性是不必要的，不然可能反而達不到預(yù)期的目標， 對于多處理器，相對比較簡單的方法會更有效，而且開銷也比較低。,設(shè)計問題,在大多數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進程并不是被指定到一個專門的處理器。不是所有處理器只有一個隊列 而是有多條基于優(yōu)先級的隊列，并且都送進相同的處理器池中。在任何情況下，我們都可以把系統(tǒng)看作是多服務(wù)器排隊結(jié)構(gòu) 對各種情況進行分析，對于多處理器，調(diào)度原則的選擇沒有在單處理器中顯得重要。因此，在多處理器系統(tǒng)中使用簡單的FCFS (先來先服務(wù)) 原則或者在靜態(tài)化先級方案中使用FCFS就足夠了,多處理器

33、進程調(diào)度,CPU,就緒隊列n,釋放,CPU,釋放,CPU,釋放,CPU,釋放,多處理器調(diào)度,就緒隊列3,就緒隊列2,就緒隊列1,分派,CPU池,在單處理器中，線程可以用作輔助構(gòu)造程序，并在處理過程中重疊執(zhí)行I/O。由于在進行線程切換時的性能損失遠遠小于進程切換的開銷，因此可以用很少的代價實現(xiàn)這些優(yōu)點 在多處理器系統(tǒng)中，線程的全部能力得到了更好的展現(xiàn)，線程可以用于開發(fā)應(yīng)用程序中真正的并行性。如果一個應(yīng)用程序的各個線程同時在各個獨立的處理器中執(zhí)行，其性能就會得到顯著的提高。,線程調(diào)度,在多處理器線程調(diào)度和處理器分配的各種方案中，比較突出的方法是： 負載分配：進程不是分配到一個特定的處理器，而是維護

34、一個就緒進程的全局隊列，每個處理器只要空閑就從隊列中選擇一個線程，負載平衡是基于一種比較永久的分配方案配工作的 成組調(diào)度：一組相關(guān)的線程基于一對一的原則，同時調(diào)度到一組處理器上運行 專用處理器分配：這種方法與負載分配的方法相反，它通過把線程指定到處理器來定義隱式的調(diào)度。在程序執(zhí)行過程中，每個程序被分配給一組處理器，處理器的數(shù)目與程序線程的數(shù)目相等。當程序終止時，處理器返回到總的處理器池中，可供分配給另一個程序 動態(tài)調(diào)度：在執(zhí)行期間，進程中線程的數(shù)目可以改變,線程調(diào)度,4 Windows 2000 調(diào)度,Windows 2000 的設(shè)計目標是在高度交互的環(huán)境中或者作為服務(wù)器盡可能地響應(yīng)單個用戶的

35、需求 Windows 2000 實現(xiàn)了剝奪式調(diào)度程序，它具有靈活的優(yōu)先級系統(tǒng)，在每一級上都包括了循環(huán)調(diào)度方法，在某些級上，優(yōu)先級可以基于它們當前的線程活動而動態(tài)變化,Windows 2000中的優(yōu)先級被組織成兩段 (兩類) ：實時和可變。每一段包括16種優(yōu)先級。需要立即關(guān)注的線程在實時類中，它包括諸如通信之類的功能和實時任務(wù) Windows 2000使用一種優(yōu)先級驅(qū)動的剝奪式調(diào)度程序，具有實時優(yōu)先級的線程優(yōu)先于其他線程 在單處理器中，當一個線程就緒時，如果它的優(yōu)先級高于當前正在執(zhí)行的線程，那么低優(yōu)先級的線程被剝奪，具有更高優(yōu)先級的進程占用處理器,進程和線程優(yōu)先級,兩類優(yōu)先級的處理方式有一定的不

36、同 在實時優(yōu)先級類中，所有線程具有固定的優(yōu)先級，并且它們的優(yōu)先級永遠不會改變，某一給定優(yōu)先級的所有活動線程在一個循環(huán)隊列中 在可變優(yōu)先級類中，一個線程的優(yōu)先級在開始時是最初指定的值，但在它的生命周期中可能會發(fā)生變化，上升或者下降。因此，在每個優(yōu)先級上都有一個FIFO隊列，一個進程可能在可變優(yōu)先級類中從一個隊列遷移到另一個隊列。但是，優(yōu)先級為15的線程不能升到16級，也就是說不能升到實時類的任何級中,進程和線程優(yōu)先級,最低 (0),最高 (15),最低 (16),最高 (31),實時優(yōu) 先級類,可變優(yōu) 先級類,Windows NT 線程調(diào)度優(yōu)先級,當Windows 2000運行在一個處理器上時，優(yōu)先級最高的線程總是活躍的，除非它正在等待一個事件 如果有多個線程具有最高的優(yōu)先級，則處理器在這一級的所有線程間被循環(huán)共享 在一個具有N個處理器的多處理器系統(tǒng)中，(N-1) 個最高優(yōu)先級的線程總是活躍的，在 (N-1) 個處理器上獨占運行。剩下的低優(yōu)先級線程共享剩下的一個處理器,多處理器調(diào)度,例題精選,假定要在一臺處理機上執(zhí)行右表作業(yè)，且假定這些作業(yè)同