1、計(jì)算機(jī)操作系統(tǒng)電子科技大學(xué)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院李玉軍李玉軍:調(diào)度scheduling死鎖deadlock同步synchronization進(jìn)程process: 如果有多個(gè)進(jìn)程線程競(jìng)爭(zhēng)CPU，那么就需要選擇下一個(gè)要運(yùn)行的進(jìn)程線程）。 在操作系統(tǒng)中完成這部分工作的程序稱為調(diào)度程序scheduler），該程序使用的算法稱為調(diào)度算法scheduling algorithm）。 進(jìn)程的調(diào)度算法對(duì)系統(tǒng)的整體性能和用戶體驗(yàn)影響很大。: 調(diào)度的生活實(shí)例:目標(biāo) 防止進(jìn)程長(zhǎng)期不能獲得調(diào)度而饑餓 盡量提高處理機(jī)的利用率 提高系統(tǒng)吞吐量 盡量減少進(jìn)程的響應(yīng)時(shí)間原則 滿足用戶需求 滿足系

2、統(tǒng)需求: 基本概念響應(yīng)時(shí)間周轉(zhuǎn)時(shí)間截止時(shí)間系統(tǒng)吞吐量: 響應(yīng)時(shí)間 從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。 響應(yīng)時(shí)間的構(gòu)成 輸入傳送時(shí)間處理時(shí)間響應(yīng)傳送時(shí)間: 周轉(zhuǎn)時(shí)間 從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔，也稱為作業(yè)周轉(zhuǎn)時(shí)間。 周轉(zhuǎn)時(shí)間的構(gòu)成 駐外存等待調(diào)度時(shí)間駐內(nèi)存等待調(diào)度時(shí)間執(zhí)行時(shí)間阻塞時(shí)間需累計(jì)需累計(jì): 平均周轉(zhuǎn)時(shí)間：多個(gè)作業(yè)周轉(zhuǎn)時(shí)間的平均值 帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為它提供的服務(wù)時(shí)間之比 平均帶權(quán)周轉(zhuǎn)時(shí)間：多個(gè)作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間的平均值 niiTnT11niiWnT11siiiTTW: 截至?xí)r間 某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成

3、的最遲時(shí)間。 系統(tǒng)吞吐量 在單位時(shí)間內(nèi)，系統(tǒng)所完成的作業(yè)數(shù)。 :面向用戶的原則響應(yīng)時(shí)間周轉(zhuǎn)時(shí)間截止時(shí)間面向系統(tǒng)的原則吞吐量利用率公平性優(yōu)先級(jí): 面向用戶的原則 響應(yīng)時(shí)間快 盡可能使絕大多數(shù)用戶的請(qǐng)求能在響應(yīng)時(shí)間內(nèi)完成， 常用于評(píng)價(jià)分時(shí)系統(tǒng)的性能。 平均周轉(zhuǎn)時(shí)間短 常用于評(píng)價(jià)批處理系統(tǒng)的性能，涉及長(zhǎng)程調(diào)度、中程調(diào)度和短程調(diào)度。 滿足截至?xí)r間 常用于評(píng)價(jià)實(shí)時(shí)系統(tǒng)的性能。: 面向系統(tǒng)的原則 系統(tǒng)吞吐量大 常用于評(píng)價(jià)批處理系統(tǒng)的性能。 處理器利用率高 大、中型多用戶系統(tǒng)較看重處理器的利用率 單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)不看重處理器的利用率 各類資源的平衡使用 使系統(tǒng)中的各種資源都盡量處于忙碌狀態(tài)。 公平性

4、 對(duì)所有進(jìn)程公平，不偏袒任何進(jìn)程。 : 面向系統(tǒng)的原則續(xù)） 優(yōu)先權(quán)：優(yōu)先權(quán)高的進(jìn)程應(yīng)優(yōu)先調(diào)度接納接納調(diào)度調(diào)度處理機(jī)處理機(jī)完成完成等待事件等待事件事件發(fā)生事件發(fā)生阻塞隊(duì)列阻塞隊(duì)列就緒隊(duì)列就緒隊(duì)列0就緒隊(duì)列就緒隊(duì)列1就緒隊(duì)列就緒隊(duì)列n被剝奪被剝奪: 面向系統(tǒng)的原則續(xù)） 優(yōu)先權(quán)續(xù)） 幾乎所有操作系統(tǒng)的調(diào)度算法都可考慮優(yōu)先權(quán)原則。 僅考慮優(yōu)先權(quán)會(huì)導(dǎo)致進(jìn)程饑餓，即某些低優(yōu)先權(quán)進(jìn)程長(zhǎng)時(shí)間得不到調(diào)度。 可以考慮動(dòng)態(tài)優(yōu)先權(quán)，將進(jìn)程排隊(duì)的等待時(shí)間等因素納入優(yōu)先權(quán)的計(jì)算。: 調(diào)度類型 非剝奪方式剝奪方式長(zhǎng)程調(diào)度中程調(diào)度短程調(diào)度I/O調(diào)度: 非剝奪搶占方式 執(zhí)行進(jìn)程只有在執(zhí)行完畢，或因申請(qǐng)I/O阻塞自己時(shí)，才中斷其

5、執(zhí)行，釋放處理機(jī)。 不利于“即時(shí)性要求較高的分時(shí)和實(shí)時(shí)系統(tǒng)，主要用于批處理系統(tǒng)。 剝奪搶占方式 在新進(jìn)程到來時(shí)，或某個(gè)具有較高優(yōu)先權(quán)的被阻塞進(jìn)程插入就緒隊(duì)列時(shí)，或在基于時(shí)間片調(diào)度的系統(tǒng)中，時(shí)間片用完而中斷當(dāng)前進(jìn)程的執(zhí)行，調(diào)度新的進(jìn)程執(zhí)行。 會(huì)產(chǎn)生較多的中斷，主要用于實(shí)時(shí)性要求較高的實(shí)時(shí)系統(tǒng)及性能要求較高的批處理系統(tǒng)和分時(shí)系統(tǒng)。: 長(zhǎng)程調(diào)度高級(jí)調(diào)度、作業(yè)調(diào)度） 用于決定把外存上處于后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列就緒/掛起上，等待短程中程調(diào)度。長(zhǎng)程調(diào)度長(zhǎng)程調(diào)度:長(zhǎng)程調(diào)度需要考慮兩個(gè)問題選擇多少個(gè)作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？ 取決于多道

6、程序的度，即允許同時(shí)在內(nèi)存中運(yùn)行的進(jìn)程數(shù)。選擇哪些作業(yè) 取決于長(zhǎng)程調(diào)度算法: 短程調(diào)度進(jìn)程調(diào)度、低級(jí)調(diào)度） 決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理器 運(yùn)行頻率最高 現(xiàn)代操作系統(tǒng)幾乎都具有短程調(diào)度功能 中程調(diào)度中級(jí)調(diào)度） 對(duì)換功能的一部份，用以提高內(nèi)存的利用率和系統(tǒng)的吞吐量。 內(nèi)存緊張時(shí)，選擇一個(gè)進(jìn)程換出到外存換出）。 內(nèi)存充裕時(shí)，從外存選擇一個(gè)掛起狀態(tài)的進(jìn)程調(diào)度到內(nèi)存換入）。 只有支持進(jìn)程掛起的操作系統(tǒng)才具有中程調(diào)度功能。: 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 : 調(diào)度算法 根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法 對(duì)于不同的系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法 常見的調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先時(shí)間片

7、輪轉(zhuǎn)基于優(yōu)先級(jí)剩余時(shí)間最短優(yōu)先響應(yīng)比高者優(yōu)先反饋: 算法：First-Come-First-Served 選擇最先進(jìn)入就緒隊(duì)列的進(jìn)程投入執(zhí)行，即進(jìn)程按照請(qǐng)求CPU的順序使用CPU。 評(píng)價(jià) 屬于非搶占調(diào)度方式 對(duì)長(zhǎng)進(jìn)程作業(yè)有利，不利于短進(jìn)程作業(yè)） 有利于CPU繁忙型的進(jìn)程，而不利于I/O繁忙型的進(jìn)程 不能直接用于分時(shí)系統(tǒng) 通常與其它調(diào)度算法混合使用 平均周轉(zhuǎn)時(shí)間長(zhǎng): 例如 計(jì)算P1、P2、P3和P4的周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。進(jìn)程名進(jìn)程名 產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353:246810121416t進(jìn)

8、程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4: 算法: Shortest Job/Process First, SJF/SPF 短進(jìn)程或短作業(yè)優(yōu)先調(diào)度，前提為執(zhí)行時(shí)間預(yù)知。 評(píng)價(jià) 非搶占調(diào)度方式 該算法對(duì)長(zhǎng)作業(yè)不利，可能導(dǎo)致長(zhǎng)進(jìn)程饑餓。 有利于短進(jìn)程，減小了平均周轉(zhuǎn)時(shí)間。 缺少剝奪機(jī)制，不適用于分時(shí)系統(tǒng)或事務(wù)處理環(huán)境。 由于作業(yè)進(jìn)程的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)估計(jì)不準(zhǔn)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)

9、間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P3P4P2P1 P2P3 P4: 算法：Round Robin 每個(gè)進(jìn)程被分配一個(gè)時(shí)間片，如果在時(shí)間片結(jié)束時(shí)該進(jìn)程還在運(yùn)行，則剝奪其CPU并分配給另一個(gè)進(jìn)程，被剝奪CPU的進(jìn)程則插入到就緒隊(duì)列末尾，等待下次調(diào)度；如果該進(jìn)程在時(shí)間片內(nèi)阻塞或結(jié)束，則立即切換CPU。 典型應(yīng)用系統(tǒng)示例分時(shí)聯(lián)機(jī)系統(tǒng)基于時(shí)間片輪轉(zhuǎn)調(diào)度基于時(shí)間片輪轉(zhuǎn)調(diào)度主機(jī)主機(jī)終端終端1終端終端2終端終端n終端終端1 1服務(wù)進(jìn)程服務(wù)進(jìn)程終端終端2服務(wù)進(jìn)程服務(wù)進(jìn)程終端終端n服務(wù)進(jìn)程服務(wù)進(jìn)程: 評(píng)價(jià) 屬于搶占調(diào)度方式 對(duì)短的、計(jì)算型進(jìn)程有利 對(duì)

10、I/O型作業(yè)進(jìn)程不利 常用于分時(shí)系統(tǒng)或事務(wù)處理系統(tǒng) 時(shí)間片的設(shè)置與系統(tǒng)性能、響應(yīng)時(shí)間密切相關(guān) 時(shí)間片設(shè)得太短會(huì)導(dǎo)致過多進(jìn)程切換，降低CPU效率；反之，設(shè)得太長(zhǎng)又可能引起對(duì)短的交互請(qǐng)求的響應(yīng)時(shí)間變長(zhǎng)。在分時(shí)系統(tǒng)中，時(shí)間片大小的確定應(yīng)綜合考慮最大用戶數(shù)目、響應(yīng)時(shí)間、系統(tǒng)效率等多種因素。:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P

11、2P3P4P1 P2P3 P4: 算法 每個(gè)進(jìn)程被賦予一個(gè)優(yōu)先級(jí)權(quán)），允許優(yōu)先級(jí)權(quán)最高的可運(yùn)行進(jìn)程先運(yùn)行。 優(yōu)先級(jí)的類型靜態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí): 靜態(tài)優(yōu)先級(jí)(static) 優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。 確定依據(jù) 進(jìn)程類型重要性、緊迫性） 進(jìn)程對(duì)資源的需求 均衡系統(tǒng)資源使用 用戶需求 評(píng)價(jià) 簡(jiǎn)單，開銷小 適合批處理進(jìn)程: 靜態(tài)優(yōu)先級(jí)的問題 若一直存在高優(yōu)先級(jí)的就緒進(jìn)程，則低優(yōu)先級(jí)的進(jìn)程可能會(huì)餓死(無窮阻塞）。 解決方法 進(jìn)程的優(yōu)先級(jí)隨著時(shí)間或執(zhí)行歷史而變化老化策略(aging)。: 動(dòng)態(tài)優(yōu)先級(jí) 在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先級(jí)可隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變，以便獲得更好的調(diào)度性能。

12、 調(diào)整時(shí)機(jī) 時(shí)鐘中斷 進(jìn)程切換 進(jìn)程終止: 基于優(yōu)先級(jí)調(diào)度算法的分類 進(jìn)程主動(dòng)釋放處理器進(jìn)程主動(dòng)釋放處理器處理器可被剝奪處理器可被剝奪非搶占式優(yōu)先級(jí)算法搶占式優(yōu)先級(jí)調(diào)度算法:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P41.1. 非搶占式調(diào)度方式非搶占式調(diào)度方式2.2. 優(yōu)先級(jí)數(shù)越小，優(yōu)先級(jí)越高優(yōu)先級(jí)數(shù)越小，優(yōu)先級(jí)越高:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4

13、P1 P2P3 P41.1. 搶占式調(diào)度方式搶占式調(diào)度方式2.2. 優(yōu)先級(jí)數(shù)越小，優(yōu)先級(jí)越高優(yōu)先級(jí)數(shù)越小，優(yōu)先級(jí)越高: 算法: Shortest Remaining Time, SRT 在SJF的基礎(chǔ)上增加了剝奪機(jī)制 調(diào)度程序總是選擇預(yù)期剩余時(shí)間最短的進(jìn)程 當(dāng)一個(gè)新進(jìn)程加入就緒隊(duì)列時(shí)，它可能比當(dāng)前運(yùn)行的進(jìn)程具有更短的剩余時(shí)間。只要新進(jìn)程就緒，調(diào)度程序就可能搶占當(dāng)前正在運(yùn)行的進(jìn)程。 優(yōu)點(diǎn) 既不像FCFS那樣偏愛長(zhǎng)進(jìn)程，也不像RR算法那樣會(huì)產(chǎn)生額外的中斷，從而減少了開銷。 周轉(zhuǎn)時(shí)間方面，SRT比SJF性能要好，短作業(yè)可以立即被選擇執(zhí)行。: 問題 需要估計(jì)預(yù)計(jì)的服務(wù)時(shí)間 存在進(jìn)程饑餓現(xiàn)象 必須記錄進(jìn)

14、程的已服務(wù)時(shí)間:246810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4: 算法: Highest Response Ratio Next 當(dāng)前進(jìn)程執(zhí)行完畢或需要阻塞時(shí)，選擇響應(yīng)比最高的進(jìn)程投入執(zhí)行。 評(píng)價(jià) 實(shí)質(zhì)上是一種動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法 是FCFS和SJF的結(jié)合，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。 利用該算法時(shí)，每次調(diào)度之前，都須先做響應(yīng)比的計(jì)算，會(huì)增加系統(tǒng)開銷，且難以準(zhǔn)確計(jì)算。要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間pR:24

15、6810121416t進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4: 短進(jìn)程優(yōu)先、剩余時(shí)間最短者優(yōu)先以及響應(yīng)比高者優(yōu)先調(diào)度算法采用了“獎(jiǎng)勵(lì)短進(jìn)程的思想。雖然性能較好，但均基于進(jìn)程的預(yù)期執(zhí)行時(shí)間未來。 反饋調(diào)度法則采用了“懲罰長(zhǎng)進(jìn)程” 的思想。根據(jù)進(jìn)程執(zhí)行歷史，調(diào)度基于搶占原則按時(shí)間片并采用動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，可以獲得較好的性能。: 算法：Multilevel Queues，采用多級(jí)隊(duì)列區(qū)別對(duì)待的方法“懲罰長(zhǎng)進(jìn)程” 多個(gè)獨(dú)立的、優(yōu)先級(jí)不同的就緒隊(duì)列 各隊(duì)列區(qū)別對(duì)待，即優(yōu)先調(diào)度優(yōu)先級(jí)高的隊(duì)列 進(jìn)程執(zhí)行

16、過程中可降級(jí)，即在整個(gè)生命周期內(nèi)可能位于不同隊(duì)列。 該算法有多個(gè)變種 主要區(qū)別在于搶占機(jī)制不同:基于時(shí)間片輪轉(zhuǎn)的反饋調(diào)度算法設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列賦予不同優(yōu)先級(jí)，第一隊(duì)列優(yōu)先級(jí)最高，依次遞減；各個(gè)隊(duì)列中進(jìn)程執(zhí)行的時(shí)間片也不相同，優(yōu)先級(jí)越高的隊(duì)列中，每個(gè)進(jìn)程的時(shí)間片就越小。新進(jìn)程進(jìn)入時(shí)，首先放入第一個(gè)隊(duì)列尾，按FCFS原則排隊(duì)，如果在一個(gè)時(shí)間片內(nèi)完成則退出，否則將該進(jìn)程調(diào)入第二隊(duì)列，依次類推。僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程，依次類推。如果CPU正在執(zhí)行第i隊(duì)列中某進(jìn)程時(shí)有新進(jìn)程進(jìn)入較高的隊(duì)列第1(i-1)中的任何一個(gè)隊(duì)列），則新進(jìn)程搶占當(dāng)前運(yùn)行進(jìn)程，并將當(dāng)前運(yùn)行進(jìn)程放回到

17、第i隊(duì)列末尾。: 基于時(shí)間片輪轉(zhuǎn)的反饋調(diào)度算法示意圖就緒隊(duì)列就緒隊(duì)列0 0就緒隊(duì)列就緒隊(duì)列1 1就緒隊(duì)列就緒隊(duì)列2 2就緒隊(duì)列就緒隊(duì)列n n至至CPU至至CPU至至CPU至至CPUS1S2S3Sn新進(jìn)程新進(jìn)程時(shí)間片:S1S2S3: 評(píng)價(jià)：多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能較好地滿足各種類型用戶的需要。 終端型作業(yè)用戶 能在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，可使終端型作業(yè)用戶都感到滿意。 對(duì)短作業(yè)用戶有利 能在前幾個(gè)隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成。 長(zhǎng)批處理作業(yè)用戶 對(duì)于長(zhǎng)作業(yè)，它將依次在第1，2,，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長(zhǎng)期得不到處理。:246810121416t進(jìn)

18、程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4q=2iq=2i: 實(shí)時(shí)系統(tǒng) 系統(tǒng)能夠及時(shí)即時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。 對(duì)于實(shí)時(shí)系統(tǒng)而言，系統(tǒng)的正確性不僅取決于對(duì)于實(shí)時(shí)系統(tǒng)而言，系統(tǒng)的正確性不僅取決于計(jì)算的邏輯結(jié)果，而且還依賴于產(chǎn)生結(jié)果的時(shí)間。計(jì)算的邏輯結(jié)果，而且還依賴于產(chǎn)生結(jié)果的時(shí)間。實(shí)時(shí)控制系統(tǒng)實(shí)時(shí)信息處理系統(tǒng): 實(shí)時(shí)系統(tǒng)的基本要求可確定性Determinism可響應(yīng)性Responsiveness用戶控制User control可靠

19、性Reliability失效弱化Fail-soft: 實(shí)時(shí)任務(wù) 具有及時(shí)性要求的、常常被重復(fù)執(zhí)行的特定進(jìn)程，在實(shí)時(shí)系統(tǒng)中習(xí)慣稱為任務(wù)。 截止時(shí)間 開始截止時(shí)間 任務(wù)在某時(shí)間以前，必須開始執(zhí)行。 完成截止時(shí)間 任務(wù)在某時(shí)間以前必須完成。: 實(shí)時(shí)任務(wù)的分類實(shí)時(shí)任務(wù)截至?xí)r間硬實(shí)時(shí)任務(wù)軟實(shí)時(shí)任務(wù)周期性周期性實(shí)時(shí)任務(wù)非周期性實(shí)時(shí)任務(wù): 實(shí)時(shí)系統(tǒng)處理能力限制 假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間為Ci，周期為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件： miiiPC11: 實(shí)時(shí)系統(tǒng)通常具備快速切換機(jī)制 對(duì)外部中斷的快速響應(yīng)能力 要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，禁止中斷的時(shí)間間隔盡量短，以

20、免耽誤時(shí)機(jī)。 快速的任務(wù)分派能力 應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男。詼p少任務(wù)切換的時(shí)間開銷。 : 實(shí)時(shí)調(diào)度的目標(biāo) 使硬實(shí)時(shí)任務(wù)在其規(guī)定的截止時(shí)間內(nèi)完成或開始），同時(shí)盡可能使軟實(shí)時(shí)任務(wù)也能在規(guī)定的截止時(shí)間內(nèi)完成或開始）。 實(shí)時(shí)調(diào)度的必要信息 就緒時(shí)間 開始截止時(shí)間和完成截止時(shí)間 處理時(shí)間 資源需求 優(yōu)先級(jí) 子任務(wù)結(jié)構(gòu):實(shí)時(shí)調(diào)度算法非搶占式時(shí)間片輪轉(zhuǎn)非搶占優(yōu)先級(jí)搶占式剝奪點(diǎn)搶占立即搶占: 實(shí)時(shí)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 實(shí)時(shí)進(jìn)程按時(shí)間片輪轉(zhuǎn)的方式執(zhí)行 響應(yīng)時(shí)間一般為秒級(jí) 廣泛用于分時(shí)系統(tǒng)及一般實(shí)時(shí)處理系統(tǒng): 實(shí)時(shí)調(diào)度算法基于優(yōu)先級(jí)的非剝奪調(diào)度算法 實(shí)時(shí)進(jìn)程按優(yōu)先級(jí)、非搶占方式執(zhí)行 響應(yīng)

21、時(shí)間一般在數(shù)百毫秒至數(shù)秒范圍 多用于多道批處理系統(tǒng)及不太嚴(yán)格的實(shí)時(shí)系統(tǒng): 實(shí)時(shí)調(diào)度算法基于優(yōu)先級(jí)的剝奪點(diǎn)剝奪調(diào)度算法 實(shí)時(shí)進(jìn)程按優(yōu)先級(jí)、搶占方式執(zhí)行 響應(yīng)時(shí)間一般在幾毫秒至幾十毫秒 用于一般實(shí)時(shí)系統(tǒng): 實(shí)時(shí)調(diào)度算法立即剝奪調(diào)度算法 實(shí)時(shí)進(jìn)程按優(yōu)先級(jí)、搶占方式執(zhí)行 響應(yīng)時(shí)間為微秒至毫秒級(jí) 可用于苛刻的實(shí)時(shí)系統(tǒng): 優(yōu)先級(jí)反轉(zhuǎn)優(yōu)先級(jí)倒置、優(yōu)先級(jí)逆轉(zhuǎn)、優(yōu)先級(jí)翻轉(zhuǎn)） 是一種不希望發(fā)生的任務(wù)調(diào)度狀態(tài)。在該種狀態(tài)下，一個(gè)高優(yōu)先級(jí)任務(wù)間接被一個(gè)低優(yōu)先級(jí)任務(wù)所搶先(preempted)，使得兩個(gè)任務(wù)的相對(duì)優(yōu)先級(jí)被倒置。 可發(fā)生于任何基于優(yōu)先級(jí)的可搶占的調(diào)度方案中。 已在火星探路者中發(fā)生。: 實(shí)時(shí)調(diào)度算法最早截止

22、時(shí)間優(yōu)先調(diào)度算法 Earliest Deadline First，EDF 根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí) 截止時(shí)間越早，優(yōu)先級(jí)越高 可以是搶占式或非搶占式: EDF實(shí)例1342134212 34t開始截止時(shí)間任務(wù)到達(dá)任務(wù)執(zhí)行EDF算法用于非搶占調(diào)度方式: 實(shí)時(shí)調(diào)度算法最低松弛度度優(yōu)先調(diào)度算法 Least Laxity First, LLF 任務(wù)松弛度計(jì)算公式 任務(wù)的松弛度 = 完成截至?xí)r間 剩余執(zhí)行時(shí)間 當(dāng)前時(shí)間 例： 若A進(jìn)程需在200ms時(shí)完成，本身運(yùn)行需要100ms，當(dāng)前時(shí)刻是10ms，則A的松弛度: 2001001090 系統(tǒng)按任務(wù)松弛度的高低進(jìn)行調(diào)度 主要用于可搶占調(diào)度方式: LLF實(shí)例實(shí)例 在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和和B A：周期：周期：20ms，執(zhí)行時(shí)間：，執(zhí)行時(shí)間：10ms； B：周期：周期：50ms，執(zhí)行時(shí)間：，執(zhí)行時(shí)間：25ms； 下圖為下圖為A、B的截止時(shí)間的截止時(shí)間 A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t: LLF實(shí)例續(xù)）實(shí)例續(xù)） A1(10)A2(0) A3(10)t01020304050607080B1(15)B1(5)B2(20)t1t2t3t4t5t6t7t8B1(25)A2(未到)B1(15)A3(