程式設計面試：實作一個執行緒安全的讀寫鎖

題干與適用場景

請實作一個執行緒安全的讀寫鎖：多個讀者可以並行持有，寫者必須獨占；並說明等待策略、釋放後的喚醒規則、是否支援重入，以及如何避免寫者長期飢餓。可以使用互斥量與條件變數，但不能直接呼叫現成的讀寫鎖。

這題適合後端、基礎設施與並行程式設計職缺，考察同步原語的正確性與取捨，不依賴特定語言。

面試官考察點

• 能否先定義狀態不變量：活躍寫者最多一個，寫者存在時活躍讀者為零。
• 能否把「公平」轉成可執行的排隊規則，而非口頭承諾。
• 能否處理虛假喚醒、例外路徑、遞迴加鎖與讀轉寫死鎖。
• 能否給出複雜度、測試情境，以及在生產環境重用標準庫的邊界。

回答前需要釐清的問題

先確認是否需要可中斷或逾時取得、同一執行緒重入、讀鎖升級為寫鎖，以及公平性是嚴格 FIFO 還是只保證等待中的寫者最終取得機會。若題目沒有指定，建議實作「寫者優先、不可重入、不可升級」的最小版本並說明介面邊界。

30 秒回答框架

先說狀態：activeReaders、activeWriter、waitingWriters。讀鎖在沒有寫者且沒有等待寫者時進入；寫鎖在沒有讀者和寫者時進入。所有狀態都在同一互斥量下修改，釋放時依策略喚醒寫者或一批讀者。等待使用 while 迴圈重新檢查條件，讀轉寫則使用明確升級協定或直接禁止。

分步驟深入解答

狀態與不變量

activeWriter 是布林值，activeReaders 是非負計數，waitingWriters 記錄排隊寫者。核心不變量是：activeWriter == true 時 activeReaders == 0；寫者進入前兩者都必須為空。等待計數只用於策略，不代表已持鎖。

取得與釋放規則

讀者等待 !activeWriter && waitingWriters == 0，寫者等待 !activeWriter && activeReaders == 0。每次條件變數返回都重新檢查條件，以避免虛假喚醒。寫者釋放後優先喚醒一個寫者；沒有寫者等待時再廣播給讀者。最後一個讀者釋放時喚醒寫者。

~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()

writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()

writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~

公平性與吞吐量

Oracle 文件指出，非公平模式可能長期推遲某一類執行緒，公平模式按近似到達順序競爭，但吞吐量通常較低。面試中應區分「避免飢餓」與「嚴格 FIFO」。

高品質示範回答

我會先實作不可重入、寫者優先的版本。所有計數由一個互斥量保護，讀者只有在沒有寫者和排隊寫者時增加計數，寫者必須等到兩個計數都為空。條件變數返回後用 while 重新檢查。釋放時若有寫者就 signal 一個寫者，否則廣播讀者。這能保持互斥不變量，也讓持續到達的讀請求不能無限插隊。

我會明確不支援讀轉寫升級，因為持讀鎖的執行緒等待寫鎖會阻塞其他讀者釋放，容易形成死鎖；升級應由呼叫方先釋放讀鎖再重新競爭，或另設帶佇列的升級協定。若需要中斷、逾時、重入或嚴格公平，我會直接重用平台標準庫並測試其文件定義，而不在業務程式碼複製不完整實作。

常見錯誤

• 用 if 取代 while，虛假喚醒後會繞過保護條件。
• 只判斷活躍讀者，不統計等待寫者，造成寫者飢餓。
• 寫者釋放時只喚醒一個讀者，造成不必要的讀並行損失；或無條件廣播造成驚群。
• 允許讀鎖升級卻沒有升級佇列，兩個讀者會互相等待。
• 把 tryLock 當作公平保證。Oracle 文件明確說明非阻塞 tryLock 可以插隊。

追問及應對

如何驗證不變量沒有被破壞？

在測試中維護原子快照：進入寫臨界區時斷言讀者數為零，進入讀臨界區時斷言沒有寫者；隨機產生讀寫執行緒並持續執行，失敗時記錄執行緒事件序列。

如何測試寫者飢餓？

持續產生讀請求，同時讓一個寫者等待；記錄寫者從排隊到取得鎖的時間和最大等待次數。測試目標是最終取得機會，而非承諾固定毫秒數。

為什麼不用一個普通互斥鎖？

普通互斥鎖實作更簡單、延遲更穩定；讀寫鎖只有在讀操作占絕大多數且讀臨界區足夠長時才可能提高並行。應以基準測試而非直覺決定。

能否支援重入？

需要記錄寫者執行緒識別與持有次數，並為每個執行緒記錄讀持有次數；這會改變升級和釋放規則。若題目未要求，明確禁止重入可降低狀態空間。

POSIX 介面有什麼提醒？

POSIX 將讀鎖與寫鎖取得拆成獨立介面，並規定失敗回傳值；實作時仍須遵守平台對優先級和遞迴行為的限制，不能把自訂策略誤稱為標準保證。

什麼時候應停止手寫？

當需求涉及中斷、逾時、診斷、重入或跨平台語義時，優先使用 Java ReentrantReadWriteLock、POSIX pthreadrwlock* 等經驗證的實作，並把公平性選項寫進評審記錄。