1、第三章第三章 處理機調度與死鎖處理機調度與死鎖 主要內容3.1 處理機調度的層次和調度算法的目標處理機調度的層次和調度算法的目標3.2 作業與作業調度作業與作業調度3.3 進程調度進程調度3.4 實時調度實時調度3.5 死鎖概述死鎖概述3.6 預防死鎖預防死鎖3.7 避免死鎖避免死鎖3.8 死鎖的檢測與解除死鎖的檢測與解除第三章 處理機調度與死鎖在多道進程環境下，進程數目進程數目往往多于處理機數目處理機數目，致使它們爭用處理機。這就要求系統能按某種算法，動態動態地把處理機分配給就緒隊列中的一個進程，使之執行。分配處理機的任務是由進程調度程序進程調度程序完成的。它是操作系統設計的中心問題之一。

2、進程調度要解決的問題 WHATWHAT：按什么原則分配：按什么原則分配CPUCPU 進程調度算法 WHENWHEN：何時分配：何時分配CPUCPU 進程調度的時機 HOWHOW： 如何分配如何分配CPUCPU CPU調度過程（進程的上下文切換）第三章 處理機調度與死鎖第三章 處理機調度與死鎖3.1 處理機調度的層次 和調度算法的目標1. 處理機調度的層次 高級調度高級調度 又稱長程調度長程調度或作業調度作業調度。根據某種算法，決定將外存上處于后備隊列中的哪幾個作業調入內存，為它們創建進程、分配必要的資源，并將它們放入就緒隊列。高級調度主要用于多道批處理系統中。 低級調度低級調度 又稱為進程調度

3、進程調度或短程調度短程調度。根據某種算法，決定就緒隊列中的哪個進程應獲得處理機，并由分派程序，將處理機分配給被選中的進程。進程調度是最基本的一種調度。 中級調度中級調度 又稱為內存調度。引入中級調度的主要目的是，提高內存利用率和系統吞吐量。把那些暫時不能運行的進程，調至外存等待，把外存上的那些已具備運行條件的就緒進程，再重新調入內存。中級調度實際上就是存儲器管理中的對換功能中級調度實際上就是存儲器管理中的對換功能。2. 處理機調度算法的目標 處理機調度算法的共同目標處理機調度算法的共同目標 資源利用率資源利用率：為提高系統的資源利用率，應使系統中的處理機和其他所有資源都盡可能地保持忙碌狀態，其

4、中最重要的、處理機的利用率可用以下方法計算： 公平性公平性：指應使諸進程都獲得合理的CPU 時間，不會發生進程饑餓現象。 平衡性平衡性：使系統中的CPU和各種外部設備都能經常處于忙碌狀態，調度算法應盡可能保持系統資源使用的平衡性。 策略強制執行策略強制執行：對所制訂的策略其中包括安全策略，只要需要，就必須予以準確地執行，即使會造成某些工作的延遲也要執行。2. 處理機調度算法的目標 批處理系統的目標批處理系統的目標 平均周轉時間短：平均周轉時間短：使作業周轉時間作業周轉時間和作業的平均周轉時間作業的平均周轉時間盡可能短。否則，會使許多用戶的等待時間過長，這將會引起他們，特別是短作業用戶的不滿。可

5、把平均周轉時間平均周轉時間描述為： 作業的周轉時間作業的周轉時間T T與系統為它提供服務的時間與系統為它提供服務的時間T TS S之比，即之比，即W=T/TSW=T/TS，稱，稱為帶權周轉時間為帶權周轉時間。而平均帶權周轉時間則可表示為： 系統吞吐量高：系統吞吐量高：吞吐量是指在單位時間內系統所完成的作業數，因而它與批處理作業的平均長度有關。事實上，如果單純是為了獲得高的系統吞吐量，就應盡量多的選擇短作業運行。處理機利用率好：處理機利用率好：對于大、中型計算機，CPU價格十分昂貴，調度方式和算法又對處理機的利用率，起著十分重要的作用。如果單純是為使處理機利用率高。應盡量多的選擇計算量大的作業運

6、行。由上所述可以看出，這些要求之間是存在著一定矛盾的。2. 處理機調度算法的目標 分時系統的目標分時系統的目標 響應時間快：響應時間快：響應時間，是從用戶通過鍵盤提交一個請求開始，直到屏幕上顯示出處理結果為止的一段時間間隔。它包括三部分時間：請求信息從鍵盤輸入開始，直至傳送到處理機的時間，處理機對請求信息進行處理的時間，以及將所形成的響應信息回送到終端顯示器的時間。 均衡性：均衡性：所謂均衡性是指，系統響應時間的快慢應與用戶所請求服務的復雜性相適應。 返回2. 處理機調度算法的目標 實時系統的目標實時系統的目標 截止時間的保證截止時間的保證：對于HRT任務，其調度方式和調度算法必須確保對截止時

7、間的要求，否則將可能造成難以預料的后果；而對于SRT任務，其調度方式和調度算法也應基本上能保證對截止時間的要求。 可預測性可預測性：在實時系統中，可預測性顯得非常重要。2. 處理機調度算法的目標第三章 處理機調度與死鎖3.2 作業與作業調度1.1.作業和作業步作業和作業步p 作業作業：作業是一個比程序更為廣泛的概念，它不僅包含了通常的程程序序和數據數據，而且還應配有一份作業說明書作業說明書，系統根據該說明書來對程序的運行進行控制。在批處理系統中，是以作業為基本單位，從外存調入內存的。p 作業步作業步：在作業運行期間，每個作業都必須經過若干個相對獨立，又相互關聯的順序加工步驟才能得到結果。我們把

8、其中的每一個加工步驟稱一個作業步，各作業步之間存在著相互聯系，往往是上一個作業步的輸出作為下一個作業步的輸入。 2.2.作業控制塊作業控制塊JCBJCBp 在多道批處理系統中，為每個作業設置了一個作業控制塊JCB，它是作業在系統中存在的標志，其中保存了系統對作業進行管理和調度所需的全部信息。在作業運行期間，系統就按照JCBJCB中的信息，和作業說明書對作業進行控制。 3.3.作業運行的三個階段和三種狀態作業運行的三個階段和三種狀態 作業從進入系統到運行結束，通常需要經歷收容、運行和完成三個階段。相應的作業也就有“后備狀態”、“運行狀態”和“完成狀態”。p 收容階段：收容階段：操作員把用戶提交的

9、作業，通過某種輸入方式或SPOOLing系統，輸入到硬盤上，再為該作業建立JCB，并把它放入作業后備隊列中，相應的，此時作業的狀態為“后備狀態后備狀態”。p 運行階段：運行階段：當作業被作業調度選中后，便為它分配必要的資源和建立進程，并將它放入就緒隊列。一個作業從第一次進入就緒狀態開始，直到它運行結束前，在此期間都處于“運行狀態運行狀態”。p 完成階段：完成階段：當作業運行完成、或發生異常情況而提前結束時，作業便進入完成階段，相應的作業狀態為“完成狀態完成狀態”。此時系統中的“終止作業”程序，將會回收已分配給該作業的作業控制塊和所有資源，并將作業運行結果信息形成輸出文件后輸出。作業調度的主要任

10、務作業調度的主要任務根據JCB中的信息，檢查系統中的資源，能否滿足作業對資源的需求，以及按照一定的調度算法，從外存的后備隊列中，選取某些作業調入內存，并為它們創建進程、分配必要的資源。然后再將新創建的進程，排在就緒隊列上等待調度。因此，也把作 業 調 度作 業 調 度 稱為接 納 調 度接 納 調 度（Admission Scheduling）。在每次執行作業調度時，都須做出以下兩個決定在每次執行作業調度時，都須做出以下兩個決定接納多少個作業接納多少個作業取決于多道程序度多道程序度，即允許多少個作業同時在內存中運行。接納哪些作業接納哪些作業取決于所采用的調度算法調度算法。先來先服務先來先服務F

11、CFS（first-come first-served）調度算法）調度算法 該算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便執行下去，直到該進程完成或阻塞時，才釋放處理機。p 優點:實現簡單。p 缺點:沒考慮進程的優先級。短作業優先短作業優先SJFSJF（short job firstshort job first）的調度算法）的調度算法該算法從就緒隊列中選出“下一個CPU執行期”最短的進程，為之分配處理機。p 缺點：p 必須預知作業的運行時間；p 對長作業非常不利；p 在采用FCFS算法時，人機無法實現交互；p 該調度算法完全未考慮作業的緊迫程度，故不能保證緊迫性作

12、業能得到及時處理。優先級調度算法優先級調度算法(priority-scheduling algorithm)(priority-scheduling algorithm)基于作業的緊迫程度，由外部賦予作業相應的優先級，調度算法是根據該優先級進行調度的。這樣就可以保證緊迫性作業優先運行。高響應比優先調度算法高響應比優先調度算法 高響應比優先調度算法則是既考慮了作業的等待時間，又考慮作業運行時間的調度算法，因此既照顧了短作業，又不致使長作業的等待時間過長，從而改善了處理機調度的性能。高響應比優先算法的實現優先級的變化規律可描述為： 由于等待時間與服務時間之和，就是系統對該作業的響應時間，故該優先級

13、又相當于響應比響應比R RP P。據此，又可表示為： 返回第三章 處理機調度與死鎖3.3 進程調度3.3.1 進程調度的任務、機制和方式 1.1.進程調度任務進程調度任務 保存處理機的現場信息：保存處理機的現場信息：在進行調度時首先需要保存當前進程的處理機的現場信息，如程序計數器程序計數器、多個通用寄存器通用寄存器中的內容等。 按某種算法選取進程：按某種算法選取進程：調度程序按某種算法，從就緒隊列中選取一個進程，將其狀態改為運行狀態，并準備把處理機分配給它。 把處理器分配給進程：把處理器分配給進程：由分派程序分派程序把處理器分配給該進程。此時需要將選中進程的進程控制塊內有關處理機現場的信息，裝

14、入處理器相應的各個寄存器中，把處理器的控制權交予該進程，讓它從上次的斷點處恢復運行。3.3.1 進程調度的任務、機制和方式 2.進程調度機制進程調度機制 排隊器：排隊器：事先將系統中的所有就緒進程就緒進程，按照一定的策略，排成一個或多個隊列。以便調度程序能最快地找到它。以后每當有一個進程轉變為就緒狀態時，排隊器便將它插入到相應的就緒隊列。 分派器：分派器：依據進程調度程序進程調度程序所選定的進程，將其從就緒隊列中取出，然后進行進程間的上下文切換上下文切換，將處理機分配給新選出的進程。 上下文切換器：上下文切換器：在對處理機進行切換時，會發生： 第一對上下文切換時，OS將保存當前進程的上下文，裝

15、入分派程序的上下文，以便分派程序運行； 第二對上下文切換是移出分派程序的上下文，裝入新選進程上下文。3.3.1 進程調度的任務、機制和方式 3.進程調度方式進程調度方式 非搶占方式非搶占方式 一旦把處理機分配給某進程后，就一直讓它運行下去，決不會因為時鐘中斷，或任何其它原因，去搶占該正在運行進程的處理機，直至該進程完成，或發生某事件而被阻塞時，才把處理機分配給其它進程。 采用這種方式時，可能引起進程調度的因素可歸結為： 正在執行的進程運行完畢，或因發生某事件而使其無法再繼續運行；正在執行的進程運行完畢，或因發生某事件而使其無法再繼續運行； 正在執行中的進程，因提出正在執行中的進程，因提出I/O

16、I/O請求而暫停執行；請求而暫停執行； 在進程通信或同步過程中，執行了某種原語操作，如在進程通信或同步過程中，執行了某種原語操作，如BlockBlock原語。原語。 優點：優點：是實現簡單、系統開銷小，適用于大多數的批處理系統。 缺點：缺點：但它不能用于分時系統和大多數實時系統。3.進程調度方式 搶占方式搶占方式 允許調度程序根據某種原則，去暫停某個正在執行的進程，將已分配給該進程的處理機，重新分配給另一進程。 搶占方式能滿足實時任務的需求。但搶占方式比較復雜，所需付出統開銷也較大。 “搶占搶占” 必須遵循的原則必須遵循的原則 優先權原則：優先權原則：允許優先級高的新到進程，搶占當前進程的處理

17、機； 短進程優先原則：短進程優先原則：許新到的短進程，可以搶占當前長進程的處理機； 時間片原則：時間片原則：各進程按時間片輪轉運行時間片輪轉運行時，當正在執行的進程的一個時間片用完后，便停止該進程的執行而重新進行調度。3.3.2 輪轉調度算法 1.1.輪轉法的基本原理輪轉法的基本原理 系統將所有的就緒進程按FCFSFCFS策略策略，排成一個就緒隊列。系統可設置每隔一定時間（如30ms），便產生一次中斷，去激活進程調度程序進程調度程序進行調度，把CPU分配給隊首進程，并令其執行一個時間片。當它運行完后，又把處理機分配給就緒隊列中新的隊首進程，也讓它執行一個時間片。 2.2.進程切換時機進程切換時

18、機 若一個時間片尚未用完，正在運行的進程便已經完成，就立即激活調度程序，將它從就緒隊列中刪除，再調度就緒隊列中隊首進程運行，并啟動一個新的時間片。 在一個時間片用完時，此時計時器中斷處理程序被激活。如果進程尚未運行完畢，調度程序把它送往就緒隊列的末尾。 3.3.2 輪轉調度算法 3.時間片大小的確定 在輪轉算法中，時間片的大小，對系統性能有很大的影響。 若選擇很小的時間片，將有利于短作業，因為它能在該時間片內完成。 但時間片小，意味著會頻繁地執行進程調度，和進程上下文的切換，這無疑會增加系統的開銷。 若時間片選擇得太長，且為使每個進程，都能在一個時間片內完成，RR算法便退化為FCFS算法，無法

19、滿足短作業和交互式用戶的需求。 一個較為可取的時間片大小是，略大于一次典型的交互所需要的時間，使大多數交互式進程，能在一個時間片內完成，從而可以獲得很小的響應時間。3.時間片大小的確定下左圖示出了時間片大小對響應時間的影響，其中圖圖a a是時間片略大于典是時間片略大于典型交互的時間型交互的時間，其中圖圖b b是時間片小于典型交互的時間是時間片小于典型交互的時間。下右圖示出了時間片分別為q=1和q=4時對平均周轉時間的影響。3.3.2 輪轉調度算法3.3.3 優先級調度算法 1.1.優先級調度算法的類型優先級調度算法的類型 把處理機分配給就緒隊列中優先級最高的進程。 非搶占式優先級調度算法：非搶

20、占式優先級調度算法：一旦把處理機分配給就緒隊列中優先級最高的進程后，該進程便一直執行下去直至完成，或者因該進程發生某事件而放棄處理機時，系統方可將處理機重新分配給另一優先級最高的進程。 搶占式優先級調度算法：搶占式優先級調度算法：把處理機分配給優先級最高的進程，使之執行。但在其執行期間，只要出現了另一個其優先級更高的進程，調度程序就將處理機分配給新到的優先級最高的進程。 2.2.優先級的類型優先級的類型 靜態優先級：靜態優先級：靜態優先級是在創建進程時確定的，在進程的整個運行期間保持不變。優先級是利用某一范圍內的一個整數來表示的，例如0255中的某一整數，又把該整數稱為優先數。確定進程優先級大

21、小的依據有如下三個：進程類型、進程對資源的需求、 用戶要求。 動態優先級：動態優先級：動態優先級是指在創建進程之初，先賦予其一個優先級，然后其值隨進程的推進，或等待時間的增加而改變，以便獲得更好的調度性能。3.3.4 多級反饋隊列調度算法 算法思想算法思想 將就緒隊列分為N級，每個就緒隊列分配給不同的時間片，隊列級別越高，時間越長，級別越小，時間片越小，最后一級采用時間片輪轉，其他隊列采用先進先出； 系統從第一級調度，當第一級為空時，系統轉向第二個隊列，.當運行進程用完一個時間片，放棄CPU時，進入下一級隊列；等待進程被喚醒時，進入原來的就緒隊列；當進程第一次就緒時，進入第一級隊列。 算法要點

22、算法要點 * 首先系統中設置多個就緒隊列； * 每個就緒隊列分配給不同時間片，優先級高的為第一級隊列，時間片最小，隨著隊列級別的降低，時間片加大； * 各個隊列按照先進先出調度算法； * 一個新進程就緒后進入第一級隊列； * 進程由于等待而放棄CPU后，進入等待隊列，一旦等待的事件發生，則回到原來的就緒隊列； * 當有一個優先級更高的進程就緒時，可以搶占CPU，被搶占進程回到原來一級就緒隊列末尾； * 當第一級隊列空時，就去調度第二級隊列，如此類推； * 當時間片到后，進程放棄CPU，回到下一級隊列。3.3.4 多級反饋隊列調度算法 算法的性能 終端型用戶：由于終端型用戶提交的作業多屬于交互型

23、作業，通常較小，系統只要能使這些作業在第一隊列規定的時間片內完成，便可使終端型用戶感到滿意。 短批處理作業用戶：如果可在第一隊列中執行完成，便獲得與終端型作業一樣的響應時間。對于稍長的短作業，也只需在第二和第三隊列各執行一時間片完成，其周轉時間仍然較短。 長批處理作業用戶：將依次在第1，2，n個隊列中運行，然后再按輪轉方式運行，用戶不必擔心其作業長期得不到處理。3.3.5 基于公平原則的調度算法 1.保證調度算法保證調度算法 保證調度算法向用戶所做出的是明確的性能保證，該算法可以做到調度的公平性，如處理機分配的公平性。 在實施公平調度算法時系統中必須具有這樣一些功能： （1）跟蹤計算每個進程自

24、創建以來已經執行的處理時間； （2）計算每個進程應獲得的處理機時間，即自創建以來的時間除以n。 （3）計算進程獲得處理機時間的比率。 （4）比較各進程獲得處理機時間的比率。 （5）調度程序應選擇比率最小的進程，將處理機分配給它，并讓該進程一直運行，直到超過最接近它的進程比率為止。 2.公平分享調度算法公平分享調度算法 在該調度算法中，調度的公平性主要是針對用戶，使所有用戶能獲得相同的處理機時間，或所要求的時間比例。然而調度又是以進程為基本單位。為此，必須考慮到每一個用戶所擁有的進程數目。返回調度算法調度算法2.優先級法(1)靜態優先級(2)動態優先級 進程的動態優先級設定原則: a.根據進程占

25、有CPU時間的長短來決定 b.根據就緒進程等待CPU的時間長短來決定 缺點:由于動態優先級隨時間的推移而變化，系統要經常計算各進程的優先級，因此，為此付出一定的開銷。例2.10 有5個進程P1,P2,P3,P4,P5,它們依次進入就緒隊列,它們的優先數和需要的處理機時間如下表,要求:1.分別寫出采用FCFS算法和靜態優先級算法中進程的執行次序2.分別計算兩種算法中進程在就緒隊列中的等待時間和平均等待時間.進程進程處理機時間處理機時間 優先數優先數 等待時間等待時間 結束時間結束時間P1103P211P323P414P552FCFS算法:次序為P1,P2,P3,P4,P5其平均等待時間=(0+9

26、+9+10+10)/5=7.6靜態優先級算法執行次序為P1,P4,P3,P5,P2其平均等待時間=(0+7+9+9+17)/5=8.4有4個進程P1、P2、P3、P4，它們進入系統的時刻和要求的運行時間如下圖所示： 進程 進入時刻 要求運行時間 P1 0.000 3 P2 1.001 6 P3 4.001 4 P4 6.001 2 （1）畫圖分別說明，系統采用先來先服務和時間片輪轉(時間片=2)調度算法時，它們的執行情況；（2）分別計算上述兩種情況下進程的平均周轉時間。 習題習題.解:采用FCFS算法時,進程的執行順序為:P1,P2,P3,P4.即:CPUt0391315P1P2P3P4所以各

27、進程的完成時間分別為:3,9,13,15.則它們的周轉時間分別為: (3-0),(9-1.001),(13-4.001),(15-6.001)平均周轉時間為(3+7.999+8.999+8.999)/4=7.24925解:采用時間片輪轉(時間片=2)算法時,進程的執行順序如圖:P1t=0就緒隊列CPUt=2P1P2t=1.001時間片用完P1P2t=4P2P1t=4.001P3t=5P2t=6.001P4t=7P2P1結束CPUt02P1P24P15P27P39P3t=9P3P4P4t=11P4結束11P2P2t=13P2結束13P3P3t=15P3結束15因此,它們的完成時間分別為:5,13

28、,15,11其周轉時間分別為:5,11.999,10.999,4.999平均周轉時間為: (5+11.999+10.999+4.999)/4=8.24925 例題3-1：假如5個就緒進程其到達系統和所需CPU時間如下表所示（單位：毫秒），如果忽略I/O以及其他開銷分別計算采用FCFS、非搶占式SJF和搶占式SJF調度算法進行CPU調度的平均周轉時間和平均帶權周轉時間。進程到達和運行時間進程進程到達時間到達時間運行時間運行時間A03B26C44D65E82 解答如下：（1）采用FCFS的調度順序為：ABCDE039131820平均周轉時間為： T=(3-0)+(9-2)+(13-4)+(18-6

29、)+(20-8)/5=8.6帶權平均周轉時間為： W=2.56 （2）采用非搶占SJF的調度順序為：ABECD039111520平均周轉時間為： T=7.6帶權平均周轉時間為： W=1.84 （3）采用搶占SJF的調度順序為：平均周轉時間為： T=7.2帶權平均周轉時間為： W=1.59AB1ECB2038101520D4 例題3-2：假如5個就緒進程其到達系統和所需CPU時間如下表所示（單位：毫秒），如果忽略I/O以及其他開銷分別計算采用HRRN、時間片輪轉（RR，時間片為1）調度算法進行CPU調度的平均周轉時間和平均帶權周轉時間。進程到達和運行時間進程進程到達時間到達時間運行時間運行時間A

30、03B26C44D65E82例題3-2解答：（1）HRRF算法： 在時刻0時進程A就緒，此時，CPU空閑，故A運行，到了時刻2時進程B就緒，到了時刻3，進程A結束，進程B進入運行，到了時刻4，進程C就緒，此時B繼續運行，接著進程D、E先后到達，進入就緒狀態。在時刻9，進程B運行結束。此時調度程序要從C、D和E中選擇一個投入運行，為此，計算它們的響應比： rc=9/4=2.25 rd=8/5=1.60 re=3/2=1.50 因此，C進程被選擇投入運行。進程運行4個單位后結束 進程C運行4個單位后結束，調度程序需要從D和E進程挑選一個運行，為此，計算它們的響應比： rd=12/5=2.40 re

31、=7/2=3.5 因此，選擇E投入運行。 綜上所述，進程的調度順序為： A、B、C、E、D 平均周轉時間為： T=8.0 平均帶權周轉時間： W=2.14第三章 處理機調度與死鎖3.4 實時調度3.4.1 實現實時調度的基本條件 1.1.提供必要的信息提供必要的信息 系統應向調度程序提供有關任務的信息：就緒時間、開始截止時間和完成截止時間、處理時間、優先級。 2.2.系統處理能力強系統處理能力強 在實時系統中，若處理機的處理能力不夠強，則有可能因處理機忙不過，而致使某些實時任務不能得到及時處理，從而導致發生難以預料的后果： 單處理機系統增強； 多處理機系統：將上述的限制條件改為： 3.3.采用

32、搶占式調度機制采用搶占式調度機制 在含有HRT任務的實時系統中，廣泛采用搶占機制。這樣便可滿足HRT任務對截止時間的要求。 4.4.具有快速切換機制具有快速切換機制 該機制應具有如下兩方面的能力： （1）對中斷的快速響應能力：具有快速硬件中斷機構，禁止中斷的時間間隔盡量短； （2）快速的任務分派能力：使系統中的每個運行功能單位適當的小，以減少任務切換的時間開銷。3.4.2 實時調度算法的分類 對實時調度算法的分類 根據實時任務性質，可將實時調度的算法分為硬實時調度算法和軟根據實時任務性質，可將實時調度的算法分為硬實時調度算法和軟實時調度算法；實時調度算法； 按調度方式，則可分為非搶占調度算法和

33、搶占調度算法。按調度方式，則可分為非搶占調度算法和搶占調度算法。 1.非搶占式調度算法 非搶占式輪轉調度算法：非搶占式輪轉調度算法：將所有實時任務排成一個輪轉隊列，調度程序每次選擇隊列中的第一個任務投入運行，當該任務完成后，便把它掛在輪轉隊列的末尾等待。這種調度算法可獲得數秒至數十秒的響應時間。 非搶占式優先調度算法：非搶占式優先調度算法：當較高優先級的實時任務到達時，把它們安排在就緒隊列的隊首，等待當前任務自我終止或運行完成后，便可去調度執行隊首的高優先進程。使其響應時間減少到數秒至數百ms。2.搶占式調度算法 基于時鐘中斷的搶占式優先級調度算法：基于時鐘中斷的搶占式優先級調度算法：在某實時

34、任務到達后，如果它的優先級高于當前任務的優先級，這時并不立即搶占當前任務的處理機，而是等到時鐘中斷發生時，調度程序才剝奪當前任務的執行，將處理機分配給新到的高優先級任務。該算法調度延遲可降為幾十至幾ms。 立即搶占的優先級調度算法：立即搶占的優先級調度算法：在這種調度策略中，要求操作系統具有快速響應外部事件中斷的能力。一旦出現外部中斷，只要當前任務未處于臨界區，便能立即剝奪當前任務的執行，把處理機分配給請求中斷的緊迫任務。這種算法把調度延遲降低到幾ms至100微秒。3.4.2 實時調度算法的分類3.4.2 實時調度算法的分類3.4.3 最早截止時間優先算法 該算法是根據任務的截止時間確定任務的

35、優先級，具有最早截止時間的任務排在隊列的前面。 1.非搶占式調度方式用于非周期實時任務 3.4.3 最早截止時間優先算法 2.搶占式調度方式用于周期實時任務3.4.4 最低松弛度優先算法 該算法在確定任務的優先級時，根據的是任務的緊急（或松弛）程度。任務緊急程度愈高，賦予該任務的優先級就愈高，以使之優先執行。松弛度計算公式進程的松弛度=必須完成時間其本身的運行時間當前時間A和B任務每次必須完成的時間 利用ELLF算法進行調度的情況 3.4.5 優先級倒置 1.優先級倒置的形成 “優先級倒置”的現象 高優先級進程（或線程）被低優先級進程（或線程）延遲或阻塞。 例子 有三個完全獨立的進程P1、P2

36、和P3，P1的優先級最高，P2次之，P3最低。P1和P2通過共享的一個臨界資源進行交互。下面是一段代碼： P1： P（mutex）； CS-1； V(mutex)； P2： program2； P3： P（mutex）； CS-3； V(mutex) ；3.4.5 優先級倒置 2.優先級倒置的解決方法 一種簡單的解決方法 假如進程P3在進入臨界區后，P3所占用的處理機就不允許被搶占。 如果系統中的臨界區都較短且不多，該方法是可行的。反之，如果P3臨界區非常長，則高優先級進程P1仍會等待很長的時間，其效果是無法令人滿意的。 一個比較實用的方法 當高優先級進程P1要進入臨界區，去使用臨界資源R，如

37、果已有一個低優先級進程P3，正在使用該資源，此時一方面P1被阻塞，另一方面由P3繼承P1的優先級，并一直保持到P3退出臨界區。返回第三章 處理機調度與死鎖3.5 死鎖概述3.5.1 資源問題 在系統中有許多不同類型的資源，其中可以引起死鎖的主要是，需要采用互斥訪問方法的、不可以被搶占的資源，即在前面介紹的臨界資源。 1.可重用資源和消耗性資源可重用資源和消耗性資源 可重用資源可重用資源 一種可供用戶重復使用多次的資源。 性質：p 每一個可重用資源中的單元，只能分配給一個進程使用，不允許多個進每一個可重用資源中的單元，只能分配給一個進程使用，不允許多個進程共享；程共享；p 進程在對可重用資源的使

38、用時，須按照請求資源、使用資源、釋放資源進程在對可重用資源的使用時，須按照請求資源、使用資源、釋放資源這樣的順序。這樣的順序。p 系統中每一類可重用資源中的單元數目是相對固定的，進程在運行期間，系統中每一類可重用資源中的單元數目是相對固定的，進程在運行期間，既不能創建，也不能刪除。既不能創建，也不能刪除。 對資源的請求和釋放通常都是利用系統調用來實現的。計算機系統中大多數資源都屬于可重用資源。1.可重用資源和消耗性資源 可消耗資源可消耗資源 又稱為臨時性資源，它是在進程運行期間，由進程動態的創建和消耗的。 性質：p 每一類可消耗性資源的單元數目，在進程運行期間是可以不斷變化的，每一類可消耗性資

39、源的單元數目，在進程運行期間是可以不斷變化的，有時它可以有許多，有時可能為有時它可以有許多，有時可能為0 0；p 進程在運行過程中，可以不斷地創造可消耗性資源的單元，將它們放入進程在運行過程中，可以不斷地創造可消耗性資源的單元，將它們放入該資源類的緩沖區中，以增加該資源類的單元數目。該資源類的緩沖區中，以增加該資源類的單元數目。p 進程在運行過程中，可以請求若干個可消耗性資源單元，用于進程自己進程在運行過程中，可以請求若干個可消耗性資源單元，用于進程自己消耗，不再將它們返回給該資源類中。消耗，不再將它們返回給該資源類中。 可消耗資源通常是由生產者進程創建，由消費者進程消耗。最典型的可消耗資源，

40、就是用于進程間通信的消息進程間通信的消息等。3.5.1 資源問題 2.可搶占資源和不可搶占資源可搶占資源和不可搶占資源 可搶占資源可搶占資源 指某進程在獲得這類資源后，該資源可以再被其他進程或系統搶占。對于這類資源是不會引起死鎖的。 CPU和主存均屬于可搶占性資源。 不可搶占資源不可搶占資源 一旦系統把某資源分配給該進程后，就不能將它強行收回，只能在進程用完后自行釋放。 磁帶機、刻錄機、打印機等也都屬于不可搶占性資源。 3.5.2 計算機系統中的死鎖 死鎖的起因，通常是源于多個進程對資源的爭奪，不僅對不可搶占資源進行爭奪時，會引起死鎖，而且對可消耗資源進行爭奪時，也會引起死鎖。 1.競爭不可搶

41、占資源引起死鎖競爭不可搶占資源引起死鎖 共享文件時的死鎖情況 進程之間通信時的死鎖 2.競爭可消耗資源引起死鎖競爭可消耗資源引起死鎖順序1：P1： send（p2 , m1）； receive（p3, m3）； P2： send（p3 , m2）； receive（p1, m1）； P3： send（p1 , m3）； receive（p2, m2）； 順序2：P1： receive（p3, m3）； send（p2 , m1）； P2： receive（p1, m1）； send（p3 , m2）； P3： receive（p2, m2）； send（p1 , m3）； 死鎖3. 進程推進順

42、序不當引起死鎖進程推進順序不當引起死鎖3.5.3 死鎖的定義、必要條件和處理方法 1.死鎖的定義死鎖的定義 如果一組進程中的每一個進程都在等待，僅由該組進程中的其它進程才能引發的如果一組進程中的每一個進程都在等待，僅由該組進程中的其它進程才能引發的事件，那么該組進程是死鎖的。事件，那么該組進程是死鎖的。 2.產生死鎖的必要條件產生死鎖的必要條件 互斥條件：互斥條件：進程對所分配到的資源進行排它性使用。 請求和保持條件：請求和保持條件：進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源已被其它進程占有，此時請求進程被阻塞，但對自己已獲得的資源保持不放。 不可搶占條件不可搶占條件：進程已

43、獲得的資源，在未使用完之前不能被搶占，只能在進程使用完時由自己釋放。 循環等待條件：循環等待條件：指在發生死鎖時，必然存在一個進程資源的循環鏈，即進程集合P0，P1，P2，Pn中的P0，正在等待一個P1占用的資源， P1正在等待P2占用的資源，Pn正在等待已被P0占用的資源。3.5.3 死鎖的定義、必要條件和處理方法 3.處理死鎖的方法 預防死鎖：預防死鎖：這是一種較簡單和直觀的事先預防方法。該方法是通過設置某些限制條件，去破壞產生死鎖四個必要條件中的一個或幾個來預防產生死鎖。預防死鎖是一種較易實現的方法，已被廣泛使用。 避免死鎖：避免死鎖：同樣是屬于事先預防策略，但它并不是事先采取各種限制措

44、施，去破壞產生死鎖的四個必要條件，而是在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而可以避免發生死鎖。 檢測死鎖：檢測死鎖：這種方法無須事先采取任何限制性措施，允許進程在運行過程中發生死鎖。但可通過檢測機構，及時地檢測出死鎖的發生，然后采取適當措施，把進程中從死鎖中解脫出來。 解除死鎖：解除死鎖：當檢測到系統中已發生死鎖時，就采取相應措施，將進程從死鎖狀態中解脫出來。常用的方法是撤消一些進程，回收它們的資源，將它們分配給已處于阻塞狀態的進程，使其能繼續運行。返回第三章 處理機調度與死鎖3.6 預防死鎖1 1. . 破壞破壞“請求和保持請求和保持”條件條件 第一種協議第一種協議

45、該協議規定，所有進程在開始運行之前，必須一次性地申請其在整個運行過程中所需的全部資源。 優點：簡單、易行且安全。 缺點： 資源被嚴重浪費，嚴重地惡化了資源的利用率。 使進程經常會發生饑餓現象。 第二種協議第二種協議 允許一個進程只獲得運行初期所需的資源后，便開始運行。進程運行過程中再逐步釋放已分配給自己的、且已用畢的全部資源，然后再請求新的所需資源。 能使進程更快的完成任務，提高設備的利用率，還可減少進程發生饑餓的機率。2. 破壞“不可搶占”條件 為了能破壞“不可搶占”條件，協議中規定，當一個已經保持了某些不可被搶占資源的進程，提出新的資源請求而不能得到滿足時，它必須釋放已經保持的所有資源，待

46、以后需要時再重新申請。這意味著進程已占有的資源會被暫時地釋放，或者說是被搶占了，從而破壞了“不可搶占”條件。 缺點： 實現復雜，需付出很大的代價。 因為反復地申請和釋放資源，致使進程的執行被無限地推遲，這不僅延長了進程的周轉時間，而且也增加了系統開銷，降低了系統吞吐量。3. 破壞“循環等待”條件 一個能保證“循環等待”條件不成立的方法是，對系統所有資源類型進行線性排序，并賦予不同的序號。設R=（R1，R2，R3,，Rm）為資源類型的集合，為每個資源類型賦予唯一的序號。如果系統中有磁帶驅動器、硬盤驅動器、打印機，則函數F可按如下來定義： F（tape drive）= 1； F (disk dri

47、ve) = 5； F (printer) =12； 在對系統所有資源類型進行線性排序后，便可采用這樣的預防協議：規定每個進程，必須按序號遞增的順序請求資源。一個進程在開始時，可以請求某類資源Ri的單元。以后，當且僅當F(Rj)F(Ri)時，進程才可以請求資源Rj的單元。如果需要多個同類資源單元，則必須一起請求。 在采用這種策略時，應如何來規定每種資源的序號是十分重要的。通常應根據大多數進程需要資源的先后順序來確定。 這種預防死鎖的策略與前兩種策略比較，其資源利用率和系統吞吐量，都有較明顯的改善。但也存在下述問題： 限制了新類型設備的增加； 作業使用各類資源的順序與系統規定的順序不同，造成對資源

48、的浪費。 限制了用戶簡單、自主地編程。返回第三章 處理機調度與死鎖3.7 避免死鎖3.7.1系統安全狀態1.1.安全狀態安全狀態 指系統能按某種進程推進順序（P1，P2，Pn），為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。此時稱（P1，P2，Pn）為安全序列。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。2.2.安全狀態之例安全狀態之例 假定系統中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分

49、配，如下表所示：進程進程最最 大大 需需 求求已已 分分 配配可用可用P P1 110105 53 3P P2 24 42 2P P3 39 92 23.7.1系統安全狀態3.由安全狀態向不安全狀態的轉換由安全狀態向不安全狀態的轉換 如果不按照安全序分配資源，則系統可能會由安全狀態進入不安全狀態。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統把剩余3臺中的1臺分配給P3，則系統便進入不安全狀態。 因為，此時也無法再找到一個安全序列， 例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此

50、都在等待對方釋放資源，即陷入僵局，結果導致死鎖。 3.7.2 利用銀行家算法避免死鎖 銀行家算法中的數據結構銀行家算法中的數據結構 (1)(1)可利用資源向量可利用資源向量AvailableAvailable：是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果Availablej=K，則表示系統中現有Rj類資源K個。 (2)(2)最大需求矩陣最大需求矩陣MaxMax：是一個nm的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj

51、類資源的最大數目為K。 (3) (3) 分配矩陣分配矩陣AllocationAllocation：也是一個nm的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocationi,j=K，則表示進程i當前已分得Rj類資源的數目為K。 (4)(4)需求矩陣需求矩陣NeedNeed：也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數。如果Needi,j=K，則表示進程i還需要Rj類資源K個，方能完成其任務。 NeedNeedi,ji,j=Max=Maxi,ji,j-Allocation-Allocationi,ji,j 3.7.2 利用銀行家算法避免死鎖 銀行家算法 設設R

52、equestiRequesti是進程是進程PiPi的請求向量，如果的請求向量，如果RequestiRequestij j=K=K，表示進程，表示進程PiPi需需要要K K個個RjRj類型的資源。類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：(1)如果RequestijNeedi,j，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。(2)如果RequestijAvailablej，便轉向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。(3)系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值： AvailableAvailablej j=Availab

53、le=Availablej j-Requesti-Requestij j; ; Allocation Allocationi,ji,j=Allocation=Allocationi,ji,j+Requesti+Requestij j; ; Need Needi,ji,j=Need=Needi,ji,j-Requesti-Requestij j; ;(4)系統執行安全性算法系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。 資源分配資源分配Pi請求資源Reques

54、tINeedI請求超量，錯返RequestIAvailable不滿足，等待Available:=Available-RequestIAllocationI:=AllocationI+RequestINeedI:=NeedI-RequestI安全確認，pi繼續Available:=Available+RequestIAllocationI:=AllocationI-RequestINeedI:=NeedI+RequestIpi等待FTFTTF3.7.2 利用銀行家算法避免死鎖安全性算法 (1)(1)設置兩個向量設置兩個向量： 工作向量Work: 它表示系統可提供給進程繼續運行所需的各類資源數目，

55、它含有m個元素，在執行安全算法開始時，Work=Available; Finish: 它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false; 當有足夠資源分配給進程時， 再令Finishi=true。 (2)(2)從進程集合中找到一個能滿足下述條件的進程：從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到， 執行步驟(3)， 否則，執行步驟(4)。(3)(3)當進程當進程PiPi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源

56、，故應執行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; (4)(4)如果所有進程的如果所有進程的FinishFinishi i=true=true都滿足，都滿足， 則表示系統處于安全狀態；否則，系統處于則表示系統處于安全狀態；否則，系統處于不安全狀態。不安全狀態。 安全性檢測算法安全性檢測算法FWork:=Available;Finish:=false; 有滿足條件的j:Finishj=falseNeedjWorkFinishj=true;Work:=Work+AllocationjTj ,finishj=trueTF安全不安

57、全銀行家算法例子銀行家算法例子R=A(10),B(5),C(7)P=p0,p1,p2,p3,p4 Max Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 3 3 23 2 2 2 0 0 1 2 29 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1 P0:p1:p2:p3:p4:(1)當前系統是否安全當前系統是否安全? 銀行家算法之例 銀行家算法之例銀行家算法之例 (1)T0(1)T0時刻的安全性時刻的安全性： (2)p1

58、請求：請求：Request1=(1,0,2)安全進程序列：銀行家算法之例 (2)P1(2)P1請求資源：請求資源：P1P1發出請求向量發出請求向量Request1(1Request1(1，0 0，2)2)，系統按，系統按銀行家算法進行檢查：銀行家算法進行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號所示。 再利用安全性算法檢查此時系統是否安全。 銀行家算

59、法例子 Claim Allocation Need Available Work FinishA B C A B C A B C A B C A B C 7 5 3 0 1 0 7 4 3 2 3 03 2 2 3 0 2 0 2 09 0 2 3 0 2 6 0 02 2 2 2 1 1 0 1 14 3 3 0 0 2 4 3 1 P0:p1:p2:p3:p4:假定分配：安全進程序列:(3) p4請求請求:Request4=(3,3,0), 能否分配能否分配?(4) P0請求資源請求資源:P0發出請求向量發出請求向量Requst0(0，2，0)，能否分配能否分配?銀行家算法之例 (3) P

60、4(3) P4請求資源：請求資源：P4發出請求向量Request4(3，3，0)，系統按銀行家算法進行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓P4等待。 (4) P0(4) P0請求資源請求資源：P0發出請求向量Requst0(0，2，0)，系統按銀行家算法進行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系統暫時先假定可為P0分配資源，并修改有關數據，如圖所示。 銀行家算法示例銀行家