Разработка ядра Linux

Лав Роберт

Семафоры

В операционной системе Linux семафоры (semaphore) — это блокировки, которые переводят процессы в состояние ожидания. Когда задание пытается захватить семафор, который уже удерживается, семафор помещает это задание в очередь ожидания (wait queue) и переводит это задание в состояние ожидания (sleep). Когда процессы [49] , которые удерживают семафор, освобождают блокировку, одно из заданий очереди ожидания возвращается к выполнению и может захватить семафор.

49

Как будет показано дальше, несколько процессов могут при необходимости одновременно удерживать один семафор.

Давайте снова возвратимся к аналогии двери и ключа. Когда человек, который хочет открыть дверь, подходит к двери, он может захватить ключ и войти в комнату. Отличие

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

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

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

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

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

• Так как поток выполнения во время конфликта при захвате блокировки находится в состоянии ожидания, то семафоры можно захватывать только в контексте процесса. Контекст прерывания планировщиком не управляется.

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

• При захвате семафора нельзя удерживать спин-блокировку, поскольку процесс может переходить в состояние ожидания, ожидая на освобождение семафора, а при удержании спин-блокировки в состояние ожидания переходить нельзя.

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

Последняя полезная функция семафоров — это то, что они позволяют иметь любое количество потоков, которые одновременно удерживают семафор. В то время как спин-блокировки позволяют удерживать блокировку только одному заданию в любой момент времени, количество заданий, которым разрешено одновременно удерживать семафор, может быть задано при декларации семафора. Это значение называется счетчиком использования (usage count) или просто счетчиком (count). Наиболее часто встречается ситуация, когда разрешенное количество потоков, которые одновременно могут удерживать семафор, равно одному, как и для спин-блокировок. В таком случае счетчик использования равен единице и семафоры называются бинарными семафорами (binary semaphore) (потому что он может удерживаться только одним заданием или совсем никем не удерживаться) или взаимоисключающими блокировками (mutex, мьютекс) (потому

что он гарантирует взаимоисключающий доступ — mutual exclusion). Кроме того, счетчику при инициализации может быть присвоено значение, большее единицы. В этом случае семафор называется счетным семафором (counting semaphore, семафор-счетчик), и он допускает количество потоков, которые одновременно удерживают блокировку, не большее чем значение счетчика использования. Семафоры-счетчики не используются для обеспечения взаимоисключающего доступа, так как они позволяют нескольким потокам выполнения одновременно находиться в критическом участке. Вместо этого они используются для установки лимитов в определенном коде. В ядре они используются мало. Если вы используете семафор, то, скорее всего, вы используете взаимоисключающую блокировку (семафор со счетчиком, равным единице).

Семафоры были формализованы Эдсгером Вайбом Дейкстрой [50] (Edsger Wybe Dijkstra) в 1968 году как обобщенный механизм блокировок. Семафор поддерживает две атомарные операции

P

и

V

, название которых происходит от голландских слов Proben (тестировать) и Verhogen (выполнить инкремент). Позже эти операции начали называть

down

и

up

соответственно.

В операционной системе Linux они имеют такое же название. Операция

down

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

up

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

50

Доктор Дейкстра (1930–2002 г.) один из самых талантливых ученых за всю (конечно, не очень долгую) историю существования вычислительной техники как области науки. Его многочисленные труды включают работы но проектированию операционных систем и по теории алгоритмов, сюда же входит концепция семафоров. Он родился в городе Роттердам, Нидерланды, и преподавал в университете штата Техас в течение 15 лет. Тем не менее, он был бы не очень доволен большим количеством директив

GOTO

в ядре Linux.

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

Создание и инициализация семафоров

Реализация семафоров зависит от аппаратной платформы и определена в файле

<asm/semaphore.h>

. Структура

struct semaphore

представляет объекты типа семафор. Статическое определение семафоров выполняется следующим образом.

static DECLARE_SEMAPHORE_GENERIC(name, count);

где

name

— имя переменной семафора, a

count

— счетчик семафора. Более короткая запись для создания взаимоисключающей блокировки (mutex), которая используются наиболее часто, имеет следующий вид.

static DECLARE_MUTEX(name);

где

name

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

sema_init(sem, count);

где

sem

— это указатель, a

count

— счетчик использования семафора. Аналогично для инициализации динамически создаваемой взаимоисключающей блокировки можно использовать функцию

init_MUTEX(sem);

Неизвестно, почему слово "mutex" в имени функции

init_MUTEX

выделено большими буквами и почему слово "init" идет перед ним, в то время как имя функции

sema_init

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