Как реализовать рекурсивную блокировку MRSW?

Question

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

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

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

Получение общей блокировки поверх эксклюзивной, очевидно, просто увеличивает количество блокировок.

Таким образом, возникает вопрос - как мне это реализовать? Обычный подход с критическим разделом и двумя семафорами здесь не работает, потому что, насколько я вижу, проснувшийся поток должен рукопожатие, вставив свой идентификатор потока в карту владельца замка.

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

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

Целевой платформой является Win32, но это не должно иметь большого значения. Обратите внимание, что я специально нацеливаюсь на Win2k, поэтому все, что связано с новым примитивом блокировки MRSW в Windows 7, не имеет значения для меня. : -)

Answer 1

Хорошо, я решил это.

Это может быть сделано всего с 2 семафорами, критической секцией и почти не более блокировкой, чем для обычной нерекурсивной блокировки MRSW (очевидно, что внутри блокировки затрачивается немного больше процессорного времени, потому что эта мультикарта должна управляться) - но это сложно . Структура, с которой я придумал, выглядит следующим образом:

<code>
// Protects everything that follows, except mWriterThreadId and mRecursiveUpgrade
CRITICAL_SECTION mLock;
// Semaphore to wait on for a read lock
HANDLE mSemaReader;
// Semaphore to wait on for a write lock
HANDLE mSemaWriter;
// Number of threads waiting for a write lock.
int mWriterWaiting;
// Number of times the writer entered the write lock.
int mWriterActive;
// Number of threads inside a read lock. Note that this does not include
// recursive read locks.
int mReaderActiveThreads;
// Whether or not the current writer obtained the lock by a recursive 
// upgrade. Note that this member might be set outside the critical
// section, so it should only be read from by the writer during his
// unlock.
bool mRecursiveUpgrade;
// This member contains the current thread id once for each
// (recursive) read lock held by the current thread in addition to an 
// undefined number of other thread ids which may or may not hold a 
// read lock, even inside the critical section (!).
std::multiset<unsigned long> mReaderActive;
// If there is no writer this member contains 0.
// If the current thread is the writer this member contains his
// thread-id.
// Otherwise it can contain either of them, even inside the 
// critical section (!).
// Also note that it might be set outside the critical section.
unsigned long mWriterThreadId;

Теперь основная идея такова:

Полное обновление mWriterWaiting и mWriterActive для разблокировки выполняется потоком разблокировки.

Для mWriterThreadId и mReaderActive это невозможно, поскольку ожидающий поток должен вставлять себя при освобождении.

Таким образом, правило заключается в том, что вы никогда не можете получить доступ к этим двум элементам , за исключением , чтобы проверить, удерживаете ли вы блокировку чтения или являетесь текущим автором записи - в частности, он может не использоваться для проверки наличия или отсутствия любые читатели / писатели - для этого вы должны использовать (несколько избыточные, но необходимые по этой причине) mReaderActiveThreads и mWriterActive.

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

Answer 2

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

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

Reader:
(1) wait on sem A
(2) increase sem B
(3) read operation
(4) decrease sem B

Writer:
(1) increase sem A 
(2) wait on sem B
(3) write operation
(4) decrease sem A

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

Я не знаком со средствами мьютекса / семафора Windows, но могу придумать, как реализовать такие семафоры с помощью API потоков POSIX (объединяя мьютекс, счетчик и условную переменную).

Answer 3

Ну, я немного подумал. Начиная с простых «двух семафоров и критической секции», в структуру добавляется счетчик блокировок писателя и TID-владелец писателя.

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

Во время блокировки писателей () я сравниваю TID-владелец, и, если писатель уже владеет им, счетчик блокировок записи увеличивается.

Установка нового TID писателя не может быть выполнена с помощью unlock () - он не знает, какой из них будет разбужен, но если писатели сбрасывают его обратно в ноль в их unlock (), это не проблема - текущий ID потока никогда не будет нулевым, и установка его является атомарной операцией.

Все звучит достаточно просто - осталась одна неприятная проблема: рекурсивная блокировка читателя-читателя, пока писатель ждет, заходит в тупик. И я не знаю, как решить эту проблему, если не делать блокировку для читателя ... каким-то образом мне нужно знать, имею ли я уже блокировку для чтения.

Использование TLS не звучит слишком хорошо после того, как я понял, что число доступных слотов может быть довольно ограниченным ...