процесс А

процесс В

Сфайловая система

функции для создания, у установки значения и ожидания изменения состояния семафора (create, post, wait)

бинарный семафор > является файлом, в котором хранится О или 1

Рис. 10.2. Два процесса, использующие бинарный именованный семафор Posix

ПРИМЕЧАНИЕ-

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

На рис. 10.1 и 10.2 мы указали три операции, которые могут быть применены к семафорам:

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

2. Ожидание изменения значения семафора (wait). При этом производится проверка его значения и процесс блокируется, если значение оказывается меньшим либо равным О, а при превышении О значение уменьшается на 1. Это может быть записано на псевдокоде как

while (semaphore value <= 0)

: /* wait: т.е. поток или процесс блокируется */ semaphore value--;

/* семафор разрешает выполнение операций */ Основным требованием является атомарность выполнения операций проверки значения в цикле while и последующего уменьшения значения семафора (то есть как одной операции) по отношению к другим потокам (это одна из причин, по которой семафоры System V были реализованы в середине 80-х как часть ядра. Поскольку операции с ними выполнялись с помощью системных вызовов, легко было гарантировать их атомарность по отношению к другим процессам).

У этой операции есть несколько общеупотребительных имен. Изначально она называлась Р, от голландского ргоЬеп (проверка, попытка), - это название было введено Эдсгером Дейкстрой. Используются также и термины down (поскольку значение семафора уменьшается) и lock, но мы будем следовать стандарту Posix и говорить об ожидании (wait).

3. Установка значения семафора (post). Значение семафора увеличивается одной командой, которая может быть записана на псевдокоде как semaphore value++:

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

Для этой операции также имеется несколько общеупотребительных терминов. Изначально она называлась V, от голландского verhogen (увеличивать). Называют ее up (значение семафора увеличивается), unlock и signal. Мы, следуя стандарту Posix, называем эту операцию post.

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

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

ПРИМЕЧАНИЕ-

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

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

Листинг 10.1. Сравнение бинарных семафоров и взаимных исключений

инициализация взаимного исключения; инициализация семафора единицей:

pthread mutexJock(&mutex); sem wait(&sem);

критическая область критическая область

pthread mutex unlock(&mutex): sem post(&sem):

Мы инициализируем семафор значением 1. Вызвав sem wait, мы ожидаем, когда значение семафора окажется больше О, а затем уменьшаем его на 1. Вызов sempost увеличивает значение с О до 1 и возобновляет выполнение всех потоков, заблокированных в вызове semwait для данного семафора.

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

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

производитель -

общий буфер

потребитель

Рис. 10.3. Задача производителя и потребителя с общим буфером

В листинге 10.2 приведен текст соответствующей программы на псевдокоде.

Листинг 10.2. Псевдокод для задачи производителя и потребителя

Producer Consumer

инициализация семафора get значением 0:

инициализация семафора put значением 1:

for ( ; : ) { for ( : : ) {

sem wait(&put); sem wait(&get):

помещение данных в буфер: обработка данных в буфере;

sem post(&get); seni post(&put):

Семафор put ограничивает возможность помещения объекта в общий буфер, а семафор get управляет потребителем при считывании объекта из буфера. Работает эта программа в такой последовательности:

1. Производитель инициализирует буфер и два семафора.

2. Пусть после этого запускается потребитель. Он блокируется при вызове sein wait, поскольку семафор get имеет значение 0.

3. После этого запускается производитель. При вызове semwait значение put уменьшается с 1 до О, после чего производитель помещает объект в буфер. Вызовом sempost значение семафора get увеличивается с О до 1. Поскольку имеется поток, заблокированный в ожидании изменения значения этого семафора, этот поток помечается как готовый к выполнению. Предположим, тем не менее, что производитель продолжает выполняться. В этом случае он блокируется при вызове sein wai t в начале цикла for, поскольку значение семафора put - 0. Производитель должен подождать, пока потребитель не извлечет данные из буфера.

4. Потребитель возвращается из semwait, уменьшая значение семафора get с О до 1. Затем он обрабатывает данные в буфере и вызывает sempost, увеличивая значение put с О до 1. Заблокированный в ожидании изменения значения этого семафора поток-производитель помечается как готовый к выполнению. Предположим опять, что выполнение потребителя продолжается. Тогда он блокируется при вызове sem wait в начале цикла for, поскольку семафор get имеет значение 0.

5. Производитель возвращается из semwai t, помещает данные в буфер, и все повторяется.

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