《操作系統(tǒng)死鎖》課件

操作系統(tǒng)死鎖操作系統(tǒng)死鎖是指多個(gè)進(jìn)程互相等待對(duì)方釋放資源，導(dǎo)致所有進(jìn)程都無法繼續(xù)執(zhí)行的狀態(tài)，也稱為死循環(huán)。死鎖會(huì)嚴(yán)重影響系統(tǒng)的性能，甚至導(dǎo)致系統(tǒng)崩潰，因此理解和預(yù)防死鎖對(duì)于操作系統(tǒng)設(shè)計(jì)和使用至關(guān)重要。死鎖概念及特征1死鎖定義死鎖是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而相互等待，導(dǎo)致所有進(jìn)程都無法繼續(xù)執(zhí)行的現(xiàn)象。2死鎖特征死鎖存在四個(gè)必要條件：互斥、請(qǐng)求和保持、不可剝奪、循環(huán)等待。3死鎖后果死鎖會(huì)導(dǎo)致系統(tǒng)資源浪費(fèi)，系統(tǒng)性能下降，甚至系統(tǒng)崩潰。4解決死鎖可以通過預(yù)防、避免、檢測(cè)和恢復(fù)等方法來解決死鎖問題。死鎖產(chǎn)生的必要條件互斥條件資源在同一時(shí)間只能被一個(gè)進(jìn)程使用。請(qǐng)求和保持條件進(jìn)程至少已經(jīng)占有了一個(gè)資源，并請(qǐng)求其他資源。不可剝奪條件進(jìn)程已經(jīng)占有的資源不能被其他進(jìn)程強(qiáng)行奪走，只有進(jìn)程自己才能釋放。環(huán)路等待條件多個(gè)進(jìn)程形成一個(gè)循環(huán)等待資源的鏈，每個(gè)進(jìn)程都在等待鏈中下一個(gè)進(jìn)程所占有的資源。資源分配圖資源分配圖是描述系統(tǒng)中資源和進(jìn)程之間關(guān)系的一種圖形表示方法。它使用節(jié)點(diǎn)和邊來表示資源、進(jìn)程以及它們之間的分配關(guān)系。每個(gè)節(jié)點(diǎn)代表一個(gè)進(jìn)程或一個(gè)資源，每個(gè)邊代表一個(gè)資源分配關(guān)系。資源分配圖分析死鎖資源分配圖每個(gè)進(jìn)程都表示為一個(gè)節(jié)點(diǎn)，每個(gè)資源也表示為一個(gè)節(jié)點(diǎn)。進(jìn)程節(jié)點(diǎn)指向資源節(jié)點(diǎn)，表示該進(jìn)程正在使用該資源。循環(huán)等待如果存在一個(gè)循環(huán)路徑，那么就會(huì)發(fā)生死鎖。例如，進(jìn)程P1占有資源R1，并請(qǐng)求資源R2，而進(jìn)程P2占有資源R2，并請(qǐng)求資源R1。環(huán)路檢測(cè)可以通過遍歷資源分配圖，尋找循環(huán)路徑來判斷是否發(fā)生了死鎖。如果發(fā)現(xiàn)環(huán)路，那么就說明系統(tǒng)處于死鎖狀態(tài)。死鎖檢測(cè)算法定義死鎖檢測(cè)算法用于識(shí)別系統(tǒng)中是否存在死鎖狀態(tài)。該算法定期檢查系統(tǒng)狀態(tài)，并通過分析資源分配情況來判斷是否發(fā)生死鎖。檢測(cè)算法通常需要維護(hù)一個(gè)資源分配圖，該圖描述了系統(tǒng)中每個(gè)進(jìn)程對(duì)每個(gè)資源的請(qǐng)求和占用情況。步驟建立資源分配圖通過圖遍歷算法尋找循環(huán)依賴如果存在循環(huán)依賴，則表示發(fā)生了死鎖類型主要有兩種類型的檢測(cè)算法：基于資源分配圖的算法和基于等待關(guān)系的算法?；谫Y源分配圖的算法更直觀，而基于等待關(guān)系的算法更易于實(shí)現(xiàn)。銀行家算法安全狀態(tài)銀行家算法通過檢查系統(tǒng)是否處于安全狀態(tài)來預(yù)防死鎖。安全狀態(tài)是指系統(tǒng)能夠按順序完成所有進(jìn)程，而不會(huì)出現(xiàn)死鎖。資源分配銀行家算法允許進(jìn)程在需要時(shí)請(qǐng)求額外的資源。然而，它會(huì)先檢查系統(tǒng)是否能夠滿足該請(qǐng)求，并確保系統(tǒng)仍然處于安全狀態(tài)。資源回收當(dāng)一個(gè)進(jìn)程完成時(shí)，它將釋放其持有的所有資源，使這些資源可供其他進(jìn)程使用。銀行家算法實(shí)例1可用資源假設(shè)系統(tǒng)有三個(gè)資源類型：A、B、C，其可用資源分別為：3,3,22進(jìn)程需求假設(shè)系統(tǒng)有五個(gè)進(jìn)程：P1、P2、P3、P4、P5，每個(gè)進(jìn)程所需的資源數(shù)量如下：進(jìn)程ABC已分配P17531,2,0P23222,1,1P39023,0,2P42222,1,0P54330,0,13安全狀態(tài)當(dāng)進(jìn)程P1、P3、P4、P5、P2依次完成時(shí)，系統(tǒng)始終處于安全狀態(tài)，不會(huì)出現(xiàn)死鎖。死鎖預(yù)防策略破壞互斥條件某些資源不可能由多個(gè)進(jìn)程共享。破壞請(qǐng)求和保持條件進(jìn)程必須在運(yùn)行前獲得所有需要的資源，不允許在運(yùn)行過程中請(qǐng)求資源。破壞環(huán)路等待條件為系統(tǒng)中的所有資源指定唯一的順序，并要求進(jìn)程按順序請(qǐng)求資源。實(shí)現(xiàn)資源有序分配進(jìn)程在請(qǐng)求資源時(shí)必須按照順序，防止循環(huán)等待條件出現(xiàn)。破壞互斥條件共享資源允許多個(gè)進(jìn)程同時(shí)訪問同一個(gè)資源。例如，一個(gè)共享文件可以被多個(gè)進(jìn)程同時(shí)讀取。非共享資源例如打印機(jī)，同一時(shí)間只能被一個(gè)進(jìn)程使用。這通常會(huì)導(dǎo)致死鎖。破壞請(qǐng)求和保持條件11.請(qǐng)求和保持條件當(dāng)一個(gè)進(jìn)程在等待被分配資源時(shí)，它可能仍然持有其他資源。22.資源請(qǐng)求進(jìn)程需要向操作系統(tǒng)請(qǐng)求資源，以便完成其任務(wù)。33.資源保持當(dāng)進(jìn)程等待資源分配時(shí)，它仍然保持已分配的資源。44.破壞方法要求進(jìn)程在請(qǐng)求資源之前釋放所有已分配的資源。破壞環(huán)路等待條件環(huán)路等待條件所有進(jìn)程必須以相同的順序請(qǐng)求資源。例如，進(jìn)程A請(qǐng)求資源R1然后R2，進(jìn)程B請(qǐng)求R2然后R1。破壞環(huán)路等待可以引入一個(gè)全局順序，所有進(jìn)程都必須按照此順序請(qǐng)求資源。例如，進(jìn)程A請(qǐng)求資源R1然后R2，進(jìn)程B請(qǐng)求資源R1然后R2。實(shí)現(xiàn)資源有序分配1資源類型排序根據(jù)資源類型進(jìn)行排序，例如磁盤、內(nèi)存、CPU。2資源分配順序按順序分配資源，避免資源分配沖突。3資源釋放順序釋放資源時(shí)保持與分配順序一致，避免出現(xiàn)死鎖。有序分配資源可以防止資源分配沖突，從而避免死鎖。死鎖避免策略安全狀態(tài)系統(tǒng)處于安全狀態(tài)時(shí)，可以保證所有進(jìn)程都能完成。資源分配在分配資源時(shí)，需要判斷是否會(huì)進(jìn)入不安全狀態(tài)。銀行家算法銀行家算法是一種常用的死鎖避免策略。安全序列安全序列是指系統(tǒng)中所有進(jìn)程按順序執(zhí)行，且不會(huì)導(dǎo)致死鎖的執(zhí)行順序。如果系統(tǒng)存在一個(gè)安全序列，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。安全狀態(tài)不一定意味著系統(tǒng)沒有死鎖，但可以有效降低死鎖風(fēng)險(xiǎn)。1安全系統(tǒng)處于安全狀態(tài)0不安全系統(tǒng)處于不安全狀態(tài)安全狀態(tài)檢查1安全狀態(tài)系統(tǒng)資源充足2安全序列按順序執(zhí)行3安全狀態(tài)系統(tǒng)安全安全狀態(tài)檢查用于判斷系統(tǒng)是否處于安全狀態(tài)。安全狀態(tài)意味著系統(tǒng)資源充足，存在一個(gè)安全序列，所有進(jìn)程可以按序執(zhí)行并完成。只有在安全狀態(tài)下，系統(tǒng)才能避免死鎖。死鎖恢復(fù)策略殺死死鎖進(jìn)程選擇一個(gè)或多個(gè)死鎖進(jìn)程，并將其終止。此方法簡(jiǎn)單粗暴，但會(huì)造成資源浪費(fèi)，并且可能導(dǎo)致數(shù)據(jù)丟失。資源搶占從死鎖進(jìn)程中搶占資源，分配給其他進(jìn)程。此方法需要慎重選擇搶占資源的進(jìn)程和資源，并確保搶占過程不會(huì)導(dǎo)致系統(tǒng)崩潰。回滾將死鎖進(jìn)程回滾到之前的一個(gè)狀態(tài)，釋放資源，并重新開始執(zhí)行?；貪L需要記錄進(jìn)程的狀態(tài)和資源使用情況，可能比較復(fù)雜。殺死死鎖進(jìn)程殺死死鎖進(jìn)程殺死死鎖進(jìn)程是解決死鎖的一種簡(jiǎn)單粗暴的方法，但也存在缺陷。潛在風(fēng)險(xiǎn)殺死死鎖進(jìn)程會(huì)導(dǎo)致數(shù)據(jù)丟失，進(jìn)程執(zhí)行狀態(tài)的丟失，以及系統(tǒng)資源的浪費(fèi)。慎用只有在死鎖無法通過其他方法解決，且數(shù)據(jù)丟失可以接受的情況下，才考慮殺死死鎖進(jìn)程。資源搶占選擇犧牲者當(dāng)死鎖發(fā)生時(shí)，選擇一個(gè)或多個(gè)進(jìn)程作為犧牲者，釋放其持有的資源。回滾操作需要將被搶占進(jìn)程恢復(fù)到先前狀態(tài)，以便釋放資源。這可能涉及回滾執(zhí)行，恢復(fù)數(shù)據(jù)等。代價(jià)高昂資源搶占可能導(dǎo)致性能損失和數(shù)據(jù)不一致，需要謹(jǐn)慎選擇和實(shí)施。資源分配圖實(shí)例分析資源分配圖是描述系統(tǒng)中資源分配狀態(tài)的圖形模型。它可以直觀地展示每個(gè)進(jìn)程當(dāng)前占有的資源和正在等待的資源。通過分析資源分配圖，我們可以判斷系統(tǒng)是否處于死鎖狀態(tài)。例如，系統(tǒng)中存在兩個(gè)進(jìn)程P1和P2，以及兩種資源R1和R2。P1占有R1，P2占有R2，P1正在等待R2，P2正在等待R1。此時(shí)系統(tǒng)處于死鎖狀態(tài)。死鎖狀態(tài)監(jiān)測(cè)動(dòng)態(tài)監(jiān)測(cè)實(shí)時(shí)監(jiān)控系統(tǒng)資源狀態(tài)，識(shí)別潛在死鎖跡象。異常檢測(cè)當(dāng)檢測(cè)到系統(tǒng)資源競(jìng)爭(zhēng)異常，觸發(fā)報(bào)警機(jī)制。數(shù)據(jù)分析分析死鎖發(fā)生頻率、原因和影響，為優(yōu)化系統(tǒng)提供參考。死鎖檢測(cè)算法原理11.資源分配圖死鎖檢測(cè)算法基于資源分配圖，該圖顯示系統(tǒng)中所有進(jìn)程和資源的分配情況。22.循環(huán)等待算法檢測(cè)資源分配圖中是否存在循環(huán)等待，如果有，則表示系統(tǒng)處于死鎖狀態(tài)。33.可達(dá)性分析算法分析每個(gè)進(jìn)程是否可以獲得所需資源，如果所有進(jìn)程都無法獲得資源，則系統(tǒng)處于死鎖狀態(tài)。44.死鎖檢測(cè)算法通過分析資源分配圖，算法可以判斷系統(tǒng)是否處于死鎖狀態(tài)，并找到處于死鎖狀態(tài)的進(jìn)程和資源。死鎖檢測(cè)算法實(shí)現(xiàn)1算法流程算法首先檢查系統(tǒng)中每個(gè)進(jìn)程是否持有資源，然后根據(jù)資源分配情況構(gòu)建資源分配圖。2循環(huán)檢測(cè)算法循環(huán)遍歷每個(gè)進(jìn)程，檢查是否能夠獲得其所需的全部資源，若能，則標(biāo)記該進(jìn)程為安全狀態(tài)。3結(jié)果判定若所有進(jìn)程均標(biāo)記為安全狀態(tài)，則系統(tǒng)處于無死鎖狀態(tài)；否則，系統(tǒng)處于死鎖狀態(tài)。死鎖預(yù)防和避免對(duì)比死鎖預(yù)防死鎖預(yù)防是指在系統(tǒng)設(shè)計(jì)階段采取措施，防止死鎖發(fā)生。通過限制資源分配或使用策略來消除死鎖產(chǎn)生的條件。死鎖避免死鎖避免是指在系統(tǒng)運(yùn)行時(shí)動(dòng)態(tài)地檢查資源分配情況，避免系統(tǒng)進(jìn)入死鎖狀態(tài)。系統(tǒng)會(huì)根據(jù)當(dāng)前狀態(tài)和未來請(qǐng)求，動(dòng)態(tài)調(diào)整資源分配，確保不會(huì)發(fā)生死鎖。死鎖恢復(fù)方法優(yōu)缺點(diǎn)殺死死鎖進(jìn)程簡(jiǎn)單易行，但可能導(dǎo)致資源浪費(fèi)，丟失工作進(jìn)度。資源搶占需要選擇合適的進(jìn)程和資源，可能導(dǎo)致系統(tǒng)性能下降。回滾恢復(fù)到之前的安全狀態(tài)，需要記錄系統(tǒng)狀態(tài)，可能增加系統(tǒng)開銷。進(jìn)程饑餓問題饑餓現(xiàn)象進(jìn)程長(zhǎng)期得不到CPU分配，無法執(zhí)行饑餓進(jìn)程一直處于等待狀態(tài)饑餓原因優(yōu)先級(jí)調(diào)度算法，低優(yōu)先級(jí)進(jìn)程長(zhǎng)期得不到執(zhí)行資源分配不公平，某些進(jìn)程長(zhǎng)期無法獲得資源進(jìn)程優(yōu)先級(jí)與死鎖1優(yōu)先級(jí)分配操作系統(tǒng)可以為進(jìn)程分配不同的優(yōu)先級(jí)。2高優(yōu)先級(jí)高優(yōu)先級(jí)進(jìn)程更容易獲得資源，更容易被調(diào)度運(yùn)行。3低優(yōu)先級(jí)低優(yōu)先級(jí)進(jìn)程可能會(huì)被長(zhǎng)時(shí)間阻塞，無法獲得所需資源，從而導(dǎo)致死鎖。4死鎖問題優(yōu)先級(jí)分配機(jī)制可能導(dǎo)致死鎖，因?yàn)楦邇?yōu)先級(jí)進(jìn)程可能會(huì)阻止低優(yōu)先級(jí)進(jìn)程獲取資源。層次化資源分配分層管理將系統(tǒng)中的資源劃分為多個(gè)層次，每個(gè)層次都包含不同的資源類型。分層訪問進(jìn)程訪問資源時(shí)，需要先申請(qǐng)較高級(jí)別的資源，再申請(qǐng)較低級(jí)別的資源。降低死鎖概率通過分層管理和分層訪問，可以有效地降低死鎖發(fā)生的概率。示例例如，可以將內(nèi)存、磁盤、文件系統(tǒng)等資源劃分到不同的層次，并制定相應(yīng)的訪問規(guī)則。死鎖相關(guān)案例分析死鎖問題在現(xiàn)實(shí)世界中經(jīng)常出現(xiàn)，例如多個(gè)應(yīng)用程序爭(zhēng)奪資源，可能會(huì)導(dǎo)致系統(tǒng)死鎖，導(dǎo)致應(yīng)用程序崩潰。舉例來說，在數(shù)據(jù)庫(kù)系統(tǒng)中，如果兩個(gè)事務(wù)同時(shí)鎖定同一數(shù)據(jù)行，可能會(huì)導(dǎo)致死鎖。如果兩個(gè)事務(wù)都等待對(duì)方