Семафор (программирование)

Это статья о методе синхронизации выполняющихся одновременно программ. Остальные значения этого слова описаны в статье Семафор.

Семафо́р — объект, позволяющий войти в заданный участок кода не более чем n потокам. Определение введено Э. Дейкстрой.

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

Семафор — это объект, с которым можно выполнить три операции.

init(n):
счётчик := n
 
enter():
ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.
 
leave():
увеличить счётчик на единицу.

Предположим, что есть такой участок кода:

semaphore.init(5);
.....
.....
semaphore.enter();
DoSomething();
semaphore.leave();

Тогда не более пяти потоков могут одновременно выполнять функцию DoSomething().

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

Применение семафоров

Вот некоторые из проблем, которые могут решать семафоры.

• запрет одновременного выполнения заданных участков кода;
• поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен одновременный доступ).

Следующий пример показывает, как наладить поочерёдный доступ к консоли.

semaphore.init(1);

Поток 1:
semaphore.enter();
cout << "Состояние массива: ";
for (int i=0; i<n; i++)
  cout << a[i] << ' ';
cout << '\n';
semaphore.leave();

Поток 2:
semaphore.enter();
cout << "Нажато Esc.\n";
semaphore.leave();

Этот код поможет предотвратить появление листинга наподобие

Состояние массива: 1 2 3 Нажато Esc.
4 5 6

Проблемы семафоров

Во-первых, можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave().

Во-вторых, семафоры чреваты взаимной блокировкой потоков. В частности, опасен такой код:

Поток 1:
semaphore1.enter();
semaphore2.enter();
...
semaphore2.leave();
semaphore1.leave();

Поток 2:
semaphore2.enter();
semaphore1.enter();
...
semaphore1.leave();
semaphore2.leave();

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

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

См. также

• Критическая секция
• Мьютекс
• Фьютекс
• Состояние гонки

Внешние ссылки

• Пример реализации семафора с политикой FIFO в Microsoft.NET