¿Cómo uso una cadena arbitraria como un candado en C++?

Question

Digamos que tengo un programa multiproceso de C++ que maneja las solicitudes en forma de una llamada de función al handleRequest(string key). Cada llamada a handleRequest se produce en una secuencia separada, y hay una cantidad arbitrariamente grande de valores posibles para key.

Quiero el siguiente comportamiento:

• llamadas simultáneas a handleRequest(key) son serializado cuando tienen el mismo valor para key.
• La serialización global está minimizada.

El cuerpo de handleRequest podría tener este aspecto:

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

Pregunta: ¿Cómo meKeyLock aplicar para conseguir el comportamiento requerido?

Una implementación ingenua podría empezar así:

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

... pero eso requiere un bloqueo global al principio y al final de cada solicitud, así como la creación de un Lock objeto separado para cada solicitud. Si la contención es alta entre llamadas al handleRequest, eso podría no ser un problema, pero podría imponer una gran sobrecarga si la contención es baja.

Answer 1

Podría hacer algo similar a lo que tiene en su pregunta, pero en lugar de un único global_key_map tiene varios (probablemente en una matriz o vector) - cuál se utiliza está determinado por alguna función hash simple en la cadena.

De esta manera en lugar de un único bloqueo global, extiéndelo sobre varios independientes.

Este es un patrón que se usa a menudo en los asignadores de memoria (no sé si el patrón tiene un nombre, debería). Cuando entra una solicitud, algo determina de qué grupo proviene la asignación (generalmente el tamaño de la solicitud, pero otros parámetros también pueden tener en cuenta), entonces solo ese grupo necesita ser bloqueado. Si una solicitud de asignación proviene de otro hilo que utilizará un conjunto diferente, no hay contención de bloqueo.

Answer 2

Esto dependerá de la plataforma, pero las dos técnicas que me gustaría probar serían:

• Uso llamado mutex/sincronización objetos, en nombre de objeto = Clave
• Usar el bloqueo basado en el sistema de archivos , donde intenta crear un archivo temporal no compartible con el nombre de la clave. Si ya existe (= ya bloqueado) se producirá un error y se le tener que sondear para volver a intentar

Ambas técnicas dependerá de los detalles de su sistema operativo. Experimenta y ve cuál funciona. .

Answer 3

Quizás sea std::map<std::string, MutexType> lo que desea, donde MutexType es del tipo del mutex que desea.Es probable que deba ajustar los accesos al mapa en otro mutex para asegurarse de que no se está insertando ningún otro subproceso al mismo tiempo (y recuerde realizar la comprobación nuevamente después de bloquear el mutex para asegurarse de que otro subproceso no haya agregado el clave mientras espera en el mutex!).

El mismo principio podría aplicarse a cualquier otro método de sincronización, como una sección crítica.

Answer 4

granularidad Levante y bloquee toda llave-rangos

Esta es una variación de la respuesta de Mike B, donde en lugar de tener varios bloqueo de fluido mapas de que una única matriz fija de bloqueos que se aplica a las claves rangos vez de llaves simples.

Ejemplo simplificado: cree una matriz de 256 bloqueos al inicio, luego use el primer byte de clave para determinar el índice de bloqueo que se adquirirá (es decir, todas las claves que comiencen con 'k' estarán protegidas por locks[107]).

Para mantener el rendimiento óptimo, debe analizar la distribución de claves y la tasa de contención. Los beneficios de este enfoque son las asignaciones dinámicas cero y la limpieza simple; también evitas el bloqueo en dos pasos. La desventaja es el potencial de picos de contención si la distribución de claves se sesga con el tiempo.

Answer 5

Después de pensarlo, otro enfoque podría ser algo como esto:

• En handleRequest, cree un Callback que hace el trabajo real.
• Crea un multimap<string, Callback*> global_key_map, protegido por un mutex.
• Si un hilo ve que key ya se está procesando, agrega Callback* al y lo devuelve.
• De lo contrario, llama a su devolución de llamada inmediatamente, y luego llama a las devoluciones de llamada que han aparecido mientras tanto para la misma clave.

Implementado algo como esto:

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

Esto tiene la ventaja de liberar hilos que de otro modo se espera de una cerradura con llave, pero aparte de eso, es más o menos la misma que la solución ingenua publicado en la pregunta.

Sin embargo, podría combinarse con las respuestas dadas por Mike B y 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; 
     };