Windows操作系統(tǒng)-處理機(jī)管理(中)

進(jìn)程和進(jìn)程控制線程進(jìn)程互斥和同步死鎖問題進(jìn)程間通信處理器調(diào)度

第三章處理機(jī)管理(中)進(jìn)程互斥和同步問題的提出互斥算法信號(hào)量(semaphore)經(jīng)典進(jìn)程同步問題管程(monitor)Windows的進(jìn)程互斥和同步進(jìn)程互斥和同步進(jìn)程間臨界資源訪問沖突共享變量的修改沖突操作順序沖突臨界資源：計(jì)算機(jī)系統(tǒng)中的硬件或軟件〔如外設(shè)、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)〕資源，各個(gè)進(jìn)程在對(duì)其進(jìn)行訪問時(shí)〔關(guān)鍵是進(jìn)行寫入或修改〕，必須互斥地進(jìn)行并非所有共享資源都是臨界資源，如只讀數(shù)據(jù)可以同時(shí)訪問在多道程序環(huán)境中，進(jìn)程之間存在相互制約的關(guān)系，這種制約關(guān)系主要是由對(duì)共享資源的競(jìng)爭(zhēng)使用而引起的。進(jìn)程互斥和同步問題的提出共享變量的修改沖突進(jìn)程互斥和同步臨界資源問題的提出一個(gè)飛機(jī)訂票系統(tǒng)，兩個(gè)終端，運(yùn)行T1、T2進(jìn)程T1:T2:......Read(x);Read(x);ifx>=1thenifx>=1thenx:=x-1;x:=x-1;write(x);write(x);......3個(gè)進(jìn)程：get,process和print進(jìn)程互斥和同步操作順序沖突臨界資源getprocessprint問題的提出Buf1Buf2磁帶打印機(jī)臨界資源的訪問過程進(jìn)程互斥和同步為了保證臨界資源的正確訪問，必須采取一定的協(xié)調(diào)措施臨界區(qū)(criticalsection)：進(jìn)程中訪問臨界資源的一段代碼。進(jìn)入?yún)^(qū)(entrysection)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問臨界區(qū)”標(biāo)志。退出區(qū)(exitsection)：用于將"正在訪問臨界區(qū)"標(biāo)志去除。剩余區(qū)(remaindersection)：代碼中的其余局部。問題的提出同步機(jī)制應(yīng)遵循的準(zhǔn)那么①空閑那么入：當(dāng)沒有進(jìn)程處于臨界區(qū)時(shí)，假設(shè)有一個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，那么應(yīng)該允許；②無空等待：已有進(jìn)程處于其臨界區(qū)，其他要求進(jìn)入臨界區(qū)的進(jìn)程必須；③有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程應(yīng)該在有限的時(shí)間內(nèi)得到滿足；④讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU〔如轉(zhuǎn)換到阻塞狀態(tài)〕進(jìn)程互斥和同步目的：防止死鎖和饑餓死鎖指多個(gè)進(jìn)程互不相讓，都得不到足夠的資源；饑餓指某一個(gè)進(jìn)程一直得不到資源問題的提出進(jìn)程互斥和同步互斥算法

——基于進(jìn)程間平等協(xié)商的互斥算法解決進(jìn)程互斥的方法：基于進(jìn)程間平等協(xié)商的互斥方法軟件方法硬件方法由操作系統(tǒng)協(xié)調(diào)互斥問題的方法進(jìn)程互斥的軟件方法有兩個(gè)進(jìn)程Pi,Pj，其中的Pi算法1：單標(biāo)志設(shè)立一個(gè)公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入：turn為i時(shí)，進(jìn)程Pi可進(jìn)入；在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識(shí)：進(jìn)程Pi退出時(shí)，改turn為進(jìn)程Pj的標(biāo)識(shí)j；缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；進(jìn)程互斥和同步互斥算法算法2：雙標(biāo)志、先檢查設(shè)立一個(gè)標(biāo)志數(shù)組flag[]：描述進(jìn)程是否在臨界區(qū)，初值均為FALSE。先檢查，后修改：在進(jìn)入?yún)^(qū)檢查另一個(gè)進(jìn)程是否在臨界區(qū)，不在時(shí)修改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志；優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；缺點(diǎn)：Pi和Pj可能同時(shí)進(jìn)入臨界區(qū)。進(jìn)程互斥和同步進(jìn)程互斥的軟件方法互斥算法算法3：雙標(biāo)志、后檢查類似于算法2，與互斥算法2的區(qū)別在于先修改后檢查?？煞乐箖蓚€(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)。缺點(diǎn)：Pi和Pj可能都進(jìn)入不了臨界區(qū)。進(jìn)程互斥和同步進(jìn)程互斥的軟件方法互斥算法算法4：先修改、后檢查、后修改者等待結(jié)合算法1和算法3，滿足空閑那么入和無空等待要求turn=j;描述可進(jìn)入的進(jìn)程〔同時(shí)修改標(biāo)志時(shí)〕在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查對(duì)方flag，如果不在臨界區(qū)那么自己進(jìn)入－－空閑那么入否那么再檢查turn：保存的是較晚的一次賦值，那么較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入－－先到先入，后到等待進(jìn)程互斥和同步進(jìn)程互斥的軟件方法互斥算法信號(hào)量(semaphore)信號(hào)量和P、V原語信號(hào)量集前面的互斥算法是進(jìn)程間的一種平等協(xié)商機(jī)制，不能滿足進(jìn)程同步機(jī)制準(zhǔn)那么的全部要求。另一種進(jìn)程互斥的解決方法是引如一個(gè)地位高于進(jìn)程的管理者來解決臨界資源的使用問題。操作系統(tǒng)可從進(jìn)程管理者的角度來處理互斥的問題，信號(hào)量就是OS提供的管理臨界資源的有效手段。信號(hào)量代表可用資源實(shí)體的數(shù)量。進(jìn)程互斥和同步信號(hào)量和P、V原語1965年，由荷蘭學(xué)者Dijkstra提出〔P、V分別是荷蘭語的proberen=test和verhogen=increment的首字母〕，是一種卓有成效的進(jìn)程同步機(jī)制。每個(gè)信號(hào)量s包含一個(gè)整數(shù)值s.count〔計(jì)數(shù)〕和一個(gè)進(jìn)程等待隊(duì)列s.queue，其中是阻塞在該信號(hào)量的各個(gè)進(jìn)程的標(biāo)識(shí)信號(hào)量只能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原語來訪問——作為OS核心代碼執(zhí)行，不受進(jìn)程調(diào)度的打斷初始化指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)〔又稱為“資源信號(hào)量”〕——假設(shè)為非負(fù)值表示當(dāng)前的空閑資源數(shù)，假設(shè)為負(fù)值其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)進(jìn)程互斥和同步信號(hào)量P原語P(s){ --s.count; //表示申請(qǐng)一個(gè)資源; if(s.count<0) //表示沒有空閑資源; {

調(diào)用進(jìn)程進(jìn)入等待隊(duì)列s.queue;

阻塞調(diào)用進(jìn)程; }}進(jìn)程互斥和同步信號(hào)量V原語V(s){ ++s.count; //表示釋放一個(gè)資源；

if(s.count<=0) //表示有進(jìn)程處于阻塞狀態(tài)；

{

從等待隊(duì)列s.queue中取出一個(gè)進(jìn)程P;

進(jìn)程P進(jìn)入就緒隊(duì)列; }}進(jìn)程互斥和同步信號(hào)量利用信號(hào)量實(shí)現(xiàn)互斥為臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex(MUTualExclusion)，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對(duì)使用P和V原語：遺漏P原語那么不能保證互斥訪問，遺漏V原語那么不能在使用臨界資源之后將其釋放〔給其他等待的進(jìn)程〕；P、V原語不能次序錯(cuò)誤、重復(fù)或遺漏進(jìn)程互斥和同步信號(hào)量利用信號(hào)量可以實(shí)現(xiàn)進(jìn)程間的同步前趨關(guān)系：并發(fā)執(zhí)行的進(jìn)程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成；為每個(gè)前趨關(guān)系設(shè)置一個(gè)互斥信號(hào)量S12，其初值為0進(jìn)程互斥和同步信號(hào)量經(jīng)典進(jìn)程同步問題1.生產(chǎn)者－消費(fèi)者問題(theproducer-consumerproblem)問題描述：假設(shè)干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，生產(chǎn)者進(jìn)程不斷寫入，而消費(fèi)者進(jìn)程不斷讀出；共享緩沖區(qū)共有n個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。進(jìn)程互斥和同步采用信號(hào)量機(jī)制：full是“滿”數(shù)目，初值為0，empty是“空”數(shù)目，初值為n。full和empty存在關(guān)系：full+empty==nmutex用于訪問緩沖區(qū)時(shí)的互斥，初值是1每個(gè)進(jìn)程中各個(gè)P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥――否那么可能死鎖(為什么？)進(jìn)程互斥和同步經(jīng)典進(jìn)程同步問題1.生產(chǎn)者－消費(fèi)者問題(theproducer-consumerproblem)2.讀者－寫者問題(thereaders-writersproblem)問題描述：對(duì)共享資源的讀寫操作，任一時(shí)刻“寫者”最多只允許一個(gè)，而“讀者”那么允許多個(gè)“讀－寫”互斥，“寫－寫”互斥，"讀－讀"允許進(jìn)程互斥和同步經(jīng)典進(jìn)程同步問題采用信號(hào)量機(jī)制：Wmutex表示"允許寫"，初值是1。公共變量Rcount表示“正在讀”的進(jìn)程數(shù)，初值是0；Rmutex表示對(duì)Rcount的互斥操作，初值是1。進(jìn)程互斥和同步2.讀者－寫者問題經(jīng)典進(jìn)程同步問題P(Rmutex);if(Rcount==0)P(Wmutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)V(Wmutex);V(Rmutex);ReaderP(Wmutex);write;V(Wmutex);Writer信號(hào)量同步的缺點(diǎn)同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖〔如P、V操作的次序錯(cuò)誤、重復(fù)或遺漏〕易讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)中并發(fā)執(zhí)行的各個(gè)程序；不利于修改和維護(hù)：各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局；正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個(gè)復(fù)雜的系統(tǒng)沒有邏輯錯(cuò)誤；進(jìn)程互斥和同步管程用信號(hào)量可實(shí)現(xiàn)進(jìn)程間的同步，但由于信號(hào)量的控制分布在整個(gè)程序中，其正確性分析很困難。管程的引入1973年，由Hoare和Hanson提出管程的根本思想是把信號(hào)量及其操作原語封裝在一個(gè)對(duì)象內(nèi)部。即：將共享變量以及對(duì)共享變量能夠進(jìn)行的所有操作集中在一個(gè)模塊中。管程的定義：管程是關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)及一組針對(duì)該資源的操作過程所構(gòu)成的軟件模塊。引入管程可提高代碼的可讀性，便于修改和維護(hù)，正確性易于保證。進(jìn)程互斥和同步管程管程的主要特性模塊化：一個(gè)管程是一個(gè)根本程序單位，可以單獨(dú)編譯；抽象數(shù)據(jù)類型：管程是一種特殊的數(shù)據(jù)類型，其中不僅有數(shù)據(jù)，而且有對(duì)數(shù)據(jù)進(jìn)行操作的代碼信息封裝：管程是半透明的，進(jìn)程可調(diào)用管程中實(shí)現(xiàn)了某些功能〔函數(shù)〕，至于這些功能是怎樣實(shí)現(xiàn)的，在其外部那么是不可見的；進(jìn)程互斥和同步管程管程作為一個(gè)模塊，它的結(jié)構(gòu)定義如下：

monitor_name=MONITOR;

共享變量說明;

define本管程內(nèi)部定義、外部可調(diào)用的函數(shù)名表;

use本管程外部定義、內(nèi)部可調(diào)用的函數(shù)名表;

內(nèi)部定義的函數(shù)說明和函數(shù)體

{

共享變量初始化語句;

}

進(jìn)程互斥和同步管程進(jìn)程互斥和同步管程bulletin=MONITOR;

r,w:condition;//r控制讀者使用黑板,w控制寫者；

writing:boolean;//當(dāng)前是否寫者使用黑板

read_account:integer;

definestart_read,end_read,start_write,end_write;

usemonitor.wait,monitor.signal;

procedurestart_read();

{

if(writing)monitor.wait(r);

read_account++;

monitor.signal(r);

}

procedureend_read();

{

read_account--;

if(read_account=0)monitor.signal(w);

}

假設(shè)已實(shí)現(xiàn)一根本管程monitor，提供signal,wait等操作

procedurestart_write();

{

if((read_account<>0)orwriting)monitor.wait(w);

writing=true;

}

procedureend_write();

{

writing=false;

if(r<>NULL)monitor.signal(r);

elsemonitor.signal(w);

}

進(jìn)程互斥和同步管程reader()：

{

while(true)

{

bulletin.start_read();

read();

bulletin.end_read();

}

}

writer()

{

while(true)

{

bulletin.start_write();

write();

bulletin.end_write();

}

}

讀者進(jìn)程寫者進(jìn)程Mutex對(duì)象：互斥對(duì)象，相當(dāng)于互斥信號(hào)量，在一個(gè)時(shí)刻只能被一個(gè)線程使用。有關(guān)的API：CreateMutex創(chuàng)立或翻開一個(gè)互斥對(duì)象，返回對(duì)象句柄；OpenMutex返回一個(gè)已存在的互斥對(duì)象的句柄，用于后續(xù)訪問；ReleaseMutex釋放對(duì)互斥對(duì)象的占用，使之成為可用；Windows支持三種同步對(duì)象對(duì)象名稱是由用戶給出的字符串。不同進(jìn)程中用同樣的名稱來創(chuàng)立或翻開對(duì)象，從而獲得該對(duì)象在本進(jìn)程的句柄。Windows的進(jìn)程互斥和同步——互斥對(duì)象、信號(hào)量對(duì)象和事件對(duì)象進(jìn)程互斥和同步HANDLECreateMutex(LPSECURITY_ATTRIBUTESlpMutexAttributes,//SDBOOLbInitialOwner,//initialownerLPCTSTRlpName//objectname);Semaphore對(duì)象：相當(dāng)于資源信號(hào)量，取值在0到指定最大值之間，用于限制并發(fā)訪問的線程數(shù)。有關(guān)的API：CreateSemaphore創(chuàng)立一個(gè)信號(hào)量對(duì)象，指定最大值和初值，返回對(duì)象句柄；OpenSemaphore返回一個(gè)已存在的信號(hào)量對(duì)象的句柄，用于后續(xù)訪問；ReleaseSemaphore釋放對(duì)信號(hào)量對(duì)象的占用；進(jìn)程互斥和同步Windows支持的三種同步對(duì)象Windows的進(jìn)程互斥和同步HANDLECreateSemaphore( LPSECURITY_ATTRIBUTESlpSemaphoreAttributes,//SD LONGlInitialCount,//initialcount LONGlMaximumCount,//maximumcount LPCTSTRlpName//objectname);Event對(duì)象：事件對(duì)象，相當(dāng)于"觸發(fā)器"，可通知一個(gè)或多個(gè)線程某事件的出現(xiàn)。有關(guān)的API：CreateEvent創(chuàng)立一個(gè)事件對(duì)象，返回對(duì)象句柄；OpenEvent返回一個(gè)已存在的事件對(duì)象的句柄，用于后續(xù)訪問；SetEvent和PulseEvent設(shè)置指定事件對(duì)象為有信號(hào)狀態(tài)；ResetEvent設(shè)置指定事件對(duì)象為無信號(hào)狀態(tài)〔nonsignaled〕進(jìn)程互斥和同步Windows支持的三種同步對(duì)象Windows的進(jìn)程互斥和同步同步對(duì)象等待(1)WaitForSingleObject在指定的時(shí)間內(nèi)等待指定對(duì)象為有信號(hào)狀態(tài)(signaledstate)；

DWORDWaitForSingleObject( HANDLEhHandle,//handleofobjecttowaitfor DWORDdwMilliseconds//time-outintervalinmilliseconds);進(jìn)程互斥和同步Windows的進(jìn)程互斥和同步(2)WaitForMultipleObjects在指定的時(shí)間內(nèi)等待多個(gè)對(duì)象為有信號(hào)狀態(tài)；

DWORDWaitForMultipleObjects( DWORDnCount,//對(duì)象句柄數(shù)組中的句柄數(shù)；

CONSTHANDLE*lpHandles,//指向?qū)ο缶浔鷶?shù)組的指針，數(shù)組中 //可包括多種對(duì)象句柄；

BOOLbWaitAll, //等待標(biāo)志：TRUE表示所有對(duì)象同時(shí)可用 //FALSE表示至少一個(gè)對(duì)象可用；

DWORDdwMilliseconds//等待超時(shí)時(shí)限；

);同步對(duì)象等待Windows的進(jìn)程互斥和同步其他同步方法CriticalSection對(duì)象：只能在同一進(jìn)程內(nèi)使用的臨界區(qū)，同一進(jìn)程內(nèi)各線程對(duì)它的訪問是互斥進(jìn)行的。把變量說明為CRITICAL_SECTION類型，就可作為臨界區(qū)使用。有關(guān)的API：InitializeCriticalSection對(duì)臨界區(qū)對(duì)象進(jìn)行初始化；EnterCriticalSection等待占用臨界區(qū)的使用權(quán)，得到使用權(quán)時(shí)返回；TryEnterCriticalSection非等待方式申請(qǐng)臨界區(qū)的使用權(quán)；申請(qǐng)失敗時(shí)，返回0；LeaveCriticalSection釋放臨界區(qū)的使用權(quán)；DeleteCriticalSection釋放與臨界區(qū)對(duì)象相關(guān)的所有系統(tǒng)資源；進(jìn)程互斥和同步Windows的進(jìn)程互斥和同步互鎖變量訪問相當(dāng)于硬件指令，對(duì)一個(gè)整數(shù)〔進(jìn)程內(nèi)的變量或進(jìn)程間的共享變量〕進(jìn)行操作。其目的是防止線程間切換的影響。有關(guān)的API：InterlockedExchange進(jìn)行32位數(shù)據(jù)的先讀后寫原子操作；InterlockedCompareExchange依據(jù)比較結(jié)果進(jìn)行賦值的原子操作；InterlockedExchangeAdd先加后存結(jié)果的原子操作；InterlockedDecrement先減1后存結(jié)果的原子操作；InterlockedIncrement先加1后存結(jié)果的原子操作；進(jìn)程互斥和同步Windows的進(jìn)程互斥和同步死鎖問題(DEADLOCK)概述死鎖的預(yù)防死鎖的檢測(cè)死鎖的防止解決死鎖問題的綜合方法概述可重用資源(reusableresource)：每個(gè)時(shí)刻只有一個(gè)進(jìn)程使用，但不會(huì)耗盡，在宏觀上各個(gè)進(jìn)程輪流使用。如CPU、主存和輔存、I/O通道、外設(shè)、數(shù)據(jù)結(jié)構(gòu)如文件、數(shù)據(jù)庫和信號(hào)量。死鎖是指系統(tǒng)中多個(gè)進(jìn)程無限制地等待永遠(yuǎn)不會(huì)發(fā)生的條件；死鎖發(fā)生原因?qū)コ赓Y源的共享；并發(fā)執(zhí)行的順序不當(dāng)死鎖問題進(jìn)程使用的資源分為可重用資源和可消耗資源兩類：可重用資源死鎖死鎖發(fā)生：雙方都擁有局部資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。如次序：P1<a>P2<a>P1<b>P2<b>概述死鎖問題可消耗資源(consumableresource)：可以動(dòng)態(tài)生成和消耗，一般不限制數(shù)量。如硬件中斷、信號(hào)、消息、緩沖區(qū)內(nèi)的數(shù)據(jù)。死鎖發(fā)生：雙方都等待對(duì)方去生成資源，如次序：P1<a>P2<a>概述死鎖問題死鎖發(fā)生條件：互斥：任一時(shí)刻只允許一個(gè)進(jìn)程使用資源請(qǐng)求和保持：進(jìn)程在請(qǐng)求其余資源時(shí)，不主動(dòng)釋放已經(jīng)占用的資源非剝奪：進(jìn)程已經(jīng)占用的資源，不會(huì)被強(qiáng)制剝奪環(huán)路等待：環(huán)路中的每一條邊是進(jìn)程在請(qǐng)求另一進(jìn)程已經(jīng)占有的資源。只有4個(gè)條件都滿足時(shí)，才會(huì)出現(xiàn)死鎖。死鎖問題概述處理死鎖問題的根本方法：預(yù)防、檢測(cè)、防止死鎖的預(yù)防預(yù)防死鎖的兩種策略：預(yù)先靜態(tài)分配法：進(jìn)程開始運(yùn)行前一次分配所需全部資源，假設(shè)系統(tǒng)不能滿足，那么進(jìn)程阻塞，直到系統(tǒng)滿足其要求——保證進(jìn)程運(yùn)行過程中不會(huì)再提出新的資源請(qǐng)求；降低了對(duì)資源的利用率，降低進(jìn)程的并發(fā)程度；有可能無法預(yù)先知道所需資源；有序資源使用法：把資源分類按順序排列，保證對(duì)資源的請(qǐng)求不形成環(huán)路；限制進(jìn)程對(duì)資源的請(qǐng)求順序；資源的排序占用系統(tǒng)開銷；預(yù)防是采用某種策略，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件。死鎖問題死鎖的檢測(cè)保存資源的請(qǐng)求和分配信息，利用某種算法對(duì)這些信息加以檢查，以判斷是否存在死鎖。死鎖檢測(cè)算法主要是檢查是否有循環(huán)等待。死鎖問題資源分配圖算法將進(jìn)程和資源間的請(qǐng)求和分配關(guān)系用一個(gè)有向圖描述，通過檢查有向圖中是否存在循環(huán)判斷是否存在死鎖死鎖的防止在分配資源時(shí)判斷是否會(huì)出現(xiàn)死鎖，如