1、1/19第4章 中斷(zhngdun)和處理機調度 4.1 中斷 4.2 處理機調度(diod) 4.3 實時調度 4.4 多處理機調度 共七十一頁2/194.1 中斷(zhngdun) 中斷的重要性：中斷和通道技術成為了計算機發展過程中一種里程碑式的重要發展，它們使得今天的計算機更加靈活、有效。 中斷對于操作系統的作用：中斷或中斷機制是實現多道程序設計與并發執行的基礎和必要條件。如果沒有中斷，操作系統就無法獲得(hud)系統的控制權，就不會將處理機（也作為一種資源）分派給不同的進程而實現并發執行。 共七十一頁3/19中斷(zhngdun)響應三個步驟： 終止(zhngzh)當前程序執行 保存

2、斷點信息 轉相應中斷處理程序 中斷打斷正常執行序列，當處理完成后，再恢復執行(如圖4.1)。在并發環境下，用戶程序不需要為中斷添加任何特定代碼。 1 2 ii+1 n 在此處產生中斷 用戶程序 中斷處理程序 圖 4.1 通過中斷轉移控制4.1 中斷 4.1.1 中斷和指令周期 重新回顧和熟悉共七十一頁4/19為適應中斷產生，在指令周期末端(m dun)要增加一個中斷階段（如圖4.2所示）。 取下一條(y tio)指令分析指令執行指令檢查中斷；初始化中斷處理程序停止開始 取指階段 分析階段 執行階段 中斷階段圖 4.2 中斷和指令周期4.1 中斷 4.1.1 中斷和指令周期 共七十一頁5/194

3、.1.2 中斷(zhngdun)處理 強迫性中斷(zhngdun)：這類中斷大致有如下幾種： 時鐘中斷：如硬件實時時鐘到時等 輸入輸出中斷：設備數據傳輸結束/設備出錯等。 控制臺中斷：系統操作員通過控制臺發出命令等。 硬件故障中斷：如掉電、內存效驗錯等。 程序性中斷：如地址越界、數據溢出，除零等。 4.1 中斷 自愿性中斷程序事先有意識安排的；通常執行訪管指令（系統調用）而引起的，其目的要求系統提供某種服務。共七十一頁6/19正在運行(ynxng)的程序中斷(zhngdun)裝置中斷處理程序時鐘中斷I/O中斷控制臺中斷硬件中斷程序錯誤中斷運行程序訪管指令中斷裝置中斷處理程序 （a）強迫性中斷

4、（b）自愿性中斷 圖4.3 兩類中斷事件4.1 中斷 4.1.2 中斷處理 確定位置中斷任意位置中斷下一步共七十一頁7/194.1 中斷(zhngdun) 4.1.2 中斷(zhngdun)處理 對于圖4.3，每類中斷事件一個中斷處理程序，及一個入口地址。 當中斷事件發生時，中斷裝置根據中斷類別自動地將對應的PSW和PC分別送入程序狀態字和程序計數器中，如此便轉入到對應的中斷處理程序，如圖4.4所示。 應當說明的是，圖4.4所示的中斷處理是比較典型的形式。對于系統的中斷處理，硬件要保存哪些信息，保存到什么地方，這些隨CPU（或系統）而不同。共七十一頁8/19 PSW1，PC1PSW2，PC2P

5、SW3，PC3PSW4，PC4PSW5，PC5PSWn，PCnCSWCAW定時器PSW1，PC1PSW2，PC2PSW3，PC3PSW4，PC4PSW5，PC5PSWn，PCn 現行(xinxng)PSW，PC舊PSW，PC新PSW，PCPC1：中斷(zhngdun)處理程序PC2：中斷處理程序PC3：中斷處理程序PC4：中斷處理程序PC5：中斷處理程序PCn：中斷處理程序圖4.4 中斷向量與中斷處理程序中斷結束4.1 中斷 共七十一頁9/19 時鐘中斷 時鐘中斷是現代操作系統不可或缺的控制手段，所以(suy)在此特別強調。時鐘中斷管理及維護的內容： 進程(jnchng)管理：用于時間片輪轉處

6、理機調度算法的系統中，記錄進程已占用處理機時間等。 作業管理：記錄作業在輸入井中等待的時間等。4.1 中斷 4.1.2 中斷處理 資源管理：動態統計運行進程占有和使用處理機等資源的時間等。共七十一頁10/19 事件處理：實時系統中定時向被控制的對象發送(f sn)控制信號。 系統維護：定時運行死鎖檢測(jin c)程序等，定時運行系統記帳程序等。 實現軟件時鐘：利用硬件間隔時鐘和一個存儲單元可以實現軟件時鐘。例如，假設硬件間隔時鐘每隔10ms產生一次中斷，某一程序每隔1000ms執行一次，則可以這樣確定該程序的執行時刻。4.1 中斷 4.1.2 中斷處理 共七十一頁11/194.1.3 多個(

7、du )中斷 由于(yuy)系統有多個事件在不停和不斷地發生，因而就勢必存在多個中斷在一個極短的時間內發生。處理多個中斷有兩種方法 ： 4.1 中斷 第1種方法：在處理一個中斷時，禁止再發生中斷。 優點這種方法保證了各個中斷按順序處理。 缺點沒有考慮相對優先級和時間限制的要求。 第2種方法：定義中斷優先級，允許高優先級的打斷低級中斷處理程序的運行。圖4.5 給出了事例。 可通過硬件和軟件定義共七十一頁12/19 t=10t=15t=25t=25t=35t=40用戶程序打印機中斷(zhngdun)處理程序通信(tng xn)中斷處理程序磁盤中斷處理程序圖4.5 多中斷處理的時間順序t=0t=20

8、打印機中斷通信中斷磁盤中斷磁盤中斷優先級低于通信，信號保留，通信中斷處理繼續磁盤中斷信號仍然存在，且高于打印機，中斷打印機中斷處理，進入磁盤中斷處理結束下一步下一步4.1.3 多個中斷 共七十一頁13/194.1.4 多道程序設計(shj) 中斷的應用使得系統的資源利用率得到提高，但即使利用了中斷，在單道情況下處理機仍有可能未得到充分的利用。例如(lr)，如果I/O操作的時間比較長，則大部分時間處理機是空閑的。解決這個問題的方法是允許多道用戶程序同時處于活動狀態。 某程序（進程）等待I/O上，可調度另一程序，這時處理機與外設都在“忙”。 由此，說明多道程序設計是提高系統效率又一重要的技術思想。

9、4.1 中斷 共七十一頁14/194. 2 處理機調度(diod) 4.2.1 高級(goj)、中級和低級調度 處理機調度是把進程指定到一個處理機中執行。在許多系統中，這個調度活動分成三個層次：高級調度、中級調度和低級調度。 高級調度是在創建新進程時，決定是否把進程添加到當前活躍的進程集合中。 中級調度是屬于交換功能的一部分，它需要決定（部分）進程是否不再處于活動空間中。 低級調度真正決定下一次執行哪一個就緒進程。圖4.6 給出了進程狀態轉換三個層次的調度。共七十一頁15/19圖4.6 調度(diod)的層次運行就緒阻塞低級靜止阻塞靜止就緒中級新建退出高級4. 2 處理機調度(diod) 4.

10、2.1 高級、中級和低級調度 共七十一頁16/19 高級調度(diod)（作業調度(diod)） 一個作業的處理可以分若干相對獨立的作業步，每個作業步可能對應一個進程。例如，一個C語言程序，作為(zuwi)批作業處理大致應當包括如下步驟： 運行C語言編譯程序對C代碼進行編譯。 對所編譯產生的浮動程序進行連接裝配。 執行所產生的目標代碼程序。 以上三個步驟運行的是三個不同的程序，因而需要三個進程完成。4. 2 處理機調度 4.2.1 高級、中級和低級調度 共七十一頁17/19圖4.7為作業(zuy)五個狀態變遷圖示。 提交SPOOLING輸入(shr)作業調度作業調度SPOOLING輸出圖4.7

11、 作業狀態轉換圖后備退出完成活動空間阻塞運行就緒4. 2 處理機調度 4.2.1 高級、中級和低級調度 高級調度（作業調度） 結束共七十一頁18/19 低級(dj)調度/處理機調度 處理機調度（CPU scheduling）是指CPU在可運行實體(sht)之間的分配。如圖4.7中虛框的活動空間部分。處理機資源管理需要解決三個問題： 依什么原則分配處理機，即確定處理機調度算法。 什么時候分配處理機，即確定處理機調度時機。 如何分配處理機，即給出處理機調度過程。 4. 2 處理機調度 4.2.1 高級、中級和低級調度 共七十一頁19/19 中斷與進程狀態(zhungti)轉換 前面討論了中斷的重要

12、性和處理過程，下面進一步說明中斷作為引起進程狀態轉換的本質加以闡述。我們仍以進程的三個基本狀態為例說明四條有向邊所表明的狀態轉移。圖4.9給出了由中斷引起進程狀態轉移的形式(xngsh)描述（圖中省略了關于中斷仲裁或控制部分）。其中，虛線表示事件，或系統產生的操作。 4. 2 處理機調度 4.2.1 高級、中級和低級調度 共七十一頁20/19圖4.9 由中斷引起的進程狀態(zhungti)轉換圖I/O(完成(wn chng)中斷申請I/O服務I/O完成調度時間片到自愿性中斷阻塞隊列就緒隊列時鐘中斷就緒阻塞運行 申請I/O服務：運行中進程需要在某處執行有關I/O指令以進行數據輸入輸出。此時用戶利

13、用的指令要么是訪管指令，要么是某種系統調用，無論那種形式，都屬于自愿性中斷而進入中斷處理；也可能由于沒有所要求空閑I/O設備而進入阻塞狀態，進入由于等待某類I/O的阻塞隊列。磁盤結束下一步下一步下一步下一步下一步下一步下一步 中斷與進程狀態轉換 共七十一頁21/19 時間片到/搶占：這條邊表明狀態轉移就比較明顯了，就是由于系統定時間隔時鐘中斷所引起的當前(dngqin)進程的一個時間片用完而從運行狀態轉移到就緒狀態。需要說明的是，這是分時系統所具有的最常見的狀態轉移。由于現代通用操作系統大多都具有分時特征，因而時鐘在系統中是必不可少的。 調度：當我們清楚了以上狀態轉移原因，這條邊所表明的狀態轉

14、移也很容易理解。這涉及到調度的時機；如前面正在運行進程由于I/O申請自愿中斷而進入阻塞狀態時，系統就需要從就緒隊列中選擇一個就緒態進程投入運行而轉換成運行態。產生(chnshng)調度的因素有很多，但基本都與中斷有關。結束下一步下一步下一步下一步下一步下一步下一步 中斷與進程狀態轉換 共七十一頁22/19 I/O完成：I/O外設數據傳輸完成產生一個I/O完成中斷信號而進入I/O中斷處理。當前進程狀態信息被保存(bocn)后，系統分析中斷原因，檢查是否有等待此次I/O完成的在阻塞隊列中的進程，如果有，則通過某種算法從阻塞隊列中摘出一個相關的進程而進入就緒隊列。這就是I/O完成，是由于I/O外設完

15、成中斷信號所引起的從阻塞到就緒狀態的轉移。 結束下一步下一步下一步下一步下一步下一步下一步 中斷(zhngdun)與進程狀態轉換 進程狀態變遷是由于中斷，但中斷不一定產生進程切換！共七十一頁23/194.2.2 進程(jnchng)調度方式 非搶占(qingzhn)方式 進程調度基本方式可分為非搶占和搶占方式： 進程被選中就一直運行下去（不會因為時鐘中斷而被迫讓出CPU），直至完成工作、自愿放棄CPU、或因某事件而被阻塞才把CPU讓出給其它進程。4. 2 處理機調度 搶占方式 搶占方式發生的情況可為：新進程到達、出現中斷且將阻塞進程轉變為就緒進程、以及用完規定的時間片等。好處為進程提供更好的服

16、務，防止一個進程長期占有CPU ，但開銷大。 共七十一頁24/194.2.3 調度(diod)算法 作業調度算法(sun f)（第2章）與進程調度算法基本概念相通或相近的，只是空間位置有所不同。 系統中處于可運行狀態進程的個數通常比處理機的個數要多，特別是在單處理機系統中尤為如此。這樣就存在從就緒隊列中選擇哪一個進程，這就是調度算法問題。 調度算法要考慮到公平性和用戶的滿意程度，即考慮面向系統和面向用戶的兩個準則。 具體考慮有如下5個指標： 4. 2 處理機調度 共七十一頁25/19 CPU 利用率；CPU利用率就是使CPU盡量處于忙狀態，是系統的一個很重要(zhngyo)的目標。通常，在一定

17、的I/O等待時間的百分比之下，運行程序的道數越多，CPU空閑時間的百分比越低。 吞吐率；吞吐率就是單位(dnwi)時間內所處理的計算任務的數目，也是面向系統的一個重要指標。 4. 2 處理機調度 4.2.3 調度算法共七十一頁26/19 周轉時間；考慮到作業調度，則為作業等待進入內存、進程在就緒隊列中等待、進程在CPU上執行和完成有關(yugun)I/O操作所花費的時間總和。對于個作業i，其周轉時間為： 系統中n個作業平均(pngjn)周轉時間為：4. 2 處理機調度 4.2.3 調度算法t ci 為完成時間t si 為到達系統的時間共七十一頁27/19周轉(zhuzhun)時間；平均周轉(z

18、huzhun)時間：平均周轉時間可以衡量不同調度算法對相同任務流的調度性能。帶權周轉時間衡量長短任務的差別（R為實際運行時間）帶權周轉時間：周轉時間不具有區分實際運行時間長短的性質。平均帶權周轉時間：4. 2 處理機調度 4.2.3 調度算法共七十一頁28/19 響應時間；響應時間就是從任務就緒到處理開始（也有的稱為等待時間）。 在交互式系統中，周轉時間不可能是最好的評價準則。因為不斷請求與不斷輸出在同時發生。 通常，響應時間一般用于分時系統性能評價，指用戶通過鍵盤或終端提出一個(y )請求開始到系統給出相應的響應結果的時間（與上面有所不同）。 系統開銷；系統開銷就是系統調度任務的過程中所付出

19、的時/空代價。 4. 2 處理機調度(diod) 4.2.3 調度算法共七十一頁29/19 先來(xin li)先服務（FCFS） 也稱為先進先出（FIFO），或嚴格排隊方式。 對于作業調度，該算法(sun f)就是從后備作業隊列中（按進入的時間順序排隊）選擇隊首一個或幾個作業，調入內存，創建進程，放入就緒隊列。 對于進程調度，該算法就是從就緒隊列中選擇一個最先進入隊列的進程，將CPU分配于它。4. 2 處理機調度 4.2.3 調度算法共七十一頁30/19 例1有四個作業（或進程），他們(t men)相應的時間見表4.1： 表4.1 比較極端作業類型的FCFS 的調度(diod)性能 作業到達

20、時間 Tin服務時間Tr開始時間TS結束時間Tc周轉時間T帶權周轉時間WA0101TA=1WA=1B11001101TB=100WB=1C21101102TC=100WC=100D3100102202TD=199WD=1.99平均 = 100 = 26問題：C的周轉時間是所需要處理時間的100倍！ 作業D的周轉時間近乎是C的兩倍，但它的帶權周轉時間卻低于2.0。 先來先服務（FCFS） 共七十一頁31/19 例2更一般(ybn)的情況，設有五個作業，見表4.2 表4.2 更一般作業類型(lixng)的FCFS 的調度性能 作業到達時間Tin服務時間Tr開始時間Ts 結束時間Tc周轉時間T帶權周

21、轉時間WA0303TA=3WA=1B2639TB=7WB=1.17C44913TC=9WC=2.25D651318TD=12WD=2.40.E821820TE=12WE=6平均 =8.60 = 2.56同樣，看到作業E的不利情況。 先來先服務（FCFS） 共七十一頁32/19 短作業(zuy)/進程優先（SJF） 降低對長作業有利的一種(y zhn)方法就是短作業優先策略，見表4.3： 表4.3 SJF 的調度性能 作業到達時間Tin服務時間Tr開始時間Ts 結束時間Tc =1.84031115939152011TA=3TB=7TC=11TD=14TE=3=7.608364522046ABCD

22、EWE=1.50WA=1WB=1.17WC=2.75WD=2.80ECDAB周轉時間T=結束時間Tc-到達時間Tin=3-0=3周轉時間 T帶權周轉時間W=周轉時間T/服務時間Tr=3/3=1帶權周轉時 間W平均結束下一步下一步下一步下一步下一步下一步下一步共七十一頁33/19 SJF對短作業有利，明顯的作業E提前接受(jishu)了服務，并且整體性能也得到了提高；SJF的問題： SJF需要(xyo)事先知道或至少需要(xyo)估計每個作業所需的處理機時間。 只要不斷的有短作業進入系統，就有可能使長作業長期得不到運行而“餓死”。 SJF 偏向短作業，不利于分時系統（由于不可搶占性）。 短作業/

23、進程優先（SJF） 共七十一頁34/194.2.3 調度(diod)算法 最高響應(xingyng)比（HRP）4. 2 處理機調度 FCFS 強調的在系統的等待時間。 SJF 強調運行的時間；由此，考慮下面比值：式子R 既考慮了在系統的等待時間，又考慮了作業自身所需的運行時間，綜合了FCFS與SJP各自特點。在進行進程調度時，從中選擇響應比高者的進程投入運行。 共七十一頁35/19 表4.4 HRP 的調度(diod)性能 作業到達時間Tin服務時間Tr開始時間Ts 結束時間Tc =2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046

24、ABCDEWE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉(zhuzhun)時間T=結束時間Tc-到達時間Tin=3-0=3周轉時間 T帶權周轉時間W=周轉時間T/服務時間Tr=3/3=1帶權周轉時 間W平均=(9-4)+4/4=2.25=(9-6)+5/5=1.6=(9-8)+2/2=1.5RCRDRERD=(13-6)+5/5=2.4RE=(13-8)+2/2=3.5結束下一步下一步下一步下一步下一步 最高響應比（HRP）共七十一頁36/19不同(b tn)調度算法對同一個 作業/進程的性能分析:作業到達時間Tin服務時間Tr從平均周轉時間及其平均帶權周轉時間

25、來看，HRP 剛好介于FCFS與SJP之間，即好于FCFS，次于SJP。 A03B26C44D65E82FCFS8.602.56SJF7.601.84HRP8.002.14共七十一頁37/194.2.3 調度(diod)算法 最短剩余時間（SRT） SRT是針對 SJF 增加了強占機制的一種調度算法，它總是選擇(xunz)預期剩余時間最短的進程。只要新進程就緒，且有更短的剩余時間，調度程序就可能搶占當前正在運行的進程。 SRT不象FCFS偏向長進程，也不象輪轉法（下個算法）產生額外的中斷，從而減少了開銷。 必須記錄過去的服務時間，從而增加了開銷。 從周轉時間來看，SRT 比SJF 有更好的性能

26、。4. 2 處理機調度 共七十一頁38/19 表4.5 SRT 的調度(diod)性能 作業到達時間Tin服務時間Tr開始時間Ts 結束時間Tc =1.5903415831582010TA=3TB=13TC=4TD=14TE=2=7.208364522046ABCBEWE=1.00WA=1WB=2.17WC=1.00WD=2.80ECDAB周轉時間T=結束(jish)時間Tc-到達時間Tin=3-0=3周轉時間 T帶權周轉時間W=周轉時間T/服務時間Tr=3/3=1帶權周轉時 間W平均01234567891011121314151617181920DB剩余時間=6-1=5；C剩余時間=4-0=

27、4；0500結束下一步下一步下一步下一步下一步下一步 最短剩余時間（SRT） 共七十一頁39/19就這個例子，平均周轉時間和帶權平均周轉時間說明了它好于前面的任何一個算法（因為它具有搶占的特點(tdin)）。其過程的另一種簡單描述： A B C E B D t0 3 4 8 10 15 20其中，B在A之后運行1個單位后，到系統時刻4時，C進入系統（或就緒隊列(duli)），此時，系統計算B和C的最短剩余時間。由于B僅運行1個單位，還剩5個單位，而C是4個單位，所以C搶占了B而投入運行。 最短剩余時間（SRT） 共七十一頁40/19不同調度(diod)算法對同一個 作業/進程的性能分析:作業到

28、達時間Tin服務時間Tr從平均周轉時間及其平均帶權周轉時間來看，SRT 好于前面的任何一個算法。 A03B26C44D65E82FCFS8.602.56SJF7.601.84HRP8.002.14SRT7.201.59共七十一頁41/19 輪轉(lnzhun)（RRRound Robin） 輪轉法是一種(y zhn)基于時鐘的搶占策略，以一個周期性間隔產生的時鐘中斷依次進行各個進程的調度。當時鐘中斷發生時，當前正在運行的進程被置于就緒隊列中，然后再基于FCFS策略選擇下一個就緒進程運行。它主要用于分時系統中。輪轉法設計的問題是時間片的長度。一般有：4. 2 處理機調度 4.2.3 調度算法T

29、為系統響應時間q 為時間片n 為就緒隊列中進程數目。共七十一頁42/19 就緒隊列進程(jnchng)數目n；當系統要求的響應時間一定時，時間片反比于就緒隊列中進程的數目。 時間(shjin)片q；q 正比 T，反比于n。 CPU 運行指令的速度；CPU速度快，q可以小一些，反之亦然。 4. 2 處理機調度 4.2.3 調度算法 輪轉（RRRound Robin） 相關的參數說明: 系統響應時間T；在進程數目一定時，時間片的長短直接正比于系統響應時間。 共七十一頁43/19 表4.6 RR 的調度(diod)性能 作業到達時間Tin服務時間Tr開始時間Ts 結束時間Tc 周轉(zhuzhun)

30、時間 T帶權周轉時 間W=2.71025710418172015TA=4TB=16TC=13TD=14TE=7=10.808364522046WE=3.50WA=1.33WB=2.67WC=3.25WD=2.80ECDAB平均對于表 4.6 的直觀解釋參見圖 4.12。 輪轉（RRRound Robin） 共七十一頁44/194.2.3 調度算法（對同樣作業/進程(jnchng)情況下，5個算法比較）FCFS A B C D ESJF A B C D EHRP A B C D ESRT A B C D ERR Aq=1 B C D E 0 5 10 15 20 圖4.12 各種調度算法的比較4

31、. 2 處理機調度(diod) 共七十一頁45/19 級隊列(duli)（MQMultilevel Queue） 可根據進程某些特性，如優先級，類型等分成幾個(j )單獨隊列；每個隊列可有各自調度算法。例如，前臺利用 RR ，后臺利用 FCFS 等。 系統進程交互進程交互編輯進程批處理進程圖4.10 多級隊列調度隊列之間如何調度？4. 2 處理機調度 4.2.3 調度算法 各隊列間可采用固定優先級的搶占式調度 規定時間比例共七十一頁46/19 多級反饋(fnku)隊列（MFQ） 4. 2 處理機調度(diod) 4.2.3 調度算法在多級隊列調度法中，進程被固定地放入一個隊列中。就緒隊列1（8

32、ms）就緒隊列2（16ms）就緒隊列3（32ms）就緒隊列n（FCFS）圖4.11 多級反饋隊列調度處理機終止共七十一頁47/19 優先級法（HPF） 4. 2 處理機調度(diod) 4.2.3 調度(diod)算法如何確定進程優先級。有兩種確定的方法： 靜態優先級；進入系統時賦予一個優先級，在整個生命周期中一直固定不變（可能不公平）。 動態優先級；創建時賦予一個優先級，可以動態改變。如處于就緒狀態時，進程的優先級應隨著等待時間的增長而增高。 優點可使資源利用率得以提高，公平性比較好。 缺點是系統開銷大，實現比較復雜。 共七十一頁48/19表4.7 給出了不同(b tn)調度算法的一些信息，

33、并進行了比較。 算法比較項FCFSRRSJFSRTHRPMFQ調度方式非搶占式搶占式(按時間片)非搶占式搶占式(進程到達)非搶占式搶占式(按時間片)吞吐量不突出時間片太小,可能變低高高高不突出響應時間可能很高，對于短進程提供良好的響應時間對短作業/進程提供良好響應時間提供良好的響應時間提供良好的響應時間不突出開銷最小低可能高可能高可能高可能高對進程的作用不利于短作業/進程和I/O忙型公平對待不利于長作業/進程不利于長進程良好的均衡（進程）可能偏向I/O繁忙的作業/進程饑餓問題無無可能可能無可能表4.7 各種常用調度算法(sun f)的比較不適合作業調度共七十一頁49/194.2.4 調度(di

34、od)時機 何時有可能調用到處理機調度程序呢？前提條件是必須進入操作系統，即處于系統態。 處于用戶態運行的用戶程序不可能直接調用操作系統中的任何模塊（系統調用的例行服務程序除外）。 一般在以下事件發生(fshng)后要執行進程調度： 4. 2 處理機調度 共七十一頁50/19 創建(chungjin)進程；創建進程時。 進程終止；一個進程終止時必須進行調度。如果沒有就緒進程，系統通常會啟動一個空轉進程(休閑進程)等待(硬/軟)中斷(zhngdun)的發生。 等待事件；進程由于等待I/O、信號量或其它原因而放棄CPU，這樣就必須選擇另外一個進程。 中斷發生；當發生I/O中斷，原先等待I/O的進程

35、就從阻塞態轉變成就緒態，是否可強占。 運行到時；在分時系統中，當前進程用完給定的時間片，時鐘中斷使該進程讓出CPU進入調度。 調度運行就緒阻塞新建完成4.2.4 調度時機 共七十一頁51/194. 3 實時(sh sh)調度 4.3.1 實現實時調度的基本(jbn)條件 實時任務對時間有嚴格的要求，因而對實時系統中的調度提出了某些特殊要求。前面的多種調度算法并不能很好地滿足實時系統對調度的要求。實時系統中任務都與一個截止時間相關聯。 分為開始截止時間和完成截止時間；根據對截止時間的要求，實時任務可以分為： 硬實時任務時間要求嚴格。 軟實時任務不是絕對嚴格的。 共七十一頁52/194. 3 實時

36、(sh sh)調度 4.3.1 實現實時(sh sh)調度的基本條件 按照任務執行是否呈周期性規律來劃分，實時任務分為周期性和非周期性任務： 周期性任務是指以固定的時間間隔出現的事件，如每周期 T 執行一次。 非周期性任務是指事件的出現無法預測，但規定了必須完成或者開始的截止時間，或者兩者都規定。 實現實時調度應具備以下幾個條件： 共七十一頁53/19 提供(tgng)必要的信息 就緒時間；成為(chngwi)就緒狀態起始時間（PCB中）。在周期任務情況下，它就是預知的一串時間序列。 開始截止時間和完成截止時間。 處理時間；指任務從開始執行到完成所需時間。 資源要求；任務開始執行時所需的一組資

37、源。 優先級；如果任務開始截止時間已經錯過，就會引起故障，因而應為該任務賦予絕對優先級，供調度程序參考。 4. 3 實時調度 4.3.1 實現實時調度的基本條件 共七十一頁54/19 系統(xtng)處理能力 實時系統通常都有多個(du )實時任務，假定系統中有 m 個周期性的硬實時任務；處理時間表示為： 周期性時間為：單處理機下，滿足上面限制條件才是可調度的。 5個硬實時任務，周期都是40ms，處理時間為 10ms，則有：系統不可調度！4. 3 實時調度 4.3.1 實現實時調度的基本條件 （1）共七十一頁55/194. 3 實時(sh sh)調度 4.3.1 實現實時(sh sh)調度的基

38、本條件 系統處理能力 提高系統處理能力途徑有兩個： 對單處理機系統須增強其處理能力，以減少每個任務處理時間（如增強速度，使10ms減少為8ms）。 采用多處理機系統。假定系統中處理機數為N，則應將上述的限制條件改為（2）： （2）共七十一頁56/19 采用搶占(qingzhn)式調度機制 4. 3 實時(sh sh)調度 4.3.1 實現實時調度的基本條件 硬實時任務廣泛采用搶占機制。問題是這樣的調度機制是比較復雜和開銷大的。 具有快速切換機制 該機制應具有如下兩個方面的能力： 對外部中斷的快速響應能力；要求系統具有快速硬件中斷機構（一般沒有問題，可以作到）。 快速任務分派能力；在完成任務調度

39、后，就應進行任務切換，應使任務切換時間開銷盡可能小。 共七十一頁57/194.3.2 實時調度(diod)算法的分類 根據任務性質，分為硬實時和軟實時調度算法。 按調度方式，分為非搶占(qingzhn)式和搶占(qingzhn)式調度算法。 因調度時間不同而分成靜態和動態調度算法。 靜態是指進程執行前，調度程序已決定各進程間執行順序。 動態是指進程執行過程中由調度程序屆時根據情況臨時決定將哪一些進程投入運行。 在多處理機環境下，可將調度算法分為集中式和分布式調度。我們僅按調度方式的不同對調度算法進行分類。 4. 3 實時調度 共七十一頁58/19 非搶占(qingzhn)式調度算法 算法比較簡

40、單，易于實現，在小型實時(sh sh)系統，或不太嚴格的實時(sh sh)控制系統中采用，又可以分為兩種： 非搶占式輪轉調度算法；常用于工業生產群控系統中，由一臺計算機控制若干個相同（或類似）的對象（實時任務），將它們排成一個輪轉隊列，依次循環調度隊列中的任務投入運行。 非搶占式優先級調度算法；如果系統中存在要求較為嚴格任務，則可采用非搶占優先級調度算法。 4. 3 實時調度 4.3.2 實時調度算法的分類 共七十一頁59/19 搶占(qingzhn)式調度算法 根據搶占時間不同而分成以下兩種調度(diod)算法。4. 3 實時調度 4.3.2 實時調度算法的分類 基于時鐘中斷的搶占式優先級調

41、度算法；某實時任務到達后（優先級高于當前任務），并不立即搶占，而是等時鐘中斷到來時，調度程序才剝奪當前任務的執行。 立即搶占優先級調度算法；要求操作系統具有快速響應外部事件中斷的能力。一旦出現外部中斷，便能立即剝奪當前任務的執行。共七十一頁60/194.3.3 實時調度(diod)算法 最早截止時間(shjin)優先（EDF） 在常用的幾種中，根據確定優先級方式不同而有形成以下幾種實時調度算法。 該算法是根據任務的開始截止時間來確定任務的優先級。截止時間愈早，其優先級愈高。算法要求在系統中保持一個實時任務就緒隊列，該隊列按任務截止時間的早晚排序；當然，具有最早截止時間的任務排在隊列的最前面。4

42、. 3 實時調度 共七十一頁61/19最早截止時間優先算法既可以用于搶占式也可用于非搶占式方式中。圖4.13給出了該算法用于非搶占式調度方式示例。在該例子(l zi)中具有四個非周期任務，它們先后到達。 任務(rn wu)1任務執行任務到達任務1t圖4.13 DEF算法用于非搶占式調度方式任務3任務4任務2任務2任務3任務4開始截止時間：任務1的任務3的任務4的任務2的結束下一步下一步 最早截止時間優先（EDF） 共七十一頁62/194.3.3 實時調度(diod)算法 最低松弛(sn ch)度優先（LLF） 4. 3 實時調度 根據任務緊急（或松弛）程度來確定任務的優先級。任務緊迫程度愈高，

43、所賦予優先級愈高。例如，一個任務在200ms時必須完成，而它本身運行時間需要100ms，因此，調度程序必須在100 ms之前調度執行（松弛程度為100ms）。 在實現該算法時，要求系統中有一個按松弛度排序的實時任務就緒隊列，松弛度最低的（數值小的）任務排在隊列的前面。 共七十一頁63/19假如一個實時系統中有兩個周期性實時任務，A和B，任務A要求每20ms執行一次，執行時間(shjin)為10ms；任務B只要求每50ms執行一次，執行時間25ms。對于A，合適截止時間依次為20、40、60、80、100 ; 對于B，合適截止時間依次為50、100、150 ; 圖4.14 給出了A和 B截止的時

44、間點。 圖4.14 A和B任務(rn wu)每次必須完成的時間0 20 40 60 80 100 120 140 160 180 200A A A A A A A A A A t B B B B 最低松弛度優先（LLF） 共七十一頁64/19松弛度=必須完成(wn chng)的時間點 - 本身所需運行時間 - 當前時間:A1(10)B1(20) 0 10 20 30 40 50 60 70 80 90 100 t1 t2 t3 t4 t5 t6 t7 t8 t 圖4.15 利用LLF算法對兩個周期性實時任務(rn wu)進行調度A2(10)A3(10)A4(10)B1(5)B2(15)B2(1

45、0)初始：t=0時刻，計算A，B松弛度：A1= 20 10 0 = 10B1= 50 25 0 = 25t=10時刻，計算A，B松弛度：A2= 40 10 10 = 20B1= 50 25 10 = 15t=30時刻，計算A，B松弛度：A2= 40 10 30 = 0B1= 50 5 30 = 15t=40時刻，計算A，B松弛度：A3= 60 10 40 = 10B1= 50 5 40 = 5t=45時刻，計算A，B松弛度：A3= 60 10 45 = 5B2= 100 25 45 = 30t=55時刻，計算A，B松弛度：A4= 80 10 55 = 35B2= 100 25 55 = 20t=70時刻，計算A，B松弛度：A4= 80 10 70 = 0B2= 100 10 70 = 20t=80時刻，計算A，B松弛度：A5= 100 10 80 = 10B2=