Семафоры. Синхронизация процессов

Семафоры

В теории операционных систем семафор представляет собой неотрицательную целую переменную, над которой возможны два вида операций: P и V.

• P-операция над семафором представляет собой попытку уменьшения значения семафора на 1. Если перед выполнением P-операции значение семафора было больше 0, P-операция выполняется без задержек. Если перед выполнением P-операции значение семафора было 0, процесс, выполняющий P-операцию, переводится в состояние ожидания до тех пор, пока значение семафора не станет большим 0.
• V-операция над семафором представляет собой увеличение значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.

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

Взаимное исключение на семафоре

Для реализации взаимного исключения, например, предотвращения возможности одновременного изменения двумя или более процессами общих данных, создается двоичный (с возможными значениями 0 и 1) семафор S. Начальное значение этого семафора - 1. Критические секции кода (секции, которые могут одновременно выполняться только одним процессом) обрамляются "скобками" P(S) (в начале секции) и V(S) (в конце секции). Процесс, входящий в критическую секцию, выполняет операцию P(S) и переводит семафор в 0. Если в критической секции уже находится другой процесс, то значение семафора уже 0, тогда второй процесс, желающий войти в критическую секцию, блокируется в своей P-операции до тех пор, пока процесс, находящийся в критической секции сейчас, не выйдет из нее, выполнив на выходе операцию V(S).

Синхронизация на семафоре

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

В случае, если одного и того же события ожидают несколько процессов, процесс, успешно выполнивший операцию P(S), должен вслед за ней выполнить V(S), чтобы продублировать сигнал о событии для следующего ожидающего процесса.

Семафор - счетчик ресурсов

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

Системные вызовы Unix/Linux

В ОС Unix/Linux механизм семафоров обслуживается тремя системными вызовами: semget, semctl и semop.

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

Системный вызов semctl позволяет выполнять управляющие операции над массивом семафоров и отдельными его элементами: читать и устанавливать значения, уничтожать массив семафоров.

Системный вызов semop выполняет прикладные семафорные операции: аналоги P- и V-операций, а также проверки состояния семафора.

Семафоры в Unix/Linux не имеют внешних имен. При получении идентификатора семафора процесс пользуется числовым ключом. Разработчики несвязанных процессов могут договориться об общем значении ключа, который они будут использовать, но у них нет гарантии в том, что это же значение ключа не будет использовано кем-то еще. Гарантированно уникальный массив семафоров можно создать с использованием ключа IPC_PRIVATE, но такой ключ не может быть внешним. Поэтому семафоры используются, как правило, родственными процессами, которые имеют возможность передавать друг другу идентификаторы семафоров, например, через наследуемые ресурсы или через параметры вызова дочерней программы.

System V IPC: базовые понятия

Вместе с ОС System V корпорация AT&T предложила три новых типа IPC средств: очереди сообщений, семафоры и разделяемая память. В BSD-системах в качестве базовой формы IPC используетютя чаще всего сокеты, чем элементы System V. Linux имеет возможность использовать оба вида IPC (BSD и System V), хотя мы не будем обсуждать сокеты в рамках курса.

IPC идентификаторы

Каждый объект IPC имеет уникальный IPC идентификатор. Когда мы говорим "объект IPC", мы подразумеваем очередь единичных сообщений, множество семафоров или разделяемый сегмент памяти. Этот идентификатор требуется ядру для однозначного определения объекта IPC. Например, чтобы сослаться на определенный разделяемый сегмент, единственное, что вам потребуется, это уникальное значение ID, которое привязано к этому сегменту.

Идентификатор IPC уникален только для своего типа объектов. То есть, скажем, возможна только одна очередь сообщений с идентификатором "12345", так же как номер "12345" может иметь какое-нибудь одно множество семафоров или (и) какой-то разделяемый сегмент.

IPC ключи

Чтобы получить уникальный ID нужен ключ. Ключ должен быть взаимно согласован процессом-клиентом и процессом-сервером. Для приложения это согласование должно быть первым шагом в построении среды.

Чтобы позвонить кому-либо по телефону, вы должны знать его номер. Кроме того, телефонная компания должна знать как провести ваш вызов к адресату. И только когда этот адресат ответит, связь состоится.

В случае System V IPC "телефон" соединяет объекты IPC одного типа. Под "телефонной компанией", или методом маршрутизации, следует понимать ключ IPC.

Для генерации ключа используются функция ftok и на стороне клиента, и на стороне сервера.

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

Пример выполнения приведен здесь.

Справочный материал

Избранные системные вызовы Linux/Unix. Краткое описание.

Cправочник библиотечных функция языка С: часть 1, часть 2 (кодировка кириллица ibm866).