Синхронизация потоков

Потоки. Синхронизация потоков

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

·   синхронизация с помощью глобальных переменных

·   синхронизация с помощью обмена событиями

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

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

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

Третий метод — синхронизация с помощью специальных объектов — потребует рассмотрения разных объектов и разных методов синхронизации с использованием объектов. В Win32 API существует большое число объектов, которые могут быть применены в качестве синхронизирующих, причем во многих случаях вместо одного объекта может применяться объект другого типа. Поэтому будет интересно рассмотреть несколько основных методов синхронизации с использованием объектов.

Общие представления о методах синхронизации

При рассмотрении способов синхронизации удобно выделить несколько основных способов, применяемых разными операционными системами. В числе таких способов можно выделить четыре метода:

·   критические секции

·   объекты исключительного владения

·   события

·   синхронизация группой объектов

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

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

Часть операций, например получение указателя на какой–либо блок в куче, не нуждается в изменении самой кучи. То есть функции, осуществляющие подобные операции могут выполняться одновременно разными потоками не конфликтуя друг с другом. Такие функции удобно назвать “читателями” — они не изменяют кучу как единый объект.

Другие операции, например выделение нового блока в куче, требуют внесения изменений в кучу — изменения в цепочке выделяемых блоков. Обычно такие изменения осуществляются не в одном месте, а требуется согласованное внесение изменений в нескольких структурах данных. В процессе такой операции структура кучи какое–то время оказывается нарушенной, вследствие чего одновременное выполнение таких действий должно быть исключено. Такие функции удобно назвать “писателями” — они изменяют кучу как единый объект.

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

Можно сформулировать несколько правил для работы с таким объектом:

·   если к объекту имеет доступ писатель, то ни читатели, ни другие писатели доступа не имеют;

·   если к объекту имеет доступ читатель, то возможен одновременный доступ других читателей и запрещен доступ писателям;

·   если объект свободен, то первый пришедший писатель или читатель имеет право доступа.

Рассмотренный пример очень удобен, так как подобная ситуация (много читателей, единственный писатель) встречается сплошь и рядом — а стандартного объекта для синхронизации доступа к такому объекту нет. Благодаря этому такой пример становится благодатной почвой для рассмотрения разных способов синхронизации.

Номер	Поток, уже имеющий доступ	Поток, требующий доступа	Действие
1	читатель	читатель	разрешить доступ
2	читатель	писатель	ожидать освобождения[1]
3	писатель	читатель	ожидать освобождения[1]
4	писатель	писатель	ожидать освобождения
5	—	читатель	разрешить доступ
6	—	писатель	разрешить доступ

Даже при простейшем анализе такой таблицы можно заметить, что писатели находятся в неравном положении — при достаточно большом числе читателей и писателей возможна полная блокировка последних, так как читатели могут получать право одновременного доступа к объекту, так что возможна ситуация, когда объект вообще не будет освобожден для писателей — хоть один читатель да найдется. Для выхода из такой ситуации следует слегка модифицировать реакцию объекта во 1м случае — если имеется ожидающий поток–писатель, то надо разрешить доступ ему, а не читателю. Для полной “симметрии” следует в 4м случае проверять наличие читателей и разрешать им доступ, даже если имеется ожидающий поток–писатель. Такой механизм, хотя и достаточно сложный в реализации, обеспечит более–менее равные права для выполнения потоков разного типа.

Критические секции

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

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

Для критической секции вводят две операции:

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

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

Вообще говоря, в других API, отличных от Win32 (например, OS/2), критическая секция рассматривается не как синхронизирующий объект, а как фрагмент кода программы, который может исполняться только одним потоком приложения. То есть вход в критическую секцию рассматривается как временное выключение механизма переключения потоков до выхода из этой секции. В Win32 API критические секции рассматриваются как объекты, что приводит к определенной путанице — они очень близки по своим свойствам к неименованным объектам исключительного владения (mutex, см. ниже).

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

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

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

·   читатели не конфликтуют с писателями (защищать надо только писателей);

·   все потоки имеют примерно равные права доступа (скажем, нельзя выделить чистых писателей и читателей);

·   при построении составных синхронизирующих объектов, состоящих из нескольких стандартных, для защиты последовательных операций над составным объектом.

Объекты исключительного владения

Объекты исключительного владения — mutex (mutual exclusion) — могут принадлежать только одному потоку одновременно. Соответственно определяются операции над этими объектами:

·   затребовать владение объектом;
При запросе владения система проверяет, владеет–ли какой–либо другой поток этим объектом или нет. Если имеется другой поток–владелец, то данный поток останавливается до тех пор, пока объект не освободиться. Как только объект становится свободным, система отдает его во владение новому потоку. Поток, уже владеющий объектом, может многократно вступать во владение им.

·   освободить объект;
При освобождении объекта система просматривает, имеются–ли другие потоки, ожидающие освобождения этого объекта. Если имеются, то возобновит работу только один поток, а все остальные продолжат ожидание — объект mutex может быть во владении только у одного потока. Освобождать объект может только тот поток, который им в данный момент владеет, другие потоки этого сделать не могут. Для полного освобождения объекта поток должен столько раз освободить его, сколько раз он затребовал владение с того момента, как ему дали этот объект во владение.

Если учесть, что владеть объектом mutex может только один поток, то получается, что такие объекты похожи на критические секции — с того момента, как система отдала объект во владение потоку все остальные, которые захотят получить его во владение, будут ожидать его освобождения. Отличия заключаются в некоторых нюансах использования — во–первых, объекты mutex могут быть использованы разными процессами (для этого предусмотрены именованные объекты, которые могут быть использованы другими процессами) и, во–вторых, ожидать владения этим объектом можно разными способами — с ограничением по времени или, например, использовать его для синхронизации сразу с несколькими объектами (другими объектами mutex, семафорами, событиями и прочим). Об этом — подробнее в последующих разделах.

События

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

·   событиями никто не владеет — то есть устанавливать события в свободное или занятое состояние могут любые потоки, имеющие право доступа к этому объекту

·   события различают только два состояния — свободное и занятое. Сколько бы раз вы не переводили событие в занятое состояние, один единственный вызов функции, освобождающей это событие, освободит его. И наоборот.

·   в классическом варианте освобождение события разрешает запуск всех потоков, ожидающих его. Объекты исключительного владения и критические секции позволяли возобновить исполнение только одного потока[2].

·   смена состояния события осуществляется в любой момент времени. Так, для вхождения в критическую секцию или для получения объекта mutex во владение необходимо было дождаться их освобождения (что выполнялось автоматически). Для событий это не так.

Соответственно, применительно к событиям, говорят о двух основных состояниях: свободном (установленном) и занятом (сброшенном) и о трех операциях, выполняемых над ними:

·   сбросить событие;
Событие в сброшенном состоянии считается занятым. Аналогия — флажок такси (в России — лампа зеленого цвета). Опущенный флаг (или выключенная лампа) означают, что такси занято. Любой поток, имеющий доступ к событию, может сбросить его, независимо от того, какой поток это событие устанавливал.

·   установить (иногда — послать) событие;
Установленное (посланное) событие считается свободным. Как только событие освобождается, все ожидающие его потоки могут возобновить свое исполнение (см. сноску). Устанавливать событие может также любой поток.

·   дождаться события;
Так как сброс и установка событий происходит в любой момент времени, независимо от предыдущего состояния события, то приходится вводить специальную операцию — дождаться освобождения объекта.

Эти особенности выделяют события в особую категорию синхронизирующих объектов. Рассмотренные ранее критические секции и объекты исключительного владения позволяют осуществить монопольный доступ к какому–либо ресурсу или объекту данных, в то время как события определяют некоторые условия, после которых возможно выполнение тех или иных операций.

Пример. Возвращаясь к примеру с глобальной кучей — для работы с ней необходимо создать составной синхронизирующий объект. Пример такого объекта можно найти в книге “Windows для профессионалов” Джеффри Рихтера. Естественно, логика построения объекта одинакова и в рассматриваемом случае, что позволяет детально сравнить несколько близких решений и заострить внимание на некоторых “мелочах”. Сейчас мы рассмотрим только “скелет” такого объекта и основные правила работы с ним. Позже, после рассмотрения функций Win32 API, рассмотрим конкретную реализацию этого составного объекта и сравним ее с чрезвычайно похожим объектом, приведенным в книге Рихтера.

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

Из этих соображений следует наличие:

·   Критической секции или объекта исключительного владения для синхронизации потоков–писателей. Выбор одного из этих объектов определяется необходимостью исключительного доступа только одного потока–писателя к данным. Удобно также, что освободить секцию или mutex может только тот поток, который его занял. В рассматриваемом примере будем использовать объект mutex, для большей схожести с Рихтером (это позволит подчернуть несколько нюансов в разработке такого объекта).

·   События, переходящего в занятое состояние при наличии хотя–бы одного читателя. В данном случае целесообразно выбрать событие, которое будет сбрасываться в занятое состояние при появлении первого потока–читателя и устанавливаться в свободное последним читателем (последним из числа тех, кто пытается осуществить чтение одновременно с другими, но не вообще последнего).

·   Счетчика числа потоков–читателей, осуществляющих одновременный доступ. Нулевое значение счетчика соответствует установленному в свободное состояние событию. При увеличении счетчика проверяется его начальное значение, и если оно было 0, то событие сбрасывается в занятое состояние. При уменьшении счетчика проверяется результат — если он 0, то событие устанавливается в свободное состояние.

Можно примерно описать структуру такого объекта (назовем его NEWSWMRG, по сравнению с объектом SWMRG, рассматриваемым у Рихтера — Single Writer Multi Reader Guard). Эта структура должна быть описана примерно так:

struct NEWSWMRG {
СОБЫТИЕ НЕТ_ЧИТАТЕЛЕЙ;
СЧЕТЧИК ЧИСЛО_ЧИТАТЕЛЕЙ;
ОБЪЕКТ_ИСКЛЮЧИТЕЛЬНОГО_ВЛАДЕНИЯ ЕСТЬ_ПИСАТЕЛИ;
};

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

void RequestWriter( NEWSWMRG* p ) {
// дождаться разрешения для писателя
Захватить объект ЕСТЬ_ПИСАТЕЛИ;
// если объект получен во владение — других писателей больше нет
// и пока мы его не освободим — не появятся.
Дождаться события НЕТ_ЧИТАТЕЛЕЙ;
// если событие установлено — читателей также нет
}

void ReleaseWriter( NEWSWMRG* p ) {
 // после изменения данных разрешаем доступ другим писателям и читателям
 Освободить объект ЕСТЬ_ПИСАТЕЛИ;
 }

void RequestReader( NEWSWMRG* p ) {
 // дождаться разрешения для читателя — убедиться, что нет писателей
 // для этого можно захватить объект ЕСТЬ_ПИСАТЕЛИ и сразу освободить его
 // захват пройдет только тогда, когда писателей нет.
 Захватить объект ЕСТЬ_ПИСАТЕЛИ;
 // реально надо не только убедиться в отсутствии писателей, но и
 // увеличить счетчик и при необходимости сбросить событие НЕТ_ЧИТАТЕЛЕЙ
 if ( ЧИСЛО_ЧИТАТЕЛЕЙ == 0 ) Сбросить событие НЕТ_ЧИТАТЕЛЕЙ в занятое;
 ЧИСЛО_ЧИТАТЕЛЕЙ++;
 // а вот теперь можно смело освобождать объект ЕСТЬ_ПИСАТЕЛИ — во время
 // работы читателя достаточно иметь сброшенное событие НЕТ_ЧИТАТЕЛЕЙ Освободить объект ЕСТЬ_ПИСАТЕЛИ;
 }

void ReleaseReader( NEWSWMRG* p ) {
 // после считывания данных уменьшаем счетчик и разрешаем доступ писателям
 // при достижении нулевого значения счетчика.
 --ЧИСЛО_ЧИТАТЕЛЕЙ;
 if ( ЧИСЛО_ЧИТАТЕЛЕЙ == 0 ) Установить событие НЕТ_ЧИТАТЕЛЕЙ в свободное;
 }

Естественно, это еще не рабочая схема, а только намек на нее. Полностью обсудим некоторые особенности при рассмотрении функций Win32 API. На первый взгляд виден небольшой “прокол” — в функции ReleaseReader счетчик сначала уменьшается, а только потом происходит проверка его значения и установка события при необходимости. Однако возможен (хотя и очень маловероятен) случай, когда поток будет прерван для выполнения операций другими потоками где–то между уменьшением счетчика и установкой события. В это время другие потоки могут изменить значение счетчика и событие будет установлено тогда, когда этого делать уже не следует.

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

[1] Возможны такие объекты, хотя это не типичный случай, когда читатели не конфликтуют с писателями. Тогда в ситуациях 2 и 3 следует разрешать доступ.

[2] В Win32 API существуют специальные механизмы, позволяющие возобновлять исполнение только одного потока при освобожении события. Однако, по сравнению с другими операционными системами, скажем OS/2, такое поведение события нетипично.