多執行緒(multi-thread) - 避免發生死結(死鎖)(deadlock)的小技巧！（一）

多執行緒(multi-thread) ！一個讓程式師又愛又恨的技術！ 
愛的是....它能善用單CPU和人機介面操作時的閒置時間，藉此加快程式運作。也能利用現在最夯的趨勢：多核心CPU，大幅增進程式效能。
恨的是....用lock時，萬一發生死結(deadlock)，可是會讓你除錯除到不知所云～(很容易發生)。程式設計的不好時，還會發生多執行緒lock競爭問題(race conditions)。結果是效能不增反減！

死結(死鎖)！這是最常發生的問題！
研究這門技術時，我看書看資料看了好久好久，並且有加上實作測試和實務應用，最後才慢慢融會貫通，才較知道如何運用多執行緒時避免死結。
在此，將我的防死結研究心得和大家分享！

///////////////////////////////////////////////////////////////////////////

有一種常見的狀況，會發生死結：

struct PlayerNode
{
        long  Number;
        CRITICAL_SECTION  LockInfo;
        PlayerNode  *pNext;
};
PlayerNode *ActorNode;
PlayerNode *EnemyNode;

void gNodeDataSwapFunc( PlayerNode *node1, PlayerNode *node2 )
{
        ::EnterCriticalSection( &node1->LockInfo );
        ::EnterCriticalSection( &node2->LockInfo );
    
        long temp = node1->Number;
        node1->Number = node2->Number;
        node2->Number = temp;

        ::LeaveCriticalSection( &node2->LockInfo );
        ::LeaveCriticalSection( &node1->LockInfo );
}
gNodeDataSwapFunc這個函式看似沒有問題，其實用在多緒程式時，就會發生死結。

假設...有二個執行緒會去呼叫gNodeDataSwapFunc。
Thread-A執行如下:
　　　　gNodeDataSwapFunc( ActorNode, EnemyNode );
Thread-B執行如下:
　　　　gNodeDataSwapFunc( EnemyNode, ActorNode );

各位看出來嚕嗎？這樣就一定會發生死結。
原因是因為...當Thread-A的ActorNode和EnemyNode傳入到gNodeDataSwapFunc，
ActorNode給它lock住後，可能就會馬上發生執行緒切換(context switch)，
然後切換到Thread-B來執行，
結果Thread-B呼叫的gListDataSwapFunc傳入的EnemyNode也頭一個就lock住，
然後要在lock這ActorNode時，會發現它已經被其他執行緒lock住了，
所以Thread-B就此進入等待...等待此lock解開後才能繼續往下執行。
接著，系統再度切換回Thread-A這邊，繼續往下執行要lock住EnemyNode，
當然發現它也被其他執行緒lock住了，所以Thread-A也進入等待...
這二個執行緒彼此互相等待對方解開鎖，才能往下執行，
但是都沒辦法，因為都已經進入等待...
此時，就是產生了死結了！ 

什麼！還看不出來嗎？
就是說...
ActorNode在Thread-A中lock住了。
EnemyNode在Thread-B中lock住了。
二個執行緒彼此都在等待對方的鎖先解開。
Thread-A會一直等待EnemyNode解開lock後才能往下執行。
Thread-B會一直等待ActorNode解開lock後才能往下執行。
這就是死結嚕！雙方無止盡的互相等待下去！


好的，一個簡單有效的解決方案是...在外圍再加上一個lock.
程式碼示例如下：
void gNodeDataSwapFunc( PlayerNode *node1, PlayerNode *node2 )
{
        ::EnterCriticalSection( &SingleLockInfo );

        ::EnterCriticalSection( &node1->LockInfo );
        ::EnterCriticalSection( &node2->LockInfo );
    
        longtemp = node1->Number;
        node1->Number = node2->Number;
        node2->Number = temp;

        ::LeaveCriticalSection( &node2->LockInfo );
        ::LeaveCriticalSection( &node1->LockInfo );

        ::LeaveCriticalSection( &SingleLockInfo );
}

SingleLockInfo在此就很重要了。
在這種典型的巢狀lock狀況中，就是要規定，一次只能一個thread才能執行裡面的內容！
就能避免多緒時發生死結！

如果可以盡量不要用多重巢狀lock的話，就盡量避開此種寫法，
則能避開死結的發生喔！

///////////////////////////////////////////////////////////////////////////

另一種狀況就是，如果...有必要同時lock很多個鎖時，
而且lock的先後順序也不一致的話，就會產生死結。
下面是會產生死結的範例程式碼：
void g_A_WorkThreadFunc()
{
        ::EnterCriticalSection( &SingleLockInfo1 );
        ::EnterCriticalSection( &SingleLockInfo2 );

        // 其中執行很多程式碼...

        ::LeaveCriticalSection( &SingleLockInfo2 );
        ::LeaveCriticalSection( &SingleLockInfo1 );
}
void g_B_WorkThreadFunc()
{
        ::EnterCriticalSection( &SingleLockInfo2 );
        ::EnterCriticalSection( &SingleLockInfo1 );

        // 其中執行很多程式碼...

        ::LeaveCriticalSection( &SingleLockInfo2 );
        ::LeaveCriticalSection( &SingleLockInfo1 );
}上述會發生死結的原因也是跟之前說明的一樣.
肇因就是不同執行緒要用相同的一堆鎖時，他們的lock順序不一致的關係.


我自己的解法是...替每一組相關的鎖加上編號，要使用鎖時，
則要按照鎖的編號順序來lock，這樣就能容易的避開人為疏失！
所以記得使用時，不能任意顛倒編號來lock喔！

這樣用說的可能很難理解...直接用程式碼來解釋吧！
程式碼示例如下：
void g_A_WorkThreadFunc()
{
        // 要按照順序來lock (這邊用三個鎖)
        ::EnterCriticalSection( &SingleLockInfo1 );
        ::EnterCriticalSection( &SingleLockInfo2 );
        ::EnterCriticalSection( &SingleLockInfo3 );

        // 其中執行很多程式碼...

        // unlock的順序就無所謂,沒有那麼重要了
        ::LeaveCriticalSection( &SingleLockInfo3 );
        ::LeaveCriticalSection( &SingleLockInfo2 );
        ::LeaveCriticalSection( &SingleLockInfo1 );
}
void g_B_WorkThreadFunc()
{
        // 要按照順序來lock (這邊只用二個鎖)
        ::EnterCriticalSection( &SingleLockInfo2 );
        ::EnterCriticalSection( &SingleLockInfo3 );

        // 其中執行很多程式碼...

        // unlock的順序就無所謂,沒有那麼重要了
        ::LeaveCriticalSection( &SingleLockInfo3 );
        ::LeaveCriticalSection( &SingleLockInfo2 );
}



OK ! enjoy it.