第十八講處理器調(diào)度算法(下)

教學(xué)目的讓學(xué)生掌握常用的實(shí)時(shí)調(diào)度算法讓學(xué)生掌握常用的多處理器調(diào)度算法教學(xué)重點(diǎn)單比率調(diào)度算法、限期調(diào)度算法、最少裕度調(diào)度算法多處理機(jī)調(diào)度算法的設(shè)計(jì)要點(diǎn)負(fù)載共享調(diào)度算法，群調(diào)度算法教學(xué)難點(diǎn)多處理機(jī)調(diào)度算法的設(shè)計(jì)要點(diǎn)2.8處理器調(diào)度算法（下）2.8處理器調(diào)度算法2.8.1低級(jí)調(diào)度的功能和類型2.8.2作業(yè)調(diào)度和低級(jí)調(diào)度算法2.8.3實(shí)時(shí)調(diào)度算法2.8.4多處理機(jī)調(diào)度算法

2.8.3

實(shí)時(shí)調(diào)度算法

實(shí)時(shí)系統(tǒng)是那些時(shí)間因素非常關(guān)鍵的系統(tǒng)。實(shí)時(shí)系統(tǒng)包括監(jiān)控系統(tǒng)、自動(dòng)駕駛系統(tǒng)、安全控制系統(tǒng)等，這些系統(tǒng)中，遲到的響應(yīng)即使正確，也和沒有響應(yīng)一樣糟糕。硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)通常分為硬實(shí)時(shí)系統(tǒng)和軟實(shí)時(shí)系統(tǒng)。前者意味著存在必須滿足的時(shí)間限制；后者意味著偶爾超過時(shí)間限制時(shí)可以容忍的。

周期性和非周期性事件實(shí)時(shí)系統(tǒng)響應(yīng)的事件可劃分為周期性事件和非周期性事件。例如，m個(gè)周期性事件，事件i的周期為Pi，每個(gè)事件需要Ci秒的CPU時(shí)間來處理，則只有滿足以下條件：

C1/P1+C2/P2+…+Cm/Pm≤1

時(shí)，才可能處理所有的負(fù)載。滿足該條件的實(shí)時(shí)系統(tǒng)稱作任務(wù)可調(diào)度的。

實(shí)時(shí)調(diào)度算法(1)

1）單比率調(diào)度算法基本思想：為每個(gè)進(jìn)程分配一個(gè)與事件發(fā)生頻率成正比的優(yōu)先數(shù)。例如，周期為20ms的進(jìn)程優(yōu)先數(shù)為50，周期為100ms的進(jìn)程優(yōu)先數(shù)為10，運(yùn)行時(shí)調(diào)度程序總是調(diào)度優(yōu)先數(shù)最高的就緒進(jìn)程，并采取搶占式分配策略。實(shí)時(shí)調(diào)度算法(2)

2）限期調(diào)度算法

基本思想：當(dāng)一個(gè)事件發(fā)生時(shí)，對應(yīng)的進(jìn)程就按照截止期限被加入就緒進(jìn)程隊(duì)列。對于一個(gè)周期性事件，其截止期限即為事件下一次發(fā)生的時(shí)間。該調(diào)度算法首先運(yùn)行隊(duì)首進(jìn)程，即截止時(shí)間最近的那個(gè)進(jìn)程。實(shí)時(shí)調(diào)度算法(3)

3）最少裕度法

基本思想：首先計(jì)算各個(gè)進(jìn)程的富裕時(shí)間，即裕度（laxity），然后選擇裕度最少的進(jìn)程執(zhí)行。裕度=截止時(shí)間-(就緒時(shí)間+計(jì)算時(shí)間)2.8.4

多處理器調(diào)度

1多處理機(jī)調(diào)度的設(shè)計(jì)要點(diǎn)

1)如何為進(jìn)程分配處理機(jī)

2)在單個(gè)處理機(jī)上是否使用多道程序設(shè)計(jì)技術(shù)

3)如何實(shí)際指派進(jìn)程如何為進(jìn)程分配處理機(jī)CPU1CPU2CPU3...CPUn就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3...就緒隊(duì)列n靜態(tài)分配法CPU1CPU2CPU3...CPUn就緒隊(duì)列...動(dòng)態(tài)分配法一個(gè)程序的多個(gè)線程同時(shí)在多個(gè)處理機(jī)上運(yùn)行（性能佳）在單個(gè)處理機(jī)上運(yùn)行單個(gè)程序，讓其線程多道運(yùn)行在單個(gè)處理機(jī)上是否使用多道程序設(shè)計(jì)技術(shù)不再采用復(fù)雜的調(diào)度算法，而采用簡單的優(yōu)先數(shù)法或FCFS算法如何實(shí)際指派進(jìn)程多處理器調(diào)度算法(1)1）負(fù)載共享調(diào)度算法

基本思想：進(jìn)程并不指派到特定處理機(jī)上，系統(tǒng)維護(hù)全局性進(jìn)程就緒隊(duì)列，當(dāng)處理機(jī)空閑時(shí)，就選擇進(jìn)程的一個(gè)線程去運(yùn)行。優(yōu)點(diǎn)：負(fù)載均衡，不須集中調(diào)度缺點(diǎn)：就緒隊(duì)列必須被互斥訪問，被剝奪線程很難在原處理機(jī)上運(yùn)行，一個(gè)進(jìn)程的所有線程未必能同時(shí)獲得處理機(jī)多處理器調(diào)度算法(2)2）群調(diào)度算法

基本思想：一群相關(guān)線程基于一對一的原則，被同時(shí)調(diào)度到一組處理機(jī)上運(yùn)行。它具有的優(yōu)點(diǎn)：

?當(dāng)緊密相關(guān)的進(jìn)程同時(shí)執(zhí)行時(shí)，同步造成的等待將減少，進(jìn)程切換也相應(yīng)減少，系統(tǒng)性能得到提高。

?由于一次性同時(shí)調(diào)度一組處理器，調(diào)度的代價(jià)也將減少。

群調(diào)度的例子

統(tǒng)一劃分進(jìn)程1進(jìn)程2空閑空閑空閑浪費(fèi)時(shí)間37.5%浪費(fèi)時(shí)間15%空閑空閑空閑50%50%80%20%例：4個(gè)處理機(jī)，2個(gè)進(jìn)程，進(jìn)程1有4個(gè)線程，進(jìn)程2有1個(gè)線程。

加權(quán)劃分進(jìn)程1進(jìn)程2多處理器調(diào)度算法(3)

3）處理器專派調(diào)度算法基本思想：給同屬一個(gè)進(jìn)程的一組線程，同時(shí)分派到一組處理機(jī)上運(yùn)行，每個(gè)線程獲得一個(gè)處理機(jī)，且它專用于處理這個(gè)線程，直到進(jìn)程運(yùn)行結(jié)束，這是群調(diào)度的一種極端形式。采用這一算法，處理器將不適用多道程序設(shè)計(jì)，即該應(yīng)用的一個(gè)線程阻塞后，線程對應(yīng)的處理器不會(huì)被調(diào)度給其他線程，而處于空閑狀態(tài)。多處理器調(diào)度算法(4)

4）動(dòng)態(tài)調(diào)度算法(1)

基本思想：由操作系統(tǒng)和應(yīng)用進(jìn)程共同完成調(diào)度。操作系統(tǒng)負(fù)責(zé)在應(yīng)用進(jìn)程之間劃分處理器。應(yīng)用進(jìn)程在分配給它的處理器上執(zhí)行可運(yùn)行線程的子集，哪一些線程應(yīng)該執(zhí)行，哪一些線程應(yīng)該掛起完全是應(yīng)用進(jìn)程自己的事。多處理器調(diào)度算法(5)

動(dòng)態(tài)調(diào)度算法(2)

?

如果有空閑處理器，滿足要求。否則，對新到達(dá)進(jìn)程，從當(dāng)前分配了一個(gè)以上處理器的進(jìn)程中收回一個(gè)，并把它分