1、1,第三章 進程管理,主講：何中勝 計算機科學工程系,2020年7月15日星期三,2,3.7 進程的調(diào)度,2020年7月15日星期三,3,無論是在批處理系統(tǒng)還是分時系統(tǒng)中，用戶進程數(shù)一般都多于處理機數(shù)，這將導致用戶進程互相爭奪處理機。另外，系統(tǒng)進程也同樣需要使用處理機。這就要求進程調(diào)度程序按一定的策略，動態(tài)地把處理機分配給處于就緒隊列中的某一個進程，以使之執(zhí)行。本節(jié)介紹進程調(diào)度的功能、進程調(diào)度發(fā)生的時機以及由進程調(diào)度引起的進程上下文切換等。,2020年7月15日星期三,4,分級調(diào)度,作業(yè)調(diào)度：又稱宏觀調(diào)度，或高級調(diào)度。其主要任務是按一定的原則對外存輸入井上的大量后備作業(yè)進行選擇，給選出的作業(yè)分

2、配內(nèi)存、輸入輸出設備等必要的資源，并建立相應的進程，以使該作業(yè)的進程獲得競爭處理機的權利。另外，當該作業(yè)執(zhí)行完畢時，還負責回收系統(tǒng)資源。 交換調(diào)度：又稱中級調(diào)度。其主要任務是按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或就緒等待狀態(tài)的進程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進程交換到外存交換區(qū)。交換調(diào)度主要涉及到內(nèi)存管理與擴充。,2020年7月15日星期三,5,分級調(diào)度(續(xù)),進程調(diào)度：又稱微觀調(diào)度或低級調(diào)度。其主要任務是按照某種策略和方法選取一個處于就緒狀態(tài)的進程占用處理機。在確定了占用處理機的進程后，系統(tǒng)必須進行進程上下文切換以建立與占用處理機進程相適應的執(zhí)行環(huán)境。 線程調(diào)

3、度。,2020年7月15日星期三,6,4級調(diào)度的關系,2020年7月15日星期三,7,在多道批處理系統(tǒng)中，存在著作業(yè)調(diào)度和進程調(diào)度。但是，在分時系統(tǒng)和實時系統(tǒng)中，一般不存在作業(yè)調(diào)度，而只有進程調(diào)度、交換調(diào)度和線程調(diào)度。這是因為在分時系統(tǒng)和實時系統(tǒng)中，為了縮短響應時間或為了滿足用戶需求的截止時間，作業(yè)不是建立在外存，而是直接建立在內(nèi)存中。在這些系統(tǒng)中，一旦用戶和系統(tǒng)的交互開始，用戶馬上要進行控制。因而，這些系統(tǒng)中沒有作業(yè)提交狀態(tài)和后備狀態(tài)。它們的輸入信息經(jīng)過終端緩沖區(qū)為系統(tǒng)所接收，或者立即處理，或者經(jīng)交換調(diào)度暫存外存中。,2020年7月15日星期三,8,進程調(diào)度方式,非搶占式(不可剝奪方式)：即

4、使就緒隊列中的某個進程的優(yōu)先級高于正在運行進程的優(yōu)先級，也要等運行進程主動讓出處理機后高優(yōu)先級進程才能得到處理機。 搶占式(可剝奪方式)：是指當就緒隊列中某一進程的優(yōu)先級高于正在運行的進程優(yōu)先級時，系統(tǒng)可剝奪正在運行進程的處理機的使用權(即使分配給它的時間片還沒有用完)，而使高優(yōu)先級的進程搶占處理機。,2020年7月15日星期三,9,引起進程調(diào)度的時機,(1) 正在執(zhí)行的進程執(zhí)行完畢。這時，如果不選擇新的就緒進程執(zhí)行，將浪費處理機資源。 (2) 執(zhí)行中進程自己調(diào)用阻塞原語將自己阻塞起來進入睡眠等待狀態(tài)。 (3) 執(zhí)行中進程調(diào)用了P原語操作，從而因資源不足而被阻塞；或調(diào)用了V原語操作激活了等待資

5、源的進程隊列。 (4) 執(zhí)行中進程提出IO請求后被阻塞。 (5) 在分時系統(tǒng)中時間片已經(jīng)用完。 (6) 在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進程時，可認為系統(tǒng)進程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進程執(zhí)行。 以上都是在CPU執(zhí)行不可剝奪方式下所引起進程調(diào)度的原因。在CPU執(zhí)行方式是可剝奪時，還有： (7) 就緒隊列中的某進程的優(yōu)先級變得高于當前執(zhí)行進程的優(yōu)先級，從而也將引發(fā)進程調(diào)度。,2020年7月15日星期三,10,進程調(diào)度程序的功能,(1)記錄系統(tǒng)中所有進程的有關信息。作為進程調(diào)度的準備，進程管理模塊必須將系統(tǒng)中各進程的執(zhí)行情況和狀態(tài)特征記錄在各進程的PCB表中。并且，進程管理模式根據(jù)各進

6、程的狀態(tài)特征和資源需求，將各進程的PCB表排成相應的隊列并進行動態(tài)隊列轉(zhuǎn)接。進程調(diào)度模塊通過PCB變化來掌握系統(tǒng)中所有進程的執(zhí)行情況和狀態(tài)特征，并在適當?shù)臅r機從就緒隊列中選擇出一個進程占據(jù)處理機。 (2)確定處理機的分配原則。即按照一定的策略選擇一個處于就緒狀態(tài)的進程，使其獲得處理機執(zhí)行。同時還確定將處理機分配給進程使用的時間片大小。根據(jù)不同的系統(tǒng)設計目的，有各種各樣的選擇策略，例如系統(tǒng)開銷較少的靜態(tài)優(yōu)先數(shù)調(diào)度法，適合于分時系統(tǒng)的輪轉(zhuǎn)法和多級反饋輪轉(zhuǎn)法等。這些選擇策略決定了調(diào)度算法的性能。,2020年7月15日星期三,11,進程調(diào)度程序的功能(續(xù)),(3)分配處理機。 (4)切換進程上下文。一

7、個進程的上下文（context）包括進程的狀態(tài)、有關變量和數(shù)據(jù)結構的值、硬件寄存器的值和PCB以及有關程序等。一個進程的執(zhí)行是在進程的上下文中執(zhí)行。當正在執(zhí)行的進程由于某種原因要讓出處理機時，系統(tǒng)要做進程上下文切換，以使另一個進程得以執(zhí)行。當進行上下文切換時，系統(tǒng)要首先檢查是否允許做上下文切換。然后，系統(tǒng)要保留有關被切換進程的足夠信息，以便以后切換回該進程時，順利恢復該進程的執(zhí)行。在系統(tǒng)保留了CPU現(xiàn)場之后，調(diào)度程序選擇一個新的處于就緒狀態(tài)的進程，并裝配該進程的上下文，使CPU的控制權轉(zhuǎn)換到被選中進程中。 (5)回收處理機。,2020年7月15日星期三,12,調(diào)度算法,1. 先來先服務（FCF

8、S）調(diào)度算法 將就緒進程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊列，并按照先來先服務的方式進行調(diào)度處理，是一種最普遍和最簡單的方法。在沒有特殊理由要優(yōu)先調(diào)度進程時，從處理的角度來看，F(xiàn)CFS方式是一種最合適的方法，無論是追加還是取出一個隊列元素在操作上都是最簡單的。 直觀看，該算法在一般意義下是公平的。即每個進程都按照它們在隊列中等待時間長短來決定它們是否優(yōu)先享受服務。不過對于那些執(zhí)行時間較短的進程來說，如果它們在某些執(zhí)行時間很長的進程之后到達，則它們將等待很長時間。在實際操作系統(tǒng)中，盡管很少單獨使用FCFS算法，但和其他一些算法配合起來，F(xiàn)CFS算法還是使用得相當多的。例如基于優(yōu)先級的調(diào)度算法就

9、是對具有同樣優(yōu)先級的進程采用的FCFS方式。,2020年7月15日星期三,13,調(diào)度算法(續(xù)),2. 輪轉(zhuǎn)調(diào)度算法（round robin scheduling） 輪轉(zhuǎn)法的基本思路是讓每個進程在就緒隊列中的等待時間與享受服務的時間成比例。輪轉(zhuǎn)法的基本概念是將CPU的處理時間分成固定大小的時間片。如果一個進程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時間片，但未完成要求的任務，則它自行釋放自己所占有的CPU而排到就緒隊列的末尾，等待下一次調(diào)度。同時，進程調(diào)度程序又去調(diào)度當前就緒隊列中的第一個進程或作業(yè)。輪轉(zhuǎn)法的原理見圖。 顯然，輪轉(zhuǎn)法只能用來調(diào)度分配那些可以搶占的資源。將它們隨時剝奪再分配給別的進程。CP

10、U是可搶占資源的一種。但如打印機等資源是不可搶占的。由于作業(yè)調(diào)度是對除了CPU之外的所有系統(tǒng)硬件資源的分配，其中包含有不可搶占資源，所以作業(yè)調(diào)度不使用輪轉(zhuǎn)法。,2020年7月15日星期三,14,調(diào)度算法(續(xù)),在輪轉(zhuǎn)法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響系統(tǒng)開銷和響應時間。如果時間片長度過短，則調(diào)度程序剝奪處理機的次數(shù)增多。這將使進程上下文切換次數(shù)也大大增加，從而加重系統(tǒng)開銷。反過來，如果時間片長度選擇過長，比方說一個時間片能保證就緒隊列中所需執(zhí)行時間最長的進程能執(zhí)行完畢，則輪轉(zhuǎn)法變成了先來先服務法。 此時間片值的設置可以是固定的(固定周期輪轉(zhuǎn))，也可以是可變的(可變

11、周期輪轉(zhuǎn))。 RR算法主要用于分時系統(tǒng)或事務處理系統(tǒng)，可保證對各終端用戶的及時響應。但它對偏重CPU的進程和偏重I/O的進程有不同的處理結果，可以采用虛擬時間片輪轉(zhuǎn)(VRR)策略來避免這個問題。新加入的特性是附加一個FCFS策略隊列來收集從I/O等待中釋放的進程。,2020年7月15日星期三,15,3. 多級反饋輪轉(zhuǎn)法 在輪轉(zhuǎn)法中，加入到就緒隊列的進程有三種情況，一種是分給它的時間片用完，但進程還未完成，回到就緒隊列的末尾等待下次調(diào)度去繼續(xù)執(zhí)行。另一種情況是分給該進程的時間片并未用完，只是因為請求IO或由于進程的互斥與同步關系而被阻塞。當阻塞解除之后再回到就緒隊列。再有一種情況就是新創(chuàng)建進程進

12、入就緒隊列。如果對這些進程區(qū)別對待，給予不同的優(yōu)先級和時間片，從直觀上看，可望進一步改善系統(tǒng)服務質(zhì)量和效率。例如，可把就緒隊列按照進程到達就緒隊列的類型和進程被阻塞時的阻塞原因分成不同的就緒隊列，每個隊列按FCFS原則排列，各隊列之間的進程享有不同的優(yōu)先級，但同一隊列內(nèi)優(yōu)先級相同。這樣，當一個進程在執(zhí)行完它的時間片之后，或從睡眠中被喚醒以及被創(chuàng)建之后，將進入不同的就緒隊列。多級反饋輪轉(zhuǎn)法與優(yōu)先級法在原理上的區(qū)別是，一個進程在它執(zhí)行結束之前，可能需要反復多次通過反饋循環(huán)執(zhí)行，而不是優(yōu)先級法中的一次執(zhí)行。,調(diào)度算法(續(xù)),2020年7月15日星期三,16,2020年7月15日星期三,17,調(diào)度算法

13、(續(xù)),4. 優(yōu)先級法 首先，系統(tǒng)或用戶按某種原則為進程指定一個優(yōu)先級來表示該進程所享有的調(diào)度優(yōu)先權。該算法的核心是確定進程的優(yōu)先級。這種算法可以是搶占式也可是非搶占式的。 確定優(yōu)先級的方法：靜態(tài)法和動態(tài)法。 靜態(tài)法根據(jù)進程的靜態(tài)特性在進程執(zhí)行之前就確定它們的優(yōu)先級，而且在執(zhí)行過程中一直保持不變。動態(tài)法則是將進程的靜態(tài)特性與動態(tài)特性結合起來確定進程的優(yōu)先級而且隨著進程的運行，其優(yōu)先級不斷變化。,2020年7月15日星期三,18,進程的靜態(tài)優(yōu)先級確定原則可以是： (1) 按進程的類型給予不同的優(yōu)先級。例如，在有些系統(tǒng)中，進程被劃分為系統(tǒng)進程和用戶進程。系統(tǒng)進程享有比用戶進程高的優(yōu)先級。對于用戶進

14、程來說，則可以分為： IO繁忙的進程， CPU繁忙的進程， IO與CPU均衡的進程， 其他進程。 對系統(tǒng)進程，也可以根據(jù)其所要完成的功能劃分為不同的類型，例如，調(diào)度進程、IO進程、中斷處理進程、存儲管理進程等。這些進程還可進一步劃分為不同類型和賦予不同的優(yōu)先級。例如，在操作系統(tǒng)中，對于鍵盤中斷的處理優(yōu)先級和對于電源掉電中斷的處理優(yōu)先級是不相同的。 (2) 將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進程的優(yōu)先級,2020年7月15日星期三,19,動態(tài)優(yōu)先級 基于靜態(tài)優(yōu)先級的調(diào)度算法實現(xiàn)簡單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結束為止始終保持不變，從而系統(tǒng)效率較低，調(diào)度性能不高?，F(xiàn)在的操作系統(tǒng)中

15、，如果使用優(yōu)先級調(diào)度的話，則大多采用動態(tài)優(yōu)先級的調(diào)度策略。 進程的動態(tài)優(yōu)先級一般根據(jù)以下原則確定： (1) 根據(jù)進程占有CPU時間的長短來決定。一個進程占有處理機的時間愈長，則在被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之，其獲得調(diào)度的可能性就會越大。 (2) 根據(jù)就緒進程等待CPU的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長，則它獲得調(diào)度選中的優(yōu)先級就越高。 由于動態(tài)優(yōu)先級隨時間的推移而變化，系統(tǒng)要經(jīng)常計算各進程的優(yōu)先級，因此，系統(tǒng)要為此付出一定的開銷。,2020年7月15日星期三,20,5. 最短進程優(yōu)先法（shortest process first） 最短作業(yè)優(yōu)先法（SPF）

16、就是從就緒隊列中選擇那些估計需要執(zhí)行時間最短的進程將處理機分配給它。 6. 最高響應比優(yōu)先法（highest responseratio next） 最高響應比優(yōu)先法（HRN）是對FCFS方式和SJF 方式的一種綜合平衡。HRN調(diào)度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應比最高的作業(yè)投入執(zhí)行。,調(diào)度算法(續(xù)),2020年7月15日星期三,21,實時調(diào)度算法,實現(xiàn)實時調(diào)度的基本條件 提供必要的信息(就緒時間、截止時間、處理時間、資源優(yōu)先級) 系統(tǒng)處理能力強 采用搶占式調(diào)度機制 具有快速切換機制 實時調(diào)度算法的分類 1)非搶占式調(diào)度算法 : 非搶占式輪轉(zhuǎn)調(diào)度算法 非

17、搶占式優(yōu)先調(diào)度算法 2)搶占式調(diào)度算法: 基于時鐘中斷的搶占優(yōu)先調(diào)度算法 立即搶占優(yōu)先權調(diào)度算法。,2020年7月15日星期三,22,2020年7月15日星期三,23,常用的幾種實時調(diào)度算法,1）最早截止時間優(yōu)先即EDF(Earliest Deadline First)算法 EDF算法用于非搶占調(diào)度方式,2020年7月15日星期三,24,2）最低松弛度優(yōu)先(LLF)算法 該算法是根據(jù)任務緊急(或松弛)的程度，來確定任務的優(yōu)先級。該算法主要用于可搶占調(diào)度方式中。 假如在一個實時系統(tǒng)中，有兩個周期性實時任務A和B，任務A要求每 20 ms執(zhí)行一次，執(zhí)行時間為 10 ms；任務B只要求每50 ms執(zhí)

18、行一次，執(zhí)行時間為 25 ms。,A和B任務每次必須完成的時間,2020年7月15日星期三,25,在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運行又需 10 ms，可算出A1的松弛度為10ms；B1必須在50ms時完成， 而它本身運行就需25 ms，可算出B1的松弛度為25 ms，故調(diào)度程序應先調(diào)度A1執(zhí)行。在t2=10 ms時，A2的松弛度可按下式算出： A2的松弛度=必須完成時間-其本身的運行時間-當前時間 =40 ms-10 ms-10 ms=20 ms 類似地，可算出B1的松弛度為15ms，調(diào)度程序應選擇B2運行。t3=30 ms時，A2的松弛度已減為0，B1的松弛度為1

19、5 ms，于是調(diào)度程序應搶占B1的處理機而調(diào)度A2運行.,利用ELLF算法進行調(diào)度的情況,2020年7月15日星期三,26,其它算法,時限調(diào)度算法與頻率單調(diào)調(diào)度算法。時限調(diào)度算法是一種以滿足用戶要求的時限為調(diào)度原則的算法。在實時系統(tǒng)中的用戶要求時限有兩種，即處理開始時限和處理結束時限。時限調(diào)度算法可以使用任一種時限。時限調(diào)度算法不可用于周期性調(diào)度與非周期性調(diào)度兩種。 時限調(diào)度算法的基本思想是：按用戶的時限要求順序設置優(yōu)先級，優(yōu)先級高者占據(jù)處理機，也就是說，時限要求最近的任務優(yōu)先占有處理機。時限調(diào)度是搶先式的。搶先式時限調(diào)度算法必須把新到達任務的時限要求和當前正在執(zhí)行任務的時限要求進行比較，如果

20、新到達任務的時限要求更近，則應執(zhí)行新到達的任務。 時限調(diào)度算法也可以用于非周期性任務調(diào)度。,2020年7月15日星期三,27,頻率單調(diào)調(diào)度算法是一種被廣泛用于多周期性實時處理的調(diào)度算法。 頻率單調(diào)調(diào)度算法的基本原理是頻率越低（周期越長）的任務的優(yōu)先級越低。 另外，設任務周期問題，任務的執(zhí)行時間為C，則使用頻率單調(diào)調(diào)度算法的必要條件是C T。,2020年7月15日星期三,28,3.8 死鎖,2020年7月15日星期三,29,死鎖例子,一個由于申請不同類型資源而產(chǎn)生死鎖的例子 設系統(tǒng)有一臺打印機(R1)一臺掃描儀(R2)，兩進程共享這兩臺設備。 用信號量S1表示R1是否可用，用信號量S2表示R2是

21、否可用， S1、 S2初值為1。,這兩個進程在并發(fā)執(zhí)行過程中，可能會發(fā)生死鎖。大家可以思考一下，如何修改，進程才不會發(fā)生死鎖。,2020年7月15日星期三,30,死鎖的概念,所謂死鎖，是指各并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。下圖是兩個進程發(fā)生死鎖時的例子。,2020年7月15日星期三,31,關于死鎖的一些結論,參與死鎖的進程最少是兩個 參與死鎖的進程至少有兩個已經(jīng)占有資源 參與死鎖的所有進程都在等待資源 參與死鎖的進程是當前系統(tǒng)中所有進程的子集 注：如果死

22、鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(tǒng)崩潰。,2020年7月15日星期三,32,永久性資源和臨時性資源,永久性資源：可以被多個進程多次使用（可再用資源） 可搶占資源 不可搶占資源 臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源） “申請-分配-使用-釋放”模式,2020年7月15日星期三,33,引起死鎖的原因,有限資源的競爭 并發(fā)進程推進的順序不當,2020年7月15日星期三,34,1. 競爭系統(tǒng)資源,若系統(tǒng)中只有一臺打印機R1和一臺讀卡機R2，可供進程P1和P2共享。若形成環(huán)路，這樣會產(chǎn)生死鎖。,2020年7月15日星期三,35,2.進程的推進順序不當,在進程

23、P1和P2并發(fā)執(zhí)行時，按照下圖曲線所示順序推進時，兩進程會順利完成，我們稱這種推進順序是合法的。若按曲線的順序推進時，進入不安全區(qū)D內(nèi)，兩進程再推進會產(chǎn)生死鎖。,2020年7月15日星期三,36,系統(tǒng)資源類型,可剝奪資源：存儲器 和不可剝奪資源：如打印機 死鎖的起因是并發(fā)進程的資源競爭。產(chǎn)生死鎖的根本原因在于系統(tǒng)提供的資源個數(shù)少于并發(fā)進程所要求的該類資源數(shù)。顯然，由于資源的有限性，不可能為所有要求資源的進程無限制地提供資源。但是，可以采用適當?shù)馁Y源分配算法，以達到消除死鎖的目的。為此，先看看產(chǎn)生死鎖的必要條件。,2020年7月15日星期三,37,產(chǎn)生死鎖的必要條件,(1) 互斥條件。并發(fā)進程所

24、要求和占有的資源是不能同時被兩個以上進程使用或操作的，進程對它所需要的資源進行排他性控制。 (2) 不剝奪條件。進程所獲得的資源在未使用完畢之前，不能被其他進程強行剝奪，而只能由獲得該資源的進程自己釋放。 (3) 部分分配。進程每次申請它所需要的一部分資源，在等待新資源的同時繼續(xù)占用已分配到的資源。 (4) 環(huán)路條件。存在一種進程循環(huán)鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。 顯然，只要使上述4個必要條件中的某一個不滿足，則死鎖就可以排除。,2020年7月15日星期三,38,饑餓(starvation),是指系統(tǒng)資源分配不合理 與死鎖區(qū)別：處于饑餓態(tài)的進程可能 是一個，也可能 是多

25、個。而處于死鎖狀態(tài)的進程至少是兩個；饑餓不是對資源的循環(huán)等待，而是單向等待。處于饑餓態(tài)的進程所等待的事件不是永遠不發(fā)生，而是在發(fā)生時總是被別的進程先響應?！梆囸I”現(xiàn)象是可以避免的,2020年7月15日星期三,39,死鎖的排除方法,解決死鎖的方法一般可分為預防、避免、檢測與恢復等三種。預防是采用某種策略，限制并發(fā)進程對資源的請求，從而使得死鎖的必要條件在系統(tǒng)執(zhí)行的任何時間都不滿足。避免是指系統(tǒng)在分配資源時，根據(jù)資源的使用情況提前做出預測，從而避免死鎖的發(fā)生。死鎖檢測與恢復是指系統(tǒng)設有專門的機構，當死鎖發(fā)生時，該機構能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進

26、程從死鎖狀態(tài)中恢復出來。 通過預防和避免的手段達到排除死鎖的目的是一件十分困難的事。死鎖的檢測和恢復則不必花費多少執(zhí)行時間就能發(fā)現(xiàn)死鎖和從死鎖中恢復出來。因此，在實際操作系統(tǒng)中大都使用檢測與恢復法排除死鎖,2020年7月15日星期三,40,死鎖預防,一種方法是打破資源的互斥和不可剝奪這兩個條件，例如允許進程同時訪問某些資源等。這種方法不能解決訪問那些不允許被同時訪問的資源時所帶來的死鎖問題。另一種方法則是打破資源的部分分配這個死鎖產(chǎn)生的必要條件。即預先分配各并發(fā)進程所需要的全部資源。如某個進程的資源得不到滿足時，則安排一定的等待次序讓其他進程釋放資源。但是，這種方法也有如下缺點： (1) 在許

27、多情況下，一個進程在執(zhí)行之前不可能提出它所需要的全部資源。 (2) 無論所需資源何時用到，一個進程只有在所有要求資源都得到滿足之后才開始執(zhí)行。 (3) 對于那些不經(jīng)常使用的資源，進程在生存過程期間一直占用它們是一種極大的浪費。 (4) 降低了進程的并發(fā)性。,2020年7月15日星期三,41,另外一種死鎖的預防方法是打破死鎖的環(huán)路條件。即把資源分類按順序排列，使進程在申請、保持資源時不形成環(huán)路。如有m種資源，則列出R1R2Rm。若進程Pi保持了資源Ri，則它只能申請比Ri級別更高的資源Rj（Ri Rj ）。釋放資源時必須是Rj先于Ri被釋放，從而避免環(huán)路的產(chǎn)生。這種方法的缺點是限制了進程對資源的

28、請求，而且對資源的分類編序也耗去一定的系統(tǒng)開銷。,2020年7月15日星期三,42,死鎖避免,死鎖避免定義:在系統(tǒng)運行過程中，對進程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據(jù)檢查結果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。 死鎖避免可被稱為動態(tài)預防，因為系統(tǒng)采用動態(tài)分配資源，在分配過程中預測出死鎖發(fā)生的可能性并加以避免的方法。 預防死鎖的幾種策略，會嚴重地損害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來避免死鎖。 由于在避免死鎖的策略中，允許進程動態(tài)地申請資源。因而，系統(tǒng)在進行資源分配之前預先計算資源分配的安全性。若此次分配不會導致系統(tǒng)

29、進入不安全狀態(tài)，則將資源分配給進程；否則，進程等待。其中最具有代表性的避免死鎖算法是銀行家算法。,2020年7月15日星期三,43,安全狀態(tài)與不安全狀態(tài),安全狀態(tài)指系統(tǒng)能按某種進程順序來為每個進程分配其所需資源，直至最大需求，使每個進程都可順序完成。若系統(tǒng)不存在這樣一個序列，則稱系統(tǒng)處于不安全狀態(tài)。,2020年7月15日星期三,44,1)安全序列,一個進程序列P1，Pn是安全的，如果對于每一個進程Pi(1in），它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj (j i )當前占有資源量之和，系統(tǒng)處于安全狀態(tài)。 (安全狀態(tài)一定是沒有死鎖發(fā)生的),2020年7月15日星期三,45,2)

30、 安全狀態(tài)之例,我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、 P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：,2020年7月15日星期三,46,3) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換,如果不按照安全序分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。 因為，此時也無法再找到一個安全序列， 例如，把其余的2臺分配給P2，這樣，在P2完成后只

31、能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結果導致死鎖。 不安全狀態(tài):不存在一個安全序列，不安全狀態(tài)可能進而導致死鎖,2020年7月15日星期三,47,利用銀行家算法避免死鎖,銀行家算法中的數(shù)據(jù)結構 (1) 可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。 (2) 最大需求矩陣Max。這是一個n

32、m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數(shù)目為K。,2020年7月15日星期三,48,銀行家算法(續(xù)),(3) 分配矩陣Allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocationi,j=K，則表示進程i當前已分得Rj類資源的數(shù)目為K。 (4) 需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Needi,j=K，則表示進程i還需要Rj類資源K個，方能完成其任務。 顯然有：Needi,j=Maxi,j-Allocation

33、i,j,2020年7月15日星期三,49,銀行家算法具體步驟,設Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。,2020年7月15日星期三,50,銀行家算法具體步驟,(3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結構中的數(shù)值： Availablej=Avail

34、ablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。,2020年7月15日星期三,51,安全性 判斷算法,(1) 設置兩個向量： 工作向量Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work=Available; Finish: 它表示系

35、統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false; 當有足夠資源分配給進程時， 再令Finishi=true。 (2) 從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。,2020年7月15日星期三,52,安全性 判斷算法(續(xù)),(3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; (4) 如果所有進程的Finishi=

36、true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。,2020年7月15日星期三,53,銀行家算法之例,假定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖 所示。,T0時刻的資源分配表,2020年7月15日星期三,54,(1) T0時刻的安全性：,T0時刻的安全序列,2020年7月15日星期三,55,(2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0

37、, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 中的圓括號所示。 再利用安全性算法檢查此時系統(tǒng)是否安全。,2020年7月15日星期三,56,P1申請資源時的安全性檢查,2020年7月15日星期三,57,(3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓P4等待。(4) P0請求資源：P

38、0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系統(tǒng)暫時先假定可為P0分配資源，并修改有關數(shù)據(jù)，如圖 所示。,2020年7月15日星期三,58,為P0分配資源后的有關資源數(shù)據(jù),2020年7月15日星期三,59,死鎖的檢測和恢復(一般系統(tǒng)使用),它是死鎖發(fā)生后的事后處理技術。它是指系統(tǒng)設有專門的機構，當死鎖發(fā)生時該機構能夠檢測到死鎖發(fā)生的位置和原因，并通過外力破壞死鎖發(fā)生的必要條件，使得并發(fā)進程從死鎖狀態(tài)中恢復出來。 允許死鎖發(fā)生，操

39、作系統(tǒng)不斷監(jiān)視系統(tǒng)進展情況，判斷死鎖是否發(fā)生。一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價恢復操作系統(tǒng)運行 當進程進行資源請求時，死鎖檢測算法檢查并發(fā)進程組是否構成資源的請求和保持環(huán)路。有限狀態(tài)轉(zhuǎn)移圖和petriNet等技術都可用來有效地判斷死鎖發(fā)生。 死鎖的恢復辦法較多。最簡單的辦法是終止各鎖住進程，或按一定的順序中止進程序列，直至已釋放到有足夠的資源來完成剩下的進程時為止。另外，也可以從被鎖住進程強迫剝奪資源以解除死鎖。,60,3.9 線程,2020年7月15日星期三,61,線程的概念,進程是程序的一次執(zhí)行過程和資源分配的基本單位。由此可知，即使是同一段程序，在不同的執(zhí)行時間，應屬

40、于不同的進程。那么，什么是線程（Thread）以及為什么在操作系統(tǒng)中要引入線程的概念呢？ 事實上，引入線程主要是為了提高系統(tǒng)的執(zhí)行效率，減少處理機的空轉(zhuǎn)時間和調(diào)度切換（保護現(xiàn)場信息）的時間，以及便于系統(tǒng)管理。 一個進程內(nèi)的基本調(diào)度單位稱為線程或稱為輕權進程（Light weight process），這個調(diào)度單位既可以由操作系統(tǒng)內(nèi)核控制，也可以由用戶程序控制。,2020年7月15日星期三,62,線程與進程的異同,可以從比較中進一步理解線程的概念。 (1)進程是資源分配的基本單位。所有與該進程有關的資源，例如打印機，輸入緩沖隊列等，都被記錄在進程控制塊PCB中。以表示該進程擁有這些資源或正在使用

41、它們。有時，為了對進程的上述兩個特性進行區(qū)分，規(guī)定線程為操作系統(tǒng)的基本調(diào)度單位，而進程則為系統(tǒng)資源的者。 (2)當發(fā)生進程調(diào)度時，它擁有一個完整的虛擬地址空間，但不同的進程擁有不同的虛擬地址空間存同時同一進程內(nèi)的不同線程共享其所屬進程的同一地址空間。 (3)線程只由相關堆棧、寄存器和線程控制塊(TCB)組成，寄存器用來存儲線程內(nèi)的局部變量，但不能存儲其它線程的相關變量，線程控制塊則用于記錄線程的有關信息，起到與PCB相對應的一些功能。,2020年7月15日星期三,63,線程與進程的異同,(4)進程切換時涉及到有關資源指針的保存以及地址空間的變化等問題，線程切換時，由于同一進程內(nèi)的線程共享資源和

42、地址空間，將不涉及資源信息的保存和地址變化問題，從而減少了操作系統(tǒng)的開銷時間。 (5)進程的調(diào)度與切換都是由操作系統(tǒng)內(nèi)核完成，而線程則既可由操作系統(tǒng)內(nèi)核完成，也可由用戶程序進行。 (6)在多線程操作系統(tǒng)中，線程是系統(tǒng)內(nèi)的執(zhí)行褓，而進程不是。 (7)一個進程內(nèi)的各個線程以及不同進程內(nèi)的各個線程均可并發(fā)執(zhí)行，在多處理機系統(tǒng)中，它們可以被分派到不同的CPU上并行運行。,2020年7月15日星期三,64,多線程系統(tǒng)中進程與線程的關系,2020年7月15日星期三,65,并不是在所有的計算機系統(tǒng)中線程都是適用的。事實上在那些很少做進程調(diào)度和切換的實時系統(tǒng)、個人數(shù)字助理系統(tǒng)中，由于任務的單一性，設置線程相反

43、會占用更多的內(nèi)存空間和寄存器。 使用線程的最大好處是在有多個任務需要處理機處理時，減少處理機的切換時間；而且，線程的創(chuàng)建和結束所需要的系統(tǒng)開銷也比進程的創(chuàng)建和結束要小得多。由此，可以推出最適合使用線程的系統(tǒng)是多處理機系統(tǒng)。在多處理機系統(tǒng)中，同一用戶程序可以根據(jù)不同的功能劃分為不同的線程，放在不同的處理機上執(zhí)行。 在用戶程序可以按功能劃分為不同的小段時，單處理機系統(tǒng)也可因使用線程而簡化程序的結構和提高執(zhí)行效率。,線程的適用范圍,2020年7月15日星期三,66,線程的分類,線程的兩個基本類型是：用戶級線程和系統(tǒng)級線程(核心級線型)。在同一個操作系統(tǒng)中，有的使用純用戶級線程，有的使用純核心級線程，

44、例如Windows NT和Os/2；有的則混合使用用戶及線程和核心級線程，例如Solaris 。 用戶級線程（user level threads）的管理過程全部由用戶程序完成，操作系統(tǒng)內(nèi)核只對進程進行管理。 為了對用戶級線程進行管理，操作系統(tǒng)提供一個在用戶空間執(zhí)行的線程庫。該線程庫提供創(chuàng)建、調(diào)度、撤銷線程功能。同時該線程庫也提供線程間的通信，線程的執(zhí)行以及存儲線程上下文的功能。用戶級線程只使用戶堆棧和分配給所屬進程的用戶寄存器。 線程的調(diào)度算法和調(diào)度過程完全由用戶自行選擇和確定。線程調(diào)度過程中僅進行線程上下文的切換而不切換處理機，而且切換僅在用戶本、用戶寄存器間進行，與操作系統(tǒng)內(nèi)核無關，所以

45、開銷相當小。,2020年7月15日星期三,67,線程的分類,核心級線程（Kernel-level Threads）由操作系統(tǒng)內(nèi)核進行管理，操作系統(tǒng)負責維護核心級線程的各種管理表格，負責線程在處理機上的調(diào)度和切換，并給應用程序提供相應的系統(tǒng)調(diào)用和應用程序接口API，以使用戶程序可以創(chuàng)建、執(zhí)行、撤消線程。 與用戶線程不同，核心級線程既可以被調(diào)度到一個處理機上并發(fā)執(zhí)行，也可以被調(diào)度到不同的處理機上并行執(zhí)行。操作系統(tǒng)內(nèi)核既負責進程的調(diào)度，也負責進程內(nèi)不同線程的調(diào)度工作。因此，核心級線程不會出現(xiàn)進程處于阻塞或等待狀態(tài)，而線程處于執(zhí)行狀態(tài)的情況。 另外，核心級線程技術也可用于內(nèi)核程序自身，從而提高操作系統(tǒng)

46、內(nèi)核程序的執(zhí)行效率。 與用戶級線程相比，核心級線程的上下文切換時間要大于用戶級線程的上下文切換時間。,2020年7月15日星期三,68,線程的狀態(tài)及轉(zhuǎn)換,線程在執(zhí)行時也有它的相關特性。線程的狀態(tài)和同步用來反映線程的這些特性。 線程有3個基本狀態(tài)，即執(zhí)行、就緒和阻塞。但是線程沒有進程中的掛起狀態(tài)。也就是說，線程是一個只與內(nèi)存和寄存器相關的概念，它的內(nèi)容不會因交換而進入外存。 針對線程的3種基本狀態(tài)，存在5種基本操作來轉(zhuǎn)換線程的狀態(tài)。這5種基本操作是： (1) 派生（spawn）：線程在進程內(nèi)派生出來，它即可由進程派生，也可由線程派生。用戶一般用系統(tǒng)調(diào)用（或相應的庫函數(shù)）派生自己的線程。,2020

47、年7月15日星期三,69,線程的狀態(tài)及轉(zhuǎn)換,一個新派生出來的線程具有相應的數(shù)據(jù)結構指針和變量，這些指針和變量作為寄存器上下文放在相應的寄存器和堆棧中。 新派生線程被放入就緒隊列。 (2) 阻塞（Block）：如果一個線程在執(zhí)行過程中需要等待某個事件發(fā)生，則被阻塞。阻塞時，寄存器上下文、程序計數(shù)器以及堆棧指針都會得到保證。 (3) 激活（unblock）：如果阻塞線程的事件發(fā)生，則該線程被激活并進入就緒隊列。 (4) 調(diào)度（schedule）：選擇一個就緒線程進入執(zhí)行狀態(tài)。 (5) 結束（Finish）：如果一個線程執(zhí)行結束，它的寄存器上下文以及堆棧內(nèi)容等將被釋放。,2020年7月15日星期三,

48、70,線程的狀態(tài)和操作關系,需要注意的一點是，在某些情況下，某個線程被阻塞也可能導致該線程所屬的進程被阻塞。,2020年7月15日星期三,71,線程的應用,幾種典型的應用是 (1) 服務器中的文件管理或通信控制。在局域網(wǎng)的文件服務器中，對文件的訪問要求可被服務器進程派生出的線程進行處理。由于服務器同時可能接受許多個文件訪問要求，則系統(tǒng)可以同時生成多個線程來進行處理。如果計算機系統(tǒng)是多處理機的，這些線程還可以安排到不同的處理機上執(zhí)行。 (2) 前后臺處理。許多用戶都有過前后臺處理經(jīng)驗，即把一個計算量較大的程序或?qū)崟r性要求不高的程序安排在處理機空閑時執(zhí)行，即后臺方式。對于同一個進程中的上述程序來說，線程可被用來減少處理機切換時間和提高執(zhí)行速度。 (3)異步處理。若程序中的兩部分在執(zhí)行上無順序規(guī)定，則這兩