第4章調(diào)度和死鎖new

1、內(nèi)容內(nèi)容調(diào)度的類型和模型調(diào)度的類型和模型調(diào)度算法調(diào)度算法實(shí)時(shí)系統(tǒng)中的調(diào)度實(shí)時(shí)系統(tǒng)中的調(diào)度多處理機(jī)調(diào)度多處理機(jī)調(diào)度調(diào)度算法舉例調(diào)度算法舉例死鎖的基本概念死鎖的基本概念死鎖的預(yù)防和避免死鎖的預(yù)防和避免死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除第四章第四章調(diào)度和死鎖調(diào)度和死鎖目的及要求目的及要求了解進(jìn)程調(diào)度的類型，領(lǐng)會(huì)調(diào)度隊(duì)列模型，領(lǐng)會(huì)并理解了解進(jìn)程調(diào)度的類型，領(lǐng)會(huì)調(diào)度隊(duì)列模型，領(lǐng)會(huì)并理解選擇調(diào)度方式和算法的準(zhǔn)則；選擇調(diào)度方式和算法的準(zhǔn)則；掌握先來(lái)先服務(wù)、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片輪轉(zhuǎn)和掌握先來(lái)先服務(wù)、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片輪轉(zhuǎn)和優(yōu)先權(quán)調(diào)度算法，領(lǐng)會(huì)和理解高響應(yīng)比優(yōu)先、多級(jí)隊(duì)列優(yōu)先權(quán)調(diào)度算法，領(lǐng)會(huì)和理解高

2、響應(yīng)比優(yōu)先、多級(jí)隊(duì)列調(diào)度和多級(jí)反饋隊(duì)列調(diào)度算法；調(diào)度和多級(jí)反饋隊(duì)列調(diào)度算法；了解實(shí)時(shí)系統(tǒng)中調(diào)度要求和調(diào)度算法；了解實(shí)時(shí)系統(tǒng)中調(diào)度要求和調(diào)度算法；了解多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度算法；了解多處理機(jī)系統(tǒng)中的進(jìn)程調(diào)度算法；領(lǐng)會(huì)并掌握死鎖的基本概念，理解產(chǎn)生死鎖的原因、產(chǎn)領(lǐng)會(huì)并掌握死鎖的基本概念，理解產(chǎn)生死鎖的原因、產(chǎn)生死鎖的必要條件；生死鎖的必要條件；領(lǐng)會(huì)和理解死鎖的預(yù)防的各種方法；領(lǐng)會(huì)和理解死鎖的預(yù)防的各種方法；領(lǐng)會(huì)系統(tǒng)的安全狀態(tài)，理解并掌握掌握銀行家算法；領(lǐng)會(huì)系統(tǒng)的安全狀態(tài)，理解并掌握掌握銀行家算法；了解和領(lǐng)會(huì)死鎖檢測(cè)的算法和死鎖解除的方法。了解和領(lǐng)會(huì)死鎖檢測(cè)的算法和死鎖解除的方法。第四章第四章調(diào)度

3、和死鎖調(diào)度和死鎖重點(diǎn)重點(diǎn)先來(lái)先服務(wù)、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片輪轉(zhuǎn)調(diào)度算先來(lái)先服務(wù)、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片輪轉(zhuǎn)調(diào)度算法；法；死鎖的基本概念，產(chǎn)生死鎖的必要條件；死鎖的基本概念，產(chǎn)生死鎖的必要條件；預(yù)防死鎖的方法；預(yù)防死鎖的方法；銀行家算法。銀行家算法。難點(diǎn)難點(diǎn)調(diào)度隊(duì)列模型；調(diào)度隊(duì)列模型；銀行家算法；銀行家算法；死鎖的檢測(cè)算法。死鎖的檢測(cè)算法。 第四章第四章調(diào)度和死鎖調(diào)度和死鎖4.1.1 4.1.1 調(diào)度類型調(diào)度類型4.1.2 4.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型4.1.3 4.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則4.14.1 調(diào)度的類型與模型調(diào)度的類型與模型1.

4、1.高級(jí)調(diào)度高級(jí)調(diào)度(High Level Scheduling)(High Level Scheduling)又稱作業(yè)調(diào)度、又稱作業(yè)調(diào)度、宏觀調(diào)度、宏觀調(diào)度、長(zhǎng)程調(diào)度長(zhǎng)程調(diào)度(Long-Term (Long-Term Scheduling)Scheduling)或接納調(diào)度或接納調(diào)度(Admission Scheduling)(Admission Scheduling)。作業(yè)調(diào)度用于決定把外存上處于作業(yè)后備隊(duì)列上的哪些作業(yè)調(diào)度用于決定把外存上處于作業(yè)后備隊(duì)列上的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后再將新創(chuàng)建的進(jìn)程排在就緒

5、隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。在批處理系統(tǒng)中，作業(yè)是先駐留在外存上的，因此需要有作業(yè)調(diào)度。然而在分，作業(yè)是先駐留在外存上的，因此需要有作業(yè)調(diào)度。然而在分時(shí)系統(tǒng)中，通過(guò)鍵盤(pán)輸入的命令和數(shù)據(jù)直接進(jìn)入內(nèi)存，無(wú)需作時(shí)系統(tǒng)中，通過(guò)鍵盤(pán)輸入的命令和數(shù)據(jù)直接進(jìn)入內(nèi)存，無(wú)需作業(yè)調(diào)度。業(yè)調(diào)度。1.1. 接納多少個(gè)作業(yè)（多道程序度）接納多少個(gè)作業(yè)（多道程序度）2.2. 接納哪些作業(yè)接納哪些作業(yè)4.1.1 4.1.1 調(diào)度類型調(diào)度類型二二低級(jí)調(diào)度低級(jí)調(diào)度(Low Level Scheduling)(Low Level Scheduling) 又稱進(jìn)程調(diào)度、又稱進(jìn)程調(diào)度、微觀

6、調(diào)度或微觀調(diào)度或短程調(diào)度短程調(diào)度(Short-Term (Short-Term Scheduling)Scheduling)。進(jìn)程調(diào)度決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，然后進(jìn)程調(diào)度決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的操作。進(jìn)程調(diào)度是最由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的操作。進(jìn)程調(diào)度是最基本的調(diào)度，任何操作系統(tǒng)都有進(jìn)程調(diào)度。基本的調(diào)度，任何操作系統(tǒng)都有進(jìn)程調(diào)度。4.1.1 4.1.1 調(diào)度類型調(diào)度類型1.1. 非搶占方式非搶占方式(Non-Preemptive Mode)(Non-Preemptive Mode) 采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給

7、某進(jìn)程后采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，便讓進(jìn)程一直執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而被，便讓進(jìn)程一直執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶阻塞時(shí)，才把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。占已經(jīng)分配出去的處理機(jī)。 這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷小，適用這種調(diào)度方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷小，適用于大多數(shù)批處理系統(tǒng)環(huán)境。缺點(diǎn)是難以滿足緊急任務(wù)的要于大多數(shù)批處理系統(tǒng)環(huán)境。缺點(diǎn)是難以滿足緊急任務(wù)的要求，不適用于實(shí)時(shí)、分時(shí)系統(tǒng)要求。求，不適用于實(shí)時(shí)、分時(shí)系統(tǒng)要求。4.1.1 4.1.1 調(diào)度類型調(diào)度類型

8、2.2. 搶占方式搶占方式(Preemptive Mode)(Preemptive Mode)這種調(diào)度方式，允許進(jìn)程調(diào)度程序根據(jù)某個(gè)原則，去停止某個(gè)正這種調(diào)度方式，允許進(jìn)程調(diào)度程序根據(jù)某個(gè)原則，去停止某個(gè)正在執(zhí)行的進(jìn)程，將已分配給進(jìn)程的處理機(jī)，重新分配給另一個(gè)進(jìn)程。在執(zhí)行的進(jìn)程，將已分配給進(jìn)程的處理機(jī)，重新分配給另一個(gè)進(jìn)程。搶占的原則有：搶占的原則有：l時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便時(shí)間片原則。各進(jìn)程按時(shí)間片運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這個(gè)原則適用于分時(shí)系統(tǒng)、大停止進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。這個(gè)原則適用于分時(shí)系統(tǒng)、大多數(shù)實(shí)時(shí)系統(tǒng)以及要求較高

9、的批處理系統(tǒng)。多數(shù)實(shí)時(shí)系統(tǒng)以及要求較高的批處理系統(tǒng)。l優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的進(jìn)程賦予較高的優(yōu)優(yōu)先權(quán)原則。通常是對(duì)一些重要的和緊急的進(jìn)程賦予較高的優(yōu)先權(quán)。當(dāng)這種進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行的先權(quán)。當(dāng)這種進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，如果其優(yōu)先權(quán)比正在執(zhí)行的進(jìn)程優(yōu)先權(quán)高，便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)進(jìn)程優(yōu)先權(quán)高，便停止正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先權(quán)高的進(jìn)程，使之執(zhí)行。高的進(jìn)程，使之執(zhí)行。l短作業(yè)（進(jìn)程）優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)（進(jìn)程）比正在執(zhí)短作業(yè)（進(jìn)程）優(yōu)先原則。當(dāng)新到達(dá)的作業(yè)（進(jìn)程）比正在執(zhí)行的作業(yè)（進(jìn)程）明顯地短時(shí)，將剝奪長(zhǎng)作業(yè)（進(jìn)程）的執(zhí)行，行的作業(yè)

10、（進(jìn)程）明顯地短時(shí)，將剝奪長(zhǎng)作業(yè)（進(jìn)程）的執(zhí)行，將處理機(jī)分配給短作業(yè)（進(jìn)程），使之優(yōu)先執(zhí)行。將處理機(jī)分配給短作業(yè)（進(jìn)程），使之優(yōu)先執(zhí)行。4.1.1 4.1.1 調(diào)度類型調(diào)度類型三三中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate Level Scheduling)(Intermediate Level Scheduling) 又稱中程調(diào)度又稱中程調(diào)度 (Medium-Term Scheduling)(Medium-Term Scheduling)。引入中級(jí)調(diào)度的目的是為了提高主存利用率和系統(tǒng)吞吐引入中級(jí)調(diào)度的目的是為了提高主存利用率和系統(tǒng)吞吐量。由于在進(jìn)程并發(fā)執(zhí)行過(guò)程中，為了充分發(fā)揮內(nèi)存的效能，量。

11、由于在進(jìn)程并發(fā)執(zhí)行過(guò)程中，為了充分發(fā)揮內(nèi)存的效能，需將那些暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存調(diào)到外存去等待（就緒掛需將那些暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存調(diào)到外存去等待（就緒掛起），而當(dāng)內(nèi)存空閑時(shí)，進(jìn)行中級(jí)調(diào)度，將那些在外存的等待起），而當(dāng)內(nèi)存空閑時(shí)，進(jìn)行中級(jí)調(diào)度，將那些在外存的等待的進(jìn)程調(diào)入內(nèi)存，插入就緒隊(duì)列（激活、解掛）的進(jìn)程調(diào)入內(nèi)存，插入就緒隊(duì)列（激活、解掛） ，等待進(jìn)程，等待進(jìn)程調(diào)度。調(diào)度。中級(jí)調(diào)度就是存儲(chǔ)管理中的對(duì)換，采用虛擬存儲(chǔ)技術(shù)的中級(jí)調(diào)度就是存儲(chǔ)管理中的對(duì)換，采用虛擬存儲(chǔ)技術(shù)的分時(shí)系統(tǒng)往往設(shè)立中級(jí)調(diào)度。分時(shí)系統(tǒng)往往設(shè)立中級(jí)調(diào)度。4.1.1 4.1.1 調(diào)度類型調(diào)度類型處理機(jī)三級(jí)調(diào)度：處理機(jī)三級(jí)調(diào)

12、度：4.1.1 4.1.1 調(diào)度類型調(diào)度類型 外存外存作 業(yè)作 業(yè)后 備后 備狀態(tài)狀態(tài)作 業(yè)作 業(yè)提 交提 交狀態(tài)狀態(tài)就緒就緒態(tài)態(tài)阻塞阻塞態(tài)態(tài)主存主存進(jìn)程調(diào)度進(jìn)程調(diào)度運(yùn)行運(yùn)行態(tài)態(tài)就緒就緒態(tài)態(tài)阻塞阻塞態(tài)態(tài)中級(jí)調(diào)度中級(jí)調(diào)度作作業(yè)業(yè)調(diào)調(diào)度度作 業(yè)作 業(yè)完 成完 成狀態(tài)狀態(tài)外存外存4.1.1 4.1.1 調(diào)度類型調(diào)度類型AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdm

13、itSuspend宏觀調(diào)度微觀調(diào)度中級(jí)調(diào)度一一僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型在分時(shí)系統(tǒng)中通常僅設(shè)置了進(jìn)程調(diào)度。此時(shí)系統(tǒng)有一個(gè)在分時(shí)系統(tǒng)中通常僅設(shè)置了進(jìn)程調(diào)度。此時(shí)系統(tǒng)有一個(gè)就緒隊(duì)列，每個(gè)進(jìn)程運(yùn)行一個(gè)時(shí)間片，進(jìn)程運(yùn)行一個(gè)時(shí)間片后就緒隊(duì)列，每個(gè)進(jìn)程運(yùn)行一個(gè)時(shí)間片，進(jìn)程運(yùn)行一個(gè)時(shí)間片后如未完成，則被放在就緒隊(duì)列末尾。如進(jìn)程運(yùn)行中因等待某事如未完成，則被放在就緒隊(duì)列末尾。如進(jìn)程運(yùn)行中因等待某事件（例如申請(qǐng)件（例如申請(qǐng)I/OI/O而等待而等待I/OI/O完成），則需排入阻塞隊(duì)列，系統(tǒng)完成），則需排入阻塞隊(duì)列，系統(tǒng)因阻塞的原因不同可設(shè)幾個(gè)阻塞隊(duì)列。因阻塞的原因不同可設(shè)幾個(gè)阻塞隊(duì)列。4

14、.1.2 4.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型事事件件出出現(xiàn)現(xiàn)CPUCPU交互用戶交互用戶時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成 就緒隊(duì)列就緒隊(duì)列等待事件等待事件 阻塞隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)度進(jìn)程調(diào)度二二具有高級(jí)調(diào)度和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)調(diào)度和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在多道批處理系統(tǒng)中，一般處理機(jī)管理設(shè)置作業(yè)和進(jìn)程在多道批處理系統(tǒng)中，一般處理機(jī)管理設(shè)置作業(yè)和進(jìn)程兩級(jí)調(diào)度。它比第一個(gè)模型增加了高級(jí)調(diào)度。模型增加了在磁兩級(jí)調(diào)度。它比第一個(gè)模型增加了高級(jí)調(diào)度。模型增加了在磁盤(pán)的作業(yè)后備隊(duì)列，作業(yè)調(diào)度的任務(wù)是從作業(yè)后備隊(duì)列中選一盤(pán)的作業(yè)后備隊(duì)列，作業(yè)調(diào)度的任務(wù)是從作業(yè)后備隊(duì)列中選一個(gè)作業(yè)為它創(chuàng)建至少一個(gè)

15、進(jìn)程，并分配資源，將它排入內(nèi)存進(jìn)個(gè)作業(yè)為它創(chuàng)建至少一個(gè)進(jìn)程，并分配資源，將它排入內(nèi)存進(jìn)程就緒隊(duì)列末尾。程就緒隊(duì)列末尾。4.1.2 4.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型CPUCPU時(shí)間片完時(shí)間片完進(jìn)程完成進(jìn)程完成 就緒隊(duì)列就緒隊(duì)列等待事件等待事件1 1 阻塞隊(duì)列阻塞隊(duì)列1 1作業(yè)調(diào)度作業(yè)調(diào)度后備作業(yè)隊(duì)列后備作業(yè)隊(duì)列等待事件等待事件n n 阻塞隊(duì)列阻塞隊(duì)列n n進(jìn)程調(diào)度進(jìn)程調(diào)度事件出現(xiàn)事件出現(xiàn)1 1事件出現(xiàn)事件出現(xiàn)n n三三同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 在通用系統(tǒng)的多模式在通用系統(tǒng)的多模式OSOS中，一般采用具有三級(jí)調(diào)度的調(diào)中，一般采用具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型，由

16、于多模式度隊(duì)列模型，由于多模式OSOS同時(shí)支持批處理、分時(shí)和實(shí)時(shí)處理同時(shí)支持批處理、分時(shí)和實(shí)時(shí)處理，所以它必須具有以上模型，所以它必須具有以上模型4.1.2 4.1.2 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型中 級(jí)中 級(jí)調(diào) 度調(diào) 度調(diào)出調(diào)出CPUCPU交互型作業(yè)交互型作業(yè)時(shí)間片完時(shí)間片完等待事件等待事件完成完成 就緒隊(duì)列就緒隊(duì)列就緒，掛起隊(duì)列就緒，掛起隊(duì)列阻塞，掛起隊(duì)列阻塞，掛起隊(duì)列 阻塞隊(duì)列阻塞隊(duì)列事事件件出出現(xiàn)現(xiàn)作業(yè)調(diào)度作業(yè)調(diào)度后備作業(yè)隊(duì)列后備作業(yè)隊(duì)列批批量量作作業(yè)業(yè)中 級(jí)中 級(jí)調(diào) 度調(diào) 度調(diào)入調(diào)入中 級(jí)中 級(jí)調(diào) 度調(diào) 度調(diào)出調(diào)出事 件事 件出現(xiàn)出現(xiàn)一一面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 為滿足用戶需求應(yīng)遵循

17、的一些準(zhǔn)則：為滿足用戶需求應(yīng)遵循的一些準(zhǔn)則：1.1. 周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短（批處理系統(tǒng)批處理系統(tǒng)） 周轉(zhuǎn)時(shí)間，是指從作業(yè)提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段周轉(zhuǎn)時(shí)間，是指從作業(yè)提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔（稱為作業(yè)周轉(zhuǎn)時(shí)間）它包括：時(shí)間間隔（稱為作業(yè)周轉(zhuǎn)時(shí)間）它包括：n作業(yè)在外存后備隊(duì)列上等待（作業(yè)）調(diào)度的時(shí)間；作業(yè)在外存后備隊(duì)列上等待（作業(yè)）調(diào)度的時(shí)間；n進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間；進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間；n進(jìn)程在進(jìn)程在CPUCPU上執(zhí)行的時(shí)間；上執(zhí)行的時(shí)間；n等待等待I/OI/O操作完成的時(shí)間。操作完成的時(shí)間。其中后三項(xiàng)在一個(gè)作業(yè)的處理過(guò)程中，可能發(fā)生多

18、次。其中后三項(xiàng)在一個(gè)作業(yè)的處理過(guò)程中，可能發(fā)生多次。4.1.34.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則提交作業(yè)后備隊(duì)列就緒隊(duì)列CPU作業(yè)調(diào)度進(jìn)程調(diào)度周轉(zhuǎn)時(shí)間等待I/O完成4.1.3 4.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則l對(duì)每個(gè)用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)對(duì)每個(gè)用戶而言，都希望自己作業(yè)的周轉(zhuǎn)時(shí)間最短。但作為計(jì)算機(jī)系統(tǒng)的管理者，總是希望能使平均周轉(zhuǎn)時(shí)間最短；這不僅會(huì)有算機(jī)系統(tǒng)的管理者，總是希望能使平均周轉(zhuǎn)時(shí)間最短；這不僅會(huì)有效地提高資源利用率，而且還可使大多數(shù)用戶感到滿意效地提高資源利用率，而且還可使大多數(shù)用戶感到滿意

19、l平均周轉(zhuǎn)時(shí)間可描述為：平均周轉(zhuǎn)時(shí)間可描述為：l作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間TiTi與系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間與系統(tǒng)為它提供的實(shí)際服務(wù)時(shí)間TsiTsi之比，之比，即即W=T/TsW=T/Ts稱為帶權(quán)周轉(zhuǎn)時(shí)間稱為帶權(quán)周轉(zhuǎn)時(shí)間, ,而平均帶權(quán)周轉(zhuǎn)時(shí)間可表示為：而平均帶權(quán)周轉(zhuǎn)時(shí)間可表示為：11niiTnT11nisiiTTnW1.1.響應(yīng)時(shí)間快響應(yīng)時(shí)間快（分時(shí)系統(tǒng)分時(shí)系統(tǒng)）l響應(yīng)時(shí)間常用于評(píng)價(jià)分時(shí)操作系統(tǒng)的性能，是選擇分時(shí)系統(tǒng)中響應(yīng)時(shí)間常用于評(píng)價(jià)分時(shí)操作系統(tǒng)的性能，是選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則之一。進(jìn)程調(diào)度算法的重要準(zhǔn)則之一。l響應(yīng)時(shí)間是從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次響應(yīng)時(shí)

20、間是從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或說(shuō)直到在屛幕上顯示出結(jié)果為止的一段時(shí)產(chǎn)生響應(yīng)為止的時(shí)間，或說(shuō)直到在屛幕上顯示出結(jié)果為止的一段時(shí)間間隔。它包括：間間隔。它包括：n從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間；從鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間；n處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間；n將所形成的響應(yīng)回送到終端顯示器的時(shí)間。將所形成的響應(yīng)回送到終端顯示器的時(shí)間。4.1.34.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則鍵入請(qǐng)求顯示器顯示請(qǐng)求響應(yīng)響應(yīng)時(shí)間CPU處理請(qǐng)求1.1. 截止時(shí)間的保證截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)實(shí)時(shí)

21、系統(tǒng)）l它是用來(lái)評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度它是用來(lái)評(píng)價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)，因而是選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)則。算法的重要準(zhǔn)則。l所謂截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須所謂截止時(shí)間，是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。完成的最遲時(shí)間。2.2. 優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則（批處理、分時(shí)和實(shí)時(shí)系統(tǒng)批處理、分時(shí)和實(shí)時(shí)系統(tǒng)）在選擇批處理、分時(shí)和實(shí)時(shí)系統(tǒng)的調(diào)度算法時(shí)，都可引用優(yōu)先權(quán)在選擇批處理、分時(shí)和實(shí)時(shí)系統(tǒng)的調(diào)度算法時(shí)，都可引用優(yōu)先權(quán)準(zhǔn)則，以便讓那些緊急的作業(yè)（或事件），得到及時(shí)的處理。在要求準(zhǔn)則，以便讓那些緊急的作業(yè)（或事件），得到及時(shí)的處理。在要求

22、較嚴(yán)格的場(chǎng)合，往往還需選擇搶占調(diào)度方式，才能保證緊急作業(yè)得到較嚴(yán)格的場(chǎng)合，往往還需選擇搶占調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)的處理。及時(shí)的處理。4.1.34.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則二二面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則1.1.系統(tǒng)吞吐量高系統(tǒng)吞吐量高 這是用來(lái)評(píng)價(jià)批處理系統(tǒng)的重要指標(biāo)。系統(tǒng)吞吐量是單位時(shí)間內(nèi)這是用來(lái)評(píng)價(jià)批處理系統(tǒng)的重要指標(biāo)。系統(tǒng)吞吐量是單位時(shí)間內(nèi)完成的作業(yè)數(shù)，它與批處理作業(yè)的平均長(zhǎng)度具有密切關(guān)系。完成的作業(yè)數(shù)，它與批處理作業(yè)的平均長(zhǎng)度具有密切關(guān)系。1.1.處理機(jī)利用率好處理機(jī)利用率好對(duì)于大中型多用戶系統(tǒng)，由于對(duì)于大中型多用戶系統(tǒng)，由于CPUC

23、PU價(jià)格十分昂貴，所以處理機(jī)利價(jià)格十分昂貴，所以處理機(jī)利用率成為衡量大、中型系統(tǒng)性能的十分重要指標(biāo)，但對(duì)單用戶微機(jī)或用率成為衡量大、中型系統(tǒng)性能的十分重要指標(biāo)，但對(duì)單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)，該準(zhǔn)則就不那么重要。某些實(shí)時(shí)系統(tǒng)，該準(zhǔn)則就不那么重要。4.4.各類資源的平衡利用各類資源的平衡利用在大中型系統(tǒng)中，有效地利用各類資源（包括在大中型系統(tǒng)中，有效地利用各類資源（包括CPUCPU、外存、外存、I/OI/O設(shè)設(shè)備等）也是一個(gè)重要指標(biāo)，對(duì)于微型機(jī)和某些實(shí)時(shí)系統(tǒng)，該準(zhǔn)則也不備等）也是一個(gè)重要指標(biāo)，對(duì)于微型機(jī)和某些實(shí)時(shí)系統(tǒng)，該準(zhǔn)則也不重要。重要。4.1.34.1.3 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度

24、方式和算法的若干準(zhǔn)則4.2.1 4.2.1 先進(jìn)先服務(wù)調(diào)度算法先進(jìn)先服務(wù)調(diào)度算法 4.2.2 4.2.2 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 4.2.3 4.2.3 時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法 4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 4.2.5 4.2.5 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 4.2.6 4.2.6 多級(jí)隊(duì)列調(diào)度算法多級(jí)隊(duì)列調(diào)度算法 4.2.7 4.2.7 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法4.2 4.2 調(diào)度算法調(diào)度算法一一調(diào)度算法調(diào)度算法先進(jìn)先服務(wù)先進(jìn)先服務(wù)FCFSFCFS( (First-Come-First-Serv

25、ed)First-Come-First-Served)調(diào)度算法是調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法。一種最簡(jiǎn)單的調(diào)度算法。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度是從后備作業(yè)隊(duì)當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度是從后備作業(yè)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放人就緒隊(duì)列。存，為它們分配資源、創(chuàng)建進(jìn)程，然后放人就緒隊(duì)列。在進(jìn)程調(diào)度中，采用在進(jìn)程調(diào)度中，采用FCFSFCFS調(diào)度算法時(shí)，則每次調(diào)度是從就調(diào)度算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中，選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給緒隊(duì)列中，選擇一

26、個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，把處理機(jī)分配給它，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻它，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后，才放棄處理機(jī)。塞后，才放棄處理機(jī)。該算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。該算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）。4.2.1 4.2.1 先進(jìn)先服務(wù)調(diào)度算法先進(jìn)先服務(wù)調(diào)度算法 4.2.1 4.2.1 先進(jìn)先服務(wù)調(diào)度算法先進(jìn)先服務(wù)調(diào)度算法 二二實(shí)例實(shí)例據(jù)此可知：據(jù)此可知： FCFSFCFS調(diào)度算法有利于調(diào)度算法有利于 CPUCPU繁忙型的作業(yè)（進(jìn)程）繁忙型的作業(yè)（進(jìn)程） ，而不利，而不利于于I IO O繁忙型的作業(yè)（進(jìn)

27、程）。繁忙型的作業(yè)（進(jìn)程）。 lCPUCPU繁忙型作業(yè)，是指該類作業(yè)需要大量的繁忙型作業(yè)，是指該類作業(yè)需要大量的 CPUCPU時(shí)間進(jìn)行計(jì)算，而很時(shí)間進(jìn)行計(jì)算，而很少請(qǐng)求少請(qǐng)求 I I（通常的科學(xué)計(jì)算便屬于（通常的科學(xué)計(jì)算便屬于CPUCPU繁忙型作業(yè)繁忙型作業(yè)) )。lI IO O繁忙型作業(yè)，是指繁忙型作業(yè)，是指CPUCPU進(jìn)行處理時(shí)，又需頻繁地請(qǐng)求進(jìn)行處理時(shí)，又需頻繁地請(qǐng)求I IO O，而每，而每次次I IO O的操作時(shí)間卻又很短。目前的大多數(shù)的事務(wù)處理，都屬于的操作時(shí)間卻又很短。目前的大多數(shù)的事務(wù)處理，都屬于I/OI/O繁忙繁忙型作業(yè)。型作業(yè)。先進(jìn)先出算法比較簡(jiǎn)單，但很少作為一個(gè)獨(dú)立的調(diào)度算

28、法被使用，一般先進(jìn)先出算法比較簡(jiǎn)單，但很少作為一個(gè)獨(dú)立的調(diào)度算法被使用，一般總是作為其他算法的一種輔助手段，例如在優(yōu)先級(jí)調(diào)度算法中，對(duì)擁有相同的總是作為其他算法的一種輔助手段，例如在優(yōu)先級(jí)調(diào)度算法中，對(duì)擁有相同的優(yōu)先級(jí)的進(jìn)程進(jìn)行調(diào)度時(shí)，可采用先進(jìn)先出算法。優(yōu)先級(jí)的進(jìn)程進(jìn)行調(diào)度時(shí)，可采用先進(jìn)先出算法。短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法SJFSJF（Shortest Job FirstShortest Job First）/ SPF(Shortest Process First/ SPF(Shortest Process First）是對(duì)短作業(yè)或短進(jìn)程優(yōu)先）是對(duì)短作業(yè)或短進(jìn)程優(yōu)先

29、調(diào)度的算法。調(diào)度的算法。SJFSJF是從后備作業(yè)中選擇一個(gè)或多個(gè)估計(jì)運(yùn)行時(shí)間最短的是從后備作業(yè)中選擇一個(gè)或多個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。SPFSPF是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并直到完成，或有事件發(fā)生將處理機(jī)分配給它，使它立即執(zhí)行并直到完成，或有事件發(fā)生而被阻塞放棄處理機(jī)，而重新調(diào)度。而被阻塞放棄處理機(jī)，而重新調(diào)度。4.2.2 4.2.2 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 4.2.2 4.2.2 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)

30、先調(diào)度算法 優(yōu)點(diǎn)：優(yōu)點(diǎn)：l比比FCFSFCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間；待時(shí)間；l提高系統(tǒng)的吞吐量；提高系統(tǒng)的吞吐量；缺點(diǎn)：缺點(diǎn)：l對(duì)長(zhǎng)作業(yè)非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行；對(duì)長(zhǎng)作業(yè)非常不利，可能長(zhǎng)時(shí)間得不到執(zhí)行；l未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；未能依據(jù)作業(yè)的緊迫程度來(lái)劃分執(zhí)行的優(yōu)先級(jí)；l難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。4.2.2 4.2.2 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 一一基本原理基本原理時(shí)間片輪轉(zhuǎn)時(shí)間片

31、輪轉(zhuǎn)Round-RobinRound-Robin（RRRR）調(diào)度算法調(diào)度算法將系統(tǒng)中所有的將系統(tǒng)中所有的就緒進(jìn)程按照就緒進(jìn)程按照FCFSFCFS原則，排成一個(gè)隊(duì)列。原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將每次調(diào)度時(shí)將CPUCPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長(zhǎng)度從幾個(gè)。時(shí)間片的長(zhǎng)度從幾個(gè)msms到幾百到幾百msms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，等待分配下一時(shí)等待分配下一時(shí)間片再執(zhí)行。間片再執(zhí)行。然后把處理

32、機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓然后把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片處理機(jī)執(zhí)行時(shí)間。在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片處理機(jī)執(zhí)行時(shí)間。 在在RRRR算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響。算法中，時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響。4.2.3 4.2.3 時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法 二二時(shí)間片時(shí)間片大小的確定大小的確定1.1.時(shí)間片長(zhǎng)度變化的影響時(shí)間片長(zhǎng)度變化的影響l過(guò)長(zhǎng)過(guò)長(zhǎng) 退化為退化為FCFSFCFS算法，進(jìn)程在一

33、個(gè)時(shí)間片內(nèi)都執(zhí)行完，響算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。應(yīng)時(shí)間長(zhǎng)。l過(guò)短過(guò)短 用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，進(jìn)程切用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，進(jìn)程切換次數(shù)增加，系統(tǒng)開(kāi)銷增大，響應(yīng)時(shí)間長(zhǎng)。換次數(shù)增加，系統(tǒng)開(kāi)銷增大，響應(yīng)時(shí)間長(zhǎng)。2.2.考慮因素考慮因素l對(duì)響應(yīng)時(shí)間的要求對(duì)響應(yīng)時(shí)間的要求T(T(響應(yīng)時(shí)間響應(yīng)時(shí)間)=N()=N(進(jìn)程數(shù)目進(jìn)程數(shù)目) )* *q(q(時(shí)間片時(shí)間片) )l就緒進(jìn)程的數(shù)目就緒進(jìn)程的數(shù)目數(shù)目越多，時(shí)間片越?。ó?dāng)響應(yīng)時(shí)間一定時(shí)）數(shù)目越多，時(shí)間片越小（當(dāng)響應(yīng)時(shí)間一定時(shí)）l系統(tǒng)的處理能力系統(tǒng)的處理能力應(yīng)當(dāng)使用戶輸入應(yīng)當(dāng)使用戶輸入的常用命令的常用命令通

34、常在一個(gè)時(shí)間片內(nèi)能處理完，否通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。4.2.3 4.2.3 時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法 優(yōu)先權(quán)優(yōu)先權(quán)( (PriorityPriority) )調(diào)度算法的基本思想是系統(tǒng)為每個(gè)進(jìn)程調(diào)度算法的基本思想是系統(tǒng)為每個(gè)進(jìn)程設(shè)置一個(gè)優(yōu)先數(shù)（對(duì)應(yīng)一個(gè)優(yōu)先級(jí)），把所有的就緒進(jìn)程按優(yōu)設(shè)置一個(gè)優(yōu)先數(shù)（對(duì)應(yīng)一個(gè)優(yōu)先級(jí)），把所有的就緒進(jìn)程按優(yōu)先級(jí)從高到低排序，調(diào)度時(shí)從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)先級(jí)從高到低排序，調(diào)度時(shí)從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)程投入運(yùn)行。程投入運(yùn)行。 一一優(yōu)先權(quán)調(diào)度

35、算法的類型優(yōu)先權(quán)調(diào)度算法的類型1.1.非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法僅當(dāng)占用僅當(dāng)占用CPUCPU的進(jìn)程運(yùn)行結(jié)束或因某種原因不能繼續(xù)運(yùn)的進(jìn)程運(yùn)行結(jié)束或因某種原因不能繼續(xù)運(yùn)行時(shí)，系統(tǒng)才進(jìn)行重新調(diào)度。行時(shí)，系統(tǒng)才進(jìn)行重新調(diào)度。 進(jìn)程切換次數(shù)少，系統(tǒng)開(kāi)銷小，但可能導(dǎo)致優(yōu)先級(jí)低進(jìn)程切換次數(shù)少，系統(tǒng)開(kāi)銷小，但可能導(dǎo)致優(yōu)先級(jí)低的進(jìn)程長(zhǎng)期搶占不到的進(jìn)程長(zhǎng)期搶占不到CPUCPU。主要用于批處理、實(shí)時(shí)性不高的實(shí)時(shí)系統(tǒng)。主要用于批處理、實(shí)時(shí)性不高的實(shí)時(shí)系統(tǒng)。4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法1.1.搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法當(dāng)系統(tǒng)中有另一優(yōu)先級(jí)更高的進(jìn)程變成就緒狀態(tài)時(shí)，當(dāng)系統(tǒng)中有另一優(yōu)

36、先級(jí)更高的進(jìn)程變成就緒狀態(tài)時(shí)，系統(tǒng)應(yīng)立即剝奪現(xiàn)運(yùn)行進(jìn)程占用系統(tǒng)應(yīng)立即剝奪現(xiàn)運(yùn)行進(jìn)程占用CPUCPU的權(quán)力，使該優(yōu)先級(jí)更的權(quán)力，使該優(yōu)先級(jí)更高的進(jìn)程投入運(yùn)行。高的進(jìn)程投入運(yùn)行。 系統(tǒng)能及時(shí)處理緊急事件，但系統(tǒng)開(kāi)銷較大。系統(tǒng)能及時(shí)處理緊急事件，但系統(tǒng)開(kāi)銷較大。主要用于實(shí)時(shí)性高的實(shí)時(shí)系統(tǒng)、性能高的批處理以及主要用于實(shí)時(shí)性高的實(shí)時(shí)系統(tǒng)、性能高的批處理以及分時(shí)系統(tǒng)。分時(shí)系統(tǒng)。4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法二二優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型1.1.靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且規(guī)定它在進(jìn)程靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且規(guī)定它在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般，優(yōu)

37、先權(quán)是利用某一范圍的整個(gè)運(yùn)行期間保持不變。一般，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來(lái)表示。例如，內(nèi)的一個(gè)整數(shù)來(lái)表示。例如，0 07 7，或，或0 0255255中的某一整中的某一整數(shù)，又稱該整數(shù)為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)數(shù)，又稱該整數(shù)為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用用“0”0”表示優(yōu)先權(quán)最高，數(shù)值愈大其優(yōu)先權(quán)愈低；而有的表示優(yōu)先權(quán)最高，數(shù)值愈大其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。系統(tǒng)恰恰相反。4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法確定進(jìn)程優(yōu)先權(quán)的依據(jù)有：確定進(jìn)程優(yōu)先權(quán)的依據(jù)有：（1 1）進(jìn)程類型。通常，系統(tǒng)進(jìn)程（如接收進(jìn)程、對(duì)換進(jìn)）進(jìn)程類型。通常，系統(tǒng)進(jìn)程（如接收進(jìn)程

38、、對(duì)換進(jìn)程、磁盤(pán)程、磁盤(pán)I/OI/O進(jìn)程）的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)進(jìn)程）的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。（2 2）進(jìn)程對(duì)資源的需求。如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存）進(jìn)程對(duì)資源的需求。如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。（3 3）根據(jù)用戶要求。這是由用戶進(jìn)程的緊迫程度及用戶）根據(jù)用戶要求。這是由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來(lái)確定進(jìn)程的優(yōu)先權(quán)。所付費(fèi)用的多少來(lái)確定進(jìn)程的優(yōu)先權(quán)。靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行、系統(tǒng)開(kāi)銷小，但不夠精確，很可靜態(tài)優(yōu)先權(quán)法簡(jiǎn)單易行、系統(tǒng)開(kāi)銷小，但不夠精確，很可能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進(jìn)程），長(zhǎng)期沒(méi)有被調(diào)度的

39、情況，因能出現(xiàn)優(yōu)先權(quán)低的作業(yè)（進(jìn)程），長(zhǎng)期沒(méi)有被調(diào)度的情況，因此，僅在要求不太高的系統(tǒng)中，才使用靜態(tài)優(yōu)先權(quán)。此，僅在要求不太高的系統(tǒng)中，才使用靜態(tài)優(yōu)先權(quán)。4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法2.2.動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨動(dòng)態(tài)優(yōu)先權(quán)是指在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，可以隨進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。進(jìn)程的推進(jìn)而改變，以便獲得更好的調(diào)度性能。l在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低在就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；的進(jìn)程在等待足夠的

40、時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；l進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓行時(shí)，其優(yōu)先級(jí)降低到出讓CPUCPU。4.2.4 4.2.4 優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法4.2.5 4.2.5 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 在批處理系統(tǒng)中，用以作業(yè)調(diào)度的短作業(yè)優(yōu)先算法是一個(gè)在批處理系統(tǒng)中，用以作業(yè)調(diào)度的短作業(yè)優(yōu)先算法是一個(gè)比較好的算法。其主要缺點(diǎn)是比較好的算法。其主要缺點(diǎn)是長(zhǎng)長(zhǎng)作業(yè)的運(yùn)行得不到保證。如果我作業(yè)的運(yùn)行得不到保證。如果我們能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)機(jī)制，并使之以速率們

41、能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)機(jī)制，并使之以速率a a增加，則長(zhǎng)作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理增加，則長(zhǎng)作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)，即機(jī)，即高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先 Highest Response Ratio Next Highest Response Ratio Next (HRRN)(HRRN)( (作業(yè)作業(yè)) )調(diào)度算法，調(diào)度算法，該優(yōu)先權(quán)的變化可描述為：該優(yōu)先權(quán)的變化可描述為：由于等待時(shí)間加上要求服務(wù)時(shí)間，就是系統(tǒng)對(duì)該作業(yè)的響由于等待時(shí)間加上要求服務(wù)時(shí)間，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RpR

42、p。據(jù)此，又可表示為。據(jù)此，又可表示為: :HRRNHRRN算法實(shí)際上是算法實(shí)際上是FCFSFCFS算法和算法和STFSTF算法的折衷算法的折衷。4.2.5 4.2.5 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 作業(yè)號(hào)ABCDE平均到達(dá)時(shí)間01234運(yùn)行時(shí)間43524完成時(shí)間4 7 12 14 18 周轉(zhuǎn)時(shí)間461011149FCFS帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8完成時(shí)間4 9 186 13周轉(zhuǎn)時(shí)間4816398SJF帶權(quán)周轉(zhuǎn)時(shí)間22.673.21.52.252.1完成時(shí)間1512189 17周轉(zhuǎn)時(shí)4RR帶權(quán)周轉(zhuǎn)時(shí)間3.753.673.233.253.37完成時(shí)

43、間4 7 149 18周轉(zhuǎn)時(shí)間46126148.4HRRN帶權(quán)周轉(zhuǎn)時(shí)間122.433.52.384.2.5 4.2.5 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先( (HRRN)(HRRN)(作業(yè)作業(yè)) )調(diào)度算法計(jì)算：調(diào)度算法計(jì)算： T=0T=0：只有作業(yè)只有作業(yè)A A已到達(dá)，調(diào)度作業(yè)已到達(dá)，調(diào)度作業(yè)A A運(yùn)行運(yùn)行。 T=4T=4：作業(yè)作業(yè)A A完成，作業(yè)完成，作業(yè)B B、C C、D D、E E已到達(dá)，計(jì)算作業(yè)已到達(dá)，計(jì)算作業(yè)B B、C C、D D、E E響應(yīng)比響應(yīng)比R RP P分別為：分別為： 1+3/3 1+3/3、1+2/51+2/5、1+1/21+1/2、1+

44、0/41+0/4，作業(yè)作業(yè)B B響應(yīng)比最大調(diào)度運(yùn)行。響應(yīng)比最大調(diào)度運(yùn)行。 T=7T=7：作業(yè)作業(yè)B B完成，作業(yè)完成，作業(yè)C C、D D、E E已到達(dá)，計(jì)算作業(yè)已到達(dá)，計(jì)算作業(yè)C C、D D、E E響響應(yīng)比應(yīng)比R RP P分別為：分別為： 1+5/5 1+5/5、1+4/21+4/2、1+3/41+3/4，作業(yè)，作業(yè)D D響應(yīng)比最響應(yīng)比最大調(diào)度運(yùn)行。大調(diào)度運(yùn)行。 T=9T=9：作業(yè)作業(yè)D D完成，作業(yè)完成，作業(yè)C C、E E已到達(dá)，計(jì)算作業(yè)已到達(dá)，計(jì)算作業(yè)C C、E E響應(yīng)比響應(yīng)比R RP P分別為：分別為： 1+7/5 1+7/5、1+5/41+5/4，作業(yè)，作業(yè)C C響應(yīng)比最大調(diào)度運(yùn)行。響

45、應(yīng)比最大調(diào)度運(yùn)行。 T=14T=14：作業(yè)作業(yè)C C完成，只有作業(yè)完成，只有作業(yè)E E未完成，調(diào)度作業(yè)未完成，調(diào)度作業(yè)E E運(yùn)行運(yùn)行。 4.2.6 4.2.6 多級(jí)隊(duì)列調(diào)度算法多級(jí)隊(duì)列調(diào)度算法 多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將就緒隊(duì)列再分為若干多隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同，將就緒隊(duì)列再分為若干個(gè)子隊(duì)列，所有的作業(yè)（或進(jìn)程）按其性質(zhì)排入相應(yīng)的隊(duì)列中，而不同的就個(gè)子隊(duì)列，所有的作業(yè)（或進(jìn)程）按其性質(zhì)排入相應(yīng)的隊(duì)列中，而不同的就緒隊(duì)列采用不同的調(diào)度算法。緒隊(duì)列采用不同的調(diào)度算法。例如前后臺(tái)系統(tǒng)可以建立兩個(gè)就緒隊(duì)列，批處理作業(yè)所建立進(jìn)程進(jìn)入例如前后臺(tái)系統(tǒng)可以建立兩個(gè)就緒隊(duì)列，批處理

46、作業(yè)所建立進(jìn)程進(jìn)入后臺(tái)就緒隊(duì)列；交互型作業(yè)所建立的進(jìn)程進(jìn)入前臺(tái)就緒隊(duì)列。前臺(tái)采用時(shí)間后臺(tái)就緒隊(duì)列；交互型作業(yè)所建立的進(jìn)程進(jìn)入前臺(tái)就緒隊(duì)列。前臺(tái)采用時(shí)間片輪轉(zhuǎn)算法，進(jìn)程按片輪轉(zhuǎn)算法，進(jìn)程按FCFSFCFS等策略排序，后臺(tái)采用優(yōu)先權(quán)高優(yōu)先的調(diào)度算法或等策略排序，后臺(tái)采用優(yōu)先權(quán)高優(yōu)先的調(diào)度算法或者短作業(yè)優(yōu)先的調(diào)度算法。者短作業(yè)優(yōu)先的調(diào)度算法。對(duì)多級(jí)就緒隊(duì)列調(diào)度策略有兩種，一種是各就緒隊(duì)列按進(jìn)程性質(zhì)賦予對(duì)多級(jí)就緒隊(duì)列調(diào)度策略有兩種，一種是各就緒隊(duì)列按進(jìn)程性質(zhì)賦予不同的優(yōu)先權(quán)，優(yōu)先權(quán)高的就緒隊(duì)列的進(jìn)程優(yōu)先被調(diào)度，例如上例中前臺(tái)就不同的優(yōu)先權(quán)，優(yōu)先權(quán)高的就緒隊(duì)列的進(jìn)程優(yōu)先被調(diào)度，例如上例中前臺(tái)就緒隊(duì)列的優(yōu)

47、先權(quán)比后臺(tái)就緒隊(duì)列的優(yōu)先權(quán)高，所以前臺(tái)隊(duì)列中的進(jìn)程優(yōu)先被緒隊(duì)列的優(yōu)先權(quán)比后臺(tái)就緒隊(duì)列的優(yōu)先權(quán)高，所以前臺(tái)隊(duì)列中的進(jìn)程優(yōu)先被調(diào)度。而只有當(dāng)優(yōu)先權(quán)高的就緒隊(duì)列空時(shí)，方才調(diào)度優(yōu)先權(quán)其次的就緒隊(duì)列調(diào)度。而只有當(dāng)優(yōu)先權(quán)高的就緒隊(duì)列空時(shí)，方才調(diào)度優(yōu)先權(quán)其次的就緒隊(duì)列進(jìn)程，在上例中只有前臺(tái)隊(duì)列空時(shí)，才調(diào)度后臺(tái)就緒隊(duì)列。這樣，只有較高進(jìn)程，在上例中只有前臺(tái)隊(duì)列空時(shí)，才調(diào)度后臺(tái)就緒隊(duì)列。這樣，只有較高優(yōu)先權(quán)的就緒隊(duì)列都空時(shí)才調(diào)度最低優(yōu)先權(quán)就緒隊(duì)列的進(jìn)程。優(yōu)先權(quán)的就緒隊(duì)列都空時(shí)才調(diào)度最低優(yōu)先權(quán)就緒隊(duì)列的進(jìn)程。 另一種調(diào)度就緒隊(duì)列的方式是為每個(gè)隊(duì)列分配一定的占用另一種調(diào)度就緒隊(duì)列的方式是為每個(gè)隊(duì)列分配一定的占用CP

48、UCPU時(shí)間的比例時(shí)間的比例。上例中為前臺(tái)隊(duì)列分配。上例中為前臺(tái)隊(duì)列分配8080的的CPUCPU時(shí)間，給后臺(tái)隊(duì)列分配時(shí)間，給后臺(tái)隊(duì)列分配2020的的CPUCPU時(shí)間。時(shí)間。4.2.7 4.2.7 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 前面介紹的各種用作進(jìn)程調(diào)度的算法，都有在一定的局限前面介紹的各種用作進(jìn)程調(diào)度的算法，都有在一定的局限性，如短進(jìn)程優(yōu)先算法僅照顧了短進(jìn)程而怠慢了長(zhǎng)進(jìn)程。況且對(duì)性，如短進(jìn)程優(yōu)先算法僅照顧了短進(jìn)程而怠慢了長(zhǎng)進(jìn)程。況且對(duì)進(jìn)程運(yùn)行的長(zhǎng)短，往往難以正確估計(jì)，所以短進(jìn)程優(yōu)先的調(diào)度算進(jìn)程運(yùn)行的長(zhǎng)短，往往難以正確估計(jì)，所以短進(jìn)程優(yōu)先的調(diào)度算法無(wú)法正確使用。法無(wú)法正確使用。而多級(jí)

49、反饋而多級(jí)反饋( (FeedbackFeedback) )隊(duì)列調(diào)度算法，則不必事先知道各隊(duì)列調(diào)度算法，則不必事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，仍能基本滿足短進(jìn)程優(yōu)先和種進(jìn)程所需的執(zhí)行時(shí)間，仍能基本滿足短進(jìn)程優(yōu)先和I/OI/O頻繁的頻繁的進(jìn)程優(yōu)先的需要，因而是目前公認(rèn)的較好的一種進(jìn)程調(diào)度算法。進(jìn)程優(yōu)先的需要，因而是目前公認(rèn)的較好的一種進(jìn)程調(diào)度算法。在在UNIXUNIX系統(tǒng)、系統(tǒng)、WindowsNTWindowsNT、OS/2OS/2中都采用了類似的調(diào)度算法中都采用了類似的調(diào)度算法4.2.7 4.2.7 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 一一調(diào)度算法調(diào)度算法1.1.設(shè)置多個(gè)就緒隊(duì)列，分別賦予

50、不同的優(yōu)先級(jí)，如逐級(jí)降低，隊(duì)列設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，如逐級(jí)降低，隊(duì)列1 1的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，規(guī)定優(yōu)先級(jí)越低則的優(yōu)先級(jí)最高。每個(gè)隊(duì)列執(zhí)行時(shí)間片的長(zhǎng)度也不同，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長(zhǎng)，如逐級(jí)加倍。時(shí)間片越長(zhǎng)，如逐級(jí)加倍。1.1.新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1 1的末尾，按的末尾，按FCFSFCFS算法調(diào)度；若按算法調(diào)度；若按隊(duì)列隊(duì)列1 1一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2 2的末尾，同樣按的末尾，同樣按FCFSFCFS算法調(diào)度；如此下去，降低到最后的隊(duì)列，則按算法調(diào)度；如此下去，

51、降低到最后的隊(duì)列，則按“時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)”算法調(diào)算法調(diào)度直到完成。度直到完成。1.1.僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾。4.2.7 4.2.7 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 就緒隊(duì)列就緒隊(duì)列1 時(shí)間片時(shí)間片S1時(shí)間片完時(shí)間片完時(shí)間片完時(shí)間片完就緒隊(duì)列就緒隊(duì)列2 時(shí)間片時(shí)間片S2S1運(yùn)行運(yùn)行運(yùn)行運(yùn)行運(yùn)行

52、運(yùn)行就緒隊(duì)列就緒隊(duì)列n 時(shí)間片時(shí)間片SnSn-1完成完成完成完成完成完成時(shí)間片完時(shí)間片完阻塞隊(duì)列阻塞隊(duì)列i阻塞阻塞阻塞阻塞阻塞阻塞事事件件發(fā)發(fā)生生4.3 4.3 實(shí)時(shí)系統(tǒng)中的調(diào)度實(shí)時(shí)系統(tǒng)中的調(diào)度 實(shí)時(shí)系統(tǒng)是指那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。通常實(shí)時(shí)系統(tǒng)是指那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。通?？煞譃橛矊?shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)?？煞譃橛矊?shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。前者是指系統(tǒng)必須滿足時(shí)間的約束。前者是指系統(tǒng)必須滿足時(shí)間的約束。后者則意味著偶爾超過(guò)時(shí)間限制也是可以容忍的。后者則意味著偶爾超過(guò)時(shí)間限制也是可以容忍的。 4.3.1 4.3.1 對(duì)實(shí)時(shí)系統(tǒng)的要求對(duì)實(shí)時(shí)系統(tǒng)的要求4.3.2 4.3.2 實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算

53、法4.3.1 4.3.1 對(duì)實(shí)時(shí)系統(tǒng)的要求對(duì)實(shí)時(shí)系統(tǒng)的要求1.1.提供必要的調(diào)度信息提供必要的調(diào)度信息如，就緒時(shí)間、開(kāi)始或完成截止時(shí)間、處理時(shí)間、資源要如，就緒時(shí)間、開(kāi)始或完成截止時(shí)間、處理時(shí)間、資源要求、絕對(duì)或相對(duì)優(yōu)先級(jí)（硬實(shí)時(shí)或軟實(shí)時(shí)）。求、絕對(duì)或相對(duì)優(yōu)先級(jí)（硬實(shí)時(shí)或軟實(shí)時(shí)）。二二調(diào)度方式調(diào)度方式采用搶先式調(diào)度。采用搶先式調(diào)度。三三快速中斷響應(yīng)快速中斷響應(yīng)在中斷處理時(shí)（硬件）關(guān)中斷的時(shí)間盡量短。在中斷處理時(shí)（硬件）關(guān)中斷的時(shí)間盡量短。四四快速上下文切換快速上下文切換相應(yīng)地采用較小的調(diào)度單位（如線程）。相應(yīng)地采用較小的調(diào)度單位（如線程）。4.3.2 4.3.2 實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法1.1

54、.時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法2.2.非搶占優(yōu)先級(jí)調(diào)度算法非搶占優(yōu)先級(jí)調(diào)度算法3.3.基于時(shí)鐘中斷搶占的優(yōu)先級(jí)調(diào)度算法基于時(shí)鐘中斷搶占的優(yōu)先級(jí)調(diào)度算法4.4.立即搶占的優(yōu)先級(jí)調(diào)度算法立即搶占的優(yōu)先級(jí)調(diào)度算法4.4 4.4 多處理機(jī)調(diào)度多處理機(jī)調(diào)度 4.4.1 4.4.1 與單處理機(jī)調(diào)度的區(qū)別與單處理機(jī)調(diào)度的區(qū)別4.4.2 4.4.2 對(duì)稱式多處理系統(tǒng)對(duì)稱式多處理系統(tǒng)(SMP)(SMP)4.4.3 4.4.3 非對(duì)稱式多處理系統(tǒng)非對(duì)稱式多處理系統(tǒng)(ASMP)(ASMP)的處理機(jī)調(diào)的處理機(jī)調(diào) 度度4.4.4 4.4.4 成組調(diào)度成組調(diào)度(Gang Scheduling)(Gang Sche

55、duling)4.4.5 4.4.5 專用處理機(jī)調(diào)度專用處理機(jī)調(diào)度(Dedicated Processor (Dedicated Processor Assignment) Assignment)4.4.1 4.4.1 與單處理機(jī)調(diào)度的區(qū)別與單處理機(jī)調(diào)度的區(qū)別一一注重整體運(yùn)行效率（而不是個(gè)別處理機(jī)的利用率）注重整體運(yùn)行效率（而不是個(gè)別處理機(jī)的利用率）二二更多樣的調(diào)度算法更多樣的調(diào)度算法三三多處理機(jī)訪問(wèn)多處理機(jī)訪問(wèn)OSOS數(shù)據(jù)結(jié)構(gòu)時(shí)的互斥（對(duì)于共享內(nèi)存數(shù)據(jù)結(jié)構(gòu)時(shí)的互斥（對(duì)于共享內(nèi)存系統(tǒng)）系統(tǒng)）四四調(diào)度單位廣泛采用線程調(diào)度單位廣泛采用線程4.4.2 4.4.2 對(duì)稱式多處理系統(tǒng)對(duì)稱式多處理系統(tǒng)(S

56、MP)(SMP)按控制方式，按控制方式，SMPSMP調(diào)度算法可分為集中控制和分散控制。下調(diào)度算法可分為集中控制和分散控制。下面所述靜態(tài)和動(dòng)態(tài)調(diào)度都是集中控制，而自調(diào)度是分散控制。面所述靜態(tài)和動(dòng)態(tài)調(diào)度都是集中控制，而自調(diào)度是分散控制。一一 靜態(tài)分配靜態(tài)分配(static assignment)(static assignment)：每個(gè)：每個(gè)CPUCPU設(shè)立一個(gè)就緒隊(duì)設(shè)立一個(gè)就緒隊(duì)列，進(jìn)程從開(kāi)始執(zhí)行到完成，都在同一個(gè)列，進(jìn)程從開(kāi)始執(zhí)行到完成，都在同一個(gè)CPUCPU上。上。1.1.優(yōu)點(diǎn)：調(diào)度算法開(kāi)銷小。優(yōu)點(diǎn)：調(diào)度算法開(kāi)銷小。2.2.缺點(diǎn)：容易出現(xiàn)忙閑不均。缺點(diǎn)：容易出現(xiàn)忙閑不均。二二 動(dòng)態(tài)分配動(dòng)態(tài)

57、分配(dynamic assignment)(dynamic assignment)：各個(gè)：各個(gè)CPUCPU采用一個(gè)公共就采用一個(gè)公共就緒隊(duì)列，隊(duì)首進(jìn)程每次分派到當(dāng)前空閑的緒隊(duì)列，隊(duì)首進(jìn)程每次分派到當(dāng)前空閑的CPUCPU上執(zhí)行。上執(zhí)行。三三 分散控制分散控制自調(diào)度自調(diào)度(self-scheduling)(self-scheduling)：各個(gè)：各個(gè)CPUCPU采用一個(gè)公共就緒隊(duì)采用一個(gè)公共就緒隊(duì)列，每個(gè)處理機(jī)都可以從隊(duì)列中選擇適當(dāng)進(jìn)程來(lái)執(zhí)行。需要對(duì)就列，每個(gè)處理機(jī)都可以從隊(duì)列中選擇適當(dāng)進(jìn)程來(lái)執(zhí)行。需要對(duì)就緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)進(jìn)行互斥訪問(wèn)控制。是最常用的算法，實(shí)現(xiàn)時(shí)緒隊(duì)列的數(shù)據(jù)結(jié)構(gòu)進(jìn)行互斥訪問(wèn)控制。

58、是最常用的算法，實(shí)現(xiàn)時(shí)易于移植采用單處理機(jī)的調(diào)度技術(shù)。易于移植采用單處理機(jī)的調(diào)度技術(shù)。4.4.3 4.4.3 非對(duì)稱式多處理系統(tǒng)非對(duì)稱式多處理系統(tǒng)(ASMP)(ASMP)1.1.主從處理機(jī)系統(tǒng)，由主處理機(jī)管理一個(gè)公共就緒隊(duì)列，主從處理機(jī)系統(tǒng)，由主處理機(jī)管理一個(gè)公共就緒隊(duì)列，并分派進(jìn)程給從處理機(jī)執(zhí)行。并分派進(jìn)程給從處理機(jī)執(zhí)行。2.2.各個(gè)處理機(jī)有固定分工，如執(zhí)行各個(gè)處理機(jī)有固定分工，如執(zhí)行OSOS的系統(tǒng)功能，的系統(tǒng)功能，I/OI/O處理，處理，應(yīng)用程序。應(yīng)用程序。4.4.4 4.4.4 成組調(diào)度成組調(diào)度(gang scheduling)(gang scheduling)將一個(gè)進(jìn)程中的一組線程，每

59、次分派時(shí)同時(shí)到一組處理機(jī)將一個(gè)進(jìn)程中的一組線程，每次分派時(shí)同時(shí)到一組處理機(jī)上執(zhí)行，在剝奪處理機(jī)時(shí)也同時(shí)對(duì)這一組線程進(jìn)行。上執(zhí)行，在剝奪處理機(jī)時(shí)也同時(shí)對(duì)這一組線程進(jìn)行。優(yōu)點(diǎn)優(yōu)點(diǎn): :1.1.通常這樣的一組線程在應(yīng)用邏輯上相互合作，成組調(diào)度通常這樣的一組線程在應(yīng)用邏輯上相互合作，成組調(diào)度提高了這些線程的執(zhí)行并行度，有利于減少阻塞和加快提高了這些線程的執(zhí)行并行度，有利于減少阻塞和加快推進(jìn)速度，最終提高系統(tǒng)吞吐量。推進(jìn)速度，最終提高系統(tǒng)吞吐量。2.2.每次調(diào)度可以完成多個(gè)線程的分派，在系統(tǒng)內(nèi)線程總數(shù)每次調(diào)度可以完成多個(gè)線程的分派，在系統(tǒng)內(nèi)線程總數(shù)相同時(shí)能夠減少調(diào)度次數(shù)，從而減少調(diào)度算法的開(kāi)銷相同時(shí)能夠

60、減少調(diào)度次數(shù)，從而減少調(diào)度算法的開(kāi)銷4.4.54.4.5 專用處理機(jī)調(diào)度專用處理機(jī)調(diào)度(dedicated processor assignment)(dedicated processor assignment)為進(jìn)程中的每個(gè)線程都固定分配一個(gè)為進(jìn)程中的每個(gè)線程都固定分配一個(gè)CPUCPU，直到該線程執(zhí)行，直到該線程執(zhí)行完成。完成。缺點(diǎn)：線程阻塞時(shí)，造成缺點(diǎn)：線程阻塞時(shí)，造成CPUCPU的閑置。優(yōu)點(diǎn)：線程執(zhí)行時(shí)不需切的閑置。優(yōu)點(diǎn)：線程執(zhí)行時(shí)不需切換，相應(yīng)的開(kāi)銷可以大大減小，推進(jìn)速度更快。換，相應(yīng)的開(kāi)銷可以大大減小，推進(jìn)速度更快。適用場(chǎng)合：適用場(chǎng)合：CPUCPU數(shù)量眾多的高度并行系統(tǒng)，單個(gè)數(shù)量眾