死鎖(Deadlock)是指多個(gè)進(jìn)程在運(yùn)行的過(guò)程中因爭(zhēng)奪資源而造成的一種僵局。當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí),若無(wú)外力作用,它們都將無(wú)法再向前推進(jìn)。在軟件設(shè)計(jì)師的考試當(dāng)中,這個(gè)知識(shí)點(diǎn)的考查是以選擇題的形式出現(xiàn)的,考點(diǎn)主要有:死鎖的必要條件、解決死鎖的方法,最難高難度會(huì)考到“銀行家算法”。本文將介紹死鎖的相關(guān)知識(shí),但不會(huì)具體講解“銀行家算法”,該算法將在本系列的下一篇文章中詳細(xì)說(shuō)明。
1、死鎖發(fā)生的必要條件
死鎖的發(fā)生必須具備四個(gè)必要條件,這四個(gè)條件相互聯(lián)系、缺一不可。
(1)互斥條件:指進(jìn)程對(duì)所分配到的資源進(jìn)行排他性使用,即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其他進(jìn)程請(qǐng)求該資源,則請(qǐng)求者只能等待,直至占有該資源的進(jìn)程用完并釋放。
(2)請(qǐng)求和保持條件:指進(jìn)程已經(jīng)保持了至少一個(gè)資源,但又提出了新的資源請(qǐng)求,而該資源又已被其他進(jìn)程占有,此時(shí)請(qǐng)求進(jìn)程阻塞,但又對(duì)自己已獲得的其他資源保持不放。
(3)不剝奪條件:指進(jìn)程已獲得的資源,在未使用完之前,不能被剝奪,只能在使用完時(shí)由自己釋放。
(4)環(huán)路等待條件:指在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程--資源的環(huán)形鏈,即進(jìn)程集合{P0,P1,P2…Pn}中的P0正在等待一個(gè)P1占用的資源,P1正在等待P2占用的資源,……Pn正在等待已被P0占用的資源。
3、判斷系統(tǒng)是否可能進(jìn)入死鎖狀態(tài)
從上面的死鎖解決方案來(lái)看,無(wú)論哪一種方式都不可避免的要增加系統(tǒng)的負(fù)擔(dān)。而同時(shí)一個(gè)系統(tǒng)是否有可進(jìn)入死鎖狀態(tài)受系統(tǒng)資源數(shù)量,需要使用該資源的進(jìn)程數(shù)量等因素影響。若系統(tǒng)本不可能引起死鎖,而我們采用了死鎖解決方案,是很不合理的。所以,考試中?嫉竭@樣的題型:給出系統(tǒng)的資源數(shù),以及需要使用該資源的進(jìn)程數(shù)量等參數(shù),讓考生判斷系統(tǒng)有無(wú)可能產(chǎn)生死鎖。下面我們以例題的方式來(lái)說(shuō)明如何解決這類(lèi)問(wèn)題。
例題1:
系統(tǒng)有3個(gè)進(jìn)程:A、B、C。這3個(gè)進(jìn)程都需要5個(gè)系統(tǒng)資源。如果系統(tǒng)有多少個(gè)資源,則不可能發(fā)生死鎖。
解答:
在分析這個(gè)問(wèn)題時(shí),我們可以取一些簡(jiǎn)單的數(shù)據(jù)代入試題進(jìn)行驗(yàn)證、分析,以得到相應(yīng)的規(guī)律。
如:
(1)當(dāng)系統(tǒng)資源數(shù)量為9時(shí),若給A與B分別分配了4個(gè)資源,C分配了1個(gè)資源,則系統(tǒng)中的每個(gè)進(jìn)程都存在資源不足的情況,而都不放手自己擁有的資源。不能正常運(yùn)行完畢,發(fā)生死鎖。
(2)當(dāng)系統(tǒng)資源數(shù)量為12時(shí),若給A、B、C各分配4個(gè)資源,則死鎖。
(3)當(dāng)系統(tǒng)資源數(shù)量為13時(shí),無(wú)論如何分配,總有至少1個(gè)進(jìn)程能得到5個(gè)資源,得到5個(gè)資源的進(jìn)程可以正常運(yùn)行完畢,而后將自己占用的資源分配給其它進(jìn)程,所以這樣能使所有進(jìn)程運(yùn)行完畢。
從上面的嘗試,我們可以總結(jié)出一個(gè)規(guī)律:先給所有進(jìn)程分配他們所需要的資源數(shù)減1個(gè)資源,然后系統(tǒng)如果能再剩余1個(gè)資源,則系統(tǒng)不會(huì)發(fā)生死鎖。這樣解答本題變得非常容易。
(5-1)*3+1=13。
例題2:
一臺(tái)計(jì)算機(jī)有10臺(tái)磁帶機(jī)被m個(gè)進(jìn)程競(jìng)爭(zhēng),每個(gè)進(jìn)程最多需要三臺(tái)磁帶機(jī),那么m至多為 時(shí),系統(tǒng)沒(méi)有死鎖的危險(xiǎn)。
A.3 B.4 C.5 D.6
解答
首先從m=6開(kāi)始考察,首先每個(gè)進(jìn)程分配1臺(tái),剩下的4臺(tái)只能分配給4個(gè)進(jìn)程,還有2個(gè)進(jìn)程沒(méi)有分配,如果已經(jīng)分配了2臺(tái)的4個(gè)進(jìn)程需要3臺(tái)的話,則系統(tǒng)就會(huì)死鎖。同樣,如果m=5,也會(huì)發(fā)生這種情況。當(dāng)m=4時(shí),每個(gè)進(jìn)程可以分得2臺(tái),還有2個(gè)進(jìn)程可分得3臺(tái),則可正常運(yùn)行,運(yùn)行完畢后可釋放資源,從而不會(huì)死鎖。在解這道題時(shí)有些學(xué)員提出“如果按照答案m=4,則這4個(gè)進(jìn)程都是需要3臺(tái)磁帶機(jī)的話,共需要12臺(tái)磁帶機(jī),這樣還不會(huì)死鎖?”。這種想法是錯(cuò)誤的,因?yàn)椴⒉皇峭瑫r(shí)把所有進(jìn)程都分配給足夠的資源才能完成這些進(jìn)程,可以是一個(gè)進(jìn)程先執(zhí)行完,釋放完資源再執(zhí)行另一個(gè)進(jìn)程。
例如:4個(gè)進(jìn)程中,每個(gè)進(jìn)程分配2臺(tái)磁帶機(jī),用去了8臺(tái)。剩下2臺(tái),仍然可以滿足兩個(gè)進(jìn)程,直到他們完成,釋放他們暫用的磁帶機(jī)。
相關(guān)推薦:2010年計(jì)算機(jī)軟件水平考試時(shí)間安排通知北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |