如何在C++中使用任意字符串作爲鎖？

Question

假設我有一個多線程的C++程序，它以函數調用handleRequest(string key)的形式處理請求。對handleRequest的每次調用都發生在一個單獨的線程中，並且key有任意數量的可能值。

我想以下行爲：

• 到handleRequest(key)同時呼叫被序列化時，他們有key相同的值。
• 全局序列化被最小化。

的handleRequest的身體可能是這樣的：

void handleRequest(string key) { 
    KeyLock lock(key); 
    // Handle the request. 
} 

問：我將如何實現KeyLock以獲得必要的行爲？

一個幼稚的做法是這樣開始：

KeyLock::KeyLock(string key) { 
    global_lock->Lock(); 
    internal_lock_ = global_key_map[key]; 
    if (internal_lock_ == NULL) { 
     internal_lock_ = new Lock(); 
     global_key_map[key] = internal_lock_; 
    } 
    global_lock->Unlock(); 
    internal_lock_->Lock(); 
} 

KeyLock::~KeyLock() { 
    internal_lock_->Unlock(); 
    // Remove internal_lock_ from global_key_map iff no other threads are waiting for it. 
} 

...但是這需要在開始一個全局鎖和每個請求的結束，和一個單獨的Lock對象爲每個請求的創建。如果在調用handleRequest之間的爭用較高，這可能不成問題，但如果爭用率較低，則可能會產生大量開銷。

Answer 1

你可以做類似於你的問題的東西，而不是一個global_key_map有幾個（可能在一個數組或向量中） - 使用哪一個是由字符串上的一些簡單的散列函數決定的。

這種方式，而不是一個單一的全局鎖，你分散了幾個獨立的。

這是一種經常用於內存分配器的模式（我不知道該模式是否有名稱 - 它應該）。當請求進入時，某些東西決定了分配來自哪個池（通常是請求的大小，但其他參數也可以考慮），那麼只有該池需要被鎖定。如果分配請求來自另一個使用不同池的線程，則不存在鎖定爭用。

Answer 2

這將依賴於平臺，但兩種技術，我會嘗試將是：

• 使用命名互斥/同步 對象，其中對象名=鍵
• 使用基於文件系統的鎖定，其中您嘗試使用密鑰名稱創建一個不共享的臨時文件 。如果它已經存在（=已 鎖定），這將失敗，你會 必須輪詢重試

這兩種技術都將取決於你的操作系統的細節。試驗一下，看看哪些工作。 。

Answer 3

也許std::map<std::string, MutexType>將是你想要的，其中MutexType是你想要的互斥體的類型。您可能必須將訪問映射到另一個互斥體中，以確保沒有其他線程同時插入（並且記住在互斥鎖被鎖定後再次執行檢查以確保另一個線程不會添加鍵在等待互斥體！）。

相同的原理可以應用於任何其他同步方法，例如臨界區。

Answer 4

擡起粒度和鎖定整個鍵範圍

這是麥克B的答案，而不是在具有幾個流體鎖地圖，你都上了鎖的單個固定陣列適用於關鍵的範圍，而不是變化的單個鍵。

簡化示例：在啓動時創建256個鎖的數組，然後使用密鑰的第一個字節確定要獲取的鎖的索引（即所有以'k'開頭的密鑰將由locks[107]保護）。

要維持最佳吞吐量，您應該分析密鑰和爭用率的分佈。這種方法的好處是零動態分配和簡單的清理;你也避免了兩步鎖定。如果密鑰分配隨着時間的推移而變得不對稱，那麼潛在的爭用高峯就會出現。

Answer 5

考慮這件事之後，另一種方法可能會去是這樣的：

• 在handleRequest，創建一個Callback，做實際工作。
• 創建一個multimap<string, Callback*> global_key_map，由互斥鎖保護。
• 如果一個線程看到key正在處理中，它會將其Callback*添加到global_key_map並返回。
• 否則，它立即調用它的回調函數，然後調用同一個鍵上顯示的回調函數。

實現這樣的事情：

LockAndCall(string key, Callback* callback) { 
    global_lock.Lock(); 
    if (global_key_map.contains(key)) { 
     iterator iter = global_key_map.insert(key, callback); 
     while (true) { 
      global_lock.Unlock(); 
      iter->second->Call(); 
      global_lock.Lock(); 
      global_key_map.erase(iter); 
      iter = global_key_map.find(key); 
      if (iter == global_key_map.end()) { 
       global_lock.Unlock(); 
       return; 
      } 
     } 
    } else { 
     global_key_map.insert(key, callback); 
     global_lock.Unlock(); 
    } 
} 

這有釋放，否則將等待一個按鍵鎖的線程的優勢，但除此之外，這幾乎是一樣的天真的我張貼在問題中。

雖然它可以與Mike B和Constantin給出的答案結合使用。

Answer 6

 /** 
     * StringLock class for string based locking mechanism 
     * e.g. usage 
     *  StringLock strLock; 
     *  strLock.Lock("row1"); 
     *  strLock.UnLock("row1"); 
     */ 
     class StringLock { 
     public: 
      /** 
      * Constructor 
      * Initializes the mutexes 
      */ 
      StringLock() { 
       pthread_mutex_init(&mtxGlobal, NULL); 
      } 
      /** 
      * Lock Function 
      * The thread will return immediately if the string is not locked 
      * The thread will wait if the string is locked until it gets a turn 
      * @param string the string to lock 
      */ 
      void Lock(string lockString) { 
       pthread_mutex_lock(&mtxGlobal); 
       TListIds *listId = NULL; 
       TWaiter *wtr = new TWaiter; 
       wtr->evPtr = NULL; 
       wtr->threadId = pthread_self(); 
       if (lockMap.find(lockString) == lockMap.end()) { 
        listId = new TListIds(); 
        listId->insert(listId->end(), wtr); 
        lockMap[lockString] = listId; 
        pthread_mutex_unlock(&mtxGlobal); 
       } else { 
        wtr->evPtr = new Event(false); 
        listId = lockMap[lockString]; 
        listId->insert(listId->end(), wtr); 
        pthread_mutex_unlock(&mtxGlobal); 
        wtr->evPtr->Wait(); 
       } 
      } 
      /** 
      * UnLock Function 
      * @param string the string to unlock 
      */ 
      void UnLock(string lockString) { 
       pthread_mutex_lock(&mtxGlobal); 
       TListIds *listID = NULL; 
       if (lockMap.find(lockString) != lockMap.end()) { 
        lockMap[lockString]->pop_front(); 
        listID = lockMap[lockString]; 
        if (!(listID->empty())) { 
         TWaiter *wtr = listID->front(); 
         Event *thdEvent = wtr->evPtr; 
         thdEvent->Signal(); 
        } else { 
         lockMap.erase(lockString); 
         delete listID; 
        } 
       } 
       pthread_mutex_unlock(&mtxGlobal); 
      } 
     protected: 
      struct TWaiter { 
       Event *evPtr; 
       long threadId; 
      }; 
      StringLock(StringLock &); 
      void operator=(StringLock&); 
      typedef list TListIds; 
      typedef map TMapLockHolders; 
      typedef map TMapLockWaiters; 
     private: 
      pthread_mutex_t mtxGlobal; 
      TMapLockWaiters lockMap; 
     };