CH處理機調度與死鎖復習第一頁，共29頁。1.處理機調度的層次及頻率三種調度：高級調度（作業調度）、低級調度（進程調度）、中級調度在上述三種調度中，進程調度的運行頻率最高，在分時系統中通常是10～100ms便進行一次進程調度，因此把它稱為短程調度。為避免進程調度占用太多的CPU時間，進程調度算法不宜太復雜。作業調度往往是發生在一個(批)作業運行完畢，退出系統，而需要重新調入一個(批)作業進入內存時，故作業調度的周期較長，大約幾分鐘一次，因此把它稱為長程調度。由于其運行頻率較低，故允許作業調度算法花費較多的時間。中級調度的運行頻率基本上介于上述兩種調度之間，因此把它稱為中程調度。第一頁第二頁，共29頁。2．一個典型的作業可分成三個作業步：①“編譯”作業步，通過執行編譯程序對源程序進行編譯，產生若干個目標程序段；②“連結裝配”作業步，將“編譯”作業步所產生的若干個目標程序段裝配成可執行的目標程序；③“運行”作業步，將可執行的目標程序讀入內存并控制其運行。第二頁第三頁，共29頁。3．低級調度的功能低級調度用于決定就緒隊列中的哪個進程(或內核級線程，為敘述方便，以后只寫進程)應獲得處理機，然后再由分派程序執行把處理機分配給該進程的具體操作。低級調度的主要功能如下：(1)保存處理機的現場信息。在進程調度進行調度時，首先需要保存當前進程的處理機的現場信息，如程序計數器、多個通用寄存器中的內容等，將它們送入該進程的進程控制塊(PCB)中的相應單元。(2)按某種算法選取進程。低級調度程序按某種算法如優先數算法、輪轉法等，從就緒隊列中選取一個進程，把它的狀態改為運行狀態，并準備把處理機分配給它。(3)把處理器分配給進程。由分派程序(Dispatcher)把處理器分配給進程。此時需為選中的進程恢復處理機現場，即把選中進程的進程控制塊內有關處理機現場的信息裝入處理器相應的各個寄存器中，把處理器的控制權交給該進程，讓它從取出的斷點處開始繼續運行。第三頁第四頁，共29頁。4．進程調度方式1)非搶占方式：在采用這種調度方式時，一旦把處理機分配給某進程后，不管它要運行多長時間，都一直讓它運行下去，決不會因為時鐘中斷等原因而搶占正在運行進程的處理機，也不允許其它進程搶占已經分配給它的處理機。直至該進程完成，自愿釋放處理機，或發生某事件而被阻塞時，才再把處理機分配給其他進程。2)搶占方式：這種調度方式允許調度程序根據某種原則去暫停某個正在執行的進程，將已分配給該進程的處理機重新分配給另一進程。第四頁第五頁，共29頁。5.搶占調度方式是基于一定原則搶占調度方式是基于一定原則的，主要有如下幾條：(1)優先權原則。通常是對一些重要的和緊急的作業賦予較高的優先權。當這種作業到達時，如果其優先權比正在執行進程的優先權高，便停止正在執行(當前)的進程，將處理機分配給優先權高的新到的進程，使之執行；或者說，允許優先權高的新到進程搶占當前進程的處理機。(2)短作業(進程)優先原則。當新到達的作業(進程)比正在執行的作業(進程)明顯的短時，將暫停當前長作業(進程)的執行，將處理機分配給新到的短作業(進程)，使之優先執行；或者說，短作業(進程)可以搶占當前較長作業(進程)的處理機。(3)時間片原則。各進程按時間片輪流運行，當一個時間片用完后，便停止該進程的執行而重新進行調度。這種原則適用于分時系統、大多數的實時系統，以及要求較高的批處理系統。第五頁第六頁，共29頁。6.選擇調度方式和調度算法的若干準則面向用戶的準則：(1)周轉時間短。(2)響應時間快。(3)截止時間的保證。(4)優先權準則。面向系統的準則(1)系統吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。第六頁第七頁，共29頁。7.調度算法先來先服務短作業(進程)優先調度算法高優先權優先調度算法基于時間片的輪轉調度算法計算各作業（或進程）的完成時間、周轉時間、帶權周轉時間以及平均時間。練習第七頁第八頁，共29頁。FCFS算法比較有利于長作業(進程)，而不利于短作業(進程)。下表列出了A、B、C、D四個作業分別到達系統的時間、要求服務的時間、開始執行的時間及各自的完成時間，并計算出各自的周轉時間和帶權周轉時間。第八頁第九頁，共29頁。圖3-4

FCFS和SJF調度算法的性能

第九頁第十頁，共29頁。8.FCFS調度算法特點據此可知，FCFS調度算法有利于CPU繁忙型的作業，而不利于I/O繁忙型的作業(進程)。CPU繁忙型作業是指該類作業需要大量的CPU時間進行計算，而很少請求I/O。通常的科學計算便屬于CPU繁忙型作業。I/O繁忙型作業是指CPU進行處理時需頻繁地請求I/O。目前的大多數事務處理都屬于I/O繁忙型作業。第十頁第十一頁，共29頁。9.SJ(P)F調度算法也存在不容忽視的缺點：(1)該算法對長作業不利，如作業C的周轉時間由10增至16，其帶權周轉時間由2增至3.1。更嚴重的是，如果有一長作業(進程)進入系統的后備隊列(就緒隊列)，由于調度程序總是優先調度那些(即使是后進來的)短作業(進程)，將導致長作業(進程)長期不被調度。(2)該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業(進程)會被及時處理。(3)由于作業(進程)的長短只是根據用戶所提供的估計執行時間而定的，而用戶又可能會有意或無意地縮短其作業的估計運行時間，致使該算法不一定能真正做到短作業優先調度。第十一頁第十二頁，共29頁。由上式可以看出：(1)如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該算法有利于短作業。(2)當要求服務的時間相同時，作業的優先權決定于其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。

(3)對于長作業，作業的優先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先級便可升到很高，從而也可獲得處理機。簡言之，該算法既照顧了短作業，又考慮了作業到達的先后次序，不會使長作業長期得不到服務。因此，該算法實現了一種較好的折衷。當然，在利用該算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。10．高響應比優先調度算法中響應比及分析第十二頁第十三頁，共29頁。11.實現實時調度的基本條件提供必要的信息：(1)就緒時間。這是該任務成為就緒狀態的起始時間，在周期任務的情況下，它就是事先預知的一串時間序列；而在非周期任務的情況下，它也可能是預知的。(2)開始截止時間和完成截止時間。對于典型的實時應用，只須知道開始截止時間，或者知道完成截止時間。(3)處理時間。這是指一個任務從開始執行直至完成所需的時間。在某些情況下，該時間也是系統提供的。(4)資源要求。這是指任務執行時所需的一組資源。(5)優先級。系統處理能力強采用搶占式調度機制具有快速切換機制：(1)對外部中斷的快速響應能力。為使在緊迫的外部事件請求中斷時系統能及時響應，要求系統具有快速硬件中斷機構，還應使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務)。(2)快速的任務分派能力。在完成任務調度后，便應進行任務切換。為了提高分派程序進行任務切換時的速度，應使系統中的每個運行功能單位適當地小，以減少任務切換的時間開銷。第十三頁第十四頁，共29頁。12.常用的幾種實時調度算法1．最早截止時間優先即EDF(EarliestDeadlineFirst)算法2．最低松弛度優先即LLF(LeastLaxityFirst)算法第十四頁第十五頁，共29頁。13.產生死鎖的原因產生死鎖的原因可歸結為如下兩點：(1)競爭資源。當系統中供多個進程共享的資源如打印機、公用隊列等，其數目不足以滿足諸進程的需要時，會引起諸進程對資源的競爭而產生死鎖。(2)進程間推進順序非法。進程在運行過程中，請求和釋放資源的順序不當，也同樣會導致產生進程死鎖。第十五頁第十六頁，共29頁。14.產生死鎖的必要條件雖然進程在運行過程中可能發生死鎖，但死鎖的發生也必須具備一定的條件。綜上所述不難看出，死鎖的發生必須具備下列四個必要條件。(1)互斥條件：指進程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個進程占用。如果此時還有其它進程請求該資源，則請求者只能等待，直至占有該資源的進程用畢釋放。(2)請求和保持條件：指進程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。(3)不剝奪條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。(4)環路等待條件：指在發生死鎖時，必然存在一個進程——資源的環形鏈，即進程集合{P0，P1，P2，…，Pn}中的P0正在等待一個P1占用的資源；P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。第十六頁第十七頁，共29頁。15.處理死鎖的基本方法(1)預防死鎖：該方法是通過設置某些限制條件，去破壞產生死鎖的四個必要條件中的一個或幾個條件，來預防發生死鎖。(2)避免死鎖：它并不須事先采取各種限制措施去破壞產生死鎖的四個必要條件，而是在資源的動態分配過程中，用某種方法去防止系統進入不安全狀態，從而避免發生死鎖。(3)檢測死鎖：這種方法并不須事先采取任何限制性措施，也不必檢查系統是否已經進入不安全區，而是允許系統在運行過程中發生死鎖。但可通過系統所設置的檢測機構，及時地檢測出死鎖的發生，并精確地確定與死鎖有關的進程和資源；然后，采取適當措施，從系統中將已發生的死鎖清除掉。(4)解除死鎖：這是與檢測死鎖相配套的一種措施。當檢測到系統中已發生死鎖時，須將進程從死鎖狀態中解脫出來。第十七頁第十八頁，共29頁。16．安全狀態所謂安全狀態，是指系統能按某種進程順序(P1，P2，…，Pn)(稱〈P1，P2，…，Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處于不安全狀態。第十八頁第十九頁，共29頁。安全狀態之例我們通過一個例子來說明安全性。假定系統中有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：第十九頁第二十頁，共29頁。由安全狀態向不安全狀態的轉換如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統把剩余3臺中的1臺分配給P3，則系統便進入不安全狀態。因為此時也無法再找到一個安全序列，第二十頁第二十一頁，共29頁。17.利用銀行家算法避免死鎖假定系統中有五個進程{P0，P1，P2，P3，P4}和三類資源{A，B，C}，各種資源的數量分別為10、5、7，在T0時刻的資源分配情況如圖3-16所示。圖3-16T0時刻的資源分配表

第二十一頁第二十二頁，共29頁。圖3-17

T0時刻的安全序列

(1)T0時刻的安全性：利用安全性算法對T0時刻的資源分配情況進行分析(見圖3-17所示)可知，在T0時刻存在著一個安全序列{P1，P3，P4，P2，P0}，故系統是安全的。第二十二頁第二十三頁，共29頁。(2)?P1請求資源：P1發出請求向量Request1(1，0，2)，系統按銀行家算法進行檢查：①Request1(1，0，2)≤Need1(1，2，2)②Request1(1，0，2)≤Available1(3，3，2)③系統先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如圖3-16中的圓括號所示。第二十三頁第二十四頁，共29頁。④

再利用安全性算法檢查此時系統是否安全。如圖3-18所示。

圖