Семафор (информатика)

Материал из Википедии — свободной энциклопедии

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

Семафо́р — объект, позволяющий войти в заданный участок кода не более чем 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();

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

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