Как сделать Windows Slim чтения писателя блокировки справедливым?

Маловероятно, что вы можете изменить сам тонкий замок, чтобы он был справедливым, тем более что в документации не указан какой-либо метод, и сегодня большинство блокировок недобросовестный по причинам производительности.

Тем не менее, довольно просто свернуть свой собственный примерно FIFO-замок с Windows События, и 64-битное управляющее слово, которым вы манипулируете сравнить и поменять местами это все еще очень тонкий. Вот схема:

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

Слово управления блокировкой имеет следующие состояния:

1. Бесплатно — ни читателей, ни писателей, ни официантов. Любой поток может получить блокировку для чтения или записи путем атомарного перевода блокировки в состояние (2) или (3).

2. N читателей в замке. Есть N читатели в замке на данный момент. Новые читатели могут немедленно получить блокировку, добавив 1 к счетчику — используйте поле из 30 битов или около того в контрольном слове для представления этого счетчика. Писатели должны блокировать (возможно, после вращения). Когда читатели покидают блокировку, они уменьшают счетчик, который может переходить в состояние (1), когда последний читатель уходит (хотя им не нужно делать ничего особенного в переходе (2) -> (1)).

3. Состояние (2) + ожидающих писателей + 0 или более ожидающих читателей. В этом состоянии в замке все еще находятся 1 или более читателей, но по крайней мере один ожидающий записи. Авторы должны ждать события ручного сброса, которое, хотя и не гарантировано, будет FIFO. В контрольном слове есть поле, указывающее, сколько авторов ожидает. В этом состоянии новые читатели, которые хотят войти в блокировку, не могут, и вместо этого устанавливают бит ожидания читателя и блокируют событие ожидания читателя. Новые записи увеличивают число ожидающих записи и блокируют событие ожидания записи. Когда последний читатель уходит (устанавливая поле счетчика читателей в 0), он сигналы событие ожидания писателя, освобождающее писателя с наибольшим временем ожидания для входа в замок.

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

Все переходы между состояниями, рассмотренные выше, выполняются атомарно с использованием функции сравнения и обмена. Типичная картина заключается в том, что любой из lock() или же unlock() вызовы смотрят на контрольное слово, определяют, в каком состоянии они находятся и какой переход должен произойти (следуя приведенным выше правилам), затем вычисляют новое контрольное слово во временном попытка поменять местами новое управляющее слово с помощью функции сравнения и замены. Иногда эта попытка не удалась, потому что другой поток одновременно изменил управляющее слово (например, другой считыватель вошел в блокировку, увеличив счетчик считывателей). Нет проблем, просто начните сначала с «определить состояние …» и попробуйте снова. Такие гонки на практике редки, так как вычисление слова состояния очень короткое, и именно так все работает со сложными блокировками на основе CAS.

Такая конструкция замка «тонкая» почти во всех смыслах. С точки зрения производительности, это почти то, что вы можете получить для общего дизайна. В частности, общие быстрые пути (а) считывателя, входящего в замок с 0 или более считывателями, уже находящимися в блоке; (b) считыватель, оставляющий замок с 0 или более считывателями, все еще находящимися в замке, и (с) записывающий элемент, входящий / выходящий из Необслуживаемая блокировка выполняется как можно быстрее в обычном случае: одна атомарная операция. Кроме того, пути входа и выхода считывателя являются «свободными от блокировки» в том смысле, что входящие считыватели временно не принимают мьютекс, внутренний для rwlock, манипулируют состоянием и затем разблокируют его при входе / выходе из блокировки. Этот подход медленный и подвержен проблемам, когда поток чтения выполняет переключение контекста в критический момент, когда удерживает внутреннюю блокировку. Такие подходы не масштабируются до уровня активности читателя с короткой критической секцией rwlock: даже если несколько читателей теоретически могут войти в критическую секцию, все они являются узким местом при входе и выходе из внутренней блокировки (что происходит дважды для каждой операции входа / выхода) ) и производительность хуже обычного мьютекса!

Он также легок в том, что ему нужна только пара объектов Windows Event, и эти объекты могут быть выделены по запросу, по требованию — они нужны только тогда, когда возникает конфликт и происходит переход состояния, требующий блокировки. Вот как CRITICAL_SECTION объекты работают.

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

В этом проекте писатели будут чередоваться в порядке FIFO с группами читателей FIFO. Писатели являются FIFO по отношению к другим авторам, а читательские пакеты — FIFO по отношению к другим читателям, но отношения между писателями и читателями не именно так FIFO: поскольку все входящие читатели добавляются в один и тот же набор ожидающих читателей, в случае, когда уже есть несколько ожидающих писателей, все прибывающие читатели переходят в следующую «партию», которая будет выпущена, что фактически ставит их впереди писателей, которые уже жду Это вполне разумно: читатели все идут однажды, поэтому добавление большего количества считывателей в пакет не требует больших затрат и, вероятно, повышает эффективность, и если вы действительно обслуживали все потоки в строгом порядке FIFO, блокировка уменьшится в поведении до простого мьютекса в условиях конкуренции.

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

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

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

И последнее замечание — эта блокировка в использовании памяти немного толще, чем блокировка Windows в случае, когда это утверждается, — потому что она выделяет одно или два события Windows. за замок, в то время как тонкий замок избегает этого. Слабая блокировка, вероятно, делает это, напрямую поддерживая поведение тонкой блокировки в ядре, поэтому управляющее слово может быть непосредственно использовано как часть списка ожидания на стороне ядра. Вы не можете воспроизвести это точно, но вы все равно можете удалить накладные расходы на блокировку другим способом: используйте локальное хранилище потока, чтобы выделить два события за нитку а не за замок. Поскольку поток может ожидать только одну блокировку за раз, вам нужна только одна структура на поток. Это приводит его в соответствие с тонкой блокировкой при использовании памяти (если у вас мало блокировок и тонны потоков).