Come posso usare una stringa arbitraria come blocco in C ++?

Question

Supponiamo che io abbia un programma C ++ multithread che gestisce le richieste sotto forma di una chiamata di funzione a handleRequest(string key). Ogni chiamata a handleRequest viene eseguita in un thread separato e esiste un numero arbitrariamente elevato di valori possibili per key.

Voglio il seguente comportamento:

• Le chiamate simultanee a handleRequest(key) sono serializzate quando hanno lo stesso valore per KeyLock.
• La serializzazione globale è ridotta al minimo.

Il corpo di Lock potrebbe assomigliare a questo:

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

Domanda: come implementerei <=> per ottenere il comportamento richiesto?

Un'implementazione ingenua potrebbe iniziare in questo modo:

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

... ma ciò richiede un blocco globale all'inizio e alla fine di ogni richiesta e la creazione di un oggetto <=> separato per ogni richiesta. Se la contesa è elevata tra le chiamate a <=>, ciò potrebbe non essere un problema, ma potrebbe imporre un sacco di sovraccarico se la contesa è bassa.

Answer 1

Potresti fare qualcosa di simile a quello che hai nella tua domanda, ma invece di una singola global_key_map ne hai diverse (probabilmente in un array o un vettore) - quale viene usato è determinato da una semplice funzione hash sulla stringa.

In questo modo invece di un singolo lucchetto globale, lo spargi su più di uno indipendente.

Questo è uno schema che viene spesso usato negli allocatori di memoria (non so se lo schema abbia un nome - dovrebbe). Quando arriva una richiesta, qualcosa determina da quale pool verrà l'allocazione (di solito la dimensione della richiesta, ma anche altri parametri possono tener conto), quindi solo quel pool deve essere bloccato. Se una richiesta di allocazione arriva da un altro thread che utilizzerà un pool diverso, non c'è contesa di blocco.

Answer 2

Dipenderà dalla piattaforma, ma le due tecniche che proverei sarebbero:

• Utilizza il nome mutex / sincronizzazione oggetti, dove nome oggetto = Chiave
• Usa il blocco basato sul filesystem, dove ti trovi prova a creare un non condivisibile file temporaneo con il nome della chiave. Se esiste già (= già bloccato) questo fallirà e tu eseguire il polling per riprovare

Entrambe le tecniche dipenderanno dai dettagli del tuo sistema operativo. Sperimenta e vedi quali funzionano. .

Answer 3

Forse un std::map<std::string, MutexType> sarebbe quello che vuoi, dove MutexType è il tipo di mutex che desideri. Probabilmente dovrai avvolgere gli accessi alla mappa in un altro mutex per assicurarti che nessun altro thread venga inserito contemporaneamente (e ricorda di eseguire nuovamente il controllo dopo che il mutex è bloccato per assicurarti che un altro thread non abbia aggiunto il chiave durante l'attesa sul mutex!).

Lo stesso principio potrebbe applicarsi a qualsiasi altro metodo di sincronizzazione, come una sezione critica.

Answer 4

Aumenta la granularità e blocca intere gamme di tasti

Questa è una variazione sulla risposta di Mike B, dove invece di avere diverse mappe di blocco dei fluidi hai un singolo array fisso di blocchi che si applicano a intervalli di chiavi anziché a singole chiavi.

Esempio semplificato: creare una matrice di 256 blocchi all'avvio, quindi utilizzare il primo byte di chiave per determinare l'indice di blocco da acquisire (ovvero tutte le chiavi che iniziano con 'k' saranno protette da locks[107]).

Per sostenere un throughput ottimale è necessario analizzare la distribuzione delle chiavi e il tasso di contesa. I vantaggi di questo approccio sono zero allocazioni dinamiche e pulizia semplice; si evita anche il blocco in due passaggi. Il rovescio della medaglia sono potenziali picchi di contese se la distribuzione delle chiavi si inclina nel tempo.

Answer 5

Dopo averci pensato, un altro approccio potrebbe andare in questo modo:

• In handleRequest, crea un Callback che fa il vero lavoro.
• Crea un multimap<string, Callback*> global_key_map, protetto da un mutex.
• Se un thread vede che key è già in fase di elaborazione, aggiunge il suo Callback* al global_key_map e ritorna.
• Altrimenti, chiama immediatamente il callback, quindi chiama i callback che sono stati visualizzati nel frattempo per lo stesso tasto.

Implementato qualcosa del genere:

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

Questo ha il vantaggio di liberare thread che altrimenti sarebbero in attesa di un blocco dei tasti, ma a parte questo è praticamente lo stesso della soluzione ingenua che ho pubblicato nella domanda.

Potrebbe essere combinato con le risposte fornite da Mike B e 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;
      };