Как я могу использовать произвольную строку в качестве блокировки в C ++?

Question

Допустим, у меня есть многопоточная программа C ++, которая обрабатывает запросы в виде вызова функции handleRequest(string key). Каждый вызов handleRequest происходит в отдельном потоке, и существует произвольно большое количество возможных значений для key.

Я хочу следующее поведение:

• Одновременные вызовы на handleRequest(key) сериализуются, когда они имеют одинаковое значение для key.
• Глобальная сериализация сведена к минимуму.

Тело handleRequest может выглядеть так:

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

Вопрос: Как мне реализовать KeyLock, чтобы получить требуемое поведение?

Наивная реализация может начинаться так:

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

... но для этого требуется глобальная блокировка в начале и конце каждого запроса и создание отдельного объекта Lock для каждого запроса. Если между вызовами на handleRequest велика конкуренция, это может не быть проблемой, но это может привести к большим накладным расходам, если конкуренция низкая.

Answer 1

Вы могли бы сделать что-то похожее на то, что у вас есть в вашем вопросе, но вместо одного global_key_map есть несколько (возможно, в массиве или в векторе) - какой из них используется, определяется некоторой простой хеш-функцией в строке. *

Таким образом, вместо единой глобальной блокировки, вы распространяете ее на несколько независимых.

Это шаблон, который часто используется в распределителях памяти (я не знаю, есть ли у шаблона имя - так и должно быть). Когда поступает запрос, что-то определяет, из какого пула будет выделено распределение (обычно размер запроса, но могут учитываться и другие параметры), тогда необходимо блокировать только этот пул. Если запрос на выделение поступает из другого потока, который будет использовать другой пул, конкуренция за блокировку отсутствует.

Answer 2

Повышение степени детализации и блокировка целых диапазонов ключей

Это вариант ответа Майка Б., где вместо нескольких карт плавных блокировок у вас есть один фиксированный массив блокировок, которые применяются к диапазонам ключей вместо отдельных ключей.

Упрощенный пример: создайте массив из 256 блокировок при запуске, затем используйте первый байт ключа, чтобы определить индекс блокировки, которую нужно получить (т. Е. Все ключи, начинающиеся с 'k', будут защищены locks[107]).

Чтобы поддерживать оптимальную пропускную способность, вы должны проанализировать распределение ключей и уровень конкуренции. Преимущества этого подхода - нулевое динамическое распределение и простая очистка; Вы также избегаете двухступенчатой ​​блокировки. Недостатком являются возможные конфликтные пики, если распределение ключей с течением времени искажается.

Answer 3

Возможно, std::map<std::string, MutexType> будет тем, что вы хотите, где MutexType - это тип мьютекса, который вы хотите. Вам, вероятно, придется обернуть доступ к карте в другой мьютекс, чтобы гарантировать, что никакой другой поток не вставляет в то же время (и не забудьте выполнить проверку снова после блокировки мьютекса, чтобы другой поток не добавил ключ во время ожидания мьютекса!).

Тот же принцип может применяться к любому другому методу синхронизации, например к критическому разделу.

Answer 4

Это будет зависеть от платформы, но я бы попробовал два метода:

• Использовать именованный мьютекс / синхронизацию объекты, где имя объекта = ключ
• Используйте блокировку на основе файловой системы, где вы попытаться создать не разделяемый временный файл с именем ключа. Если он уже существует (= уже заблокирован) это не удастся, и вы будете нужно опросить, чтобы повторить попытку

Оба метода будут зависеть от деталей вашей ОС. Поэкспериментируйте и посмотрите, что работает. ,

Answer 5

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

Answer 6

Подумав об этом, другой подход может выглядеть примерно так:

• В handleRequest создайте Callback, который выполняет фактическую работу.
• Создать multimap<string, Callback*> global_key_map, защищенный мьютексом.
• Если поток видит, что key уже обрабатывается, он добавляет свой Callback* к global_key_map и возвращает.
• В противном случае он немедленно вызывает свой обратный вызов, а затем вызывает обратные вызовы, обнаруженные в тот же момент для того же ключа.

Реализовано что-то вроде этого:

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

Преимущество этого заключается в освобождении потоков, которые в противном случае ожидали бы блокировку клавиш, но, кроме того, они в значительной степени совпадают с наивным решением, которое я разместил в вопросе.

Впрочем, его можно объединить с ответами Майка Б и Константина.