電子科技大學(xué)《計(jì)算機(jī)操作系統(tǒng)》第2章 并發(fā)與進(jìn)程-調(diào)度

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)程（線程）競爭CPU，那么就 需要選擇下一個(gè)要運(yùn)行的進(jìn)程（線程）。 在操作系統(tǒng)中完成這部分工作的程序稱為調(diào) 度程序（scheduler），該程序使用的算法 稱為調(diào)度算法（scheduling algorithm）。 進(jìn)程的調(diào)度算法對系統(tǒng)的整體性能和用戶體 驗(yàn)影響很大。 調(diào)度的生活實(shí)例 目 標(biāo) 防止進(jìn)程長期不能獲得調(diào)度而饑餓 盡量提高處理機(jī)的利用率 提高系統(tǒng)吞吐量 盡量減少進(jìn)程

2、的響應(yīng)時(shí)間 原 則 滿足用戶需求 滿足系統(tǒng)需求 基本概念 響應(yīng) 時(shí)間 周轉(zhuǎn) 時(shí)間 截止 時(shí)間 系統(tǒng) 吞吐量 響應(yīng)時(shí)間 從用戶通過鍵盤提交一個(gè)請求開始，直至系統(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í)間的平均值 n i i T n

3、 T 1 1 n i i W n T 1 1 si i i T T W 截至?xí)r間 某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最 遲時(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ù)用戶的請求能在響應(yīng)時(shí)間 內(nèi)完成， 常用于評(píng)價(jià)分時(shí)系統(tǒng)的性能。 平均周轉(zhuǎn)時(shí)間短 常用于評(píng)價(jià)批處理系統(tǒ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)的性能。 處理器利用率高 大、中型多用戶

4、系統(tǒng)較看重處理器的利用率 單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)不看重處理器的利用率 各類資源的平衡使用 使系統(tǒng)中的各種資源都盡量處于忙碌狀態(tài)。 公平性 對所有進(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)程 長時(shí)間得不到調(diào)度。 可以考慮動(dòng)態(tài)優(yōu)先權(quán)，將進(jìn)程排隊(duì)的等待時(shí)間等因

5、素 納入優(yōu)先權(quán)的計(jì)算。 調(diào)度類型 非剝奪方式剝奪方式 長程 調(diào)度 中程 調(diào)度 短程 調(diào)度 I/O調(diào)度 非剝奪（搶占）方式 執(zhí)行進(jìn)程只有在執(zhí)行完畢，或因申請I/O阻塞自 己時(shí)，才中斷其執(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)。 長程調(diào)度（高級(jí)調(diào)度、作業(yè)調(diào)度） 用于決定把外存上處于后備隊(duì)列中的作業(yè)調(diào)

6、入內(nèi)存， 并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建 的進(jìn)程排在就緒隊(duì)列（就緒/掛起）上，等待短程（中程） 調(diào)度。 長程調(diào)度長程調(diào)度 長程調(diào)度需要考慮兩個(gè)問題 選擇多少個(gè)作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？ 取決于多道程序的度多道程序的度，即允許同時(shí)在內(nèi)存中運(yùn)行的 進(jìn)程數(shù)。 選擇哪些作業(yè) 取決于長程調(diào)度算法長程調(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)度） 對換功能的一部份，用以提高內(nèi)存的利用率和系統(tǒng) 的吞吐量。 內(nèi)存緊張時(shí)，選擇一個(gè)進(jìn)程換出到外存（換出）。 內(nèi)存充裕時(shí)，從外存選擇一個(gè)掛起狀

7、態(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ī)定的資源分配算 法 對于不同的系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算 法 常見的調(diào)度算法先 來 先 服 務(wù) 短 作 業(yè) 優(yōu) 先 時(shí) 間 片 輪 轉(zhuǎn) 基 于 優(yōu) 先 級(jí) 剩 余 時(shí) 間 最 短 優(yōu) 先 響 應(yīng) 比 高 者 優(yōu) 先 反 饋 算法：First-Come-First-Served 選擇最先進(jìn)入就緒隊(duì)列的進(jìn)程投入執(zhí)行，即進(jìn)程按照 請求CPU的順序使用CPU。 評(píng)價(jià) 屬于非搶占調(diào)度方式 對長進(jìn)程（作業(yè)）有利，不利于短進(jìn)程（作業(yè)） 有利于CPU繁忙型的進(jìn)

8、程，而不利于I/O繁忙型 的進(jìn)程 不能直接用于分時(shí)系統(tǒng) 通常與其它調(diào)度算法混合使用 平均周轉(zhuǎn)時(shí)間長 示例 計(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í)間片 P1022 1 P2161 P3214 P4353 246810121416t 進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 P2P3 P4 算法: Shortest Job/Process First, SJF/SPF 短進(jìn)程

9、或短作業(yè)優(yōu)先調(diào)度，前提為執(zhí)行時(shí)間預(yù) 知。 評(píng)價(jià) 非搶占調(diào)度方式 該算法對長作業(yè)不利，可能導(dǎo)致長進(jìn)程饑餓。 有利于短進(jìn)程，減小了平均周轉(zhuǎn)時(shí)間。 缺少剝奪機(jī)制，不適用于分時(shí)系統(tǒng)或事務(wù)處理 環(huán)境。 由于作業(yè)（進(jìn)程）的長短只是根據(jù)用戶所提供 的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)估計(jì) 不準(zhǔn)運(yùn)行時(shí)間，致使該算法不一定能真正做到 短作業(yè)優(yōu)先調(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í)間片 P1022 1 P2161 P3214 P4353 P1 P3 P4 P2 P1 P2P3 P4 算法：Round Robin 每個(gè)進(jìn)程被分配一個(gè)時(shí)間片，如果在時(shí)間片

10、結(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)度方式 對短的、計(jì)算型進(jìn)程有利 對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è)得太長又可能引起對短的 交互請

11、求的響應(yīng)時(shí)間變長。在分時(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í)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 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í)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 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)

12、優(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)程對資源的需求 均衡系統(tǒng)資源使用 用戶需求 評(píng)價(jià) 簡單，開銷小 適合批處理進(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)度性能。 調(diào)整時(shí)機(jī) 時(shí)鐘中斷 進(jìn)程切換 進(jìn)程終止 基于優(yōu)先級(jí)調(diào)度算法的分類 進(jìn)程主動(dòng)釋放處理器進(jìn)程主動(dòng)釋放處理器 處理器可被剝奪

13、處理器可被剝奪 非搶占式優(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í)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 P2P3 P4 1.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í)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 P2P3 P4 1.1. 搶占式調(diào)度方式搶占式調(diào)度方式 2

14、.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那樣偏愛長進(jìn)程，也不像RR算法那 樣會(huì)產(chǎn)生額外的中斷，從而減少了開銷。 周轉(zhuǎn)時(shí)間方面，SRT比SJF性能要好，短作業(yè)可 以立即被選擇執(zhí)行。 問題 需要估計(jì)預(yù)計(jì)的服務(wù)時(shí)間 存在進(jìn)程饑餓現(xiàn)象 必須記錄進(jìn)程的已服務(wù)時(shí)間 246810121416t 進(jìn)程名進(jìn)程名

15、產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 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ì)使長作業(yè)長期 得不到服務(wù)。 利用該算法時(shí)，每次調(diào)度之前，都須先做響應(yīng) 比的計(jì)算，會(huì)增加系統(tǒng)開銷，且難以準(zhǔn)確計(jì)算。 要求服務(wù)時(shí)間 響應(yīng)時(shí)間 要求服務(wù)時(shí)間 要求服務(wù)時(shí)間等待時(shí)間 p R 2468101214

16、16t 進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 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)度法則采用了“懲罰長進(jìn)程” 的思想。根據(jù)進(jìn)程 執(zhí)行歷史，調(diào)度基于搶占原則（按時(shí)間片）并采用動(dòng)態(tài)優(yōu) 先級(jí)機(jī)制，可以獲得較好的性能。 算法：Multilevel Queues，采用多級(jí)隊(duì)列區(qū)別對 待的方法“懲罰長進(jìn)程” 多個(gè)獨(dú)立的、優(yōu)先級(jí)不同的就緒隊(duì)列 各隊(duì)列區(qū)別對待，即優(yōu)先調(diào)度優(yōu)先級(jí)

17、高的隊(duì)列 進(jìn)程執(zhí)行過程中可降級(jí)，即在整個(gè)生命周期內(nèi)可能位于 不同隊(duì)列。 該算法有多個(gè)變種 主要區(qū)別在于搶占機(jī)制不同 基于時(shí)間片輪轉(zhuǎn)的反饋調(diào)度算法 1. 設(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í)間片就越小。 2. 新進(jìn)程進(jìn)入時(shí)，首先放入第一個(gè)隊(duì)列尾，按 FCFS原則排隊(duì)，如果在一個(gè)時(shí)間片內(nèi)完成則退 出，否則將該進(jìn)程調(diào)入第二隊(duì)列，依次類推。 3. 僅當(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)中的任

18、何一個(gè)隊(duì)列），則新進(jìn)程搶占 當(dāng)前運(yùn)行進(jìn)程，并將當(dāng)前運(yùn)行進(jìn)程放回到第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 至至CPU S1 S2 S3 Sn 新進(jìn)程新進(jìn)程 時(shí)間片:S1S2S3 評(píng)價(jià)：多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能較好 地滿足各種類型用戶的需要。 終端型作業(yè)用戶 能在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，可使終端型 作業(yè)用戶都感到滿意。 對短作業(yè)用戶有利 能在前幾個(gè)隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成。 長批處理作業(yè)用戶 對于長作業(yè)，它將依次在第1，2,，n個(gè)隊(duì)列

19、中運(yùn)行， 然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到 處理。 246810121416t 進(jìn)程名進(jìn)程名產(chǎn)生時(shí)間產(chǎn)生時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間優(yōu)先級(jí)優(yōu)先級(jí)時(shí)間片時(shí)間片 P1022 1 P2161 P3214 P4353 P1 P2 P3 P4 P1 P2P3 P4 q=2q=2i i 實(shí)時(shí)系統(tǒng) 系統(tǒng)能夠及時(shí)（即時(shí)）響應(yīng)外部事件的請求，在規(guī)定 的時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào) 一致地運(yùn)行。 對于實(shí)時(shí)系統(tǒng)而言，系統(tǒng)的正確性不僅取決于對于實(shí)時(shí)系統(tǒng)而言，系統(tǒng)的正確性不僅取決于 計(jì)算的計(jì)算的邏輯結(jié)果邏輯結(jié)果，而且還依賴于產(chǎn)生結(jié)果的，而且還依賴于產(chǎn)生結(jié)果的時(shí)間時(shí)間。 實(shí)時(shí)控 制系統(tǒng) 實(shí)時(shí)

20、信 息處理 系統(tǒng) 實(shí)時(shí)系統(tǒng)的基本要求 可確定性 Determin ism 可響應(yīng)性 Respons iveness 用戶控制 User control 可靠性 Reliabilit y 失效弱化 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，

21、則在單處理機(jī)情況下，必須滿足下 面的限制條件： m i i i P C 1 1 實(shí)時(shí)系統(tǒng)通常具備快速切換機(jī)制 對外部中斷的快速響應(yīng)能力 要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，禁止中斷 的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)。 快速的任務(wù)分派能力 應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男。?以減少任務(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)搶占 立即

22、搶占 實(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)時(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)度狀

23、態(tài)。在該種狀態(tài)下， 一個(gè)高優(yōu)先級(jí)任務(wù)間接被一個(gè)低優(yōu)先級(jí)任務(wù)所搶先 (preempted)，使得兩個(gè)任務(wù)的相對優(yōu)先級(jí)被倒置。 可發(fā)生于任何基于優(yōu)先級(jí)的可搶占的調(diào)度方案中。 已在火星探路者中發(fā)生。 實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先調(diào)度算 法 Earliest Deadline First，EDF 根據(jù)任務(wù)的截止時(shí)間來確定任務(wù)的優(yōu)先級(jí) 截止時(shí)間越早，優(yōu)先級(jí)越高 可以是搶占式或非搶占式 EDF實(shí)例 1342 134 2 12 34 t 開始截止時(shí)間 任務(wù)到達(dá) 任務(wù)執(zhí)行 EDF算法用于非搶占調(diào)度方式 實(shí)時(shí)調(diào)度算法最低松弛度度優(yōu)先調(diào)度算法 Least Laxity First, LLF 任務(wù)松弛度計(jì)算公式 任

24、務(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í)例 在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B A：周期：20ms，執(zhí)行時(shí)間：10ms； B：周期：50ms，執(zhí)行時(shí)間：25ms； 下圖為A、B的截止時(shí)間 A1A2A3A4 A5 A6A7A8 B1B2B3 0 20 406080100120140160 t LLF實(shí)例（續(xù)） A1(10)A2(0) A3(10) t 01020304050607080 B1(15) B1(5)B2(20) t1t2t3t4t5t6t7t8 B1(25) A