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

Семафоры
Первый из таких подходов был предложен Дейкстрой в 1965 г. Дейкстра предложил новый тип данных, именуемый семафором. Семафор представляет собой переменную целого типа, над которой
определены две операции: down(P) и up(V).1 Операция down проверяет значение семафора, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем операция down считается незавершенной. Важно отметить, что вся операция является неделимой, т.е. проверка значения, его уменьшение и, возможно, блокирование процесса производятся как одно атомарное действие, которое не может быть прервано. Операция up увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, ОС разблокирует один из них с тем, чтобы он завершил выполнение операции down, т.е. вновь уменьшил значение семафора. При этом также постулируется, что увеличение значения семафора и, возможно, разблокирование одного из процессов и уменьшение значения являются атомарной неделимой операцией. Чтобы прояснить смысл использования семафоров для синхронизации, можно привести простую аналогию из повседневной жизни. Представим себе супермаркет, посетители которого, прежде чем войти в торговый зал, должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая количество тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N = 1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (так как имеет только 2 состояния: 0 и 1). Использование
двоичного семафора для организации взаимного исключения проиллюстрировано на Рис. 5.
процесс 1
int semaphore; … down(semaphore); /* критическая секция процесса 1 */ … up(semaphore); …
процесс 2
int semaphore; … down(semaphore); /* критическая секция процесса 2 */ … up(semaphore); …
Рис. 5 Взаимное исключение с использованием семафора Семафоры представляют собой мощное средство синхронизации, однако программирование с использованием семафоров является достаточно тяжелой задачей, причем незаметная на первый взгляд логическая ошибка может привести к образованию тупиковых ситуаций или нарушению условий синхронизации. С целью облегчить написание корректных программ были предложены более высокоуровневые средства синхронизации, которые мы рассмотрим далее.
Семафоры представляют собой одну из форм IPC и, как правило, используются для синхронизации доступа нескольких процессов к разделяемым ресурсам, так как сами по себе другие средства IPC не предоставляют механизма синхронизации. Как уже говорилось, классический семафор представляет собой особый вид числовой переменной, над которой определены две неделимые операции: уменьшение ее значения с возможным блокированием процесса и увеличение значения с возможным разблокированием одного из ранее заблокированных процессов. Объект System V IPC представляет собой набор семафоров.
Как правило, использование семафоров в качестве средства синхронизации доступа к другим разделяемым объектам предполагает следующую схему: - с каждым разделяемым ресурсом связывается один семафор из набора; - положительное значение семафора означает возможность доступа к ресурсу (ресурс свободен), неположительное – отказ в доступе (ресурс занят); - перед тем как обратиться к ресурсу, процесс уменьшает значение соответствующего ему семафора, при этом, если значение семафора после уменьшения должно оказаться отрицательным, то процесс будет заблокирован до тех пор, пока семафор не примет такое значение, чтобы при уменьшении его значение оставалось неотрицательным; - закончив работу с ресурсом, процесс увеличивает значение семафора (при этом разблокируется один из ранее заблокированных процессов, ожидающих увеличения значения семафора, если таковые имеются); - в случае реализации взаимного исключения используется двоичный семафор, т.е. такой, что он может принимать только значения 0 и 1: такой семафор всегда разрешает доступ к ресурсу не более чем одному процессу одновременно. Рассмотрим набор вызовов для оперирования с семафорами в UNIX System V.
Доступ к семафорам
Для получения доступа к массиву семафоров (или его создания) используется системный вызов: #include
#include
#include i
nt semget (key_t key, int nsems, int semflag);
Первый параметр функции semget() – ключ для доступа к разделяемому ресурсу, второй - количество семафоров всоздаваемом наборе (длина массива семафоров) и третий параметр – флаги, управляющие поведением вызова. Подробнее процесс создания разделяемого ресурса описан выше. Отметим семантику прав доступа к такому типу разделяемых ресурсов, как семафоры: процесс, имеющий право доступа к массиву семафоров по чтению, может проверять значение семафоров; процесс, имеющий право доступа по записи, может как проверять, так и изменять значения семафоров. В случае, если среди флагов указан IPC_CREAT, аргумент nsems должен представлять собой положительное число, если же этот флаг не указан, значение nsems игнорируется. Отметим, что в заголовочном файле определена константа SEMMSL, задающая максимально возможное число семафоров в наборе. Если значение аргумента nsems больше этого значения, вызов semget() завершится неудачно. В случае успеха вызов semget() возвращает положительный дескриптор созданного разделяемого ресурса, в случае неудачи -1.

Операции над семафорами

Используя полученный дескриптор, можно производить изменять значения одного или нескольких семафоров в наборе, а также проверять их значения на равенство нулю, для чего используется системный вызов semop():
#include
#include #include
int semop (int semid, struct sembuf *semop, size_t nops);
Этому вызову передаются следующие аргументы: semid – дескриптор массива семафоров; semop – массив из объектов типа struct sembuf, каждый из которых задает одну операцию над семафором; nops – длина массива semop. Количество семафоров, над которыми процесс может одновременно производить операцию в одном вызове semop(), ограничено константой SEMOPM, описанной в файле . Если процесс попытается вызвать semop() с параметром nops, большим этого значения, этот вызов вернет неуспех.
Управление массивом семафоров
#include
#include #include
int semctl (int semid, int num, int cmd, union semun arg);
С помощью этого системного вызова можно запрашивать и изменять управляющие параметры разделяемого ресурса, а также удалять его. Первый параметр вызова – дескриптор массива семафоров. Параметр num представляет собой индекс семафора в массиве, параметр cmd задает операцию, которая должна быть выполнена над данным семафором. Последний аргумент имеет тип union semun и используется для считывания или задания управляющих параметров одного семафора или всего массива, в зависимости от значения аргумента cmd. Тип данных union semun определен в файле и выглядит следующим образом:
union semun { int val; // значение одного семафора
struct semid_ds *buf; /* параметры массива семафоров в целом */ ushort *array; /* массив значений семафоров */ }
где struct semid_ds – структура, описанная в том же файле, в полях которой хранится информация о всем наборе семафоров в целом, а именно, количество семафоров в наборе, права доступа к нему и статистика доступа к массиву семафоров. Приведем некоторые наиболее часто используемые значения аргумента cmd: IPC_STAT – скопировать управляющие параметры набора семафоров по адресу arg.buf; IPC_SET – заменить управляющие параметры набора семафоров на те, которые указаны в arg.buf. Чтобы выполнить эту операцию, процесс должен быть владельцем или создателем массива семафоров, либо обладать правами привилегированного пользователя, при этом процесс может изменить только владельца массива семафоров и права доступа к нему; IPC_RMID – удалить массив семафоров. Чтобы выполнить эту операцию, процесс должен быть владельцем или создателем массива семафоров, либо обладать правами привилегированного пользователя; GETALL, SETALL – считать / установить значения всех семафоров в массив, на который указывает arg.array; GETVAL – возвратить значение семафора с номером num. Последний аргумент вызова игнорируется; SETVAL – установить значение семафора с номером num равным arg.val. В случае успешного завершения вызов возвращает значение, соответствующее конкретной выполнявшейся операции (0, если не оговорено иное), в случае неудачи – -1. Отметим, что использование данного вызова с командами GETVAL и GETALL позволяет процессу проверить значение семафора без риска оказаться заблокированным. Команды же SETVAL и SETALL чаще всего используются для инициализации семафоров, начальное значение которых посемантике алгоритма работы с ними должно быть отлично от нуля21. Тут, однако, существует тонкий момент, указывающий на один из недостатков данной реализации семафоров. Поскольку создание массива семафоров и его инициализация требуют использования двух разных системных вызовов, в некоторых приложениях возможно возникновение следующей ситуации:  процесс, ответственный за создание и инициализацию семафоров (назовем его А) создает массив семафоров, обратившись к вызову semget();  до того, как процесс А успеет выполнить инициализацию путем обращения к semctl() или semop(), он будет выгружен планировщиком и на выполнение поступит другой процесс (назовем его В);  процесс В попытается обратиться к семафору, ожидая, что его начальное значение уже установлено, что может привести к непредвиденной и очень трудноуловимой ошибке в результате возникновения гонок (race conditions). К счастью, этой ситуации можно избежать, используя некий обходной маневр. В структуре struct semid_ds существует поле sem_otime, в котором хранится время последнего вызова semop() для данного массива семафоров. Стандарт POSIX гарантирует, что при создании массива семафоров это поле инициализируется нулем. Оно становится равным текущему времени лишь после первого вызова semop(), инициализирующего массив семафоров. Таким образом, процессу, который начинает работу с массивом семафоров, ожидая, что он уже проинициализирован, следует прежде всего проверить значение указанного поля (с помощью вызова semctl() с параметром IPC_STAT) , и лишь в случае, если оно отлично от нуля, приступать к работе.