第6章處理器管理(3)6.1進程的概念

6.2進程的狀態(tài)和轉(zhuǎn)換

6.3進程的控制

6.4進程的協(xié)調(diào)

6.5進程間的通信

6.6進程的安全性

6.7線程的概念

6.8作業(yè)管理

6.9處理器調(diào)度進程管理6.6進程的安全性背景在多道程序系統(tǒng)中，多個進程并發(fā)運行，共享資源，從而提高了資源的利用率。但是若對資源的管理和使用不當，在一定條件下會導(dǎo)致系統(tǒng)發(fā)生一種隨機性故障――死鎖。在一些系統(tǒng)中，比如實時控制系統(tǒng)，系統(tǒng)一旦發(fā)生死鎖將導(dǎo)致災(zāi)難性的后果。主要內(nèi)容：6.6.1死鎖的概念6.6.2產(chǎn)生死鎖的必要條件6.6.3死鎖的預(yù)防6.6.4死鎖的避免6.6.5死鎖的檢測和解除(自學(xué))（1）什么叫死鎖？ 死鎖是多個（兩個或兩個以上）進程循環(huán)等待它方占有的資源，而無限期僵持下去的局面。若無外力作用它們都無法向前推進。說明：陷入死鎖狀態(tài)的進程稱為死鎖進程，等待它們所占用資源的或者需要它們進行某種合作的其它進程就會相繼陷入死鎖，最終可能導(dǎo)致整個系統(tǒng)處于癱瘓狀態(tài)。

6.6.1死鎖的概念產(chǎn)生死鎖的原因根本原因是：資源有限且操作不當。(1)競爭資源 當系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖；(2)進程推進的順序不當 進程在運行過程中，請求和釋放資源的順序不當，導(dǎo)致進程的死鎖。說明：資源少未必會產(chǎn)生死鎖。競爭資源1競爭非剝奪性資源：系統(tǒng)中的可重用資源（處理機、主存、暫存、I/O通道、打印機以及文件、數(shù)據(jù)庫等）可分為：可剝奪性資源：處理機不可剝奪性資源：如打印機。當系統(tǒng)把這類資源分配給進程后，只能在使用完畢后由進程自愿釋放，系統(tǒng)不能強行收回。R2已經(jīng)分配給PA、R1已經(jīng)分配給PB（互相等待對方釋放資源）死鎖模型：PA、PB和R1、R2間已經(jīng)形成一個環(huán)路。以致進入死鎖狀態(tài)。R1R2PAPB申請R2已分配給PB申請R1已分配給PA打印機R2磁帶機R1PAPB1競爭非剝奪性資源：2.進程推進順序不當例：PV操作造成的死鎖。信號量S1,S2(初值為1)，分別表示資源R1和R2空閑。進程PA：進程PB：

…

…L1:P(S1)

M1:P(S2)L2:P(S2)M2:P(S1)

使用資源R1和R2使用資源R1和R2V(S1)V(S2)V(S2)V(S1)

說明：有可能PA達到L1時進程PB達到M1。信號量S1和S2執(zhí)行了P操作，其值均為0，當P1和P2繼續(xù)執(zhí)行時它們分別在L2和M2上無限期等待。這就造成了死鎖。6.6.2產(chǎn)生死鎖的四個必要條件（COFFMAN等人1971年總結(jié)了）發(fā)生死鎖的四個必要條件

[ref]COFFMAN,E.G.,ELPHICK,M.J.,andSHOSHANI,A.:"SystemDeadlocks,"ComputingSurveys,vol.3,pp.67-78,June1971.⑴互斥條件:

進程訪問的是臨界資源，該資源一次只能被一個進程所使用。⑵不可搶占條件:

一個資源僅能被占有它的進程所釋放，而不能被其他進程剝奪。⑶部分分配:（占有且申請條件） 一個進程在請求新的資源的同時，保持對某些資源的占有。⑷循環(huán)等待條件:

存在一個進程等待的環(huán)路鏈，鏈中每一個進程占用有著某個(或某些)資源，又在等待鏈中的另一個進程所占有的資源。6.6.3死鎖的預(yù)防死鎖的預(yù)防：保證系統(tǒng)不進入死鎖狀態(tài)的一種策略。根據(jù)產(chǎn)生死鎖的四個必要條件，只要使用其中之一不能成立，死鎖就不會出現(xiàn)。但必要條件1（互斥條件）是由設(shè)備的固有特性所決定的，不僅不能改變，相反還應(yīng)加以保證。因此實際上只有三種方法。打破不可搶占條件打破占有且申請條件打破循環(huán)等待條件1.打破不可搶占條件采用的策略：一個已經(jīng)保持了某些資源的進程，當它再提出新的資源要求而不能立即得到滿足時，必須釋放它已經(jīng)保持的所有資源，供其它進程使用，待以后需要時再重新申請。實現(xiàn)比較復(fù)雜，會降低系統(tǒng)性能反復(fù)地申請和釋放資源，使進程的執(zhí)行無限地推遲，延長了周轉(zhuǎn)時間，增加了系統(tǒng)的開銷，降低了系統(tǒng)吞吐量。2打破占有且申請條件

實行資源預(yù)先分配策略系統(tǒng)要求任一進程必須預(yù)先申請它所需的全部資源，而且僅當該進程的全部資源要求能得到滿足時，系統(tǒng)才能給予一次性分配，然后啟動該進程運行在分配時只要有一種資源不滿足，系統(tǒng)就不會給進程分配資源。進程運行期間，不會再請求新的資源，所以，再分配就不會發(fā)生。特點：實現(xiàn)困難，一些進程無法預(yù)先確定所需全部資源。資源利用率低。進程延遲進行，降低進程的并發(fā)性。3.打破循環(huán)等待條件

實行資源有序分配有序資源使用法。基本思想：把系統(tǒng)中所有資源類型線性排隊，并按遞增規(guī)則賦予每類資源以唯一的編號（例如輸入機＝1，打印機＝2，磁帶機＝3，磁盤＝4等等）。進程申請資源時，必須嚴格按資源編號的遞增順序進行，否則系統(tǒng)不予分配。優(yōu)點：資源利用率和系統(tǒng)吞吐量與另兩種方法相比有較明顯的改善。缺點：(1)限制了進程對資源的申請；對所有資源合理編號增加系統(tǒng)開銷。(2)增加了進程對資源的占用時間：為了遵循原則，暫不使用的資源也需要提前申請。

6.6.4死鎖的避免

死鎖的避免與死鎖的預(yù)防區(qū)別在于：

死鎖的預(yù)防 設(shè)法至少破壞產(chǎn)生死鎖的四個必要條件（去除不可搶占條件）之一，嚴格地防止死鎖的出現(xiàn)。

死鎖的避免 不那么嚴格地限制產(chǎn)生死鎖必要條件的存在，只是在系統(tǒng)運行過程中小心地避免死鎖的最終發(fā)生。因為即使死鎖必要條件成立，也未必一定會發(fā)生死鎖。死鎖避免比死鎖預(yù)防允許更多的并發(fā)。最著名的死鎖避免算法是銀行家算法(Dijkstra提出)。銀行家算法銀行家算法(避免死鎖的調(diào)度方法)，EdsgerW.Dijkstra于1965年提出。假定小鎮(zhèn)銀行家擁有資金，數(shù)量為Σ，被N個客戶共享，銀行家對客戶提出下列約束：每個客戶必須預(yù)先說明所要的最大資金量；每個客戶每次提出部分資金量的申請并獲得分配；如果銀行滿足客戶對資金的最大需求量，客戶在資金運作后，應(yīng)在有限時間內(nèi)全部歸還銀行。只要客戶遵守上述約束條件，銀行家將保證做到：若一個客戶所要的最大資金量不超過Σ，銀行一定會接納此客戶，并滿足其資金要求銀行在收到一個客戶的資金請求時，可能會因為資金不足而讓客戶等待，但能在有限時間內(nèi)滿足。資金——資源；客戶——進程。銀行家算法分配資源時，申請者要把同類資源的最大需求量告訴系統(tǒng)，若系統(tǒng)現(xiàn)存的可用資源數(shù)能滿足申請者剩余需求量，就滿足當前的部分/全部申請，否則推遲分配。目的：這樣至少保證有一個申請者能得到所需的全部資源，可執(zhí)行到結(jié)束，然后釋放資源供別的申請者使用。若系統(tǒng)保證申請者在有限的時間內(nèi)能獲得所需的全部資源，則稱系統(tǒng)處于安全狀態(tài)；否則為不安全狀態(tài)，有可能引起死鎖。安全狀態(tài)：指系統(tǒng)中的所有進程能按照某種次序{P1，P2，…，Pn}分配資源，并且依次運行完畢。安全序列{P1，P2，…，Pn}：對于每一個進程Pi(i=1,…,n)，它需要的附加資源（完成執(zhí)行尚需要的資源數(shù)量）不超過系統(tǒng)中當前剩余資源與所有進程Pj(j<i)當前占有資源數(shù)量之和。不安全狀態(tài)：在某個時刻系統(tǒng)中不存在一個安全序列。該算法對于進程的每一個資源申請加以動態(tài)檢查。分配資源后，若系統(tǒng)進入不安全狀態(tài)，則不予分配；若分配后，系統(tǒng)仍處于安全狀態(tài)，則分配資源。說明：只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)；不安全狀態(tài)可能會導(dǎo)致死鎖，但不一定導(dǎo)致死鎖進程運行過程中可能會主動釋放一些資源，使系統(tǒng)重新回到安全狀態(tài)；避免死鎖的實質(zhì)是如何使系統(tǒng)不進入不安全狀態(tài)（預(yù)測可能發(fā)生死鎖，并不能預(yù)測一定發(fā)生死鎖）。安全狀態(tài)和安全序列安全狀態(tài)的例子例：假定系統(tǒng)有三個進程P1、P2、P3，共有12個資源。進程P1總共要求10個資源，P2和P3分別要求4個資源和9個資源。設(shè)在T0時刻，進程P1、P2和P3已經(jīng)獲得5個資源、2個資源和2個資源，還有3個資源空閑沒有分配。T0時刻系統(tǒng)時安全的。這時存在一個安全序列<P2，P1，P3>527進程最大需求已分配尚需P1105P2P34229系統(tǒng)剩余資源3

不安全狀態(tài)的例子例：若進程P3提出再申請1個資源的要求，系統(tǒng)從剩余的資源中分配1個給P3后剩余2個資源。新的系統(tǒng)狀態(tài)如下表所示：此時，找不到安全序列，系統(tǒng)已經(jīng)從安全狀態(tài)轉(zhuǎn)到了不安全狀態(tài)。進程最大需求已分配尚需P11055P2P3423926系統(tǒng)剩余資源2銀行家算法是在能確保系統(tǒng)處于安全狀態(tài)時才把資源分配給申請者。死鎖避免策略主要是根據(jù)系統(tǒng)是否處于安全狀態(tài)，來決定分配資源與否。與死鎖預(yù)防策略相比，死鎖避免策略提高了資源利用率，但增加了系統(tǒng)開銷。6.6.4死鎖的避免6.6.5死鎖的檢測和解除(自學(xué))背景：死鎖預(yù)防與死鎖避免的方法比較保守，它們以犧牲系統(tǒng)效率和浪費資源為代價，與操作系統(tǒng)的設(shè)計目標相違背。死鎖的檢測和解除：系統(tǒng)為進程分配資源時不加以任何限制，即允許死鎖發(fā)生；但操作系統(tǒng)不斷監(jiān)督進程的進展路徑，判斷系統(tǒng)是否發(fā)生死鎖；若檢測到死鎖發(fā)生，則設(shè)法以最小的代價加以解除，使系統(tǒng)恢復(fù)正常。小結(jié)（1）死鎖的概念死鎖是兩個或兩個以上的進程中的每一個都在等待其中另一個進程釋放資源而被封鎖，它們都無法向前推進，稱這種現(xiàn)象為死鎖現(xiàn)象。

產(chǎn)生死鎖的原因是