嵌入式軟件設(shè)計中查找缺陷的幾個技巧
加入技術(shù)交流群
圖3：有消息傳遞的死鎖
一些操作系統(tǒng)過多地使用消息傳遞來進(jìn)行線程間通信和同步。在這些類型的系統(tǒng)中，當(dāng)某線程向另一個線程傳遞消息時，發(fā)送線程將阻塞，直到從接收線程收到響應(yīng)為止。接收線程通常將一直阻塞到從其它某個線程接收到一個消息為止。這些結(jié)構(gòu)中也會發(fā)生死鎖。為了給一個基于消息的操作系統(tǒng)建立一張資源分配圖，我們利用消息通道來模擬分配的資源。圖3是一個例子。線程2建立了通道T2 Ch，當(dāng)它未因為等待這個通道上的一個消息而阻塞時，線程2就將鎖定這個通道。當(dāng)它阻塞并等待一個消息時，另一個線程可在這個通道上向它發(fā)送一個消息，并且這個消息將立即被接收到。
現(xiàn)在考慮下面這個系統(tǒng)：線程1指向Mutex并在通道T2 Ch上向線程2發(fā)送消息。在線程2中的某個地方，線程2在通道T3 Ch上向線程3發(fā)送消息。線程3也在通道T4 Ch上向線程4發(fā)送消息。在線程4中的某個地方，它也嘗試指向Mutex，如果得不到，它就將阻塞。顯然，各資源之間存在一條循環(huán)路徑，這表明有可能發(fā)生死鎖。例如，如果某一時刻線程1保持Mutex而線程4嘗試指向它，線程4就將在Mutex上阻塞。然后當(dāng)線程3嘗試在通道T4 Ch上向線程4發(fā)送一個消息時，線程3將阻塞，等待來自線程4的應(yīng)答(因為線程4是由于等待Mutex而阻塞，不是為了等待這個消息)。類似地，當(dāng)線程2嘗試向線程3發(fā)送一個消息時，將被阻塞；線程1嘗試向線程2發(fā)送一個消息時也將阻塞，由于它仍然保持著Mutex，所以系統(tǒng)將發(fā)生死鎖。
對付死鎖的最容易的辦法是通過設(shè)計進(jìn)行避免。采用以下任何一條設(shè)計約束都可排除死鎖出現(xiàn)的可能性：
* 任意時刻線程鎖定的資源不超過一個。
* 線程開始執(zhí)行前就完全分配它所需的全部資源。
* 指向多個資源的線程必須按照一種系統(tǒng)范圍的預(yù)設(shè)順序來鎖定(并釋放)這些資源。
如果無法通過設(shè)計來避免死鎖，則應(yīng)該建立資源分配圖。檢查資源分配圖可以識別潛在的死鎖。通過仔細(xì)跟蹤系統(tǒng)中的所有線程和它們鎖定的共享資源，可以維護(hù)資源分配圖并周期性地進(jìn)行檢查，及時發(fā)現(xiàn)循環(huán)等待的特征。
建立資源分配圖需要識別每個受保護(hù)的共享資源，以及指向其中某一資源的所有線程。如果使用一個操作系統(tǒng)，可以采用下面的過程步驟：
1. 識別所有可能阻塞的系統(tǒng)調(diào)用，如Mutex_Lock()，每個受保護(hù)的共享資源總是有一些與訪問它有關(guān)的阻塞調(diào)用。
2. 識別出獲取共享資源的阻塞調(diào)用之后，在源代碼中查找它們的各次調(diào)用情況。
3. 對于每次調(diào)用，記錄下指向資源的線程名稱和該資源的名稱。通常調(diào)用本身將受保護(hù)的資源作為一個參數(shù)來傳遞，調(diào)用在源代碼中所處的位置表明了哪個線程需要該資源。通過這種方式，可以識別出所有受保護(hù)的資源以及分配資源的線程。
4. 建立資源分配圖，并檢查是否有任何資源存在循環(huán)路徑。當(dāng)線程和共享資源較少時，畫出資源分配圖比較簡單。在較為復(fù)雜的系統(tǒng)中，最好將這些信息輸入分析表格，并編寫一個宏來檢查線程和資源分配結(jié)構(gòu)，以識別潛在的死鎖。編寫好宏之后，就可以快速地對資源分配變化進(jìn)行重新評估。編寫宏時，可以忽略不會導(dǎo)致死鎖的資源之間的循環(huán)。在表2所示的例子中，各種資源之間有許多循環(huán)，但只有線程6和線程7之間可能存在死鎖。
在一些類型的系統(tǒng)中，預(yù)先確定每一個共享資源并建立分配圖是不實際或不可能的。此時可以增加一些額外的代碼，以便在系統(tǒng)運行時檢測出潛在的死鎖。許多不同的算法都致力于優(yōu)化這個檢測過程，但本質(zhì)上它們幾乎都動態(tài)地建立某種資源分配圖。只要有線程請求、分配或釋放資源，分配圖就會被修改和檢測，以確定是否存在表明潛在死鎖的循環(huán)路徑。
檢測到某個死鎖之后，唯一的克服方法是強(qiáng)迫線程釋放關(guān)鍵的資源。通常，這意味著中斷正保持著所需資源的線程。對于某些應(yīng)用，這種方法可能是無法接受的。另一個有趣的解決方案是在運行時收集資源分配情況并進(jìn)行事后分析處理，以確定在程序運行過程中是否有死鎖情況發(fā)生。盡管這種方法并不能防止在運行時發(fā)生死鎖，但它確實有助于在死鎖出現(xiàn)后發(fā)現(xiàn)問題并進(jìn)行修復(fù)。
還有一些工具也可以用來幫助發(fā)現(xiàn)代碼中的死鎖。例如，Solaris程序設(shè)計員可以采用 Sun公司的LockLint工具來對代碼進(jìn)行統(tǒng)計分析。它可以發(fā)現(xiàn)對鎖定技術(shù)的不一致用法，識別引起競爭條件和死鎖的許多原因。
評論