Como faço para usar uma seqüência arbitrária como um bloqueio em C ++?

Question

Vamos dizer que eu tenho um programa multithreaded C ++ que lida com solicitações na forma de uma função chamada para handleRequest(string key). Cada chamada para handleRequest ocorre em um segmento separado, e há um número arbitrariamente grande de possíveis valores para key.

Eu quero o seguinte comportamento:

• As chamadas simultâneas para handleRequest(key) são serializados quando eles têm o mesmo valor para key.
• serialização global é minimizada.

O corpo de handleRequest pode ter esta aparência:

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

Pergunta:? Como eu poderia implementar KeyLock para obter o comportamento necessário

Uma implementação simples pode começar assim:

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

... mas que requer um bloqueio global no início e no final de cada solicitação, e a criação de um objeto Lock separado para cada solicitação. Se discórdia é alta entre chamadas para handleRequest, que pode não ser um problema, mas poderia impor um monte de sobrecarga se a contenção é baixa.

Answer 1

Você poderia fazer algo parecido com o que você tem na sua pergunta, mas em vez de um único global_key_map ter vários (provavelmente em uma matriz ou vector) -. Qual é usado é determinado por alguns função hash simples na corda

Dessa forma, em vez de um único bloqueio global, você espalhar que ao longo de vários queridos independentes.

Este é um padrão que é frequentemente usado em alocadores de memória (não sei se o padrão tem um nome - deve). Quando uma solicitação chega, algo que determina que congregam a alocação virá de (geralmente o tamanho do pedido, mas outros parâmetros podem levar em consideração também), então somente que as necessidades de piscina a ser bloqueado. Se um pedido de atribuição vem de outro segmento que irá utilizar um conjunto diferente, não há contenção de bloqueio.

Answer 2

Vai depender da plataforma, mas as duas técnicas que eu tentaria seria:

• Use nomeado mutex / sincronização objetos, onde o nome do objeto = Key
• Use sistema de arquivos baseado em bloqueio, onde você tentar criar um não-compartilháveis arquivo temporário com o nome da chave. Se já existir (= já bloqueado) isto irá falhar e você vai tem que pesquisa a repetição

As duas técnicas dependerá do detalhe de seu sistema operacional. Experimentar e ver o que funciona. .

Answer 3

Talvez uma std::map<std::string, MutexType> seria o que você quer, onde MutexType é o tipo de exclusão mútua que quiser. Você provavelmente terá de envolver os acessos ao mapa em outro mutex, a fim de garantir que nenhum outro segmento está inserindo ao mesmo tempo (e lembre-se de executar a verificação novamente após o mutex é bloqueado para garantir que outro segmento não adicionou o chave, enquanto espera na mutex!).

O mesmo princípio pode aplicar-se a qualquer outro método de sincronização, tais como uma secção crítica.

Answer 4

granularidade Raise e bloquear todo-chave faixas

Esta é uma variação sobre a resposta de Mike B, onde em vez de ter vários bloqueio fluido mapeia você tem uma única matriz fixa de fechaduras que se aplicam a chave varia em vez de chaves individuais.

exemplo simplificado: criar matriz de 256 bloqueios no arranque, em seguida, utilizar primeiro byte de chave para determinar o índice de bloqueio para ser adquirido (isto é, todas as chaves que começam com 'k' vai ser guardada por locks[107])

.

Para sustentar óptimo rendimento você deve analisar a distribuição de chaves e taxa de contenção. Os benefícios desta abordagem são alocações dinâmicas de zero e limpeza simples; você também evitar bloqueio de duas etapas. A desvantagem é potenciais picos de contenção, se a distribuição de chaves torna-se tempo ao longo distorcida.

Answer 5

Depois de pensar nisso, uma outra abordagem poderia ser algo como isto:

• Em handleRequest, criar um Callback que faz o trabalho real.
• Criar um multimap<string, Callback*> global_key_map, protegido por um mutex.
• Se um segmento vê que key já está sendo processada, ele adiciona a sua Callback* ao global_key_map e retorna.
• Caso contrário, ele chama seu retorno imediato, e depois chama os retornos de chamada que apareceram nesse meio tempo para a mesma chave.

Implementado algo como isto:

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

Isto tem a vantagem de libertar-se tópicos que seriam esperando por uma fechadura com chave, mas para além de que é praticamente o mesmo que a solução ingênua eu postei na questão.

Pode ser combinado com as respostas dadas por Mike B e Constantin, no entanto.

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