Wie verwende ich eine beliebige Zeichenfolge als Sperre in C++?

Question

Angenommen, ich habe ein Multithread-C++ - Programm, das Anfragen in Form eines Funktionsaufrufs an handleRequest(string key) behandelt. Jeder Aufruf an handleRequest erfolgt in einem separaten Thread, und es gibt eine beliebig große Anzahl möglicher Werte für key.

Ich möchte folgendes Verhalten:

• gleichzeitige Anrufe handleRequest(key) serialisiert, wenn sie den gleichen Wert für key haben.
• Die globale Serialisierung ist minimiert.

Der Körper handleRequest könnte wie folgt aussehen:

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

Frage: Wie würde ich KeyLock implementieren das erforderliche Verhalten zu bekommen?

könnte eine naive Implementierung wie folgt beginnen:

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. 
} 

... aber das erfordert eine globale Sperre am Anfang und am Ende jeder Anfrage, und die Schaffung eines separaten Lock Objekt für jede Anforderung. Wenn der Konflikt zwischen den Aufrufen an handleRequest hoch ist, ist das möglicherweise kein Problem, aber es kann viel Overhead verursachen, wenn die Konkurrenz gering ist.

Answer 1

Sie könnten etwas ähnliches wie in Ihrer Frage tun, aber statt einer einzigen global_key_map haben Sie mehrere (wahrscheinlich in einem Array oder Vektor) - welche verwendet wird, wird durch eine einfache Hash-Funktion in der Zeichenfolge bestimmt.

Auf diese Weise verbreiten Sie das anstelle einer einzelnen globalen Sperre über mehrere unabhängige.

Dies ist ein Muster, das häufig in Speicherzuweisungen verwendet wird (ich weiß nicht, ob das Muster einen Namen hat - es sollte). Wenn eine Anfrage eingeht, bestimmt etwas, aus welchem ​​Pool die Zuweisung stammt (normalerweise die Größe der Anfrage, aber auch andere Parameter können berücksichtigt werden), dann muss nur dieser Pool gesperrt werden. Wenn eine Zuordnungsanforderung von einem anderen Thread eingeht, der einen anderen Pool verwendet, gibt es keine Sperrkonflikte.

Answer 2

Es ist auf der Plattform abhängen, aber die beiden Techniken, die ich versuchen würde wäre:

• Verwendung benanntes Mutex/Synchronisation Objekte, in dem Objekt name = Key
• Verwenden-Dateisystem-basierte Sperr , wo Sie versuchen, eine nicht shareable temporäre Datei mit dem Schlüsselnamen zu erstellen. Wenn es bereits vorhanden ist (= bereits gesperrt), wird dies fehlschlagen, und Sie werden haben abzufragen

Beide Techniken wiederholen auf dem Detail Ihres OS ab. Experimentieren Sie und sehen Sie, was funktioniert. .

Answer 3

Vielleicht wäre ein std::map<std::string, MutexType> was Sie wollen, wo MutexType ist der Typ des Mutex Sie wollen.Wahrscheinlich müssen Sie die Zugriffe auf die Map in einem anderen Mutex umbrechen, um sicherzustellen, dass kein anderer Thread zur gleichen Zeit eingefügt wird (und denken Sie daran, die Überprüfung erneut durchzuführen, nachdem der Mutex gesperrt wurde, um sicherzustellen, dass kein anderer Thread die hinzugefügt hat während Sie auf den Mutex warten!).

Das gleiche Prinzip könnte auch auf andere Synchronisierungsmethoden angewendet werden, z. B. auf einen kritischen Abschnitt.

Answer 4

Raise Granularität und sperren gesamte Schlüsselbereiche

Dies ist eine Variation auf Mike B Antwort, wo anstelle von mehrere Flüssigkeitssperre mit Karten, die Sie eine einzige feste Anordnung von Schlössern, die stattdessen auf Schlüsselbereiche gelten von einzelnen Schlüsseln.

Vereinfachtes Beispiel: Beim Start ein Array mit 256 Sperren erstellen und dann das erste Byte des Schlüssels verwenden, um den zu erfassenden Index zu ermitteln (d. H. Alle mit 'k' beginnenden Schlüssel werden von locks[107] geschützt).

Um den optimalen Durchsatz aufrechtzuerhalten, sollten Sie die Verteilung der Schlüssel und die Konkurrenzrate analysieren. Die Vorteile dieses Ansatzes sind null dynamische Zuordnungen und einfache Bereinigung; Sie vermeiden auch eine zweistufige Verriegelung. Der Nachteil sind mögliche Konkurrenzspitzen, wenn die Schlüsselverteilung im Zeitverlauf verzerrt wird.

Answer 5

Nachdem darüber nachzudenken, könnte ein anderer Ansatz etwas so gehen:

• In handleRequest, eine Callback erstellen, die die eigentliche Arbeit erledigt.
• Erstellen Sie eine multimap<string, Callback*> global_key_map, geschützt durch einen Mutex.
• Wenn ein Thread sieht, dass key bereits verarbeitet wird, fügt er Callback* zu global_key_map hinzu und kehrt zurück.
• Andernfalls ruft es seinen Callback sofort auf und ruft dann die Callbacks auf, die in der Zwischenzeit für denselben Schlüssel angezeigt wurden.

Umgesetzt etwas wie folgt aus:

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(); 
    } 
} 

Dies hat den Vorteil Fäden zu befreien, die sonst für eine Tastensperre warten würde, aber abgesehen davon, dass es so ziemlich das gleiche wie die naive Lösung I in der Frage gepostet.

Es könnte aber mit den Antworten von Mike B und Constantin kombiniert werden.

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; 
     };