嵌入式軟件設(shè)計(jì)中查找缺陷的幾個(gè)技巧
掃描二維碼
隨時(shí)隨地手機(jī)看文章
部分軟件開(kāi)發(fā)項(xiàng)目依靠結(jié)合代碼檢查、結(jié)構(gòu)測(cè)試和功能測(cè)試來(lái)識(shí)別軟件缺陷。盡管這些傳統(tǒng)技術(shù)非常重要，而且能發(fā)現(xiàn)大多數(shù)軟件問(wèn)題，但它們無(wú)法檢查出當(dāng)今復(fù)雜系統(tǒng)中的許多共性錯(cuò)誤。本文將介紹如何避免那些隱蔽然而常見(jiàn)的錯(cuò)誤，并介紹的幾個(gè)技巧幫助工程師發(fā)現(xiàn)軟件中隱藏的錯(cuò)誤。
結(jié)構(gòu)測(cè)試或白盒測(cè)試能有效地發(fā)現(xiàn)代碼中的邏輯、控制流、計(jì)算和數(shù)據(jù)錯(cuò)誤。這項(xiàng)測(cè)試要求對(duì)軟件的內(nèi)部工作能夠一覽無(wú)遺(因此稱(chēng)為"白盒"或"玻璃盒")，以便了解軟件結(jié)構(gòu)的詳細(xì)情況。它檢查每個(gè)條件表達(dá)式、數(shù)學(xué)操作、輸入和輸出。由于需要測(cè)試的細(xì)節(jié)眾多，結(jié)構(gòu)測(cè)試每次檢查一個(gè)軟件單元，通常為一個(gè)函數(shù)或類(lèi)。
代碼審查也使用與實(shí)現(xiàn)缺陷和潛在問(wèn)題查找同樣復(fù)雜的技術(shù)。與白盒測(cè)試一樣，審查通常針對(duì)軟件的各個(gè)單元進(jìn)行，因?yàn)橐粋€(gè)有效的審查過(guò)程要求的是集中而詳盡的檢查。
與審查和白盒測(cè)試不同，功能測(cè)試或黑盒測(cè)試假設(shè)對(duì)軟件的實(shí)現(xiàn)一無(wú)所知，它測(cè)試由受控輸入所驅(qū)動(dòng)的輸出。功能測(cè)試由測(cè)試人員或開(kāi)發(fā)人員所編寫(xiě)的測(cè)試過(guò)程組成，它們規(guī)定了一組特定程序輸入對(duì)應(yīng)的預(yù)期程序輸出。測(cè)試運(yùn)行之后，測(cè)試人員將實(shí)際輸出與預(yù)期輸出進(jìn)行比較，查找問(wèn)題。黑盒測(cè)試可以有效地找出未能實(shí)現(xiàn)的需求、接口問(wèn)題、性能問(wèn)題和程序最常用功能中的錯(cuò)誤。
雖然將這些技術(shù)結(jié)合起來(lái)可以找出隱藏在一個(gè)特定軟件程序中的大部分錯(cuò)誤，但它們也有局限。代碼審查和白盒測(cè)試每次只針對(duì)一小部分代碼，忽視了系統(tǒng)的其它部分。黑盒測(cè)試通常將系統(tǒng)作為一個(gè)整體來(lái)處理，忽視了實(shí)現(xiàn)的細(xì)節(jié)。一些重要的問(wèn)題只有在集中考察它們?cè)谡麄€(gè)系統(tǒng)內(nèi)相互作用時(shí)的細(xì)節(jié)才能被發(fā)現(xiàn)；傳統(tǒng)的方法無(wú)法可靠地找出這些問(wèn)題。必須整體地檢查軟件系統(tǒng)，查找具體問(wèn)題的特定原因。由于詳盡徹底地分析程序中的每個(gè)細(xì)節(jié)和它與代碼中所有其它部分之間的相互作用通常是不大可能的，因此分析應(yīng)該針對(duì)程序中已經(jīng)知道可能導(dǎo)致問(wèn)題的特定方面。本文將探討其中三個(gè)潛在的問(wèn)題領(lǐng)域：
* 堆棧溢出
* 競(jìng)爭(zhēng)條件
* 死鎖
讀者可在網(wǎng)上閱讀本文的第二部分，它將探討下列問(wèn)題：
* 時(shí)序問(wèn)題
* 可重入條件
在采用多任務(wù)實(shí)時(shí)設(shè)計(jì)技術(shù)的系統(tǒng)中，以上所有問(wèn)題都相當(dāng)普遍。
一、堆棧溢出
處理器使用堆棧來(lái)存儲(chǔ)臨時(shí)變量、向被調(diào)函數(shù)傳遞參數(shù)、保存線程“狀態(tài)”，等等。如果系統(tǒng)不使用虛擬內(nèi)存(換句話說(shuō)，它不能將內(nèi)存頁(yè)面轉(zhuǎn)移到磁盤(pán)上以釋放內(nèi)存空間供其它用途)，堆棧將固定為產(chǎn)品出廠時(shí)的大小。如果由于某種原因堆棧越出了編程人員所分配的數(shù)量范圍，程序?qū)⒆兊貌淮_定。這種不穩(wěn)定可能導(dǎo)致系統(tǒng)發(fā)生嚴(yán)重故障。因此，確保系統(tǒng)在最壞情況下能夠分配到足夠的堆棧至關(guān)重要。
表1：堆棧分析表格的一部分
確保永不發(fā)生堆棧溢出的唯一途徑就是分析代碼，確定程序在各種可能情況下的最大堆棧用量，然后檢查是否分配了足夠的堆棧。測(cè)試不大可能觸發(fā)特定的瞬時(shí)輸入組合進(jìn)而導(dǎo)致系統(tǒng)出現(xiàn)最壞情況。
堆棧深度分析的概念比較簡(jiǎn)單：
1. 為每個(gè)獨(dú)立的線程建立一棵調(diào)用樹(shù)。
2. 確定調(diào)用樹(shù)中每個(gè)函數(shù)的堆棧用量。
3. 檢查每棵調(diào)用樹(shù)，確定從樹(shù)根到外部“樹(shù)葉”的哪條調(diào)用路徑需要使用的堆棧最多。
4. 將每個(gè)獨(dú)立線程調(diào)用樹(shù)的最大堆棧用量相加。
5. 確定每個(gè)中斷優(yōu)先級(jí)內(nèi)各中斷服務(wù)程序(ISR)的最大堆棧用量并計(jì)算其總和。但是，如果ISR本身沒(méi)有堆棧而使用被中斷線程的堆棧，則應(yīng)將ISR使用的最大堆棧數(shù)加到各線程堆棧之上。
6. 對(duì)于每個(gè)優(yōu)先級(jí)，加上中斷發(fā)生時(shí)用來(lái)保存處理器狀態(tài)的堆棧數(shù)。
7.如果使用RTOS，則加上RTOS自身內(nèi)部用途需要的最大堆棧數(shù)(與應(yīng)用代碼引發(fā)的系統(tǒng)調(diào)用不同，后者已包含在步驟2中)。
除此之外，還有兩個(gè)重要事項(xiàng)需要考慮。首先，僅僅從高級(jí)語(yǔ)言源代碼建立的調(diào)用樹(shù)很可能并不完善。大部分編譯器采用運(yùn)行時(shí)庫(kù)(run-time library)來(lái)優(yōu)化常用計(jì)算任務(wù)，如大值整數(shù)的乘除、浮點(diǎn)運(yùn)算等，這些調(diào)用只在編譯器產(chǎn)生的匯編語(yǔ)言中才可見(jiàn)。運(yùn)行時(shí)庫(kù)函數(shù)本身可能使用大量的堆?？臻g，在分析時(shí)必須將它們包括進(jìn)去。如果使用的是C++語(yǔ)言，則以下所有類(lèi)型的函數(shù)(方法)也都必須包含到調(diào)用樹(shù)內(nèi)：結(jié)構(gòu)器、析構(gòu)器、重載運(yùn)算符、復(fù)制結(jié)構(gòu)器和轉(zhuǎn)換函數(shù)。所有的函數(shù)指針也都必須進(jìn)行解析，并且將它們調(diào)用的函數(shù)包含進(jìn)分析之中。
第二，編譯器使用一個(gè)C庫(kù)來(lái)實(shí)現(xiàn)memcpy()、cos()和atof ()等標(biāo)準(zhǔn)函數(shù)，而這些例程的源代碼可能無(wú)法得到。如果能夠得到它們的源代碼，就有可能確定程序用到的每個(gè)庫(kù)調(diào)用在最壞情況下的堆棧使用數(shù)量。如果這些庫(kù)只包含在目標(biāo)文件中，則編譯器廠商必須提供每個(gè)庫(kù)例程使用的堆棧數(shù)。如果沒(méi)有這些信息，就無(wú)法通過(guò)分析來(lái)確定最壞情況下程序使用的最大堆棧數(shù)。幸運(yùn)的是，許多面向嵌入式系統(tǒng)的編譯器廠商都提供這些信息。
通常，每次一個(gè)函數(shù)被調(diào)用時(shí)，編譯器將使用堆棧來(lái)保存返回地址并傳遞函數(shù)參數(shù)。函數(shù)的自動(dòng)(局部)變量通常也在堆棧當(dāng)中。不過(guò)，由于編譯器會(huì)盡可能通過(guò)將參數(shù)或局部變量放入寄存器來(lái)優(yōu)化代碼，因此檢查匯編語(yǔ)言以精確地確定堆棧用量非常重要。編譯器也有可能在代碼中的其它地方選擇使用堆棧，如用堆棧來(lái)保存中間計(jì)算結(jié)果。
有些與編譯器一起打包銷(xiāo)售的開(kāi)發(fā)環(huán)境包含生成調(diào)用樹(shù)的工具，還有許多第三方的調(diào)用樹(shù)生成工具。但是，除非它們能夠?qū)R編語(yǔ)言進(jìn)行分析，否則這些工具可能會(huì)遺漏運(yùn)行時(shí)庫(kù)和C庫(kù)的調(diào)用。不過(guò)無(wú)論在哪種情況下，開(kāi)發(fā)分析匯編語(yǔ)言文件并提取函數(shù)名稱(chēng)以及各函數(shù)內(nèi)部調(diào)用的腳本都比較簡(jiǎn)單。分析的結(jié)果可寫(xiě)入一個(gè)文件，而這個(gè)文件能夠方便地輸入到表格之中。
確定了各個(gè)函數(shù)的堆棧用量之后，必須計(jì)算每個(gè)線程所需的最大堆棧數(shù)。由于一般程序通常涉及數(shù)百個(gè)函數(shù)，調(diào)用跨越多層深度，處理這些信息的一種簡(jiǎn)便方法就是采用分析表格。如表1所示，表格的各行包含了函數(shù)名稱(chēng)、該函數(shù)使用的最大堆棧數(shù)(包括調(diào)用其它函數(shù)所需的堆棧數(shù))，以及它調(diào)用的所有函數(shù)的清單。通過(guò)編程控制，這個(gè)表格從每個(gè)函數(shù)的"根"開(kāi)始迭代循環(huán)，計(jì)算該函數(shù)及其調(diào)用的所有函數(shù)需要的堆棧。這些信息存放在堆棧路徑列中，這樣，采用每個(gè)線程根函數(shù)(如main)的堆棧路徑數(shù)據(jù)就可以方便地計(jì)算出需要的最大堆棧數(shù)了。這個(gè)過(guò)程包含了先前介紹的堆棧分析過(guò)程中的前四個(gè)步驟。
1. 在測(cè)試期間，觀察堆棧所能達(dá)到的深度，并保證有較大的堆?？臻g余量。
2. 檢測(cè)堆棧溢出，并采取改進(jìn)措施。
觀察堆棧深度的方法很簡(jiǎn)單:
* 向整個(gè)內(nèi)存堆棧區(qū)寫(xiě)入一個(gè)特定的數(shù)據(jù)圖案符號(hào)，如55AA。
* 在預(yù)期使用最大堆棧空間的條件下運(yùn)行系統(tǒng)。
* 使用仿真器或其它工具檢查堆棧存儲(chǔ)區(qū)，看有多少符號(hào)圖案由于堆棧的使用而被改寫(xiě)了。
當(dāng)然，這些步驟并不能保證在一些不同條件下不會(huì)需要更多的堆棧，但確實(shí)可以表明所需要的最小堆棧數(shù)。
使用帶內(nèi)存管理單元(MMU)的處理器時(shí)，有可能檢測(cè)出運(yùn)行時(shí)的堆棧溢出現(xiàn)象。MMU將內(nèi)存劃分為多個(gè)區(qū)域，用一個(gè)受保護(hù)的內(nèi)存段來(lái)“警戒”堆棧區(qū)域。發(fā)生堆棧溢出時(shí)，處理器將訪問(wèn)這個(gè)受保護(hù)段。這個(gè)操作將引發(fā)一個(gè)異常事件(如產(chǎn)生SIGSEGV信號(hào))，可被程序捕獲到。創(chuàng)建線程時(shí)，與實(shí)時(shí)POSIX標(biāo)準(zhǔn)兼容的RTOS提供有這種堆棧警戒功能選項(xiàng)，大大簡(jiǎn)化了編程人員的工作。GNU工具等其它開(kāi)發(fā)環(huán)境包含有編譯器開(kāi)關(guān)，可在程序中添加實(shí)現(xiàn)堆棧警戒功能所需的代碼，但它們?nèi)匀灰揽康讓硬僮飨到y(tǒng)來(lái)有效地處理堆棧溢出。但是，按照這種方式檢測(cè)溢出還只是問(wèn)題的一部分。為了使這類(lèi)設(shè)計(jì)更為有效，系統(tǒng)必須能夠從堆棧溢出中恢復(fù)過(guò)來(lái)并繼續(xù)正確地工作。
在一個(gè)對(duì)安全或任務(wù)要求嚴(yán)格的應(yīng)用中，系統(tǒng)運(yùn)行時(shí)在測(cè)試或檢測(cè)堆棧溢出期間監(jiān)視堆棧的深度可能并不是一項(xiàng)足夠的風(fēng)險(xiǎn)控制措施。對(duì)于一些應(yīng)用，必須確保系統(tǒng)絕對(duì)不會(huì)越出所分配的堆棧范圍；只有通過(guò)完整的堆棧深度分析才能證明這一點(diǎn)。這意味著，如果整個(gè)程序在同一內(nèi)存空間運(yùn)行，則必須對(duì)所有代碼執(zhí)行這項(xiàng)分析。不過(guò)，如果使用MMU，分析常可簡(jiǎn)化。在設(shè)計(jì)系統(tǒng)時(shí)，可將所有關(guān)鍵代碼置于一個(gè)或多個(gè)獨(dú)立線程內(nèi)，而這些線程分別在各自的保護(hù)內(nèi)存段中運(yùn)行。這樣，只要對(duì)這些關(guān)鍵線程進(jìn)行堆棧使用分析就可以了。當(dāng)然，這項(xiàng)簡(jiǎn)化設(shè)計(jì)假定當(dāng)非關(guān)鍵線程溢出其堆棧并失效時(shí)，關(guān)鍵線程仍可正確執(zhí)行。
由于分析工作所需的堆棧使用數(shù)據(jù)來(lái)自匯編語(yǔ)言清單，因此修改代碼時(shí)，相應(yīng)模塊的堆棧使用信息必須予以更新。如果使用不同的編譯器版本，或者改變了優(yōu)化設(shè)置，也必須復(fù)核整個(gè)分析過(guò)程。在理想情況下，編譯器將提供每個(gè)函數(shù)(如果不是每個(gè)線程的話)的堆棧使用數(shù)量，因?yàn)樗鼡碛杏?jì)算需要的所有信息。例如，瑞薩公司提供有Call Walker，這是該公司高性能的Embedded Workshop開(kāi)發(fā)環(huán)境的一部分。這個(gè)工具可以圖形化地顯示每個(gè)函數(shù)使用的調(diào)用樹(shù)和堆棧，包括運(yùn)行時(shí)庫(kù)和C庫(kù)的函數(shù)。Call Walker也能找出使用堆棧數(shù)量最大的路徑。使用這樣的工具可以實(shí)現(xiàn)步驟1到步驟3的自動(dòng)化。
大部分軟件開(kāi)發(fā)項(xiàng)目依靠結(jié)合代碼檢查、結(jié)構(gòu)測(cè)試和功能測(cè)試來(lái)識(shí)別軟件缺陷。盡管這些傳統(tǒng)技術(shù)非常重要，而且能發(fā)現(xiàn)大多數(shù)軟件問(wèn)題，但它們無(wú)法檢查出當(dāng)今復(fù)雜系統(tǒng)中的許多共性錯(cuò)誤。本文將介紹如何避免那些隱蔽然而常見(jiàn)的錯(cuò)誤，并介紹的幾個(gè)技巧幫助工程師發(fā)現(xiàn)軟件中隱藏的錯(cuò)誤。
二、競(jìng)爭(zhēng)條件
當(dāng)兩個(gè)或更多獨(dú)立線程同時(shí)訪問(wèn)同一資源時(shí)，就出現(xiàn)了競(jìng)爭(zhēng)條件。競(jìng)爭(zhēng)條件的影響多種多樣，取決于具體的情況。清單1解釋了一個(gè)潛在的競(jìng)爭(zhēng)條件。函數(shù)Update_Sensor()通過(guò)調(diào)用get_raw()來(lái)讀取傳感器的原始數(shù)據(jù)。在處理過(guò)程中，該數(shù)據(jù)被乘上一個(gè)定標(biāo)因子，并加上一個(gè)偏移量。處理是在該數(shù)據(jù)的一個(gè)臨時(shí)副本上進(jìn)行的，然后，該臨時(shí)副本被寫(xiě)入共享變量。
清單1：競(jìng)爭(zhēng)條件
如果在數(shù)據(jù)寫(xiě)入之前，使用shared_sensor的另一個(gè)線程或ISR先占(preempt)了這個(gè)線程，它將得到原來(lái)的傳感器讀數(shù)。使用臨時(shí)副本可以防止先占線程讀取只經(jīng)過(guò)部分處理的數(shù)據(jù)。不過(guò)，如果這些代碼在一個(gè)數(shù)據(jù)總線不足32位的處理器上運(yùn)行，就會(huì)存在競(jìng)爭(zhēng)條件。
在一個(gè)8位或16位的處理器上，向shared_sensor的寫(xiě)入操作并不是一次性完成的。在8位處理器上，寫(xiě)入32位浮點(diǎn)值可能需要四條指令，在16位處理器上可能需要兩條指令。如果在對(duì)shared_sensor進(jìn)行連續(xù)寫(xiě)入中途Update_Sensor()被先占，則先占線程將從由一部分老數(shù)據(jù)和一部分新數(shù)據(jù)組成的shared_sensor讀取一個(gè)數(shù)值。根據(jù)應(yīng)用的具體情況，這有可能造成嚴(yán)重的后果。解決的辦法是鎖定調(diào)度程序，或在更新共享變量期間禁止中斷。
消除競(jìng)爭(zhēng)條件通常很簡(jiǎn)單，但找出隱藏在代碼中的競(jìng)爭(zhēng)條件則需要仔細(xì)的分析。
對(duì)于由一個(gè)循環(huán)程序和不同ISR組成的簡(jiǎn)單系統(tǒng)，分析競(jìng)爭(zhēng)條件很簡(jiǎn)單，只需檢查每個(gè)ISR并識(shí)別它引用的所有共享變量。共享變量通常是這些系統(tǒng)中的全局?jǐn)?shù)據(jù)，一旦這些共享變量被找出來(lái)之后，就可以檢查它們?cè)诖a中的各次使用情況。每次訪問(wèn)都必須按需要進(jìn)行保護(hù)，以避免潛在的沖突。在簡(jiǎn)單設(shè)計(jì)中，一般通過(guò)在關(guān)鍵代碼段周?chē)怪袛鄟?lái)實(shí)現(xiàn)保護(hù)。遵守下列規(guī)則可幫助避免競(jìng)爭(zhēng)問(wèn)題：
* 如果一個(gè)ISR對(duì)共享數(shù)據(jù)進(jìn)行寫(xiě)入，則該ISR之外的每次可中斷的讀操作都必須予以保護(hù)。
* 如果一個(gè)ISR對(duì)共享數(shù)據(jù)進(jìn)行寫(xiě)入，則該ISR之外的任何讀－修－寫(xiě)操作都必須予以保護(hù)。
* 如果一個(gè)ISR讀取共享數(shù)據(jù)，則對(duì)該數(shù)據(jù)的可中斷寫(xiě)操作必須予以保護(hù)。
* 如果一個(gè)ISR和其它代碼都要檢查一個(gè)硬件狀態(tài)標(biāo)志，以便在使用某資源之前確定其可用性，如：
if (!resource_busy)
{
// Use resource
}
則從檢查標(biāo)志之時(shí)開(kāi)始，到硬件設(shè)置標(biāo)志表示資源不可用為止，必須采取保護(hù)措施。
對(duì)于使用了優(yōu)先級(jí)不同的多個(gè)線程的更為復(fù)雜的系統(tǒng)，其分析也非常相似。上述規(guī)則仍然適用于ISR使用的所有數(shù)據(jù)。此外，還必須識(shí)別出每個(gè)線程使用的共享數(shù)據(jù)。首先從系統(tǒng)中優(yōu)先級(jí)最高的線程開(kāi)始，找出它與任何優(yōu)先級(jí)較低的線程共享的所有數(shù)據(jù)，然后按照上述四條規(guī)則進(jìn)行保護(hù)。對(duì)于軟件使用的其它每個(gè)優(yōu)先級(jí)，再重復(fù)這一過(guò)程。
注意，如果系統(tǒng)采用了一種循環(huán)調(diào)度算法，則特定優(yōu)先級(jí)內(nèi)的所有線程可在任意時(shí)刻相互先占。這意味著前述四條分析規(guī)則在考慮較低優(yōu)先級(jí)的線程之外，還必須考慮同一優(yōu)先級(jí)的所有線程。
多線程系統(tǒng)通常使用某種類(lèi)型的操作系統(tǒng)，它能夠提供多種保護(hù)選擇?？梢允褂没コ饣蛐盘?hào)量，或者鎖定調(diào)度器。有時(shí)也可使用其它進(jìn)程間通信(IPC)基本技術(shù)：通過(guò)向消息隊(duì)列發(fā)送消息(而非修改共享變量)來(lái)表示數(shù)據(jù)已經(jīng)改變。在許多情況下，最好由單一線程來(lái)管理共享資源，它負(fù)責(zé)處理所有的讀寫(xiě)請(qǐng)求，并在內(nèi)部防止訪問(wèn)沖突。在復(fù)雜的代碼中辨認(rèn)潛在的競(jìng)爭(zhēng)條件可能是一項(xiàng)乏味而又耗時(shí)的工作。相應(yīng)的輔助工具從用來(lái)識(shí)別全局?jǐn)?shù)據(jù)訪問(wèn)的簡(jiǎn)單腳本到先進(jìn)的動(dòng)態(tài)分析程序如Polyspace Verifier。雖然比較困難，但詳盡的代碼分析是識(shí)別這類(lèi)錯(cuò)誤的唯一途徑。測(cè)試不大可能能夠建立重復(fù)觸發(fā)競(jìng)爭(zhēng)條件所需的精確時(shí)序序列。
三、死鎖
在共享資源的系統(tǒng)中，防止訪問(wèn)沖突極為重要，但這有可能導(dǎo)致另一個(gè)問(wèn)題：死鎖。當(dāng)通過(guò)"鎖定"一個(gè)資源來(lái)防止任何其它線程訪問(wèn)這個(gè)資源，以避免競(jìng)爭(zhēng)條件時(shí)，必須對(duì)設(shè)計(jì)進(jìn)行評(píng)估，確保絕對(duì)不會(huì)發(fā)生死鎖。死鎖測(cè)試通常沒(méi)有什么效果，因?yàn)橹挥心撤N特定順序的資源鎖定才可能產(chǎn)生死鎖，而一般的測(cè)試不大可能導(dǎo)致這種順序。
死鎖只不過(guò)是多線程環(huán)境中一個(gè)鎖定資源的問(wèn)題。以下四個(gè)條件必須同時(shí)具備，才會(huì)發(fā)生死鎖。防止其中任何一個(gè)條件出現(xiàn)都可以排除死鎖的可能性：
* 相互排除---每次只有一個(gè)線程可以使用某個(gè)鎖定的資源；
* 非先占---其它線程不能強(qiáng)迫另一個(gè)線程釋放資源；
* 保持并等待---線程在等待需要的其它任何資源時(shí)，保持它們已經(jīng)鎖定的資源；
* 循環(huán)等待---存在一個(gè)線程循環(huán)鏈，其中每個(gè)線程保持鏈中下一個(gè)線程所需要的資源。
圖1：循環(huán)等待
圖1中的資源分配圖是死鎖問(wèn)題的一個(gè)例子。線程1首先鎖定Buf資源，在保持Buf時(shí)，指向Bus，然后是Mux。如果線程1一直運(yùn)行到結(jié)束，它最終將釋放所有這些資源。線程2運(yùn)行時(shí)，必須指向Bus、Sem，最后是Mux。線程3運(yùn)行時(shí)，需要Sem和Buf。
在這個(gè)設(shè)計(jì)實(shí)例中，無(wú)法保證任何一個(gè)線程能夠在另一個(gè)線程開(kāi)始執(zhí)行之前結(jié)束。如果一個(gè)線程不能得到需要的某個(gè)資源，它將掛起執(zhí)行(阻塞)，直到該資源有效為止。在系統(tǒng)運(yùn)行過(guò)程中，各線程都將對(duì)資源進(jìn)行鎖定或解鎖。由于各線程運(yùn)行和指向其資源的相對(duì)時(shí)序各不相同，有可能出現(xiàn)由于各個(gè)線程正在等待被其它線程保持的資源，導(dǎo)致所有線程都無(wú)法運(yùn)行的情況。例如，如果線程1保持Buf，線程2保持Bus，而線程3已經(jīng)取得了Sem，則系統(tǒng)將發(fā)生死鎖。因?yàn)榘凑諒腂uf到Bus到Sem，再回到Buf的線程分配箭頭，循環(huán)等待條件得到了滿足。
圖2：沒(méi)有死鎖
潛在死鎖問(wèn)題識(shí)別出來(lái)之后，通常很容易進(jìn)行修復(fù)。在圖2中，對(duì)線程3進(jìn)行了修改，使其在得到Sem之前首先設(shè)法指向Buf。這樣，循環(huán)等待的條件就被打破了，系統(tǒng)將不會(huì)再受到死鎖的影響。
圖3：有消息傳遞的死鎖
一些操作系統(tǒng)過(guò)多地使用消息傳遞來(lái)進(jìn)行線程間通信和同步。在這些類(lèi)型的系統(tǒng)中，當(dāng)某線程向另一個(gè)線程傳遞消息時(shí)，發(fā)送線程將阻塞，直到從接收線程收到響應(yīng)為止。接收線程通常將一直阻塞到從其它某個(gè)線程接收到一個(gè)消息為止。這些結(jié)構(gòu)中也會(huì)發(fā)生死鎖。為了給一個(gè)基于消息的操作系統(tǒng)建立一張資源分配圖，我們利用消息通道來(lái)模擬分配的資源。圖3是一個(gè)例子。線程2建立了通道T2 Ch，當(dāng)它未因?yàn)榈却@個(gè)通道上的一個(gè)消息而阻塞時(shí)，線程2就將"鎖定"這個(gè)通道。當(dāng)它阻塞并等待一個(gè)消息時(shí)，另一個(gè)線程可在這個(gè)通道上向它發(fā)送一個(gè)消息，并且這個(gè)消息將立即被接收到。
現(xiàn)在考慮下面這個(gè)系統(tǒng)：線程1指向Mutex并在通道T2 Ch上向線程2發(fā)送消息。在線程2中的某個(gè)地方，線程2在通道T3 Ch上向線程3發(fā)送消息。線程3也在通道T4 Ch上向線程4發(fā)送消息。在線程4中的某個(gè)地方，它也嘗試指向Mutex，如果得不到，它就將阻塞。顯然，各資源之間存在一條循環(huán)路徑，這表明有可能發(fā)生死鎖。例如，如果某一時(shí)刻線程1保持Mutex而線程4嘗試指向它，線程4就將在Mutex上阻塞。然后當(dāng)線程3嘗試在通道T4 Ch上向線程4發(fā)送一個(gè)消息時(shí)，線程3將阻塞，等待來(lái)自線程4的應(yīng)答(因?yàn)榫€程4是由于等待Mutex而阻塞，不是為了等待這個(gè)消息)。類(lèi)似地，當(dāng)線程2嘗試向線程3發(fā)送一個(gè)消息時(shí)，將被阻塞；線程1嘗試向線程2發(fā)送一個(gè)消息時(shí)也將阻塞，由于它仍然保持著Mutex，所以系統(tǒng)將發(fā)生死鎖。
對(duì)付死鎖的最容易的辦法是通過(guò)設(shè)計(jì)進(jìn)行避免。采用以下任何一條設(shè)計(jì)約束都可排除死鎖出現(xiàn)的可能性：
* 任意時(shí)刻線程鎖定的資源不超過(guò)一個(gè)。
* 線程開(kāi)始執(zhí)行前就完全分配它所需的全部資源。
* 指向多個(gè)資源的線程必須按照一種系統(tǒng)范圍的預(yù)設(shè)順序來(lái)鎖定(并釋放)這些資源。
如果無(wú)法通過(guò)設(shè)計(jì)來(lái)避免死鎖，則應(yīng)該建立資源分配圖。檢查資源分配圖可以識(shí)別潛在的死鎖。通過(guò)仔細(xì)跟蹤系統(tǒng)中的所有線程和它們鎖定的共享資源，可以維護(hù)資源分配圖并周期性地進(jìn)行檢查，及時(shí)發(fā)現(xiàn)循環(huán)等待的特征。
建立資源分配圖需要識(shí)別每個(gè)受保護(hù)的共享資源，以及指向其中某一資源的所有線程。如果使用一個(gè)操作系統(tǒng)，可以采用下面的過(guò)程步驟：
1. 識(shí)別所有可能阻塞的系統(tǒng)調(diào)用，如Mutex_Lock()，每個(gè)受保護(hù)的共享資源總是有一些與訪問(wèn)它有關(guān)的阻塞調(diào)用。
2. 識(shí)別出獲取共享資源的阻塞調(diào)用之后，在源代碼中查找它們的各次調(diào)用情況。
3. 對(duì)于每次調(diào)用，記錄下指向資源的線程名稱(chēng)和該資源的名稱(chēng)。通常調(diào)用本身將受保護(hù)的資源作為一個(gè)參數(shù)來(lái)傳遞，調(diào)用在源代碼中所處的位置表明了哪個(gè)線程需要該資源。通過(guò)這種方式，可以識(shí)別出所有受保護(hù)的資源以及分配資源的線程。
4. 建立資源分配圖，并檢查是否有任何資源存在循環(huán)路徑。當(dāng)線程和共享資源較少時(shí)，畫(huà)出資源分配圖比較簡(jiǎn)單。在較為復(fù)雜的系統(tǒng)中，最好將這些信息輸入分析表格，并編寫(xiě)一個(gè)宏來(lái)檢查線程和資源分配結(jié)構(gòu)，以識(shí)別潛在的死鎖。編寫(xiě)好宏之后，就可以快速地對(duì)資源分配變化進(jìn)行重新評(píng)估。編寫(xiě)宏時(shí)，可以忽略不會(huì)導(dǎo)致死鎖的資源之間的循環(huán)。在表2所示的例子中，各種資源之間有許多循環(huán)，但只有線程6和線程7之間可能存在死鎖。
在一些類(lèi)型的系統(tǒng)中，預(yù)先確定每一個(gè)共享資源并建立分配圖是不實(shí)際或不可能的。此時(shí)可以增加一些額外的代碼，以便在系統(tǒng)運(yùn)行時(shí)檢測(cè)出潛在的死鎖。許多不同的算法都致力于優(yōu)化這個(gè)檢測(cè)過(guò)程，但本質(zhì)上它們幾乎都動(dòng)態(tài)地建立某種資源分配圖。只要有線程請(qǐng)求、分配或釋放資源，分配圖就會(huì)被修改和檢測(cè)，以確定是否存在表明潛在死鎖的循環(huán)路徑。
檢測(cè)到某個(gè)死鎖之后，唯一的克服方法是強(qiáng)迫線程釋放關(guān)鍵的資源。通常，這意味著中斷正保持著所需資源的線程。對(duì)于某些應(yīng)用，這種方法可能是無(wú)法接受的。另一個(gè)有趣的解決方案是在運(yùn)行時(shí)收集資源分配情況并進(jìn)行事后分析處理，以確定在程序運(yùn)行過(guò)程中是否有死鎖情況發(fā)生。盡管這種方法并不能防止在運(yùn)行時(shí)發(fā)生死鎖，但它確實(shí)有助于在死鎖出現(xiàn)后發(fā)現(xiàn)問(wèn)題并進(jìn)行修復(fù)。
還有一些工具也可以用來(lái)幫助發(fā)現(xiàn)代碼中的死鎖。例如，Solaris程序設(shè)計(jì)員可以采用 Sun公司的LockLint工具來(lái)對(duì)代碼進(jìn)行統(tǒng)計(jì)分析。它可以發(fā)現(xiàn)對(duì)鎖定技術(shù)的不一致用法，識(shí)別引起競(jìng)爭(zhēng)條件和死鎖的許多原因。
下載文檔
