Модель переменных условий

Модель переменных условий

А теперь давайте объединим все это в едином фрагменте кода, представляющем то, что мы будем называть моделью переменных условий (condition variable model, CV model), которая может существовать в виде сигнальной (signal) и широковещательной (broadcast) моделей. В первых примерах будет использована широковещательная модель. Результат представляет собой программную модель, с которой мы будем работать еще не один раз, и которая может быть использована для решения широкого круга задач синхронизации. Для удобства изложения примеры сформулированы в терминах задачи производителя и потребителя.

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

В упомянутом фрагменте кода имеется несколько ключевых элементов.

• Структура данных типа STATE_TYPE, в которой содержатся все данные, или переменные состояний (state variables), такие как сообщения, контрольные суммы и счетчики, используемые в программе 8.2.

• Мьютекс и одно или более событий, связанных с этой структурой данных и обычно входящих в ее состав.

• Одна или несколько булевых функций, предназначенных для вычисления предикатов переменных условий (condition variable predicates), представляющих собой условия (состояния), наступления которых может ожидать поток. Например, в качестве предикатов могут использоваться следующие условия: "готово новое сообщение", "имеется свободное место в буфере", "очередь не пуста". Можно связывать с каждым предикатом переменной условия отдельное событие, но возможно также использование одного события для представления изменения состояния или же для представления комбинации нескольких предикатов (получаемой посредством применения операции логического "или"). В последнем случае для определения фактического состояния должны проверяться возвращаемые значения отдельных предикативных функций при блокированном мьютексе. Если предикат (логическое выражение) является простым, необходимость в использовании отдельной функции отпадает.

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

Этот код ориентирован на работу под управлением Windows 9x и всех версий Windows NT. Для упрощения решения впоследствии в нем будет использована функция SignalObjectAndWait.

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

В данном примере намеренно и вполне осознанно используется функция PulseEvent, хотя некоторые авторы, а кое-где и документация Microsoft (см. замечания в соответствующем разделе MSDN), этого делать не рекомендуют. Причины нашего выбора будут ясны из последующего обсуждения и подкреплены примерами, а читателю предлагается решить (корректно) эту задачу, используя функцию SetEvent.

typedef struct _state_t {

 HANDLE Guard; /* Мьютекс, защищающий объект. */

 HANDLE CvpSet; /* Вручную сбрасываемое событие — выполняется условие, определяемое предикатом cvp(). */

 … другие переменные условий …

 /* Структура состояния, содержащая счетчики, контрольные суммы и прочее. */

 struct STATE_VAR_TYPE StateVar;

 } STATE_TYPE State;

…

/* Инициализировать состояние, создавая мьютекс и событие. */

…

/* Поток ПРОИЗВОДИТЕЛЯ, который изменяет состояние. */

WaitForSingleObject(State.Guard, INFINITE);

/* Изменить состояние таким образом, чтобы выполнялось условие, */

/* определяемое предикатом CV. */

/* Пример: к данному моменту подготовлено одно или несколько сообщений.*/

State.StateVar.MsgCount += N;

PulseEvent(State.CvpSet);

ReleaseMutex(State.Guard);

/* Конец интересующей нас части кода потока производителя. */

…

/* Ожидание определенного состояния функцией потока ПОТРЕБИТЕЛЯ. */

WaitForSingleObject(State.Guard, INFINITE);

while (!cvp(&State)) {

 ReleaseMutex(State.Guard);

 WaitForSingleObject(State.CvpSet, TimeOut);

 WaitForSingleObject(State.Guard, INFINITE);

}

/* Теперь этот поток владеет мьютексом, и выполняется условие, */

/* определяемое предикатом cvp(&State). */

/* Предпринять соответствующее действие, возможно, изменяя состояние.*/

…

ReleaseMutex(State.Guard);

/* Конец интересующей нас части кода потока потребителя. */ 

Комментарии по поводу модели переменных условий

В приведенном выше фрагменте кода очень важная роль принадлежит циклу в той части кода, которая соответствует потребителю. Этот цикл включает три операции: 1) освобождение мьютекса, заблокированного до входа в цикл; 2) ожидание события; 3) повторное блокирование мьютекса. Как будет показано далее, использование конечного интервала ожидания события является весьма существенным.

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

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

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

Помимо того, что это упрощает разработку программ и является существенно необходимым в случае использования потоков Pthreads, есть еще одна причина, по которой следует изучать модель CV, заключающаяся в том, что именно эта модель используется рядом сторонних производителей для реализации классов потоков и объектов синхронизации, не зависящих от ОС. Владея изложенным в этой книге материалом, вы сможете очень быстро разобраться в особенностях этих реализаций.

Примечание

В версии Windows NT 4.0 была введена новая функция — SignalObjectAndWait (SOAW), которая выполняет упомянутые два шага атомарным образом. В дальнейших примерах программ предполагается, что эта функция доступна, и она будет использоваться, а это означает, что под управлением Windows 9x такие программы выполняться не смогут. Тем не менее, на стадии ознакомления с моделью CV функция SOAW не применяется, чтобы сделать более понятной мотивировку необходимости ее использования впоследствии, а на Web-сайте книги приведены альтернативные варианты реализации некоторых примеров, в которых вместо мьютексов используются объекты CS. (Функцию SOAW нельзя применять вместе с объектами CS.) О значительных преимуществах функции SignalObjectAndWait в отношении производительности свидетельствуют данные, представленные в приложении В (табл. В.5). 

Использование модели переменных условий

Модель переменных условий при правильной ее реализации работает следующим образом:

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

• Функция PulseEvent должна применяться к событию при блокированном мьютексе, чтобы никакой другой поток не мог изменить объект, что могло бы сделать недействительным условие, определенное предикатом.

• Поток потребителя тестирует предикат переменной условия при блокированном мьютексе. Если условие, выраженное предикатом, выполняется, выполнять функцию ожидания нет никакой необходимости.

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

• Интервал ожидания события должен быть конечным, чтобы обеспечить правильную обработку в том случае, если поток производителя применит к событию функцию PulseEvent в промежутке времени между освобождением мьютекса (шаг 1) и выполнением ожидания события (шаг 2). Таким образом, без использования конечного интервала ожидания сигнал мог бы потеряться, что является еще одним примером проявления проблемы состязательности. К потере сигналов могут приводить и асинхронные вызовы процедур, описанные далее в этой главе. Используемый в приведенном выше фрагменте кода интервал ожидания является настраиваемым параметром. (С комментариями по поводу оптимальных значений этого параметра вы можете ознакомиться, обратившись к приложению В.)

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

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

Разновидности модели переменных условий

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

Вернувшись к табл. 8.1, можно увидеть, что сбрасываемые вручную события характеризуются освобождением нескольких потоков. Это именно так в случае нашего примера, в котором генерируются несколько сообщений и существует несколько потоков потребителя, и все они должны быть оповещены о произошедших изменениях. В то же время, если поток производителя создает всего лишь одно сообщение и имеется несколько потоков потребителя, то событие должно быть автоматически сбрасываемым, а поток производителя должен вызывать функцию SetEvent, чтобы обеспечить освобождение только одного потока. В этом случае мы имеем дело не с сигнальной разновидностью модели CV, а с широковещательной. При этом по-прежнему остается существенным, чтобы освобожденный поток потребителя, который приобретает права владения мьютексом, изменил объект для указания того, что доступные сообщения отсутствуют (то есть, что условие, определяемое предикатом переменной условия, уже не выполняется).

Из четырех возможных комбинаций, указанных в табл. 8.1, для модели переменных условий важны только две. Что касается двух других комбинаций, то в силу конечности интервала ожидания эффект комбинации "автоматически сбрасываемое событие/PulseEvent" будет тем же, что и комбинации "автоматически сбрасываемое событие/SetEvent" (сигнальная модель CV), однако зависимость от длительности интервала ожидания приведет к снижению характеристик реактивности.

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

Подводя итоги, можно сделать вывод, что комбинация "автоматически сбрасываемое событие/SetEvent" представляет собой сигнальную модель CV, в которой освобождается единственный из ожидающих потоков, а комбинация "вручную сбрасываемое событие/PulseEvent" — широковещательную модель CV, в которой освобождаются все ожидающие потоки. Для потоков Pthreads существуют те же различия, но использование конечных интервалов ожидания событий для широковещательной модели в данном случае не требуется, тогда как в Windows этот фактор является весьма существенным, поскольку освобождение мьютекса и ожидание события не выполняются атомарно, то есть за одну операцию. В то же время, введение функции SignalObjectAndWait меняет эту ситуацию.

Пример предиката переменной условия

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

State.StateVar.Count >= K;

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

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

Семафоры и модель переменных условий

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

Модель CV обладает достаточно мощными возможностями, которых хватает для реализации семафоров. Как уже отмечалось ранее, в основе этого метода лежит определение предиката, эквивалентного утверждению: "значение счетчика является ненулевым", и создание структуры состояния, содержащей текущее значение счетчика и его максимально допустимое значение. В упражнении 10.11 представлено завершенное решение, позволяющее манипулировать функциями ожидания путем изменения значений счетчика на несколько единиц одной операцией. Создание семафоров для потоков Pthreads не предусмотрено, поскольку переменные условий предоставляют достаточно широкие возможности.