C++線程安全對象緩存的設計選項

我正在編寫C++中的數據緩存模板庫，其中併發讀取可以完成併發寫入，但不能用於同一個密鑰。該模式可以用以下環境來解釋：C++線程安全對象緩存的設計選項

緩存寫入的互斥鎖。
緩存中每個鍵的互斥鎖。

這種方式如果一個線程從緩存中請求一個密鑰並且不存在可以啓動該唯一密鑰的鎖定計算。與此同時，其他線程可以檢索或計算其他鍵的數據，但嘗試訪問第一個鍵的線程會獲得鎖定等待。

的主要限制是：

決不計算同時一個鍵的值。
計算2個不同鍵的值可以同時完成。
數據檢索不能鎖定其他線程從其他鍵檢索數據。

我其他方面的限制，但已經解決是：

固定的（在編譯時已知），最大緩存大小與基於MRU-（最近使用的）抖動。
檢索引用（株連mutexed共享計數）

我不知道用1個互斥體的每個關鍵是要實現這個正確的方式，但我沒有發現任何其他顯着不同的方式。

你知道其他模式來實現這個還是你覺得這是一個合適的解決方案？我不喜歡有大約100個互斥體的想法。（高速緩存大小約爲100個鍵）

來源

2010-01-26 Andrea Cuneo

也許第一句話說明了這一點，但我並不清楚併發限制是否適用於讀取同一對象。換句話說，兩個線程可以同時使用現有的密鑰嗎？ – 2010-01-26 14:05:07

是的，如果已經存在於緩存中，則2個線程應同時讀取相同的密鑰。否則，如果該鍵不存在，則一個線程必須對該鍵進行鎖定，而第二個線程必須等待另一個線程完成計算並將該對象添加到緩存中。在此期間，其他線程被允許從其他鍵讀取。這可以通過緩存的多讀/單寫互斥來完成;當被鎖定寫入時，新的條目將被添加到緩存中。你可以把它看作一個元組。密鑰互斥鎖被鎖定，然後釋放緩存互斥鎖。 – 2010-01-26 15:05:34

你想鎖定，你想等待。因此，某些地方應該有「條件」（類Unix系統上的pthread_cond_t）。

我建議如下：

有一個全局mutex其僅用於在地圖上添加或刪除鍵。
映射將鍵映射到值，其中值是包裝器。每個包裝都包含一個條件並可能包含一個值。該值在設置時發出信號。

當線程希望從緩存中獲取值時，它首先獲取全局互斥鎖。然後它會在地圖：

如果該鍵的包裝，而且包裝包含一個值，那麼線程有其價值，並可以釋放全局互斥鎖。
如果這個鍵有一個包裝，但沒有值，那麼這意味着一些其他線程正忙於計算值。線程然後阻塞條件，當線程完成時被其他線程喚醒。
如果沒有包裝，則線程在地圖中註冊一個新包裝，然後繼續計算值。計算該值時，它會設置該值並指示條件。

在僞代碼，這看起來是這樣的：

 
mutex_t global_mutex 
hashmap_t map 

lock(global_mutex) 
w = map.get(key) 
if (w == NULL) { 
    w = new Wrapper 
    map.put(key, w) 
    unlock(global_mutex) 
    v = compute_value() 
    lock(global_mutex) 
    w.set(v) 
    signal(w.cond) 
    unlock(global_mutex) 
    return v 
} else { 
    v = w.get() 
    while (v == NULL) { 
     unlock-and-wait(global_mutex, w.cond) 
     v = w.get() 
    } 
    unlock(global_mutex) 
    return v 
}

在pthreads而言，lock是pthread_mutex_lock()，unlock是pthread_mutex_unlock()，unlock-and-wait是pthread_cond_wait()和signal是pthread_cond_signal()。 unlock-and-wait原子地釋放互斥並將線程標記爲等待條件;當線程喚醒時，互斥鎖會自動重新獲取。

這意味着每個包裝必須包含一個條件。這體現了您的各種要求：

沒有線程長時間保持互斥（阻塞或計算值）。
當要計算一個值時，只有一個線程執行該操作，其他希望訪問該值的線程只等待它可用。

注意，當一個線程希望得到一個值，並發現一些其他線程已經忙於計算它的線程最終鎖定全局互斥鎖兩次：在開始一次，一旦當值可用。一個更復雜的解決方案，每個包裝一個互斥體，可能會避免第二次鎖定，但除非爭用非常高，否則我懷疑這是值得的。

關於有很多互斥體：互斥體便宜。一個互斥體基本上是一個int，它只不過是用來存儲它的四個左右的RAM字節。當心Windows術語：在Win32中，我稱之爲互斥體的互鎖區域被視爲「互鎖區域」;當調用CreateMutex()時，Win32創建的東西是完全不同的，它可以從幾個不同的進程訪問，並且由於涉及到內核的往返行爲，因此成本更高。請注意，在Java中，每個對象實例都包含一個互斥量，而Java開發人員似乎並不太在這個主題上過分暴躁。

來源

2010-01-26 17:58:12

您可以使用互斥池而不是爲每個資源分配一個互斥量。由於要求讀取，請首先檢查相關插槽。如果它已經有一個互斥標記，則阻塞該互斥量。如果不是，則爲該插槽分配一個互斥信號併發出信號，並將該互斥鎖從池中取出。一旦互斥信號無信號，清除插槽並將互斥鎖返回到池中。

來源

2010-01-26 13:59:28

儘管如此，所有這些仍然是線程安全的。如果兩個線程同時嘗試將一個互斥鎖分配給一個插槽，會發生什麼情況？ :) – jalf 2010-01-26 18:21:13

非常正確。我的回答實際上只是一個指向基本理念的柵欄。與任何多線程應用程序一樣，魔鬼的細節...... – 2010-01-26 18:38:44

實際上這不是一個大問題，我喜歡這個想法。假設我使用多讀取器/單寫入器互斥來訪問緩存，當1個線程想要向緩存中添加一個密鑰，要求獨佔訪問時，添加密鑰，從該池中分配一個互斥鎖並鎖定它釋放緩存互斥並開始計算。我仍然無法確定當沒有人鎖定它時如何將互斥量「返回」到池中。任何想法？ :) – 2010-01-27 10:00:46

一種簡單得多的解決方案就是在整個緩存中使用一個讀寫器鎖。考慮到你知道有最大數量的條目（並且它相對較小），這聽起來像是向緩存添加新密鑰是一種「罕見」事件。一般的邏輯是：

acquire read lock 
search for key 
if found 
    use the key 
else 
    release read lock 
    acquire write lock 
    add key 
    release write lock 
    // acquire the read lock again and use it (probably encapsulate in a method) 
endif

不知道更多關於使用模式，我不能肯定地說這是一個很好的解決方案。但是，這非常簡單，如果使用率主要是讀取，那麼就鎖定而言非常便宜。

來源

2010-01-26 15:50:05

爲什麼我們需要讀鎖？ – Jagannath 2010-01-26 15:56:53

我的假設（可能不正確）是需要某種獨佔訪問才能將新條目添加到緩存中。讀取鎖定（在讀取器/寫入器鎖定上）將在保持寫入鎖定的同時添加新項目時確保安全。 – 2010-01-26 15:58:49

我雖然關於這樣的事情，但不適合我的環境。我有一種預熱階段，其中大部分所需的密鑰都是由各種線程選擇的，以未知的方式或順序（取決於先前的鍵的結果）。密鑰重用一段時間後，另一組計算開始。在計算階段我不能失去並行性;因此不能使用單個寫入互斥鎖。 – 2010-01-26 16:06:42

C++線程安全對象緩存的設計選項

回答

相關問題