СЕМАФОРЫ

Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. Он предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.

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

Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р (от датского слова proberen — проверять) и V (от verhogen увеличивать). Пусть переменная S представляет собой семафор. Тогда классическое определение действия V(S) и P(S) операций выглядит следующим образом:

P(S):	ЕСЛИ S = 0 ТО процесс блокируется; ИНАЧЕ S = S – 1;
V(S):	S = S + 1;

Эта запись означает следующее:

- при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1.

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

- при выполнении операции V над семафором S к его значению просто прибавляется 1. Во время выполнения этой операции к переменной S нет доступа другим потокам.

Никакие прерывания во время выполнения примитивов V и Р недопустимы.

Одной из типовых задач, требующих организации взаимодействия процессов с использованием семафоров, является задача producer-consumer (производитель-потребитель).

Например. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись.

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

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

Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е = N, a f = 0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис.1).

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

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

Семафор может находиться в сигнальном или несигнальном состоянии. Приложение выполняет ожидание для семафора при помощи таких функций, как WaitForSingleObject() или WaitForMultipleObject().

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

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

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

Для ожидания сигнализации одного объекта у Win32 используют функцию WaitForSingleQbject(), синтаксис которой следующий:

DWORD WaitForSingleObject(HANDLE handle, DWORD timeout);

Параметры:

handle – определяет дескриптор синхронизированного объекта;

timeout – задает максимальное время ожидания в милисекундах (значение INFINITE свидетельствует о бесконечном ожидании).

Возвращаемое значение: Функция WaitForSingleObject() возвращает такие значения: WAIT_OBJECT_0 - состоялась сигнализация объекта; WAIT_TIMEOUT - минуло время ожидания (если timeout не равнялся INFINITE), а объект своего состояния так и не изменил.

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

DWORD WaitForMultipleObjects(DWORD count, CONST HANDLE handles, BOOL waitall, DWORD timeout);

Параметры:

count – длина массива дескрипторов;

handles – задает максимальное время ожидания в миллисекундах (значение INFINITE свидетельствует о бесконечном ожидании).

waitall – флажок режима ожидания;

timeout – аналогичная к WaitForSingleObject

Возвращаемое значение:

Функция принимает массив дескрипторов handles длиной count (максимальная длина массива 64 элемента). Режим ожидания и возвращенное значение зависеть от флажка waitall.

Если waitall равняется TRUE, задан режим ожидания всех объектов. Ожидание завершается в случае осуществления сигнализации всех объектов, функция повернет WAIT_OBJECT_0.

Если waitall равняется FALSE, задан режим ожидания одного объекта. Ожидание завершается в случае осуществления сигнализации хотя бы одного из объектов, функция повернет WAIT_OBJECT_0+i, где i- индекс дескриптора этого объекта в массиве handles.

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

С каждым семафором связывается счетчик, начальное и максимальные значения которого задаются при создании семафора. Значение этого счетчика уменьшается, когда задача вызывает для семафора функцию WaitForSingleObject() или WaitForMultipleObject(), и увеличивается при вызове функции ReleaseSemaphore().

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

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

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

Это связано с тем, что первые три вызова функции WaitForSingleObject() приведут к последовательному уменьшению значения счетчика семафора до нуля, в результате чего семафор переключится в несигнальное состояние.

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

Как долго продлится ожидание?

До тех пор, пока одна из первых трех задач не освободит семафор, увеличив его счетчик на единицу вызовом функции ReleaseSemaphore(). Сразу после этого будет запущена одна из задач, ожидающих наш семафор.

Рассмотрим функции программного интерфейса операционной системы Windows, предназначенные для работы с семафорами.

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

HANDLE CreateSemaphore (LPSECURITY_ATTRIBUTES lpThreadSecurity, LONG lSemInitialCount, LONG lSemMaxCount, LPCTSTR lpszSemName)

Параметры:

lpThreadSecurity – указатель на структуру, содержащую атрибуты доступа к семафору. Если атрибуты не используются, он может содержать значение, равное NULL;

lSemInitialCount – начальное значение счетчика в семафоре, которое должно быть больше или равно нулю и меньше либо равно значению параметра lSemMaxCount;

lSemMaxCount – максимальное значение счетчика в семафоре. Это значение должно быть больше нуля;

lpszSemName– указатель на строку, содержащую имя семафора. Имя не должно совпадать с именем существующего события, семафора или объекта отображения файла;

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

Для уничтожения семафора вы должны передать его идентификатор функции CloseHandle(). Заметим, что при завершении процесса все созданные им семафоры уничтожаются автоматически.

Если семафор используется только для синхронизации задач, созданных в рамках одного приложения, вы можете создать безымянный семафор, указав в качестве параметра lpszSemName функции CreateSemaphore() значение NULL.

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

Существующий семафор можно открыть функцией OpenSemaphore(), синтаксис которой следующий

HANDLE OpenSemaphore (DWORD dwAccessFlag, BOOL bInherit, LPCTSTR lpszSemName)

Параметры:

dwAccessFlag – указатель на требуемый тип доступа к семафору;

bInherit – определяет возможность наследования семафора другими процессами, создаваемые функцией CreateProcess();

lpszSemName– указатель на строку, содержащую имя открываемого семафора.

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

Флаги доступа могут принимать одно из трех значений:

Параметр	Описание
SEMAPHORE_ALL_ACCESS	Устанавливает все возможное флаги доступа для данного семафора
SEMAPHORE_MODIFY_STATE	Разрешает изменение счетчика ресурсов в функции ReleaseSemaphore()
SYNCHONIZE	Разрешает использование в любой из ожидающих функций сигнала об изменении состояния семафора

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

BOOL ReleaseSemaphore (HANDLE hSemaphore, LONG lReleaseCount, LPLONG lpPreviosCount)

Параметры:

hSemaphore – хэндл освобожденного объекта семафора;

lReleaseCount – число, которое определяет значение, установленное в счетчике ресурсов семафора при его освобождении;

lpPreviosCount – указатель на место хранения предыдущего значения счетчика.

Возвращаемое значение. При успешном выполнении функция возвращает TRUE, в противном случае – возвращается NULL.

Функция ReleaseSemaphore() увеличивает значение счетчика семафора, идентификатор которого передается ей через параметр hSemaphore, на значение, указанное в параметре lReleaseCount.

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

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

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

Таким образом, функция используется для решения двух задач:

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

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

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

В программном интерфейсе операционной системы Windows нет функции, специально предназначенной для уменьшения значения счетчика семафора.

Этот счетчик уменьшается, когда задача вызывает функции ожидания, такие как WaitForSingleObject() или WaitForMultipleObject(). Если задача вызывает несколько раз функцию ожидания для одного и того же семафора, содержимое его счетчика каждый раз будет уменьшаться.

Таким образом, алгоритм работы с семафорами выглядит следующим образом:

поток создает или открывает семафор с помощью функций CreateSemaphore() или OpenSemaphore() соответственно;

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

при завершении поток вызывает функцию ReleaseSemaphore(), освобождающую семафор.

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

Одной из проблем, которая возникает при использовании семафоров является проблема синхронизации – взаимные блокировки (дедлоки, клинчи, тупики).