Документальные противоречия о ReentrantReadWriteLock. В конечном итоге блокировка записи имеет приоритет над блокировкой чтения или нет в обычном режиме?

Question

От ReentrantLock Javadoc:

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

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

Поток, который пытается получить справедливую блокировку записи (не реентерабельно), будет блокироваться, если и блокировка чтения, и блокировка записи не свободны (что подразумевает отсутствие ожидающих потоков). (Обратите внимание, что неблокирующие методы ReentrantReadWriteLock.ReadLock.tryLock() и ReentrantReadWriteLock.WriteLock.tryLock() не учитывают этот справедливый параметр и получат блокировку, если это возможно, независимо от ожидающих потоков.)

Может быть, это проблема моего английского, но я вижу противоречия в этом описании:
С первого параграфа я не понимаю смысла политики порядка прибытия

1. Из первого абзаца я понимаю, что блокировка приобретает самую старую ожидающую нить. Если самый старый поток - поток чтения, то это будет группа прочитанных потоков, которые ожидают дольше, чем самый длинный ожидающий поток записи.
2. Из второго абзаца я понимаю, что блокировка чтения не будет установлена, если блокировка записи существует в wait-set.

Пожалуйста, проясните это противоречие.

Answer 1

Вот цитата из вашей цитаты:

или если есть группа читателей темы

Другими словами: писатель побеждает одного читателя; но когда группа читателей хочет блокировку, они получают блокировку.

Что касается вопроса: "и что на самом деле означает группа " ... это будет деталь реализации, доступная только при изучении исходного кода.

Answer 2

Я не вижу противоречий в приведенном вами описании, и я думаю, что вы понимаете #1 правильно, но #2 неправильно.

И, кстати, я думаю, что описание GhostCat неверно. Нет ничего, что суммирует время ожидания разных потоков и сравнивает их. Логика на самом деле намного проще.

Мой ответ, как правило, длинный, но, надеюсь, объяснительный.

Неправильный режим

Давайте начнем с "несправедливой" блокировки режима в первую очередь. "Несправедливость" здесь означает, что

Несправедливая блокировка, которая постоянно утверждается, может на неопределенный срок отложить один или несколько потоков чтения или записи

Так что "справедливость" здесь означает, что ни одна нить не может ждать вечно. "Несправедливость" означает, что если существует постоянный поток потоков для получения блокировки чтения, и у нас есть некоторый поток (W1) который ожидает блокировки записи, когда новый поток для блокировки чтения (Rn) может встать перед блокировкой W1 нить и т. д. могут случиться при неудачных обстоятельствах бесконечно. Обратите внимание, что даже в "нечестном" режиме ReentrantReadWriteLock пытается быть достаточно справедливым, это просто не гарантирует справедливости, потому что, как говорит док, "справедливость" не бесплатна, а стоимость ниже пропускной способности.

Пример несправедливого режима

Так как же может произойти настоящее несправедливое поведение. Предположим, что есть W0 поток, содержащий блокировку записи и очередь на данный момент R0 а также R1 в ожидании блокировки чтения, затем W1 в ожидании блокировки записи, а также в будущем будет огромный поток новых потоков для блокировки чтения Ri, Также предположим, что поток R1 поток имеет самый низкий приоритет в системе, и ОС никогда не повышает приоритет потоков, даже если они не работают в течение очень долгого времени.

1. Блокировка записи удерживается W0, ожидающая очередь [ R0, R1, W1 ]
2. W0 снимает блокировку записи, R0 сейчас проснулся и получил блокировку чтения R1 имеет низкий приоритет и не проснулся, поэтому не может получить блокировку чтения прямо сейчас. Очередь ожидания сейчас [ R1, W1 ]
3. W1 проснулся, но не может захватить замок из-за R0
4. Сейчас пока R0 все еще держит блокировку чтения, новый поток чтения R2 прибывает. Поскольку блокировка чтения уже получена, и первый поток в очереди ожидания является читателем R1, R2 немедленно получает блокировку чтения. Блокировка чтения удерживается [ R0, R2 ]. Очередь ожидания еще [ R1, W1 ].
5. Сейчас R0 снимает блокировку, но W1 все еще не может получить блокировку записи, так как она удерживается сейчас R2, Очередь ожидания еще [ R1, W1 ].
6. Сейчас пока R2 все еще держит блокировку чтения, новый поток чтения R3 прибывает, получает блокировку чтения, и та же самая история продолжается и продолжается.

Здесь важно то, что:

• Первая запись в теме W1 заблокирован от чтения потоком чтения R1 который не проснулся, чтобы получить блокировку из-за низкого приоритета и / или чистой неудачи.
• для новоприбывших Ri поток, чтобы выяснить, есть ли какой-либо поток записи во всей очереди, требует некоторого времени и усилий, и, таким образом, применяется более простая эвристика (шаг #4): является ли самый первый ожидающий поток потоком записи или чтения, и R1 читает тот, который позволяет быстрое приобретение. Также обратите внимание, что эта логика на шаге 4 с проверкой первого потока в очереди является попыткой быть честной, о чем я упоминал ранее, и это лучше, чем просто наивная реализация, у которой нет такой проверки.

Честный режим

Так что теперь вернемся к справедливости. Как вы можете найти в источниках внутреннего класса FairSync (я удалил мелкие детали):

class FairSync extends Sync {
     final boolean writerShouldBlock() {
         return hasQueuedPredecessors();
     }
     final boolean readerShouldBlock() {
         return hasQueuedPredecessors();
     }
}

Таким образом, буквально да, разница между "честным" и "несправедливым" заключается в том, что в потоке считывателя в "честном" режиме перед получением блокировки чтения, которую он мог бы получить без нарушения контракта ReadWriteLock, дополнительно проверяется, существует ли какой-либо другой поток в очередь перед этим. В этом случае W1 поток из предыдущего примера не мог ждать вечно, так как R2 и следующий поток не получит блокировку чтения до этого.

Пример честного режима

Еще одна попытка на том же примере в честном режиме:

1. Блокировка записи удерживается W0, ожидающая очередь [ R0, R1, W1 ]
2. W0 снимает блокировку записи, R0 получает очередь блокировки чтения [ R1, W1 ]
3. W1 проснулся, но не может захватить замок из-за R0
4. R2 прибывает в очередь. Хотя блокировка чтения удерживается R0 а также R2 кажется, что в состоянии приобрести это также, это не делает это, потому что это видит W1 впереди себя. Блокировка чтения удерживается R0 и очередь [ R1, W1, R2 ]
5. Теперь оба W1 а также R2 не может получить блокировку до R1 удаляется из очереди. Из-за этого наконец R1 Проснувшись, получает блокировку, выполняет обработку и снимает блокировку.
6. в заключение W1 получает блокировку записи и R2, R3 а другие все еще в очереди в ожидании.

С точки зрения этого примера R0 а также R1 сформировать "группу", но R2 не принадлежит к этой "группе", потому что это после W1 в очереди.

Резюме

Итак, первый абзац описывает, что происходит, когда блокировка снята, а стратегия проста: первый ожидающий поток получает блокировку. Если первый ожидающий поток оказывается потоком чтения, то все остальные потоки чтения в очереди до того, как первый поток записи получит блокировку чтения. Все такие прочитанные темы называются "группа". Обратите внимание, что это не означает, что все прочитанные потоки ожидают блокировки!

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

Answer 3

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

"Группа читательских тем" может быть только одной веткой.

В спецификации нет противоречий, но это может быть не так ясно, как могло бы быть.

Предположим, что поток A удерживает блокировку записи на мьютексе.

Поток B прибывает и пытается получить блокировку записи. Затем приходит поток C и пытается получить блокировку чтения. Затем приходит поток D и пытается получить блокировку чтения. Затем приходит поток E и пытается получить блокировку записи. Затем приходит поток F и пытается получить блокировку чтения.

Теперь поток А разблокирует мьютекс. Политика честного режима подразумевает, что поток B получит блокировку: он ждал дольше всего.

Когда поток B снимает блокировку, потоки C и D получат блокировку чтения, но не поток F. C и D являются "группой потоков чтения, ожидающих дольше всех ожидающих потоков записи". Поток F все еще заблокирован, потому что он ждал меньше, чем поток E, который является потоком записи.

Если поток E затем отменяет ожидание (например, время ожидания истекло), то поток F теперь является самым старым ожидающим потоком, а текущая блокировка является блокировкой чтения, поэтому поток F может получить блокировку до того, как потоки C и D освободят свои.

Если поток G теперь попытается получить блокировку записи, он будет блокироваться, пока все потоки C, D и F не снимают свои блокировки чтения.

Если поток H сейчас попытается получить блокировку чтения, он заблокируется: существует ожидающий поток записи.

Если поток, который я сейчас пытаюсь получить, блокирует запись, он блокируется: существует очередь ожидающих потоков.

Теперь C, D и F снимают свои блокировки, поэтому поток G (самый длинный ожидающий поток) получает блокировку записи.

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

Наконец, когда поток H снимает блокировку, я могу его получить.