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