1、24 七月 2022第3章 處理機調度與死鎖24 七月 2022目 錄3.1 處理機調度的類型和準則3.2 作業調度算法3.3 進程調度算法3.4 死鎖的基本概念3.5 死鎖的預防和避免3.6 死鎖的檢測與解除24 七月 2022教學目標熟練掌握： 死鎖的產生、解決掌握： 調度算法 了解： 死鎖的預防和避免以及死鎖的檢測方法、解除方法。 24 七月 20223.1 處理機調度的類型和準則 處理機調度分為作業調度、進程調度和對換調度，不同操作系統中所采用的調度層次不完全相同。例如，批處理系統中，通常設置作業調度和進程調度；分時系統中只需設置進程調度，一些較完善的系統中還設置了對換調度。不同系統選

2、擇調度方式和算法的準則也可能不同。24 七月 20223.1.1 作業調度1.作業 作業是用戶在一次解題或一個事務處理過程中要求計算機系統所做工作的集合，包括用戶程序、所需的數據集作業說明書。通常作業控制塊中包含的主要內容有：資源要求。資源使用情況。作業的控制方式、類型和優先級等。作業名、作業狀態。24 七月 20222.作業的狀態及轉換 一個作業從進入系統到運行結束，一般需要經歷提交、收容、運行、完成4個階段。相應地，這4個階段對應的作業處于提交、后備、運行和完成4種狀態。作業的狀態及其轉換如下圖所示。24 七月 20223.作業調度的功能 作業調度又稱宏觀調度、高級調度或長程調度，是適用于

3、批處理系統的一種調度方式。其主要功能是按照一定的原則從外存作業后備隊列中選擇若干個作業裝入內存，給它們分配內存、I/O設備等必要的資源，并建立相應的進程，最后將新創建的進程插入就緒隊列。作業調度的運行頻率較低，通常為幾分鐘一次。 作業調度時，每次從外存后備隊列中選擇多少個作業調入內存，這取決于多道程序的度。多道程序的度指的是系統中能夠同時運行的作業數，應該保證作業調度后內存中的作業數不超過多道程序的度。24 七月 20224.作業調度的時機 系統進行作業調度時，要從時間和空間兩個方面考慮。首先看CPU是否有較多的空閑時間，其次看內存是否有足夠的可用區。通常，調度一個作業的時機有以下3種：時機1

4、23一個作業完成以后。新作業提交。處理機利用率低。24 七月 20223.1.2 進程調度 1.進程調度的功能 進程調度又稱微觀調度、短程調度或低級調度，其主要功能是按照某種策略從就緒隊列中選取一個進程，將處理機分配給它，使它執行。進程調度的運行頻率很高，一般幾十毫秒就運行一次。 進程調度是操作系統中最基本的一種調度，在一般的操作系統中都必須配置進程調度。24 七月 20222.進程調度方式非搶占方式和搶占方式3.進程調度的時機 引起進程調度的原因不僅與操作系統的類型有密切關系，而且還與下列因素有關：（1）當前進程完成。（2）當前進程由于某事件阻塞。（3）搶占調度方式下，一個新到來的進程比當前

5、進程的優先級高。（4）分配給當前進程的時間片已經用完。24 七月 20223.1.3 對換調度 對換調度又稱中程調度或中級調度，其主要功能是按照給定的原則和策略，將處于外存對換區中的具備執行條件的進程調入內存，或將處于內存的暫時不能執行的進程調到外存對換區。對換調度的運行頻率介于作業調度與進程調度之間。 引入對換調度的主要目的是提高內存的利用率和系統吞吐量，它實際上是存儲器管理中的交換功能，因此這部分內容將在存儲器管理部分介紹。24 七月 2022原因周轉時間短資源使用的均衡性響應時間短保證截止時間系統吞吐量CPU利用率高3.1.4 選擇調度方式和調度算法的準則24 七月 20223.2 作業

6、調度算法3.2.1 先來先服務調度算法 先來先服務調度算法是指每次從作業后備隊列中選擇最先進入該隊列的一個或幾個作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列，即哪一個作業先提交給系統，就先運行哪一個作業。24 七月 20223.2.2 短作業優先調度算法 短作業優先調度算法是指每次調度總是從作業后備隊列中選擇一個或幾個估計運行時間最短的作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列。24 七月 20223.2.3 優先級調度算法 優先級調度算法也稱為優先權調度算法，是基于作業運行緊迫性的一種調度算法。每個作業被賦予一個優先級，用于描述作業運行的緊迫程度。 作業調度

7、程序每次從作業后備隊列中選擇一個或幾個優先級最高的作業，將它們調入內存，分配必要的資源，創建進程并放入就緒隊列。 這種算法總是優先調度優先級高的作業，有可能使低優先級的作業處于“饑餓”狀態。24 七月 20223.2.4 高響應比優先調度算法 高響應比優先調度算法是FCFS和SJF兩種算法的折中，既考慮作業進入系統的時間，又顧及作業的運行時間的長度。響應比R可以定義如下： 響應比R=等待時間+服務時間/服務時間=等待時間/服務時間+1 作業等待時間是指一個作業從進入系統直到本次調度的時間。作業服務時間即作業的估計運行時間。 24 七月 2022 由響應比的計算公式可以看出： （1）作業服務時間

8、越短響應比越高，短小作業越能較快得到系統響應。因此該算法有利于短作業。 （2）對于服務時間相同的作業，等待時間長的作業響應比高，優先得到調度，即先來的作業優先。 （3）一個服務時間很長的作業在系統中等待的時間不斷增加，響應比就會不斷提高，被調用的可能性隨之不斷增大。這種算法可以避免大作業在系統中長期得不到調度。 因此，該算法既照顧了短作業，又兼顧了長作業，不足之處是每次調度都要計算所有后備作業的響應比，增加了系統開銷。24 七月 20223.3 進程調度算法 進程調度是任何類型操作系統中都具備的調度，也是最基本的調度，其性能優劣直接影響操作系統的性能。根據不同的系統設計目標，可選擇不同的進程調

9、度算法。常見的進程調度算法有先來先服務調度算法、短進程優先調度算法、優先級調度算法、時間片輪轉調度算法和多級反饋隊列調度算法。24 七月 20223.3.1 先來先服務調度算法 先來先服務（FCFS）調度算法是指每次從就緒隊列中選擇最先進入該隊列的進程，將處理機分配給它，使之執行，該進程一直執行下去，直到完成或因某種原因而阻塞時才釋放處理機。 同先來先服務作業調度算法一樣，該算法對長進程有利，對短進程不利。另外，該算法有利于CPU繁忙型作業，不利于I/O繁忙型作業。CPU繁忙型作業指需要大量的CPU時間進行計算，而很少請求I/O的作業；I/O繁忙型作業指需要頻繁請求I/O的作業。24 七月 2

10、0223.3.2 短進程優先調度算法 短進程優先（SPF）調度算法是指每次從就緒隊列中選擇估計執行時間最短的進程，將處理機分配給它，使之執行，該進程一直執行下去，直到完成或因某種原因而阻塞時才釋放處理機。 該算法可能使長進程長期得不到調度。24 七月 20223.3.3 優先級調度算法1.調度方式 根據已占有CPU的進程是否可被搶占可把優先級調度算法分為非搶占式優先級調度算法和搶占式優先級調度算法。24 七月 2022 2.優先級的類型 1）靜態優先級 （1）進程的類型。通常系統進程的優先級高于用戶進程的優先級，前臺用戶進程的優先級高于后臺用戶進程的優先級。 （2）進程所需的資源情況。根據進程

11、的資源需求量來確定優先級，如估計運行時間、所需內存大小、I/O的數量等。通常規定進程優先級與進程所需資源量多少成反比，即資源請求越多的進程優先級越低，反之越高。 （3）作業的優先級。根據作業的優先級來決定其所屬進程的優先級。24 七月 2022 2）動態優先級 動態優先級在進程創建時確定，隨著進程推進優先級發生變化。 （1）隨著就緒進程等待CPU時間的增加，優先級不斷提高。一個初始時優先級較低的進程，在就緒隊列中等待的時間越長，其優先級變得越高，一段時間以后其優先級將變得最高而獲得CPU。 （2）隨著進程占有CPU時間的增加，優先級不斷降低。在采用搶占調度方式的系統中，規定進程優先級隨著執行時

12、間的增加而降低，可防止一個進程長時間壟斷CPU。24 七月 20223.3.4 時間片輪轉調度算法 時間片輪轉（RR）調度算法主要用于分時系統中的進程調度。在時間片輪轉調度算法中，系統將所有就緒進程按到達時間的先后次序排成一個隊列，進程調度程序總是選擇就緒隊列中的隊首進程，讓它執行一個固定的時間片（如50 ms），時間片結束時若該進程未完成，系統便將它送至就緒隊列末尾，再把處理機分配給就緒隊列的隊首進程。這樣，就緒隊列中的進程輪流執行一個時間片，如此反復，直到完成為止。24 七月 20223.3.5 多級反饋隊列調度算法實現思想：（1）就緒隊列和時間片大小的設置.設置多個就緒隊列，各隊列賦予不

13、同的優先級。（2）進程排隊原則。（3）調度。每次調度選擇當前優先級最高的非空就緒隊列中的進程；若正在執行第i個隊列中的某進程時，有進程進入某高優先級的隊列，則該進程搶占處理機，將當前進程插入第i個隊列的末尾。24 七月 20223.4 死鎖的基本概念 在多道程序系統中，由于多個進程并發執行，改善了系統資源的利用率并提高了系統的吞吐量，但可能導致死鎖。例如，有一座獨木橋，如果有兩人分別從橋的兩邊上橋，當他們在橋上相遇時，若他們互不退讓，就會出現誰也不能過河的局面。 死鎖是指多個并發執行的進程因競爭系統資源而造成的一種僵局，若無外力作用，這些進程都將無法向前推進。24 七月 20223.4.1 產

14、生死鎖的原因 1.競爭資源引起死鎖 系統中的資源分為可剝奪性資源和不可剝奪性資源相應的，競爭資源有兩種。 1）競爭可剝奪性資源 可剝奪性資源是指進程獲得這種資源后，該資源又可被系統或其他進程剝奪。由于CPU可以被高優先級的進程搶占，因此，CPU屬于可剝奪性資源；由于作業可以在內存中移動，即進程的內存可被系統剝奪，因此，內存也屬于可剝奪性資源。進程在競爭這類資源時不會引起死鎖。24 七月 2022 2）競爭不可剝奪性資源 不可剝奪性資源是指進程獲得這種資源后，除非進程用完后自行釋放，系統不能強行收回。如磁帶機、打印機等大多數物理設備和一些共享數據結構都屬于不可剝奪性資源。競爭不可剝奪性資源可能引

15、起死鎖。 2.進程間推進順序不當引起死鎖 競爭資源可能引起死鎖，但不是必然，只有在競爭資源過程中，請求和釋放資源的順序不當才會產生死鎖。24 七月 2022進程要求對所分配的資源進行排他性控制一段時間內某資源僅為一個進程所占有。互斥條件在等待分配新資源的同時，進程繼續占有已分配到的資源。請求和保持條件進程所獲得的資源在未使用完畢之前，不能被其他進程強行奪走，即只能由獲得該資源的進程自行釋放。不剝奪條件存在一種進程資源循環等待鏈，鏈中的每一個進程已獲得的資源同時被鏈中的下一個進程所請求。循環等待條件必要條件3.4.2 產生死鎖的必要條件24 七月 2022方法123預防死鎖。通過設置某些限制條件

16、，去破壞產生死鎖的4個必要條件中的一個或幾個來防止發生死鎖。避免死鎖。在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而避免死鎖檢測及解除死鎖。通過系統的檢測機構及時地檢測出死鎖，然后采取某種措施解除死鎖。3.4.3 處理死鎖的基本方法24 七月 20223.5 死鎖的預防和避免 死鎖的預防和避免都是通過施加某些限制條件，來防止死鎖的發生。24 七月 20223.5.1 死鎖的預防 預防死鎖是一種靜態的解決死鎖問題的方法。為了使系統安全運行，應在設計操作系統時，對資源的使用進行適當限制，預防系統在運行過程中產生死鎖。由于產生死鎖的4個必要條件必須同時存在，系統才會產生死鎖，所以，只

17、要使4個必要條件中至少有一個不能成立，就可以達到預防死鎖的目的。由于互斥性是某些資源的固有特性（如打印機是一種不能同時供多個進程使用的互斥資源），所以一般不破壞互斥條件。 1）破壞不剝奪條件 2）破壞請求和保持條件 3）破壞循環等待條件24 七月 20223.5.2 死鎖的避免 1.安全狀態 如果在某時刻，系統能按某種進程順序如來為每個進程分配其所需的資源，直至最大需求，使每個進程都可以順利執行完成，則稱此時的系統處于安全狀態，稱序列為安全序列。若某一時刻系統中不存在任何一個安全序列，則稱此時的系統狀態為不安全狀態。24 七月 2022 并非所有的不安全狀態都必然轉化為死鎖狀態，但當系統進入不

18、安全狀態后，便可能進入死鎖狀態；反之，只要系統處于安全狀態，便可以避免進入死鎖狀態。因此，在避免死鎖的方法中，允許進程動態地申請資源，系統在進行資源分配之前，先計算資源分配的安全性。若此次分配不會導致系統進入不安全狀態，便將資源分配給進程，否則進程等待。24 七月 2022 2.安全狀態向不安全狀態的轉換 假定某系統中有R1、R2和R3三類資源，在T0時刻P1、P2、P3和P4這4個進程對資源的占用和需求情況見教材表324 七月 20223.6 死鎖的檢測與解除 死鎖預防和死鎖避免算法都是在系統為進程分配資源前或分配資源時施加限制條件或進行檢測。如果在分配資源時系統沒有采取任何措施，就必須提供

19、死鎖檢測和解除的手段。 死鎖的檢測和解除則是為進程分配資源時不采取任何措施，而是通過系統所設置的檢測機構，及時地檢測出死鎖的發生，然后采取適當的措施，將死鎖解除掉。因此，系統中必須保存資源的請求和分配信息，并提供一種算法來檢測系統是否已進入死鎖狀態。24 七月 20223.6.1 死鎖的檢測 1.資源分配圖 資源分配圖資源分配圖又稱進程資源圖。該圖由一組結點和一組邊構成，結點分為進程結點和資源結點，進程結點用圓圈表示，資源結點用方框表示，方框里的小圓圈的個數表示這類資源的數目。圖中的有向邊也分兩種，一種是由進程指向資源的有向邊，稱為請求邊，表示該進程請求一個某類資源；一種是由資源指向進程的有向邊，稱為分配邊，表示已分配給該進程一個某類資源。24 七月 2022 如圖下圖所示的資源分配圖中，有三個R1資源和兩個R2資源，已分配給進程P1兩個R1資源，分配給進程P2一個R1資源和一個R2資源。進程P1請求一個R2資源，進程P2請求一個R1資源。資源分配圖24 七月 2022 2.死鎖定理 可以通過將資源分配圖簡化的方法來檢測系統狀態S是否是死鎖狀態。簡化方式如下： （1）在資源分配圖中，找出一個既不孤立又不阻塞的進程結點Pi（即從進程集合中找到一個有邊相連，且資源申請數量小于或等于系統