Мелкозернистая блокировка

Question

Скажем, у нас большой массив и много потоков, работающих с конкретными индексами в этом массиве.Два потока не могут работать с одним индексом одновременно, один должен дождаться окончания работы другого.И отсталый вопрос: как реализовать блокировку test-and-set для каждого индекса массива в Linux / C / C ++?

Answer 1

Для мелкозернистой блокировки используйте массив блокировок чтения / записи (как рекомендует Кэри Хиклинг).Хэшируйте значение индекса и фильтруйте его через битовую маску (или используйте модуль), чтобы выбрать, какую блокировку использовать.

Это эффективно разбивает индексы на N сегментов, где N - количество создаваемых вами блокировок.Выберите степень двойки для количества блокировок для легкой маскировки битов (маска = N - 1).Единственным недостатком в этом сценарии является то, что вы не просто блокируете определенный индекс, вы блокируете каждый индекс, который при хешировании выравнивается с одним и тем же указателем блокировки.создать, более мелкозернистая блокировка (16, вероятно, хорошая отправная точка).Блокировки чтения также доступны и для rw_locks, поэтому вам нужно только дождаться блокировки во время записи.

Answer 2

Вам нужен простой мьютекс и выполните:

    mutex.lock();
    //access array using index
    mutex.unlock();

Или POSIX обеспечивает блокировку чтения-записи. Поэтому вы можете сделать:

    pthread_rwlock_rdlock(rw_lock_ptr);
    // read the array
    pthread_rwlock_unlock(rw_lock_ptr);

И

    pthread_rwlock_wrlock(rw_lock_ptr);
    // update the array
    pthread_rwlock_unlock(rw_lock_ptr);

Это позволяет использовать общие блокировки для операций чтения и эксклюзивные блокировки для операций записи.

Я бы предложил, чтобы у вас был класс или пара для каждого элемента массива и реализован один из вышеперечисленных. Если вы скрываете блокировку мьютекса в функциях чтения / обновления класса, то вы можете легче ограничить область применения блокировок мьютекса и избежать взаимных блокировок.

Answer 3

Сделать тип элемента массива синхронизированным.Если вы хотите изменить свои данные, у вас может быть std::pair<T, std::mutex>;если у вас есть возможность получить спин-блокировку при каждом доступе, вы можете получить std::pair<T, std::atomic<bool>>.Затем просто предоставьте каждому доступу к массиву эксклюзивный доступ к элементу с помощью данных синхронизации.