執行緒同步 9：死鎖問題

這次要介紹的是死鎖。 聽到這名字，會不會讓人以為又是具有某種特殊性質的執行緒鎖？ 不，死鎖並不是一種執行緒鎖，而是一種我們並不樂見的情況……

情境

在真正開始之前，先讓我們看一段程式範例。 這個範例取材自我自己的程式專案，不過經過了非常用力的刪減修改，基本只保留了用來呈現死鎖問題的最核心部份。 程式碼雖然以 C++ 語法撰寫，但因為這次的範例並不是一個完整可編譯執行的程式， 因此也可以把它看作是虛擬碼，應將重點放在理解而非測試。

我建立了一個叫作 Logger 的軟體模組， 它被設計用來將程式運作時所發生的各種事情記錄在一個文字檔內， 供後續需要時可以人工追查程式運作中曾經歷過的事情。 所以在整個程式的程式碼各處都會呼叫 WriteLogger() 函式， 目的是將當下所產生的訊息記錄傳送給 Logger 模組，讓它將記錄以某種格式編碼為一段文字之後寫入檔案儲存。 其中將記錄轉換為文字訊息的部份還提供了幾種不同的格式可供使用者依據喜好需求而做選用， 在 Logger 內以一個整數旗標用來表示使用者所偏好的格式 ID。 最後，這個 Logger 還可以讓使用者在任何時候變更有關的設定參數， 無論是編碼格式或甚可能是想要更改記錄檔的檔名或存放位置等都可以， 只要呼叫 ReloadLogger() 就能夠變更 Logger 的設定配置。 並且修改這些配置和程式正常的訊息記錄動作並不互相衝突， 使用者完全可以在程式運作的任何階段去呼叫 ReloadLogger() 修改配置， 並且同時可能隨時也都有人正在呼叫 WriteLogger() 函式； 一邊正在儲存程式記錄而另一邊同時可以修改配置， 並且變更後的配置可以立刻生效，變更後的下一筆寫入就會立刻套用新的設定來編碼和寫檔。 最後當然，這些函式可能在程式的任何地方、任何執行緒裡被呼叫， 因此對執行緒的衝突保護也是必須實現的部份，並且本篇的重點也就在這上面。

解說完了這個 Logger 模組的功能後，現在讓我們來看看這個模組的程式碼。 首先先來看看 Logger 的資料結構：

struct Logger
{
    Mutex conf_mutex;   // 用來保護 name 和 mode 的互斥子
    string name;
    int mode;

    Mutex file_mutex;   // 用來保護 file 的互斥子
    File file;
}

Logger 資料結構裡面最核心的就只有 3 個東西， 一個真正用來寫檔案的檔案物件 file， 可能是 C 語言裡面的 FILE*，或者 C++ 裡面的 std::fstream，或其它； 另兩個則是記錄當前寫檔檔案名稱的 name，以及當下所使用的訊息編碼方式 mode； 至於剩下兩個則是用來在多緒使用環境下做衝突保護的互斥子，想必對於本系列讀者來說應該已經很熟悉了。

接下來看看用來給使用這呼叫並將資訊給寫入檔案的 WriteLogger() 函式：

void WriteLogger(Logger &data, Record rec)
{
    data.file_mutex.Lock();

    // 如果不是已開檔狀態的話就在這裡開檔
    if(!data.file.IsOpened())
    {
        data.conf_mutex.Lock();
        data.file.Open(data.name);
        data.conf_mutex.Unlock();
    }

    // 將傳入的資料以某種方式編碼成文字並寫入檔案
    string msg = rec.Encode(data.mode);
    data.file.Write(msg);

    data.file_mutex.Unlock();
}

在通常的情況下，這函式一進來就會上鎖 file_mutex 互斥子以保護接下來要操作的 file 物件， 然後將函式傳入的訊息編碼程文字，然後將文字寫入檔案，解鎖互斥子並離開，一氣呵成。 不過偶有時候函式一進來會發現其實還沒開檔， 這可能是因為這是程式執行以來第一次呼叫這函式，也有可能是因為剛才被修改了配置而被關了檔。 然而不論何種原因，這裡如果發現檔案未開的話，那就把它打開，這樣後續才能正常寫檔。 而為了避免在開檔的過程當中正好碰上其它人正在修改設定， 讓我們可能剛剛好拿到才被改到一半的檔名，從而造成後續的錯誤， 因此在開檔的過程中需要上鎖用來保護配置相關變數的 conf_mutex 互斥子。 至於我們在編碼文字的時候所取用的那個 mode 變數則不需要上鎖保護， 原因如前篇讀寫鎖所解釋， 我們並不需要擔心 mode 被改到一半被我們讀取的問題。

接下來看最後一個函式，就是用來讓使用者中途變更 Logger 配置的 ReloadLogger() 函式：

void ReloadLogger(Logger &data, string name, int mode)
{
    data.conf_mutex.Lock();

    // 對於能直接簡單覆寫的數值就直接覆寫
    data.mode = mode;

    // 檔名的變更就不是只簡單複寫就完事了。
    // 如果原來的檔案物件已經處於開啟狀態的話，
    // 就需要關閉再重開，才能讓後續寫入的資料被寫到新檔案去。
    if( data.name != name )
    {
        data.name = name;

        data.file_mutex.Lock();

        if(data.file.IsOpened())
            data.file.Close();

        data.file_mutex.Unlock();
    }

    data.conf_mutex.Unlock();
}

作為設計用來修改配置的函式，一進來就上鎖了 conf_mutex 互斥子，合情合理。 既然互斥子上鎖了，那接下來自然就是直接修改用來記錄配置的那些變數了。 編碼代號的部份無需多加擔憂，只要變數直接覆寫就好，但是檔案名稱的變更就不一樣了。 直接覆蓋檔名變數的話，如果檔案物件已經開啟， 那後續呼叫 WriteLogger() 時資料依然會寫到舊檔案去，而不是寫到新檔案。 因此當檔名需要更動的時候，這裡就順手將檔案物件給關了， 這樣後面再呼叫 WriteLogger() 的時候自然就會用新的檔名重新開檔一次； 而當然，在做這個關檔操作的時候需要上鎖 file_mutex 互斥子，以免同時剛好就遇到有其他人正在寫檔。

死鎖問題

介紹完這個範例程式之後，不知道有沒有眼尖的讀者已經發現問題？ 範例程式裡使用了兩個互斥子來分別保護 Logger 內的各變數， 因此 Logger 的函式在多緒隨意呼叫的情況下都不會產生資料衝突的問題； 但是在一個相當湊巧的機會下，程式卡死了！

當有人呼叫 ReloadLogger() 變更配置參數，並且需要變更存檔的檔名， 於是就如同我們所預期的那樣，函式會走到要上鎖 file_mutex 的那一步。 然而不巧，此時正好有另一條執行緒正好呼叫了 WriteLogger() 要寫檔， 所以 file_mutex 一時被它給佔用了，得等。 一般來說這並不是個問題，因為等它寫完檔後自然就會釋放 file_mutex 互斥子； 然而這次不一樣，這次的檔案物件已經是處在關閉的狀態！

可能因為這剛好是程式啟動之後第一次呼叫 WriteLogger()， 也可能是自從上次呼叫 ReloadLogger() 而關檔過後到現在正好沒有人呼叫 WriteLogger() 來寫檔， 於是檔案物件一直都還是處於關閉的狀態。 然而無論如何，現在 ReloadLogger() 正在等待上鎖 file_mutex 互斥子， 而 WriteLogger() 則剛好正在等待上鎖 conf_mutex 互斥子； 然而 conf_mutex 已經被 ReloadLogger() 給鎖定了， 所以除非等到 ReloadLogger() 結束離開，否則 WriteLogger() 必須得等在那。 那麼 ReloadLogger() 是什麼情況呢？ ReloadLogger() 也在等待一個已經被 WriteLogger() 給佔住的 file_mutex 互斥子。 這下可好了，兩人都在等待一個被對方押著的互斥子， 並且雙方都已經卡在那裡等待了，誰也不可能有機會釋放自己持有的互斥鎖。 於是兩條執行緒就這樣互相等到天荒地老永遠不會回來， 而這就是我們所謂的「死鎖」(Dead Lock)狀態！

當死鎖發生，這兩個執行緒就卡死在那裡永遠不可能再前進一步。 然後這時也許可能又有第三條執行緒呼叫了一個簡單的函式，比如說可能是一個簡單的用來取得當前檔案名稱的函式：

string GetLoggerName(Logger &data)
{
    data.conf_mutex.Lock();
    string name = data.name;
    data.conf_mutex.Unlock();

    return name;
}

如此簡單的一個函式，也不需要上鎖兩個互斥子，只需要在取得檔名的時候暫時鎖上 conf_mutex 就好了， 然而 conf_mutex 卻已經被僵持的兩個執行緒給佔住永不釋放。 得，這呼叫 GetLoggerName() 的第三個執行緒也跟著卡死了，死鎖問題於是擴大！

為什麼需要多鎖？

導致死鎖問題發生的根本原因來自於使用了多個互斥子。 因為需要同時鎖定兩個以上的互斥子， 這才給予「雙方同時佔住一個鎖並要求等待被對方佔住的鎖」這樣的情況的發生機會； 而如果我們只使用一個互斥子，自然就不會產生這種互相佔鎖的問題。 然而進一步我們就要問，為什麼會需要使用多個互斥子呢？只使用一個互斥子有什麼問題嗎？ 回顧上面的範例，Logger 內使用了 conf_mutex 和 file_mutex 兩個互斥子， 而如果我們改為只使用一個互斥子，遇到什麼需要的情況就鎖定這個互斥子就好， 那麼死鎖的問題就迎刃而解！ 然而，採用多個互斥子所為何事呢？

通常使用多個互斥子的目的是為了提升性能。 同樣以前面範例為例，若只使用一個互斥子， 那麼無論是 WriteLogger() 還是 ReloadLogger() 的平均等待時間都將會延長。 當呼叫 ReloadLogger() 的時候，可能只是單純改個編碼選項而已， 然而如果正好碰上 WriteLogger() 正在工作的話，就會需要等待它完成才能成功上鎖互斥子； 同樣當呼叫 WriteLogger() 的時候正好碰上 ReloadLogger() 正在修改設定的話， 也會需要先等待它完成，即便可能兩個函式需要操作的物件並不重疊卻仍然需要等待。 那麼至此這個 Logger 之所以要設計使用兩個互斥子的目的就浮現出來了。 假設在實際的使用情境中，大部份的 WriteLogger() 呼叫其實可能並不會碰上需要重開檔案的機會， 而大部份的 ReloadLogger() 呼叫也多半僅僅只是改變編碼選項而已， 那麼把兩種資源分開來使用兩個互斥子來分別做保護的話，就可以讓兩個函式僅僅只鎖定其中一個互斥子就好。 如此這兩個函式的運作就不會受到彼此的影響，無需要去等待和鎖定那些保護著自己其實並不需要的資源的互斥子。 這樣一來，兩個函式在大部份的情況下都能夠順暢的各自工作而不需不必要的卡來卡去。 只有在少部份的情況下才會真正需要操作使用更多的受保護資源， 例如在本例中就是像在呼叫 ReloadLogger() 修改檔名時正好碰上 WriteLogger() 也正在寫檔的情況， 這時才會真的需要同時鎖上兩個互斥子； 只不過這只是預期中的少數需要消耗比較多等待時間的時機，而對於平均大部份情況來說是不受影響的。

這就是為什麼在實際的程式設計中常常總是免不了需要使用多個互斥子的關係， 主要就是為了減少不必要的鎖定等待以提升整體性能。 而當然，隨著互斥子的使用數量增加，也就給予死鎖問題能夠產生的前置條件。

鎖定順序

在了解採用多互斥子的目的之後，想必已經明白將多個互斥鎖合併為一個雖然確實可以避免問題，但並不實際。 在現實的程式設計裡，主要的解決方案是採用統一的鎖定順序來避免死鎖的發生。

死鎖情況能夠發生的條件就是兩個(或以上)執行緒分別佔住了對方需要的互斥子。 比如兩條執行緒都需要鎖定 A、B 兩個互斥子， 第一條執行緒先鎖定 A 再鎖定 B，而第二條執行緒則先鎖定 B 再鎖定 A， 那麼恭喜，這兩條執行緒總會有機會能卡死在一起！ 那如果調整一下鎖定的順序呢？ 兩條執行緒都需要鎖定 A、B 兩個互斥子，並且我們讓它們都先鎖定 A 再鎖定 B， 你看這樣死鎖是不是就沒有機會發生了？ 這就是通常解決死鎖問題的方法。

理論上統一了互斥子的鎖定順序就可以解決問題，然而實際落實到程式設計仍有許多需要參酌考量的因素。 例如以本篇的範例程式來說，如果我們規定必需要遵循的鎖定順序是先 conf_mutex 再 file_mutex， 那麼 WriteLogger() 函式就需要修改為像下面這樣 (至於 ReloadLogger() 則不需要更動)：

void WriteLogger(Logger &data, Record rec)
{
    // 雖然只有在檔案物件未開啟的情況下才需要鎖定這個互斥子，
    // 但是因為要求的鎖定順序的關係，
    // 因此不論後面需要不需要，
    // 這裡都要先鎖定 conf_mutex 互斥子。
    data.conf_mutex.Lock();

    // 作為一個設計用來寫檔的函式，
    // 本來就需要鎖定 file_mutex 互斥子。
    data.file_mutex.Lock();

    if(!data.file.IsOpened())
        data.file.Open(data.name);

    // 到這裡確定後面不再需要 conf_mutex 互斥子了，
    // 於是先解除對它的鎖定，
    // 這樣至少能在下面寫檔的時候不讓 ReloadLogger() 卡住。
    data.conf_mutex.Unlock();

    string msg = rec.Encode(data.mode);
    data.file.Write(msg);

    data.file_mutex.Unlock();
}

你看這些解決方案都是有代價的！ 統一互斥子的鎖定順序雖然避免了死鎖問題， 但也讓 WriteLogger() 函式每次呼叫進來都要鎖定 conf_mutex 互斥子， 而原先是只有在少數需要的時候才會去鎖定 conf_mutex 互斥子。 因此這項修改的代價就是讓每次 WriteLogger() 的呼叫多出了可能的額外等待。

那麼如果換個鎖定順序呢？ 這次我們改成規定鎖定順序是先 file_mutex 再 conf_mutex。 在此方案下，原來的 WriteLogger() 就不需要修改， 而是 ReloadLogger() 需要修改成像下面這樣：

void ReloadLogger(Logger &data, string name, int mode)
{
    // 本來後面不一定會需要鎖定 file_mutex 互斥子，
    // 但是後面有需要再鎖定的話就沒法符合鎖定順序的要求，
    // 因此只要後面可能有需要，就要在這裡先行鎖定。
    data.file_mutex.Lock();

    // 作為一個設計用來變更設定配置的函式，
    // 本來就需要鎖定 conf_mutex 互斥子。
    data.conf_mutex.Lock();

    data.mode = mode;

    if( data.name != name )
    {
        data.name = name;

        if(data.file.IsOpened())
            data.file.Close();
    }

    data.conf_mutex.Unlock();
    data.file_mutex.Unlock();
}

採用這個鎖定順序下，WriteLogger() 的效能不受影響了， 但是換成每次的 ReloadLogger() 呼叫無論實際需要不需要都得去鎖定 file_mutex， 使得 ReloadLogger() 本身因為可能需要的額外等待而導致執行耗時變長。

於是接下來就會進入衡量利弊的環節。 規範統一的互斥子鎖定順序可以避免死鎖問題， 但是要統一使用何種鎖定順序則可能會影響程式最終在不同情況下的表現， 而其中的得失取捨就是設計者們需要針對各自的實際條件去考量計劃的問題。 以本篇的 Logger 範例來看， 我預期 WriteLogger() 無論是呼叫的數量還是頻率都會遠高於 ReloadLogger()， 因此採用先 file_mutex 再 conf_mutex 的鎖定順序總體來看會比較有利， 其核心就是以 ReloadLogger() 的性能犧牲去保全 WriteLogger() 的性能。

結論

本篇介紹了多緒設計裡所不樂見的死鎖問題與它的發生原因， 並解釋了使用多個互斥子來分別保護不同組別的資源是為了可以減少不必要的鎖定機會以提升效能。 為了避免死鎖問題，當需要同時鎖定多個互斥子時需要約定並遵守一致的鎖定順序， 這在解決死鎖問題發生機會的同時也會導致某些情況下的程式效能犧牲， 而這部份需要程式設計者針對各自的實際設計與使用情況去做考量斟酌。

上一篇：「執行緒同步 8：讀寫鎖」
下一篇：「執行緒同步 10：輪詢」