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

como abrir un candado pequeño sin llave y sin romperlo

Question

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

Quiero el siguiente comportamiento:

• Las llamadas simultáneas a handleRequest(key) se serializan cuando tienen el mismo valor para la key .
• La serialización global se minimiza.

El cuerpo de handleRequest podría verse así:

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

Pregunta: ¿Cómo implementaría KeyLock para obtener el comportamiento requerido?

Una implementación ingenua podría comenzar 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, y la creación de un objeto de Lock por separado para cada solicitud. Si la contención es alta entre las llamadas a handleRequest , eso podría no ser un problema, pero podría imponer una gran sobrecarga si la contención es baja.

Answer 1

Dependerá de la plataforma, pero las dos técnicas que probaría serían:

• Use objetos nombrados mutex / synchronization, donde object name = Key
• Use 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), esto fallará y tendrá que sondear para volver a intentarlo

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

Answer 2

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

• En handleRequest , crea una Callback que hace el trabajo real.
• Cree una multimap<string, Callback*> global_key_map , protegida por un mutex.
• Si un hilo ve que la key ya se está procesando, agrega su Callback* al global_key_map 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 estarían esperando un bloqueo de teclas, pero aparte de eso, es prácticamente lo mismo que la solución ingenua que publiqué en la pregunta.

Sin embargo, podría combinarse con las respuestas dadas por Mike B y Constantin.

Answer 3

Podrías hacer algo similar a lo que tienes en tu pregunta, pero en lugar de un único global_key_map tienes varios (probablemente en una matriz o vector): el que se usa está determinado por una función hash simple en la cadena.

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

Este es un patrón que a menudo se usa 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 4

Tal vez un std::map<std::string, MutexType> sea ​​lo que desee, donde MutexType es el tipo de 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 5

Aumentar la granularidad y bloquear rangos de claves completos

Esta es una variación de la respuesta de Mike B, donde en lugar de tener varios mapas de bloqueo de fluidos tiene una única matriz fija de bloqueos que se aplican a rangos de teclas en lugar de teclas individuales.

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