OS-03中斷及處理機(jī)調(diào)度

1、 處理器調(diào)度的類型處理器調(diào)度的類型 調(diào)度算法調(diào)度算法 Linux進(jìn)程調(diào)度進(jìn)程調(diào)度 Windows 2000/xp線程調(diào)度線程調(diào)度 中斷：中斷：在進(jìn)程運(yùn)行過(guò)程中出現(xiàn)某種緊急情況，必在進(jìn)程運(yùn)行過(guò)程中出現(xiàn)某種緊急情況，必須中止當(dāng)前正在運(yùn)行的程序，轉(zhuǎn)去處理其它事件，須中止當(dāng)前正在運(yùn)行的程序，轉(zhuǎn)去處理其它事件，處理完畢后恢復(fù)原來(lái)程序的運(yùn)行。處理完畢后恢復(fù)原來(lái)程序的運(yùn)行。 中斷系統(tǒng)：中斷系統(tǒng)：中斷裝置中斷裝置+中斷處理程序中斷處理程序 中斷分類：中斷分類：內(nèi)中斷和外中斷；硬中斷和軟中斷；內(nèi)中斷和外中斷；硬中斷和軟中斷；可屏蔽中斷和不可屏蔽中斷；強(qiáng)迫性中斷和自愿可屏蔽中斷和不可屏蔽中斷；強(qiáng)迫性中斷和自愿性中

2、斷性中斷 P49-59 ：選擇性自學(xué)：選擇性自學(xué) 操作系統(tǒng)必須為多個(gè)進(jìn)程可能有競(jìng)爭(zhēng)的請(qǐng)求分配計(jì)算機(jī)資操作系統(tǒng)必須為多個(gè)進(jìn)程可能有競(jìng)爭(zhēng)的請(qǐng)求分配計(jì)算機(jī)資源。對(duì)處理器而言，可分配的資源是在處理器上的執(zhí)行時(shí)源。對(duì)處理器而言，可分配的資源是在處理器上的執(zhí)行時(shí)間，分配途徑是調(diào)度間，分配途徑是調(diào)度 處理器調(diào)度處理器調(diào)度：指采用合理的策略和方法在多個(gè)可運(yùn)行實(shí)體：指采用合理的策略和方法在多個(gè)可運(yùn)行實(shí)體間分配間分配CPU資源。資源。 處理器調(diào)度算法處理器調(diào)度算法：按照什么原則和方法分配處理器資源：按照什么原則和方法分配處理器資源 處理機(jī)調(diào)度必須設(shè)計(jì)成可以滿足多個(gè)目標(biāo)，例如公平、任處理機(jī)調(diào)度必須設(shè)計(jì)成可以滿足多個(gè)

3、目標(biāo)，例如公平、任何進(jìn)程都不會(huì)餓死、有效地使用處理器時(shí)間和低開(kāi)銷等何進(jìn)程都不會(huì)餓死、有效地使用處理器時(shí)間和低開(kāi)銷等 面向用戶準(zhǔn)則所關(guān)心的性能指標(biāo)面向用戶準(zhǔn)則所關(guān)心的性能指標(biāo) 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 T :指一個(gè)進(jìn)程從提交到完成之間的時(shí)間間隔，指一個(gè)進(jìn)程從提交到完成之間的時(shí)間間隔，包括實(shí)際執(zhí)行時(shí)間加上等待時(shí)間（等待包括實(shí)際執(zhí)行時(shí)間加上等待時(shí)間（等待+就緒）。就緒）。 帶權(quán)的周轉(zhuǎn)時(shí)間帶權(quán)的周轉(zhuǎn)時(shí)間 W：周轉(zhuǎn)時(shí)間與執(zhí)行時(shí)間的比值周轉(zhuǎn)時(shí)間與執(zhí)行時(shí)間的比值 響應(yīng)時(shí)間響應(yīng)時(shí)間 從提交一個(gè)請(qǐng)求到開(kāi)始處理的時(shí)間間隔。從提交一個(gè)請(qǐng)求到開(kāi)始處理的時(shí)間間隔。 最后期限最后期限 當(dāng)可以指定進(jìn)程完成的最后期限時(shí)，調(diào)度當(dāng)可以指

4、定進(jìn)程完成的最后期限時(shí)，調(diào)度原則將服從于其他目標(biāo)，使得距最后期限最近原則將服從于其他目標(biāo)，使得距最后期限最近 平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間： p61 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間： p61 面向面向系統(tǒng)準(zhǔn)則所關(guān)心的性能指標(biāo)系統(tǒng)準(zhǔn)則所關(guān)心的性能指標(biāo) 吞吐量吞吐量 單位時(shí)間內(nèi)完成的任務(wù)數(shù)。調(diào)度策略將試圖單位時(shí)間內(nèi)完成的任務(wù)數(shù)。調(diào)度策略將試圖使得每個(gè)時(shí)間單位完成的進(jìn)程數(shù)目最大。使得每個(gè)時(shí)間單位完成的進(jìn)程數(shù)目最大。 處理器使用率處理器使用率 處理器忙的時(shí)間百分比。盡量是處理器忙的時(shí)間百分比。盡量是CPU處于繁忙狀態(tài)。處于繁忙狀態(tài)。 公平公平 進(jìn)程應(yīng)該被平等對(duì)待，沒(méi)有一個(gè)進(jìn)程會(huì)被餓死進(jìn)程應(yīng)該被平等對(duì)待

5、，沒(méi)有一個(gè)進(jìn)程會(huì)被餓死 強(qiáng)制優(yōu)先級(jí)強(qiáng)制優(yōu)先級(jí) 當(dāng)進(jìn)程被指定了優(yōu)先級(jí)，調(diào)度策略會(huì)先當(dāng)進(jìn)程被指定了優(yōu)先級(jí)，調(diào)度策略會(huì)先選擇高優(yōu)先級(jí)的進(jìn)程選擇高優(yōu)先級(jí)的進(jìn)程 平衡資源平衡資源 保持系統(tǒng)中所有資源忙。這個(gè)準(zhǔn)則也可用保持系統(tǒng)中所有資源忙。這個(gè)準(zhǔn)則也可用于中程調(diào)度和長(zhǎng)程調(diào)度于中程調(diào)度和長(zhǎng)程調(diào)度多道程序的關(guān)鍵是調(diào)度。典型的調(diào)度類型有：多道程序的關(guān)鍵是調(diào)度。典型的調(diào)度類型有： 長(zhǎng)程調(diào)度長(zhǎng)程調(diào)度( (作業(yè)調(diào)度作業(yè)調(diào)度, ,高級(jí)調(diào)度）決定加入到待高級(jí)調(diào)度）決定加入到待執(zhí)行的進(jìn)程池中執(zhí)行的進(jìn)程池中 中程調(diào)度中程調(diào)度（交換調(diào)度（交換調(diào)度, ,中級(jí)調(diào)度）將進(jìn)程調(diào)入內(nèi)中級(jí)調(diào)度）將進(jìn)程調(diào)入內(nèi)存存, ,或者將進(jìn)程交換到硬盤或

6、者將進(jìn)程交換到硬盤 短程調(diào)度短程調(diào)度（進(jìn)程調(diào)度，低級(jí)調(diào)度）決定哪一個(gè)（進(jìn)程調(diào)度，低級(jí)調(diào)度）決定哪一個(gè)就緒進(jìn)程將被處理器執(zhí)行就緒進(jìn)程將被處理器執(zhí)行 線程調(diào)度線程調(diào)度：決定哪一個(gè)線程被處理器執(zhí)行：決定哪一個(gè)線程被處理器執(zhí)行下一次允許哪一個(gè)進(jìn)程進(jìn)入的下一次允許哪一個(gè)進(jìn)程進(jìn)入的決策決策可以基于簡(jiǎn)單可以基于簡(jiǎn)單的先來(lái)先服務(wù)原則，或者也可以基于管理系統(tǒng)性的先來(lái)先服務(wù)原則，或者也可以基于管理系統(tǒng)性能的工具能的工具使用的原則包括優(yōu)先級(jí)、期待執(zhí)行時(shí)間和使用的原則包括優(yōu)先級(jí)、期待執(zhí)行時(shí)間和I/O需求需求同樣，可以根據(jù)請(qǐng)求哪個(gè)同樣，可以根據(jù)請(qǐng)求哪個(gè)I/O資源和試圖平衡資源和試圖平衡I/O使用的目的進(jìn)行決策使用的目的

7、進(jìn)行決策中程調(diào)度的目標(biāo)有中程調(diào)度的目標(biāo)有2個(gè)：個(gè)：解決內(nèi)存資源緊張的矛盾解決內(nèi)存資源緊張的矛盾減小并發(fā)度以降低系統(tǒng)開(kāi)銷減小并發(fā)度以降低系統(tǒng)開(kāi)銷 中程調(diào)度算法將結(jié)合存儲(chǔ)管理來(lái)設(shè)計(jì)。中程調(diào)度算法將結(jié)合存儲(chǔ)管理來(lái)設(shè)計(jì)。從執(zhí)行的頻率看從執(zhí)行的頻率看 長(zhǎng)程調(diào)度程序的執(zhí)行頻率相對(duì)低些，并且僅僅是長(zhǎng)程調(diào)度程序的執(zhí)行頻率相對(duì)低些，并且僅僅是粗略地決定是否接受新進(jìn)程以及接受哪一個(gè)粗略地決定是否接受新進(jìn)程以及接受哪一個(gè) 為進(jìn)行交換決策，中程調(diào)度程序執(zhí)行得略微頻繁為進(jìn)行交換決策，中程調(diào)度程序執(zhí)行得略微頻繁一些一些 短程調(diào)度程序，即分派程序執(zhí)行得最頻繁，并且短程調(diào)度程序，即分派程序執(zhí)行得最頻繁，并且精確地決定下一次執(zhí)

8、行哪一個(gè)進(jìn)程精確地決定下一次執(zhí)行哪一個(gè)進(jìn)程根據(jù)已占有處理機(jī)的進(jìn)程是否可被剝奪這一原則，根據(jù)已占有處理機(jī)的進(jìn)程是否可被剝奪這一原則，調(diào)度方式（策略）可分為：調(diào)度方式（策略）可分為： 非剝奪方式：非剝奪方式：一旦某個(gè)就緒進(jìn)程分得處理機(jī)之后，一旦某個(gè)就緒進(jìn)程分得處理機(jī)之后，只要不是其自身的原因被阻塞只要不是其自身的原因被阻塞 ( (如要求如要求I/OI/O操作操作) ) 而不能繼續(xù)運(yùn)行時(shí)，就一直運(yùn)行下去，直至運(yùn)行而不能繼續(xù)運(yùn)行時(shí)，就一直運(yùn)行下去，直至運(yùn)行結(jié)束結(jié)束 缺點(diǎn)：緊急進(jìn)程無(wú)法立即運(yùn)行，實(shí)時(shí)性差；缺點(diǎn)：緊急進(jìn)程無(wú)法立即運(yùn)行，實(shí)時(shí)性差； 短進(jìn)程周轉(zhuǎn)時(shí)間長(zhǎng)，公平性差。短進(jìn)程周轉(zhuǎn)時(shí)間長(zhǎng)，公平性差。 剝

9、奪方式：剝奪方式：當(dāng)一個(gè)正在運(yùn)行的進(jìn)程沒(méi)有運(yùn)行完時(shí)，當(dāng)一個(gè)正在運(yùn)行的進(jìn)程沒(méi)有運(yùn)行完時(shí)，系統(tǒng)采取某種手段強(qiáng)行剝奪已分配給該進(jìn)程的處理系統(tǒng)采取某種手段強(qiáng)行剝奪已分配給該進(jìn)程的處理器資源。而被剝奪的進(jìn)程重新回到就緒隊(duì)列中等待器資源。而被剝奪的進(jìn)程重新回到就緒隊(duì)列中等待 在剝奪方式下，可以通過(guò)剝奪處理器所有權(quán)的方式，在剝奪方式下，可以通過(guò)剝奪處理器所有權(quán)的方式，暫停當(dāng)前進(jìn)程的運(yùn)行，已滿足更緊急進(jìn)程的處理要暫停當(dāng)前進(jìn)程的運(yùn)行，已滿足更緊急進(jìn)程的處理要求。求。v 有三個(gè)進(jìn)程有三個(gè)進(jìn)程p1，p2，p3到達(dá)時(shí)間為：到達(dá)時(shí)間為：0，3，4，優(yōu)先級(jí)依，優(yōu)先級(jí)依次增高，運(yùn)行所需的時(shí)間分別為次增高，運(yùn)行所需的時(shí)間分別

10、為20，4，2，假設(shè)現(xiàn)按優(yōu)先，假設(shè)現(xiàn)按優(yōu)先級(jí)策略調(diào)度執(zhí)行，并且不采用時(shí)間片原則，請(qǐng)分別求出非級(jí)策略調(diào)度執(zhí)行，并且不采用時(shí)間片原則，請(qǐng)分別求出非剝奪方式和剝奪方式下各個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間。剝奪方式和剝奪方式下各個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間。最短進(jìn)程最短進(jìn)程SPN（短進(jìn)程優(yōu)先調(diào)度算法）（短進(jìn)程優(yōu)先調(diào)度算法） 減少減少FCFSFCFS固有的對(duì)長(zhǎng)進(jìn)程的偏愛(ài)的另一種方法是固有的對(duì)長(zhǎng)進(jìn)程的偏愛(ài)的另一種方法是最短進(jìn)程最短進(jìn)程 (SPN) (SPN) 策略，策略，這是一種非剝奪的策略這是一種非剝奪的策略，其原則是下一次選擇所需處理時(shí)間最短的進(jìn)程，其原則是下一次選擇所需處理時(shí)間最短的進(jìn)程，因此，短進(jìn)程將會(huì)越過(guò)長(zhǎng)進(jìn)程，得到優(yōu)先運(yùn)

11、行因此，短進(jìn)程將會(huì)越過(guò)長(zhǎng)進(jìn)程，得到優(yōu)先運(yùn)行 SPNSPN策略的難點(diǎn)在于需要知道或至少需要估計(jì)每策略的難點(diǎn)在于需要知道或至少需要估計(jì)每個(gè)進(jìn)程所需要的處理時(shí)間個(gè)進(jìn)程所需要的處理時(shí)間 長(zhǎng)進(jìn)程可能被長(zhǎng)進(jìn)程可能被“餓死餓死”最短剩余時(shí)間優(yōu)先調(diào)度算法最短剩余時(shí)間優(yōu)先調(diào)度算法 (SRTN) 對(duì)對(duì)SPNSPN增加剝奪機(jī)制。當(dāng)一個(gè)時(shí)鐘中斷周期到后，增加剝奪機(jī)制。當(dāng)一個(gè)時(shí)鐘中斷周期到后，調(diào)度程序總是調(diào)度程序總是選擇預(yù)期剩余時(shí)間最短選擇預(yù)期剩余時(shí)間最短的進(jìn)程的進(jìn)程 當(dāng)一個(gè)新進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)當(dāng)一個(gè)新進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間，因此，調(diào)度程序行的進(jìn)程具有更短的剩余時(shí)間

12、，因此，調(diào)度程序?qū)儕Z當(dāng)前程序，將處理器分配給新進(jìn)程。將剝奪當(dāng)前程序，將處理器分配給新進(jìn)程。 和和SPNSPN一樣，調(diào)度程序必須有關(guān)于處理時(shí)間的估一樣，調(diào)度程序必須有關(guān)于處理時(shí)間的估計(jì)，并且存在長(zhǎng)進(jìn)程被餓死的危險(xiǎn)計(jì)，并且存在長(zhǎng)進(jìn)程被餓死的危險(xiǎn)最高響應(yīng)比優(yōu)先調(diào)度算法（最高響應(yīng)比優(yōu)先調(diào)度算法（HRRN） 響應(yīng)比：響應(yīng)比： R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s w w表示等待時(shí)間；表示等待時(shí)間；s s表示執(zhí)行所需時(shí)間表示執(zhí)行所需時(shí)間 最高響應(yīng)比也是對(duì)最短進(jìn)程法的一種改進(jìn)，當(dāng)當(dāng)最高響應(yīng)比也是對(duì)最短進(jìn)程法的一種改進(jìn)，當(dāng)當(dāng)前進(jìn)程完成或被阻塞時(shí)，前進(jìn)程完成或被阻塞時(shí)，選擇響應(yīng)比最大的

13、進(jìn)程選擇響應(yīng)比最大的進(jìn)程先執(zhí)行先執(zhí)行，是一種，是一種非剝奪非剝奪的策略。的策略。 響應(yīng)比響應(yīng)比R R，代表了進(jìn)程的年齡，算法在保證短進(jìn)，代表了進(jìn)程的年齡，算法在保證短進(jìn)程優(yōu)先的同時(shí)又兼顧了長(zhǎng)進(jìn)程程優(yōu)先的同時(shí)又兼顧了長(zhǎng)進(jìn)程折中折中最高響應(yīng)比優(yōu)先調(diào)度算法（最高響應(yīng)比優(yōu)先調(diào)度算法（HRRN） R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s 當(dāng)一系列進(jìn)程同時(shí)進(jìn)入系統(tǒng)時(shí)，由于短作業(yè)當(dāng)一系列進(jìn)程同時(shí)進(jìn)入系統(tǒng)時(shí)，由于短作業(yè)s s值值小，小，R R值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。 但隨著長(zhǎng)作業(yè)等待的時(shí)間但隨著長(zhǎng)作業(yè)等待的時(shí)間(w)(w)增長(zhǎng)，增長(zhǎng)，R R值不斷

14、增大，值不斷增大，到達(dá)一定的等待時(shí)間，長(zhǎng)進(jìn)程最終將憑借年齡的到達(dá)一定的等待時(shí)間，長(zhǎng)進(jìn)程最終將憑借年齡的增長(zhǎng)戰(zhàn)勝短進(jìn)程，從而獲得處理器。增長(zhǎng)戰(zhàn)勝短進(jìn)程，從而獲得處理器。 可見(jiàn)，在可見(jiàn)，在HRRNHRRN算法中，長(zhǎng)作業(yè)不會(huì)被餓死算法中，長(zhǎng)作業(yè)不會(huì)被餓死 優(yōu)先級(jí)調(diào)度算法：按進(jìn)程的優(yōu)先級(jí)調(diào)度，選擇就緒優(yōu)先級(jí)調(diào)度算法：按進(jìn)程的優(yōu)先級(jí)調(diào)度，選擇就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程到處理機(jī)上運(yùn)行。隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程到處理機(jī)上運(yùn)行。優(yōu)先數(shù)確定方式：優(yōu)先數(shù)確定方式： 靜態(tài)優(yōu)先級(jí)：每個(gè)進(jìn)程創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)靜態(tài)優(yōu)先級(jí)：每個(gè)進(jìn)程創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)先數(shù)在進(jìn)程整個(gè)生命周期都是固定不變的。先數(shù)在進(jìn)程整個(gè)生命

15、周期都是固定不變的。 動(dòng)態(tài)優(yōu)先級(jí)：每個(gè)進(jìn)程被創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該動(dòng)態(tài)優(yōu)先級(jí)：每個(gè)進(jìn)程被創(chuàng)建時(shí)被賦予一個(gè)優(yōu)先數(shù)，該優(yōu)先數(shù)在進(jìn)程的生命周期內(nèi)是可以動(dòng)態(tài)變化的優(yōu)先數(shù)在進(jìn)程的生命周期內(nèi)是可以動(dòng)態(tài)變化的 大多數(shù)動(dòng)態(tài)優(yōu)先級(jí)設(shè)計(jì)方案大多數(shù)動(dòng)態(tài)優(yōu)先級(jí)設(shè)計(jì)方案 把交互式和把交互式和I/OI/O頻繁的進(jìn)程移到優(yōu)先級(jí)隊(duì)列的頂端，而頻繁的進(jìn)程移到優(yōu)先級(jí)隊(duì)列的頂端，而讓計(jì)算量大的進(jìn)程移到較低的優(yōu)先級(jí)上讓計(jì)算量大的進(jìn)程移到較低的優(yōu)先級(jí)上 對(duì)與優(yōu)先級(jí)相同的進(jìn)程，按先來(lái)先服務(wù)或輪轉(zhuǎn)法則分對(duì)與優(yōu)先級(jí)相同的進(jìn)程，按先來(lái)先服務(wù)或輪轉(zhuǎn)法則分配處理機(jī)配處理機(jī) 對(duì)于一給定時(shí)間周期，一個(gè)正在運(yùn)行的進(jìn)程，每請(qǐng)求對(duì)于一給定時(shí)間周期，一個(gè)

16、正在運(yùn)行的進(jìn)程，每請(qǐng)求一次一次I/OI/O操作后其優(yōu)先級(jí)就自動(dòng)加操作后其優(yōu)先級(jí)就自動(dòng)加 1 1，直接反映出，直接反映出I/OI/O請(qǐng)求的頻率，從而使請(qǐng)求的頻率，從而使I/OI/O設(shè)備具有很高的利用率設(shè)備具有很高的利用率優(yōu)先級(jí)調(diào)度算法分類：優(yōu)先級(jí)調(diào)度算法分類： 非搶占的優(yōu)先級(jí)調(diào)度法非搶占的優(yōu)先級(jí)調(diào)度法：一旦一個(gè)高優(yōu)先級(jí)的進(jìn)程占有：一旦一個(gè)高優(yōu)先級(jí)的進(jìn)程占有了處理器，就一直運(yùn)行下去，直到因等待某事被阻塞或了處理器，就一直運(yùn)行下去，直到因等待某事被阻塞或執(zhí)行結(jié)束，才選擇就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程來(lái)執(zhí)行。執(zhí)行結(jié)束，才選擇就緒隊(duì)列中優(yōu)先級(jí)最高的進(jìn)程來(lái)執(zhí)行。 可搶占的優(yōu)先級(jí)調(diào)度法可搶占的優(yōu)先級(jí)調(diào)度法：任何

17、時(shí)刻都按照高優(yōu)先級(jí)進(jìn)程：任何時(shí)刻都按照高優(yōu)先級(jí)進(jìn)程在處理器上運(yùn)行的原則進(jìn)行進(jìn)程調(diào)度。當(dāng)一高優(yōu)先級(jí)進(jìn)在處理器上運(yùn)行的原則進(jìn)行進(jìn)程調(diào)度。當(dāng)一高優(yōu)先級(jí)進(jìn)程運(yùn)行時(shí)，若有一更高優(yōu)先級(jí)進(jìn)程到達(dá)就緒隊(duì)列，則當(dāng)程運(yùn)行時(shí)，若有一更高優(yōu)先級(jí)進(jìn)程到達(dá)就緒隊(duì)列，則當(dāng)前運(yùn)行進(jìn)程立刻將處理器讓給更高優(yōu)先級(jí)的進(jìn)程（即使前運(yùn)行進(jìn)程立刻將處理器讓給更高優(yōu)先級(jí)的進(jìn)程（即使未處理完，也無(wú)遇到阻塞情況）未處理完，也無(wú)遇到阻塞情況） 可搶占CPU Process Arrival time Priority Burst time P1 0 0 8 P2 2 1 5 P3 4 3 7 P4 0 2 3 P5 5 7 2 Gantt Cha

18、rt0 0 3 3 4 4 5 5 7 7 13 17 2513 17 25P1P4P2P2P3P3P50 0 3 3 4 4 5 5 7 7 13 17 2513 17 25P1P4P2P2P3P3P5輪轉(zhuǎn)調(diào)度輪轉(zhuǎn)調(diào)度 簡(jiǎn)單輪轉(zhuǎn)法是以就緒隊(duì)列中的所有進(jìn)程均以相同的速簡(jiǎn)單輪轉(zhuǎn)法是以就緒隊(duì)列中的所有進(jìn)程均以相同的速度往前推進(jìn)為其特征。其時(shí)間片的長(zhǎng)短，影響著進(jìn)程度往前推進(jìn)為其特征。其時(shí)間片的長(zhǎng)短，影響著進(jìn)程的進(jìn)展速度的進(jìn)展速度 當(dāng)就緒進(jìn)程很多時(shí)，如果時(shí)間片很長(zhǎng)，就會(huì)影響一些當(dāng)就緒進(jìn)程很多時(shí)，如果時(shí)間片很長(zhǎng)，就會(huì)影響一些需要需要“緊急緊急”運(yùn)行的作業(yè)。同樣這對(duì)短作業(yè)和要求運(yùn)行的作業(yè)。同樣這對(duì)短作業(yè)和

19、要求 I/O 操作多的作業(yè)顯然是不利的操作多的作業(yè)顯然是不利的 因而，在簡(jiǎn)單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級(jí)輪轉(zhuǎn)法因而，在簡(jiǎn)單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級(jí)輪轉(zhuǎn)法分級(jí)輪轉(zhuǎn)法分級(jí)輪轉(zhuǎn)法 將一個(gè)就緒隊(duì)列根據(jù)進(jìn)程的優(yōu)先級(jí)不同，劃分二將一個(gè)就緒隊(duì)列根據(jù)進(jìn)程的優(yōu)先級(jí)不同，劃分二個(gè)或二個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同個(gè)或二個(gè)以上的就緒隊(duì)列，并賦給每個(gè)隊(duì)列不同的優(yōu)先級(jí)，甚至可以分配不同的時(shí)間片的優(yōu)先級(jí)，甚至可以分配不同的時(shí)間片 一般情況下，調(diào)度算法把相同的時(shí)間片分配給優(yōu)一般情況下，調(diào)度算法把相同的時(shí)間片分配給優(yōu)先級(jí)高的就緒隊(duì)列中的隊(duì)首進(jìn)程先級(jí)高的就緒隊(duì)列中的隊(duì)首進(jìn)程 只有當(dāng)優(yōu)先級(jí)高的就緒隊(duì)列中的所有進(jìn)程全部運(yùn)只有

20、當(dāng)優(yōu)先級(jí)高的就緒隊(duì)列中的所有進(jìn)程全部運(yùn)行完畢或等待行完畢或等待I/OI/O操作而沒(méi)有進(jìn)程運(yùn)行時(shí)，才把操作而沒(méi)有進(jìn)程運(yùn)行時(shí)，才把處理機(jī)分配給低優(yōu)先級(jí)就緒隊(duì)列中的進(jìn)程處理機(jī)分配給低優(yōu)先級(jí)就緒隊(duì)列中的進(jìn)程分級(jí)輪轉(zhuǎn)法分級(jí)輪轉(zhuǎn)法 為了公平性，低優(yōu)先級(jí)就緒隊(duì)列的進(jìn)程如果獲為了公平性，低優(yōu)先級(jí)就緒隊(duì)列的進(jìn)程如果獲得調(diào)度，將得到比高優(yōu)先級(jí)就緒隊(duì)列進(jìn)程更多得調(diào)度，將得到比高優(yōu)先級(jí)就緒隊(duì)列進(jìn)程更多的時(shí)間片，加以彌補(bǔ)的時(shí)間片，加以彌補(bǔ) 這樣能大大降低長(zhǎng)作業(yè)的交換頻率，減少系統(tǒng)這樣能大大降低長(zhǎng)作業(yè)的交換頻率，減少系統(tǒng)在交換作業(yè)時(shí)的時(shí)間消耗，又給了短作業(yè)較高在交換作業(yè)時(shí)的時(shí)間消耗，又給了短作業(yè)較高的優(yōu)先級(jí)的優(yōu)先級(jí)反饋反

21、饋FB（多級(jí)反饋隊(duì)列調(diào)度算法）（多級(jí)反饋隊(duì)列調(diào)度算法） 分級(jí)輪轉(zhuǎn)調(diào)度和動(dòng)態(tài)優(yōu)先級(jí)算法的結(jié)合，分級(jí)輪轉(zhuǎn)調(diào)度和動(dòng)態(tài)優(yōu)先級(jí)算法的結(jié)合，采用剝奪策略采用剝奪策略 劃分多個(gè)就緒隊(duì)列，優(yōu)先級(jí)逐步降低。劃分多個(gè)就緒隊(duì)列，優(yōu)先級(jí)逐步降低。 新建進(jìn)程進(jìn)入優(yōu)先級(jí)最高的隊(duì)列中，每當(dāng)進(jìn)程規(guī)定的時(shí)新建進(jìn)程進(jìn)入優(yōu)先級(jí)最高的隊(duì)列中，每當(dāng)進(jìn)程規(guī)定的時(shí)間片用完，被剝奪時(shí)，就送往低一級(jí)的就緒隊(duì)列。間片用完，被剝奪時(shí)，就送往低一級(jí)的就緒隊(duì)列。 進(jìn)程調(diào)度時(shí)總是先執(zhí)行高優(yōu)先級(jí)隊(duì)列中的進(jìn)程。高優(yōu)先進(jìn)程調(diào)度時(shí)總是先執(zhí)行高優(yōu)先級(jí)隊(duì)列中的進(jìn)程。高優(yōu)先級(jí)隊(duì)列為空后，才轉(zhuǎn)去處理低一級(jí)優(yōu)先級(jí)隊(duì)列中的進(jìn)程。級(jí)隊(duì)列為空后，才轉(zhuǎn)去處理低一級(jí)優(yōu)先級(jí)隊(duì)列中的

22、進(jìn)程。 同一優(yōu)先級(jí)隊(duì)列（除最低）的進(jìn)程，按同一優(yōu)先級(jí)隊(duì)列（除最低）的進(jìn)程，按FIFOFIFO機(jī)制調(diào)度。機(jī)制調(diào)度。最低優(yōu)先級(jí)隊(duì)列，按時(shí)間片輪轉(zhuǎn)調(diào)度算法執(zhí)行最低優(yōu)先級(jí)隊(duì)列，按時(shí)間片輪轉(zhuǎn)調(diào)度算法執(zhí)行反饋反饋FB 在反饋調(diào)度算法中，長(zhǎng)進(jìn)程也存在餓死的現(xiàn)象在反饋調(diào)度算法中，長(zhǎng)進(jìn)程也存在餓死的現(xiàn)象 當(dāng)比運(yùn)行進(jìn)程更高優(yōu)先級(jí)隊(duì)列到來(lái)一個(gè)新進(jìn)程時(shí)，則當(dāng)比運(yùn)行進(jìn)程更高優(yōu)先級(jí)隊(duì)列到來(lái)一個(gè)新進(jìn)程時(shí)，則應(yīng)該處理高優(yōu)先級(jí)隊(duì)列的進(jìn)程。有兩種方案：應(yīng)該處理高優(yōu)先級(jí)隊(duì)列的進(jìn)程。有兩種方案： 搶占方式：即當(dāng)高優(yōu)先級(jí)進(jìn)程到來(lái)時(shí)，立即搶占處搶占方式：即當(dāng)高優(yōu)先級(jí)進(jìn)程到來(lái)時(shí)，立即搶占處理進(jìn)程的處理器，被搶占進(jìn)程回到原來(lái)就緒隊(duì)列的理進(jìn)程

23、的處理器，被搶占進(jìn)程回到原來(lái)就緒隊(duì)列的末尾。（末尾。（沒(méi)有特殊說(shuō)明時(shí)，認(rèn)為是搶占方式） 非搶占方式：當(dāng)前進(jìn)程用完規(guī)定的時(shí)間片后，再調(diào)非搶占方式：當(dāng)前進(jìn)程用完規(guī)定的時(shí)間片后，再調(diào)度高優(yōu)先級(jí)的進(jìn)程。度高優(yōu)先級(jí)的進(jìn)程。反饋反饋FB 對(duì)于被阻塞的進(jìn)程，當(dāng)阻塞取消后的處理方法：對(duì)于被阻塞的進(jìn)程，當(dāng)阻塞取消后的處理方法： 進(jìn)入低一級(jí)的就緒隊(duì)列進(jìn)入低一級(jí)的就緒隊(duì)列 回到原就緒隊(duì)列回到原就緒隊(duì)列 放入高一級(jí)的就緒隊(duì)列中放入高一級(jí)的就緒隊(duì)列中 進(jìn)入最高級(jí)的就緒隊(duì)列進(jìn)入最高級(jí)的就緒隊(duì)列 時(shí)間片的長(zhǎng)短由如下四個(gè)因素決定：時(shí)間片的長(zhǎng)短由如下四個(gè)因素決定： 系統(tǒng)的響應(yīng)時(shí)間系統(tǒng)的響應(yīng)時(shí)間 當(dāng)進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長(zhǎng)短直

24、當(dāng)進(jìn)程數(shù)目一定時(shí)，時(shí)間片的長(zhǎng)短直接影響系統(tǒng)的響應(yīng)時(shí)間接影響系統(tǒng)的響應(yīng)時(shí)間 就緒隊(duì)列中進(jìn)程的數(shù)目就緒隊(duì)列中進(jìn)程的數(shù)目 當(dāng)系統(tǒng)對(duì)響應(yīng)時(shí)間要求一定時(shí)，當(dāng)系統(tǒng)對(duì)響應(yīng)時(shí)間要求一定時(shí)，就緒隊(duì)列中進(jìn)程數(shù)少則時(shí)間片長(zhǎng)，反之亦然就緒隊(duì)列中進(jìn)程數(shù)少則時(shí)間片長(zhǎng)，反之亦然 進(jìn)程狀態(tài)轉(zhuǎn)換進(jìn)程狀態(tài)轉(zhuǎn)換 (即進(jìn)程由就緒態(tài)到運(yùn)行，或反之即進(jìn)程由就緒態(tài)到運(yùn)行，或反之) 的時(shí)間的時(shí)間開(kāi)銷開(kāi)銷 計(jì)算機(jī)本身的處理能力計(jì)算機(jī)本身的處理能力 執(zhí)行速度和可運(yùn)行作業(yè)的道數(shù)執(zhí)行速度和可運(yùn)行作業(yè)的道數(shù)v現(xiàn)有現(xiàn)有5各進(jìn)程，到達(dá)就緒隊(duì)列的時(shí)間和所需的服各進(jìn)程，到達(dá)就緒隊(duì)列的時(shí)間和所需的服務(wù)時(shí)間如下表所示務(wù)時(shí)間如下表所示 求求 ：FCFS, RR (

25、q=1、4) , SPN, SRTN, HRRN, FB(q=1、2i )進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213

26、141516171819ABCDE012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012

27、345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABC

28、DE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82012345678910111213141516171819ABCDE進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間A03B26C44D65E82各種調(diào)度算法各有其特點(diǎn)，但分級(jí)輪轉(zhuǎn)法和反饋各種調(diào)度算法各有其特點(diǎn)，但分級(jí)輪轉(zhuǎn)法和反饋法較為理想法較為理想除

29、了從就緒進(jìn)程中選取一合理的進(jìn)程投入運(yùn)行外，除了從就緒進(jìn)程中選取一合理的進(jìn)程投入運(yùn)行外，進(jìn)程調(diào)度程序還必須給該進(jìn)程分配運(yùn)行時(shí)間片進(jìn)程調(diào)度程序還必須給該進(jìn)程分配運(yùn)行時(shí)間片為了保證終端用戶提供服務(wù)請(qǐng)求之后，能及時(shí)得為了保證終端用戶提供服務(wù)請(qǐng)求之后，能及時(shí)得到響應(yīng)，一般規(guī)定的時(shí)間片在幾十毫秒到幾百毫到響應(yīng)，一般規(guī)定的時(shí)間片在幾十毫秒到幾百毫秒之間不等秒之間不等調(diào)度算法分析：調(diào)度算法分析： 將就緒進(jìn)程分成高和低優(yōu)先級(jí)兩個(gè)隊(duì)列。如果進(jìn)將就緒進(jìn)程分成高和低優(yōu)先級(jí)兩個(gè)隊(duì)列。如果進(jìn)程運(yùn)行中超過(guò)了規(guī)定的時(shí)間片就進(jìn)入低優(yōu)先級(jí)隊(duì)程運(yùn)行中超過(guò)了規(guī)定的時(shí)間片就進(jìn)入低優(yōu)先級(jí)隊(duì)列，而列，而I/OI/O操作完成的進(jìn)程，即由阻塞

30、狀態(tài)進(jìn)入操作完成的進(jìn)程，即由阻塞狀態(tài)進(jìn)入高優(yōu)先級(jí)就緒隊(duì)列高優(yōu)先級(jí)就緒隊(duì)列 調(diào)度算法是調(diào)度算法是: : 首先從高優(yōu)先就緒隊(duì)列中選擇一個(gè)首先從高優(yōu)先就緒隊(duì)列中選擇一個(gè)進(jìn)程來(lái)運(yùn)行，如果在高優(yōu)先級(jí)就緒隊(duì)列中沒(méi)有進(jìn)進(jìn)程來(lái)運(yùn)行，如果在高優(yōu)先級(jí)就緒隊(duì)列中沒(méi)有進(jìn)程，則從低優(yōu)先級(jí)就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行程，則從低優(yōu)先級(jí)就緒隊(duì)列中選擇一個(gè)進(jìn)程運(yùn)行 此算法此算法對(duì)于要求對(duì)于要求 I/O 量大的就緒進(jìn)程有利量大的就緒進(jìn)程有利 (高優(yōu)先級(jí)高優(yōu)先級(jí)) ，而對(duì)，而對(duì)于那些于那些計(jì)算量大的就緒進(jìn)程不利計(jì)算量大的就緒進(jìn)程不利 (未計(jì)算完畢就進(jìn)入低優(yōu)先未計(jì)算完畢就進(jìn)入低優(yōu)先級(jí)就緒隊(duì)列級(jí)就緒隊(duì)列) 由于外部設(shè)備的運(yùn)行速度大大低于

31、主機(jī)的運(yùn)行速度，所以為由于外部設(shè)備的運(yùn)行速度大大低于主機(jī)的運(yùn)行速度，所以為了保持了保持I/O通道和設(shè)備處于忙碌狀態(tài)，受通道和設(shè)備處于忙碌狀態(tài)，受I/O限制的進(jìn)程優(yōu)先限制的進(jìn)程優(yōu)先于受于受CPU限制的進(jìn)程運(yùn)行。只有當(dāng)所有的受限制的進(jìn)程運(yùn)行。只有當(dāng)所有的受I/O限制的進(jìn)程限制的進(jìn)程全部被阻塞，才選取某個(gè)受全部被阻塞，才選取某個(gè)受CPU限制的低優(yōu)先級(jí)就緒進(jìn)程在限制的低優(yōu)先級(jí)就緒進(jìn)程在處理機(jī)上運(yùn)行處理機(jī)上運(yùn)行 對(duì)交互式用戶來(lái)說(shuō)，對(duì)交互式用戶來(lái)說(shuō)，這個(gè)策略提供了良好的響應(yīng)這個(gè)策略提供了良好的響應(yīng)，也保持了，也保持了I/O和中央處理機(jī)之間的高度并行和中央處理機(jī)之間的高度并行 傳統(tǒng)的UNIX調(diào)度的基本目標(biāo)是

32、分時(shí)交互環(huán)境 調(diào)度算法設(shè)計(jì)成為交互用戶提供好的響應(yīng)時(shí)間，同時(shí)保證低優(yōu)先級(jí)的后臺(tái)作業(yè)不會(huì)餓死。是分時(shí)調(diào)度算法的代表 傳統(tǒng)的UNIX調(diào)度程序在每個(gè)優(yōu)先級(jí)隊(duì)列中采用使用循環(huán)法的多級(jí)反饋。該系統(tǒng)使用1秒剝奪，也就是說(shuō)，如果一個(gè)正在運(yùn)行的進(jìn)程在1秒內(nèi)沒(méi)有阻塞或完成，它將被剝奪。優(yōu)先級(jí)基于進(jìn)程類型和執(zhí)行歷史 每秒都重新計(jì)算每個(gè)進(jìn)程的優(yōu)先級(jí)，并進(jìn)行一次新的調(diào)度決策 基本優(yōu)先級(jí)的目的是把所有的進(jìn)程劃分成固定的優(yōu)先級(jí)。這些區(qū)用于優(yōu)化訪問(wèn)塊設(shè)備 (如磁盤) 和允許操作系統(tǒng)迅速響應(yīng)系統(tǒng)調(diào)用 按優(yōu)先級(jí)的順序，這些區(qū)如下 交換程序 塊I/O設(shè)備控制 文件操作字符I/O設(shè)備控制用戶進(jìn)程當(dāng)系統(tǒng)包含多個(gè)處理器時(shí)，在設(shè)計(jì)調(diào)度功

33、能時(shí)就當(dāng)系統(tǒng)包含多個(gè)處理器時(shí)，在設(shè)計(jì)調(diào)度功能時(shí)就會(huì)產(chǎn)生一些新問(wèn)題會(huì)產(chǎn)生一些新問(wèn)題多處理器系統(tǒng)可以劃分為以下幾類多處理器系統(tǒng)可以劃分為以下幾類 松耦合、分布式多處理器、集群松耦合、分布式多處理器、集群：由一組相對(duì)自治的系：由一組相對(duì)自治的系統(tǒng)組成，每個(gè)處理器有自己的主存和統(tǒng)組成，每個(gè)處理器有自己的主存和I/OI/O通道通道 專門功能的處理器專門功能的處理器：例如：例如I/OI/O處理器。在這種情況下，處理器。在這種情況下，有一個(gè)通用的主處理器，專用處理器受主處理器的控制，有一個(gè)通用的主處理器，專用處理器受主處理器的控制，并給主處理器提供服務(wù)并給主處理器提供服務(wù) 緊耦合多處理器緊耦合多處理器：由一

34、組共享同一個(gè)主存并在操作系統(tǒng)：由一組共享同一個(gè)主存并在操作系統(tǒng)完全控制下的處理器組成完全控制下的處理器組成關(guān)注最后一類系統(tǒng)，特別是與調(diào)度有關(guān)的問(wèn)題關(guān)注最后一類系統(tǒng)，特別是與調(diào)度有關(guān)的問(wèn)題 粒度粒度 刻畫(huà)多處理器的一種比較好的方法，是考慮系統(tǒng)中進(jìn)程刻畫(huà)多處理器的一種比較好的方法，是考慮系統(tǒng)中進(jìn)程之間的同步粒度，或者說(shuō)同步頻率之間的同步粒度，或者說(shuō)同步頻率 可以根據(jù)粒度區(qū)分可以根據(jù)粒度區(qū)分5類并行度類并行度 獨(dú)立獨(dú)立：多個(gè)無(wú)關(guān)進(jìn)程：多個(gè)無(wú)關(guān)進(jìn)程 非常粗非常粗：在網(wǎng)絡(luò)節(jié)點(diǎn)上進(jìn)行分布處理，以形成一個(gè)計(jì)算：在網(wǎng)絡(luò)節(jié)點(diǎn)上進(jìn)行分布處理，以形成一個(gè)計(jì)算環(huán)境環(huán)境 粗粗：在多道程序環(huán)境中并發(fā)進(jìn)程的多處理：在多道程

35、序環(huán)境中并發(fā)進(jìn)程的多處理 中等中等：在一個(gè)應(yīng)用程序中的并行處理或多任務(wù)處理：在一個(gè)應(yīng)用程序中的并行處理或多任務(wù)處理(線程線程) 細(xì)細(xì)：指令流中固有的并行：指令流中固有的并行 獨(dú)立并行度 進(jìn)程間沒(méi)有顯式的同步。每個(gè)進(jìn)程都代表各自獨(dú)立的應(yīng)用或作業(yè)。這類并行度的一個(gè)典型應(yīng)用是分時(shí)系統(tǒng)。每個(gè)用戶都執(zhí)行一個(gè)特定的應(yīng)用，如字處理或使用電子表格。多處理器和多道程序單處理器一樣提供相同的服務(wù)。由于有多個(gè)處理器可用，因而用戶的平均響應(yīng)時(shí)間非常短 有可能達(dá)到這樣的性能：每個(gè)用戶都如同在使用個(gè)人計(jì)算機(jī)或工作站。如果任何一個(gè)文件或信息被共享，則單個(gè)系統(tǒng)必須連接在一個(gè)有網(wǎng)絡(luò)支持的分布式系統(tǒng)中 在許多實(shí)例中，多處理器共享

36、系統(tǒng)比分布式系統(tǒng)的成本效益更合算，它允許節(jié)約使用磁盤和其他外圍設(shè)備 粗粒度和非常粗粒度的并行度 是指進(jìn)程之間在一個(gè)非常粗的級(jí)別上存在著同步。這種情況可以簡(jiǎn)單地處理成一組運(yùn)行在多道程序單處理器上的并發(fā)進(jìn)程，在多處理器上對(duì)用戶軟件進(jìn)行很少的改動(dòng)或者不進(jìn)行改動(dòng)就可以提供支持 一般來(lái)說(shuō)，使用多處理器體系結(jié)構(gòu)，對(duì)所有需要通信或同步的并發(fā)進(jìn)程集合都有好處。當(dāng)進(jìn)程間存在非常頻繁的交互時(shí)，分布式系統(tǒng)可以提供好的支持。但是，當(dāng)交互更加頻繁時(shí)，分布式系統(tǒng)中的網(wǎng)絡(luò)通信開(kāi)銷會(huì)抵消一部分潛在的加速，在這種情況下，多處理器組織能提供最有效的支持 中等粒度的并行度 應(yīng)用程序可以作為進(jìn)程中的一組線程被有效地實(shí)現(xiàn)。在這種情況下

37、，可以由程序員顯式地指定應(yīng)用程序潛在的并行性。典型地，在應(yīng)用程序的線程之間，需要更高程度的合作與交互，從而導(dǎo)致中等粒度級(jí)的同步 盡管多處理器和多道程序單處理器都支持獨(dú)立、非常粗和粗粒度的并行度，并對(duì)調(diào)度功能產(chǎn)生少許影響或沒(méi)有影響，但是在處理線程調(diào)度時(shí)，我們?nèi)匀恍枰匦路治稣{(diào)度。由于應(yīng)用程序中各個(gè)線程間的交互是如此地頻繁，關(guān)于線程調(diào)度的決策可能會(huì)影響整個(gè)應(yīng)用的性能 細(xì)粒度的并行度 代表著比線程中的并行更加復(fù)雜的使用。盡管在高度并行的應(yīng)用中已經(jīng)完成了大量的工作，迄今為止，這仍然是一個(gè)特殊的、被分割的領(lǐng)域多處理器中的調(diào)度涉及到以下三個(gè)相關(guān)問(wèn)題多處理器中的調(diào)度涉及到以下三個(gè)相關(guān)問(wèn)題 把進(jìn)程分配到處理器

38、把進(jìn)程分配到處理器 在單個(gè)處理器上使用多道程序在單個(gè)處理器上使用多道程序 一個(gè)進(jìn)程的實(shí)際分派一個(gè)進(jìn)程的實(shí)際分派在討論這三個(gè)問(wèn)題時(shí)，必須記住所采用的方法通在討論這三個(gè)問(wèn)題時(shí)，必須記住所采用的方法通常取決于應(yīng)用程序的粒度等級(jí)和可用的處理器的常取決于應(yīng)用程序的粒度等級(jí)和可用的處理器的數(shù)目數(shù)目把進(jìn)程分配到處理器把進(jìn)程分配到處理器 假設(shè)多處理器結(jié)構(gòu)中各個(gè)處理器在訪問(wèn)主存和假設(shè)多處理器結(jié)構(gòu)中各個(gè)處理器在訪問(wèn)主存和I/O設(shè)備時(shí)沒(méi)有特別優(yōu)勢(shì)，那么最簡(jiǎn)單的調(diào)度方設(shè)備時(shí)沒(méi)有特別優(yōu)勢(shì)，那么最簡(jiǎn)單的調(diào)度方法是把處理器看作是一個(gè)資源池，并按照要求把法是把處理器看作是一個(gè)資源池，并按照要求把進(jìn)程分配到相應(yīng)的處理器。帶來(lái)的

39、問(wèn)題是：分配進(jìn)程分配到相應(yīng)的處理器。帶來(lái)的問(wèn)題是：分配應(yīng)該是應(yīng)該是靜態(tài)靜態(tài)的還是的還是動(dòng)態(tài)動(dòng)態(tài)的的 靜態(tài)：靜態(tài)：一個(gè)進(jìn)程從被激活到完成，被永久地分配到一個(gè)進(jìn)程從被激活到完成，被永久地分配到一個(gè)處理器，則需要為每個(gè)處理器維護(hù)一個(gè)專門的一個(gè)處理器，則需要為每個(gè)處理器維護(hù)一個(gè)專門的短程隊(duì)列。短程隊(duì)列。 其優(yōu)點(diǎn)是調(diào)度的開(kāi)銷比較小，因?yàn)樗羞M(jìn)程關(guān)于處其優(yōu)點(diǎn)是調(diào)度的開(kāi)銷比較小，因?yàn)樗羞M(jìn)程關(guān)于處理器的分配只進(jìn)行一次理器的分配只進(jìn)行一次 靜態(tài)分配的缺點(diǎn)是某個(gè)處理器可能空閑，這時(shí)它的靜態(tài)分配的缺點(diǎn)是某個(gè)處理器可能空閑，這時(shí)它的隊(duì)列為空，而另一個(gè)處理器卻積壓了許多工作隊(duì)列為空，而另一個(gè)處理器卻積壓了許多工作 動(dòng)

40、態(tài)動(dòng)態(tài)：為防止靜態(tài)分配浪費(fèi)：為防止靜態(tài)分配浪費(fèi)CPU資源的情況，需資源的情況，需要使用一個(gè)公共隊(duì)列。所有進(jìn)程都進(jìn)入一個(gè)全局要使用一個(gè)公共隊(duì)列。所有進(jìn)程都進(jìn)入一個(gè)全局隊(duì)列，然后調(diào)度到任何一個(gè)可用的處理器中。這隊(duì)列，然后調(diào)度到任何一個(gè)可用的處理器中。這樣，在一個(gè)進(jìn)程的生命周期中，它可以在不同的樣，在一個(gè)進(jìn)程的生命周期中，它可以在不同的時(shí)間在不同的處理器上執(zhí)行時(shí)間在不同的處理器上執(zhí)行把進(jìn)程分配到處理器把進(jìn)程分配到處理器處理器結(jié)構(gòu)處理器結(jié)構(gòu) 主從式結(jié)構(gòu)主從式結(jié)構(gòu)：操作系統(tǒng)的主要核心功能總是在某個(gè)特定的：操作系統(tǒng)的主要核心功能總是在某個(gè)特定的處理器上運(yùn)行，其他處理器可能僅用于執(zhí)行用戶程序處理器上運(yùn)行，其

41、他處理器可能僅用于執(zhí)行用戶程序 主處理器負(fù)責(zé)調(diào)度作業(yè)。當(dāng)一個(gè)進(jìn)程被激活時(shí)，如果從處主處理器負(fù)責(zé)調(diào)度作業(yè)。當(dāng)一個(gè)進(jìn)程被激活時(shí)，如果從處理器需要服務(wù)理器需要服務(wù) (例如一次例如一次I/O調(diào)用調(diào)用) ，它必須給主處理器發(fā)，它必須給主處理器發(fā)送一個(gè)請(qǐng)求，然后等待服務(wù)的執(zhí)行送一個(gè)請(qǐng)求，然后等待服務(wù)的執(zhí)行 這種方法簡(jiǎn)單，由于處理器擁有對(duì)所有存儲(chǔ)器和這種方法簡(jiǎn)單，由于處理器擁有對(duì)所有存儲(chǔ)器和I/O資源資源的控制，因而可以簡(jiǎn)化沖突解決方案的控制，因而可以簡(jiǎn)化沖突解決方案 缺點(diǎn)是缺點(diǎn)是: 主處理器的失敗導(dǎo)致整個(gè)系統(tǒng)失敗主處理器的失敗導(dǎo)致整個(gè)系統(tǒng)失敗; 主處理器可能主處理器可能成為性能瓶頸成為性能瓶頸把進(jìn)程分配到

42、處理器把進(jìn)程分配到處理器處理器結(jié)構(gòu)處理器結(jié)構(gòu) 對(duì)等式結(jié)構(gòu)對(duì)等式結(jié)構(gòu)：操作系統(tǒng)可以在任何一個(gè)處理器中執(zhí)行。：操作系統(tǒng)可以在任何一個(gè)處理器中執(zhí)行。每個(gè)處理器從可用進(jìn)程池中進(jìn)行自調(diào)度。這種方法增加每個(gè)處理器從可用進(jìn)程池中進(jìn)行自調(diào)度。這種方法增加了操作系統(tǒng)的復(fù)雜性，必須確保兩個(gè)處理器不會(huì)選擇同了操作系統(tǒng)的復(fù)雜性，必須確保兩個(gè)處理器不會(huì)選擇同一個(gè)進(jìn)程，進(jìn)程也不會(huì)從隊(duì)列中丟失一個(gè)進(jìn)程，進(jìn)程也不會(huì)從隊(duì)列中丟失 也可以提供一個(gè)處理器子集專門用于內(nèi)核處理，或者是也可以提供一個(gè)處理器子集專門用于內(nèi)核處理，或者是基于優(yōu)先級(jí)和執(zhí)行歷史來(lái)管理內(nèi)核進(jìn)程和其他進(jìn)程之間基于優(yōu)先級(jí)和執(zhí)行歷史來(lái)管理內(nèi)核進(jìn)程和其他進(jìn)程之間的差別等

43、的差別等在單個(gè)處理器上使用多道程序在單個(gè)處理器上使用多道程序 傳統(tǒng)的多處理器處理是粗粒度或獨(dú)立同步粒度，顯然單傳統(tǒng)的多處理器處理是粗粒度或獨(dú)立同步粒度，顯然單個(gè)處理器能夠在許多進(jìn)程間切換，以達(dá)到較高的使用率個(gè)處理器能夠在許多進(jìn)程間切換，以達(dá)到較高的使用率和更好的性能。和更好的性能。 但是，對(duì)于運(yùn)行在有許多處理器的多處理器系統(tǒng)中的中但是，對(duì)于運(yùn)行在有許多處理器的多處理器系統(tǒng)中的中等粒度等粒度(線程線程)應(yīng)用程序，當(dāng)多個(gè)處理器可用時(shí)，要求每個(gè)應(yīng)用程序，當(dāng)多個(gè)處理器可用時(shí)，要求每個(gè)處理器盡可能地忙就不再那么重要了。相反，我們更加處理器盡可能地忙就不再那么重要了。相反，我們更加關(guān)注如何能為應(yīng)用提供最好

44、的平均性能。關(guān)注如何能為應(yīng)用提供最好的平均性能。進(jìn)程分派進(jìn)程分派 選擇哪一個(gè)進(jìn)程運(yùn)行？選擇哪一個(gè)進(jìn)程運(yùn)行？ 在多道程序單處理器上，與簡(jiǎn)單的先來(lái)先服務(wù)策略相比在多道程序單處理器上，與簡(jiǎn)單的先來(lái)先服務(wù)策略相比較，使用優(yōu)先級(jí)或者基于過(guò)去的使用歷史的高級(jí)調(diào)度算較，使用優(yōu)先級(jí)或者基于過(guò)去的使用歷史的高級(jí)調(diào)度算法可以提高性能法可以提高性能 當(dāng)考慮多處理器時(shí)，這些復(fù)雜性是不必要的，不然可能當(dāng)考慮多處理器時(shí)，這些復(fù)雜性是不必要的，不然可能反而達(dá)不到預(yù)期的目標(biāo)，反而達(dá)不到預(yù)期的目標(biāo)， 對(duì)于多處理器，相對(duì)比較簡(jiǎn)單的方法會(huì)更有效，而且開(kāi)對(duì)于多處理器，相對(duì)比較簡(jiǎn)單的方法會(huì)更有效，而且開(kāi)銷也比較低。銷也比較低。 在大多

45、數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進(jìn)程并不是被指定到一個(gè)在大多數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進(jìn)程并不是被指定到一個(gè)專門的處理器。不是所有處理器只有一個(gè)隊(duì)列專門的處理器。不是所有處理器只有一個(gè)隊(duì)列 而是有多條基于優(yōu)先級(jí)的隊(duì)列，并且都送進(jìn)相同的處理器池而是有多條基于優(yōu)先級(jí)的隊(duì)列，并且都送進(jìn)相同的處理器池中。在任何情況下，我們都可以把系統(tǒng)看作是多服務(wù)器排隊(duì)中。在任何情況下，我們都可以把系統(tǒng)看作是多服務(wù)器排隊(duì)結(jié)構(gòu)結(jié)構(gòu) 對(duì)各種情況進(jìn)行分析，對(duì)于多處理器，調(diào)度原則的選擇沒(méi)有對(duì)各種情況進(jìn)行分析，對(duì)于多處理器，調(diào)度原則的選擇沒(méi)有在單處理器中顯得重要。因此，在多處理器系統(tǒng)中使用簡(jiǎn)單在單處理器中顯得重要。因此，在多處理器系統(tǒng)中使

46、用簡(jiǎn)單的的FCFS (先來(lái)先服務(wù)先來(lái)先服務(wù)) 原則或者在靜態(tài)化先級(jí)方案中使用原則或者在靜態(tài)化先級(jí)方案中使用FCFS就足夠了就足夠了 在單處理器中在單處理器中，線程可以用作輔助構(gòu)造程序，并，線程可以用作輔助構(gòu)造程序，并在處理過(guò)程在處理過(guò)程中重疊執(zhí)行中重疊執(zhí)行I/O。由于在進(jìn)行線程切換時(shí)的性能損失遠(yuǎn)遠(yuǎn)小。由于在進(jìn)行線程切換時(shí)的性能損失遠(yuǎn)遠(yuǎn)小于進(jìn)程切換的開(kāi)銷，因此可以用很少的代價(jià)實(shí)現(xiàn)這些優(yōu)點(diǎn)于進(jìn)程切換的開(kāi)銷，因此可以用很少的代價(jià)實(shí)現(xiàn)這些優(yōu)點(diǎn) 在多處理器系統(tǒng)中在多處理器系統(tǒng)中，線程的全部能力得到了更好的展現(xiàn)，線，線程的全部能力得到了更好的展現(xiàn)，線程可以用于開(kāi)發(fā)應(yīng)用程序中真正的并行性。如果程可以用于開(kāi)發(fā)

47、應(yīng)用程序中真正的并行性。如果一個(gè)應(yīng)用程一個(gè)應(yīng)用程序的各個(gè)線程同時(shí)在各個(gè)獨(dú)立的處理器中執(zhí)行序的各個(gè)線程同時(shí)在各個(gè)獨(dú)立的處理器中執(zhí)行，其性能就會(huì)，其性能就會(huì)得到顯著的提高。得到顯著的提高。 在多處理器線程調(diào)度和處理器分配的各種方案中，比較突出在多處理器線程調(diào)度和處理器分配的各種方案中，比較突出的方法是：的方法是： 負(fù)載分配負(fù)載分配：進(jìn)程不是分配到一個(gè)特定的處理器，而是維護(hù)一個(gè)就緒進(jìn)程不是分配到一個(gè)特定的處理器，而是維護(hù)一個(gè)就緒進(jìn)程的全局隊(duì)列，每個(gè)處理器只要空閑就從隊(duì)列中選擇一個(gè)線程，進(jìn)程的全局隊(duì)列，每個(gè)處理器只要空閑就從隊(duì)列中選擇一個(gè)線程，負(fù)載平衡是基于一種比較永久的分配方案配工作的負(fù)載平衡是基于

48、一種比較永久的分配方案配工作的 成組調(diào)度成組調(diào)度：一組相關(guān)的線程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處一組相關(guān)的線程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處理器上運(yùn)行理器上運(yùn)行 專用處理器分配專用處理器分配：這種方法與負(fù)載分配的方法相反，它通過(guò)把線程這種方法與負(fù)載分配的方法相反，它通過(guò)把線程指定到處理器來(lái)定義隱式的調(diào)度。在程序執(zhí)行過(guò)程中，每個(gè)程序被指定到處理器來(lái)定義隱式的調(diào)度。在程序執(zhí)行過(guò)程中，每個(gè)程序被分配給一組處理器，處理器的數(shù)目與程序線程的數(shù)目相等。當(dāng)程序分配給一組處理器，處理器的數(shù)目與程序線程的數(shù)目相等。當(dāng)程序終止時(shí)，處理器返回到總的處理器池中，可供分配給另一個(gè)程序終止時(shí)，處理器返回到總的處理器

49、池中，可供分配給另一個(gè)程序 動(dòng)態(tài)調(diào)度動(dòng)態(tài)調(diào)度：在執(zhí)行期間，進(jìn)程中線程的數(shù)目可以改變：在執(zhí)行期間，進(jìn)程中線程的數(shù)目可以改變Windows 2000 的設(shè)計(jì)目標(biāo)是在高度交互的環(huán)境中的設(shè)計(jì)目標(biāo)是在高度交互的環(huán)境中或者作為服務(wù)器盡可能地響應(yīng)單個(gè)用戶的需求或者作為服務(wù)器盡可能地響應(yīng)單個(gè)用戶的需求Windows 2000 實(shí)現(xiàn)了剝奪式調(diào)度程序，它具有靈實(shí)現(xiàn)了剝奪式調(diào)度程序，它具有靈活的優(yōu)先級(jí)系統(tǒng)，在每一級(jí)上都包括了循環(huán)調(diào)度活的優(yōu)先級(jí)系統(tǒng)，在每一級(jí)上都包括了循環(huán)調(diào)度方法，在某些級(jí)上，優(yōu)先級(jí)可以基于它們當(dāng)前的方法，在某些級(jí)上，優(yōu)先級(jí)可以基于它們當(dāng)前的線程活動(dòng)而動(dòng)態(tài)變化線程活動(dòng)而動(dòng)態(tài)變化Windows 2000中的優(yōu)先級(jí)被組織成兩段中的優(yōu)先級(jí)被組織成兩段 (兩類兩類) ：實(shí)：實(shí)時(shí)和可變。每一段包括時(shí)和可變。每一段包括16種優(yōu)先級(jí)。需要立即關(guān)注種優(yōu)先級(jí)。需要立即關(guān)注的線程在實(shí)時(shí)類中，它包括諸如通信之類的功能和的線程在實(shí)時(shí)類中，它包括諸如通信之類的功能和實(shí)時(shí)任務(wù)實(shí)時(shí)任務(wù)Windows 2000使用一種優(yōu)先級(jí)驅(qū)動(dòng)的剝奪式調(diào)度程使用一種優(yōu)先級(jí)驅(qū)動(dòng)的剝奪式調(diào)度程序，具有實(shí)時(shí)優(yōu)先級(jí)的線程優(yōu)先于其他線程序，具有實(shí)時(shí)優(yōu)先級(jí)的線程優(yōu)先于其他線程在單處理器中，當(dāng)一