1、3. 實(shí)時(shí)調(diào)度,實(shí)時(shí)系統(tǒng)例子：實(shí)驗(yàn)控制、過程控制設(shè)備、機(jī)器人、空中交通管制、遠(yuǎn)程通信、軍事指揮與控制系統(tǒng)，下一代系統(tǒng)還包括自動(dòng)駕駛汽車、具有彈性關(guān)節(jié)的機(jī)器人控制器、智能化生產(chǎn)中的系統(tǒng)查找、空間站和海底勘探。 每種實(shí)時(shí)系統(tǒng)都有若干個(gè)實(shí)時(shí)進(jìn)程，來反應(yīng)或控制某個(gè)外部事件，它們往往帶有某種程度的緊迫性，需要實(shí)時(shí)系統(tǒng)的調(diào)度有特殊處理，所以引入實(shí)時(shí)調(diào)度。,3. 實(shí)時(shí)調(diào)度,3. 實(shí)時(shí)調(diào)度,實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,提供必要的信息,開始/完成截止時(shí)間 就緒時(shí)間 處理時(shí)間 資源要求 優(yōu)先級(jí),3. 實(shí)時(shí)調(diào)度,實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,系統(tǒng)處理能力強(qiáng),有6個(gè)周期性的硬實(shí)時(shí)任務(wù)，處理時(shí)間都為10ms，周期時(shí)間都為50ms

2、，判斷實(shí)時(shí)系統(tǒng)是否可調(diào)度？,假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，處理時(shí)間為Ci，周期時(shí)間為Pi (1i m)。 單處理機(jī)下必須滿足：,3. 實(shí)時(shí)調(diào)度,實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,思考：提高實(shí)時(shí)系統(tǒng)處理能力的方法？,為多處理機(jī)（N個(gè)）時(shí)，限制條件變?yōu)椋?3. 實(shí)時(shí)調(diào)度,實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件,采用搶占式調(diào)度機(jī)制（硬實(shí)時(shí)系統(tǒng)） 具有快速切換機(jī)制,對(duì)外部中斷的快速響應(yīng)能力 要求快速硬件中斷機(jī)構(gòu)、允許中斷的間隔短 快速的任務(wù)分派能力 系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?3. 實(shí)時(shí)調(diào)度,實(shí)時(shí)調(diào)度算法的分類,根據(jù)實(shí)時(shí)任務(wù)性質(zhì)不同可分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度； 根據(jù)調(diào)度方式不同可分非搶占調(diào)度和搶占調(diào)度算法； 根據(jù)

3、調(diào)度時(shí)間的不同分成靜態(tài)和動(dòng)態(tài)調(diào)度算法； 在多處理機(jī)情況下可分為集中式和分布式調(diào)度算法。,3. 實(shí)時(shí)調(diào)度,實(shí)時(shí)調(diào)度算法的分類,非搶占式調(diào)度算法 非搶占式輪轉(zhuǎn)調(diào)度算法 非搶占式優(yōu)先調(diào)度算法 搶占式調(diào)度算法 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 立即搶占的優(yōu)先權(quán)調(diào)度算法,3. 實(shí)時(shí)調(diào)度,非搶占式輪轉(zhuǎn)調(diào)度算法,響應(yīng)時(shí)間在幾秒到數(shù)十秒 之間。 應(yīng)用于不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)，比如工業(yè)生產(chǎn)的群控系統(tǒng)。,Round-robin Non-preemptive Scheduler,3. 實(shí)時(shí)調(diào)度,非搶占式優(yōu)先調(diào)度算法,當(dāng)實(shí)時(shí)任務(wù)到達(dá)，放在就緒隊(duì)列隊(duì)首，等待當(dāng)前任務(wù)的自我終止或運(yùn)行完成。 響應(yīng)時(shí)間為數(shù)百毫秒，適用于較

4、為嚴(yán)格的實(shí)時(shí)控制系統(tǒng)。,Priority-Driven Nonpreemptive Scheduler,3. 實(shí)時(shí)調(diào)度,基于時(shí)鐘中斷的 搶占式優(yōu)先權(quán)調(diào)度算法,當(dāng)優(yōu)先級(jí)高于當(dāng)前任務(wù)的實(shí)時(shí)任務(wù)到達(dá)，則等到下一個(gè)時(shí)鐘中斷，搶占當(dāng)前任務(wù)的處理機(jī)。 響應(yīng)時(shí)間為幾到數(shù)十毫秒之間，應(yīng)用于較嚴(yán)格的實(shí)時(shí)系統(tǒng)。,Priority-Driven Preemptive Scheduler on Preemption Points,3. 實(shí)時(shí)調(diào)度,立即搶占的 優(yōu)先權(quán)調(diào)度算法,一旦出現(xiàn)請(qǐng)求中斷的 緊急任務(wù)，只要當(dāng)前任務(wù)未在臨界區(qū)，立即搶占它的CPU 響應(yīng)時(shí)間為100微秒到幾毫秒之間 系統(tǒng)必須具有快速響應(yīng)外部中斷能力,Im

5、mediate Preemptive Scheduler,3. 實(shí)時(shí)調(diào)度,最早截止時(shí)間優(yōu)先算法EDF,根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)； 可用于搶占式調(diào)度和非搶占式調(diào)度。,1,3,4,2,3. 實(shí)時(shí)調(diào)度,最低松弛度優(yōu)先算法 LLF,根據(jù)任務(wù)的緊急（或松弛）程度確定任務(wù)的優(yōu)先級(jí) 松弛度必須完成的時(shí)間還需運(yùn)行的時(shí)間 當(dāng)前時(shí)間 松弛度是動(dòng)態(tài)變化的 主要用于可搶占式調(diào)度方式,3. 實(shí)時(shí)調(diào)度,最低松弛度優(yōu)先算法 LLF,必須完成時(shí)間,B1(10) B1(15) B2(5) B2(15),0 10 20 30 40 50 60 70 80,t,t1 t2 t3 t4 t5 t6 t7 t8,t1=

6、0,A1(10) A2(10) A3(10) A4(10),4. 多處理機(jī)系統(tǒng)中的調(diào)度,緊密耦合MPS和松散耦合MPS 緊密耦合MPS：通常是通過高速總線或高速交叉開關(guān)，來實(shí)現(xiàn)多個(gè)處理器之間的互連，它們共享主存儲(chǔ)器和I/O設(shè)備。 松散耦合MPS：通常是通過通道或通信線路，來實(shí)現(xiàn)多臺(tái)計(jì)算機(jī)之間的互連。,對(duì)稱MPS和非對(duì)稱MPS 根據(jù)系統(tǒng)中所用處理器的相同與否劃分： 對(duì)稱多處理器系統(tǒng)(SMPS)：在系統(tǒng)中所包含的處理器在功能和結(jié)構(gòu)上都是相同的。 非對(duì)稱多處理器系統(tǒng)：在系統(tǒng)中有多種類型的處理器單元，一主多從。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程分配方式,對(duì)稱多處理器系統(tǒng),把多處理器看成是一個(gè)處理器池。

7、 靜態(tài)分配方式（Static Assignment） 問題是：處理器會(huì)出現(xiàn)忙閑不均,一個(gè)進(jìn)程從開始執(zhí)行直至其完成，都被固定地配到一個(gè)處理器上去執(zhí)行。 每個(gè)處理器設(shè)置一個(gè)專用的就緒隊(duì)列。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程分配方式,對(duì)稱多處理器系統(tǒng),動(dòng)態(tài)分配方式（Dynamic Assignment） 優(yōu)點(diǎn)：解決了各處理器的忙閑不均現(xiàn)象 缺點(diǎn)：對(duì)于松散耦合系統(tǒng)會(huì)增加調(diào)度開銷,設(shè)置一個(gè)公共的就緒隊(duì)列，所有就緒進(jìn)程都被放在該隊(duì)列中，分配時(shí)可將進(jìn)程分配到任一處理器,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程分配方式,非對(duì)稱多處理器系統(tǒng),主/從式分配方式 優(yōu)點(diǎn)：系統(tǒng)處理比較簡(jiǎn)單、不會(huì)出現(xiàn) 處理器的忙閑不均現(xiàn)象 缺點(diǎn)

8、：具有不可靠性,OS核心部分駐留在主機(jī)，從機(jī)只是用戶程序，進(jìn)程調(diào)度由主機(jī)完成 每當(dāng)從機(jī)空閑，向主機(jī)發(fā)送索求進(jìn)程信號(hào)，等待主機(jī)為它分配進(jìn)程,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,自調(diào)度方式(Self-Scheduling),成組調(diào)度方式 (Gang Scheduling),專用處理器分配方式 (Dedicated Processor Assignment),4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,自調(diào)度方式(Self-Scheduling),在系統(tǒng)中設(shè)置有一個(gè)公共的進(jìn)程或線程就緒隊(duì)列，所有處理器在空閑時(shí)，都可自己到該隊(duì)列中取得一進(jìn)程或線程來運(yùn)行。 采用單處理器下使用的調(diào)度算

9、法，如FCFS。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,優(yōu)點(diǎn)： 系統(tǒng)中的公共就緒隊(duì)列可按單處理機(jī)系統(tǒng)所采用的各種方式加以組織； 調(diào)度算法可用單處理機(jī)系統(tǒng)所用的算法； 只要有任務(wù)，就不會(huì)出現(xiàn)處理機(jī)空閑的情況。 缺點(diǎn)：瓶頸問題、低效性、線程切換頻繁,自調(diào)度方式(Self-Scheduling),4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,成組調(diào)度方式(Gang Scheduling),將一進(jìn)程中一組線程，分配到一組處理器上去執(zhí)行,優(yōu)點(diǎn)： 一組相互合作的進(jìn)程或線程能并行執(zhí)行，可有效地減少進(jìn)/線程阻塞情況的發(fā)生，從而減少線程的切換； 每次調(diào)度可解決一組線程的處理器分配問題，因而可顯著

10、減少調(diào)度的頻率，從而減少調(diào)度開銷。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,成組調(diào)度方式(Gang Scheduling),面向所有應(yīng)用程序平均分配處理器時(shí)間 假定系統(tǒng)中有N個(gè)處理器和M個(gè)應(yīng)用程序，每個(gè) 應(yīng)用程序中至多含有N個(gè)線程，則每個(gè)應(yīng)用程序 至多可占有N個(gè)處理器的1/M時(shí)間。 面向所有線程平均分配處理器時(shí)間 假定M個(gè)應(yīng)用程序共有L個(gè)線程，則每個(gè)線程至多可占有N個(gè)處理器的1/L時(shí)間。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,成組調(diào)度方式(Gang Scheduling),1/2 1/2,4/5 1/5,面向所有應(yīng)用程序平均分配,面向所有線程平均分配,1/2*3/4 =3

11、/8=37.5%,1/5*3/4 =3/20=15%,4. 多處理機(jī)系統(tǒng)中的調(diào)度,進(jìn)程（線程）調(diào)度方式,專用處理器分配方式(Dedicated Processor Assignment),在一個(gè)應(yīng)用程序的執(zhí)行期間，專門為該應(yīng)用程序分 配一組處理器，每一個(gè)線程一個(gè)處理器，這組處理 器僅供該應(yīng)用程序?qū)Ｓ?，直至該?yīng)用程序完成。 雖然會(huì)造成處理機(jī)的嚴(yán)重浪費(fèi)，但在高度并行的系 統(tǒng)，每個(gè)處理器的利用率不是十分重要。 在同時(shí)執(zhí)行的多道應(yīng)用程序中，其線程總數(shù)不應(yīng)超過系統(tǒng)中處理機(jī)的數(shù)目。,4. 多處理機(jī)系統(tǒng)中的調(diào)度,單機(jī)雙核調(diào)度方案,是否雙核一定比單核運(yùn)行快呢？,5. 死鎖的概念,5. 死鎖的概念,例1： 兩個(gè)

12、小孩在一起玩耍，一個(gè)在玩皮球，另一個(gè)玩自動(dòng)步槍，如果這兩個(gè)小孩都要對(duì)方手中的玩具，而又不肯先放掉自己拿著的玩具，這時(shí)就發(fā)生了僵持局面。,5. 死鎖的概念,例2： 設(shè)系統(tǒng)有一臺(tái)打印機(jī)和一臺(tái)掃描儀，進(jìn)程P1、P2并發(fā)執(zhí)行，在某時(shí)刻T，進(jìn)程P1和P2分別占用了打印機(jī)和掃描儀。在時(shí)刻T1（T1T），P1又要申請(qǐng)掃描儀，但由于掃描儀被P2占用，P1只有等待。在時(shí)刻T2（T2T），P2又申請(qǐng)打印機(jī)，但由于打印機(jī)被P1占用，P2只有等待。如此兩進(jìn)程均不能執(zhí)行完成。稱這種現(xiàn)象為死鎖。,5. 死鎖的概念,一組進(jìn)程中每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，而處于的一種僵持局面，若無(wú)外力作用，它們都無(wú)法

13、向前推進(jìn)，這種現(xiàn)象稱為進(jìn)程死鎖(Deadlock)，這組進(jìn)程就稱為死鎖進(jìn)程。,5. 死鎖的概念,競(jìng)爭(zhēng)資源引起進(jìn)程死鎖 可剝奪和非可剝奪資源 可剝奪資源：進(jìn)程在獲得這個(gè)資源后可以在被其它進(jìn)程或系統(tǒng)剝奪 非可剝奪資源：資源被系統(tǒng)分配給某個(gè)進(jìn)程后就不能強(qiáng)行收回，只能進(jìn)程自己釋放 競(jìng)爭(zhēng)非可剝奪資源,5. 死鎖的概念,競(jìng)爭(zhēng)資源引起進(jìn)程死鎖 競(jìng)爭(zhēng)臨時(shí)性資源(進(jìn)程通信時(shí)),S1、S2為消息 箭頭分別為發(fā)送和接收,5. 死鎖的概念,進(jìn)程推進(jìn)順序不當(dāng)引起死鎖,P1Req(R1) P1Req(R2) P1Rel(R1) P1Rel(R2),P2Rel(R1) P2Rel(R2) P2Req(R1) P2Req(R

14、2),D,5. 死鎖的概念,不能剝奪進(jìn)程擁有資源,進(jìn)程在等待一新資源時(shí)繼續(xù)占有已分配的資源,涉及的資源是非共享的,5. 死鎖的概念,存在一種進(jìn)程的循環(huán)鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中的下一個(gè)進(jìn)程所請(qǐng)求,5. 死鎖的概念,預(yù)防死鎖(deadlock prevention) 通過設(shè)置某些限制條件，去破壞死鎖四個(gè)必要條件中的一個(gè)或多個(gè)，來防止死鎖。,較易實(shí)現(xiàn)，廣泛使用。 由于所施加的限制往往太嚴(yán)格，可能導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量的降低。,5. 死鎖的概念,避免死鎖(deadlock avoidance) 不事先采取限制去破壞產(chǎn)生死鎖的條件，而是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系

15、統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖的發(fā)生。,事先只需要較弱的限制條件，可獲得較高的資源利用率和系統(tǒng)吞吐量。 實(shí)現(xiàn)較難。,5. 死鎖的概念,檢測(cè)死鎖(deadlock detection),事先并不采取任何限制，也不檢查系統(tǒng)是否進(jìn)入不安全區(qū)，允許死鎖發(fā)生； 但可通過檢測(cè)機(jī)構(gòu)及時(shí)檢測(cè)出死鎖的發(fā)生，并精確確定與死鎖有關(guān)的進(jìn)程和資源，然后采取適當(dāng)措施，將系統(tǒng)中已發(fā)生的死鎖清除掉。,5. 死鎖的概念,解除死鎖(deadlock recovery),與檢測(cè)死鎖相配套，用于將進(jìn)程從死鎖狀態(tài)解脫 出來。 常用的方法是撤消或掛起一些進(jìn)程。以回收一些 資源，再將它們分配給處于阻塞狀態(tài)的進(jìn)程，使 之轉(zhuǎn)為就緒狀態(tài)。 實(shí)現(xiàn)難度大，但可獲得較好的資源利用率和系統(tǒng) 吞吐量。,5. 死鎖的概