18. Семафоры и мьютексы. (Лекция 5)
Семафор (semaphore) – объект, позволяющий войти в заданный участок кода не более чем n потокам. Специальный объект, позволяющий блокировать или активировать процесс, обратившийся к нему. Автор – Дейкстра (Dijkstra, 1965).
- Семафор инициализируется неотрицательным значением счетчика.
- Операция wait уменьшает счетчик семафора. Если счетчик был равен 0, то вызывающий процесс блокируется.
- Операция signal увеличивает счетчик. Если имелись блокированные процессы то запускается один из них.
ОС должна обеспечить атомарность выполнения wait и signal – до их завершения процессы не могут обращаться к семафору.
Семафор - это объект, с которым можно выполнить три операции.
1. init(n):
счётчик := n
2. enter():
ждать пока счётчик станет больше 0; после этого уменьшить счётчик на единицу.
3. leave():
увеличить счётчик на единицу.
Предположим, что есть такой участок кода:
semaphore.init(5);
.....
void DoSomething( void )
{
semaphore.enter();
.......
semaphore.leave();
}
Тогда не более пяти потоков могут одновременно выполнять функцию DoSomething().
В более сложных семафорах может использоваться очередь; при этом потоки, ожидающие освобождения семафора, будут проходить через семафор именно в том порядке, в котором они вызывали enter().
Проблемы, которые могут решать семафоры: запрет одновременного выполнения заданных участков кода; поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен одновременный доступ).
Проблемы семафоров: можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже, когда дважды вызывается leave(). Семафоры чреваты взаимной блокировкой потоков (несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами).
Сильный (strong) семафор – для очереди процессов используется алгоритм FIFO. Слабый (weak) семафор – алгоритм очереди неопределен.
Мьютекс (mutex – от mutual exclusion) – особый вид двоичных семафоров, допускающий право владения. Мьютекс - одноместный семафор, служащий в программировании для синхронизации одновременно выполняющихся потоков. Мьютексы - это один из вариантов семафорных механизмов для организации взаимного исключения. Их основное назначение — организация взаимного исключения для потоков из одного и того же или из разных процессов. Двоичный семафор имеет два состояния – занят и свободен (signaled). У свободного мьютекса счетчик не растет и первое обращение wait «захватывает» мьютекс. Процесс при этом называется владельцем.
Задача мьютекса — защита объекта от доступа к нему других потоков, отличных от того, который завладел мьютексом. В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом. Если другому потоку будет нужен доступ к переменной, защищённой мьютексом, то этот поток засыпает до тех пор, пока мьютекс не будет освобождён.
Цель
использования мьютексов — защита данных
от повреждения; однако им порождаются
другие проблемы — такие, как взаимная
блокировка (несколько процессов находятся
в состоянии бесконечного ожидания
ресурсов, занятых самими этими процессами)
и состояние гонки (работа системы зависит
от того, в каком порядке выполняются
части кода).
Для семафора signal может выполнить любой процесс, а для мьютекса только владелец. Для мьютекса владелец не может заблокировать сам себя.
Различия: 1) Семафоры являются более гибкой формой мьютексов. В отличие от мьютексов, программа имеет контроль над тем, сколько потоков одновременно могут захватывать семафор.
2) Мьютекс может быть захвачен не более чем одним потоком управления. О потоке управления, который захватил мьютекс, говорят, что он является владельцем мьютекса. Освободить мьютекс может только его владелец. В силу этого мьютексы нельзя использовать в процедурах обработки прерываний.
3) Семафор предоставляет одновременный доступ к общему ресурсу не одному, а нескольким потокам.
4) Мьютексы в отличие от семафоров позволяют избежать инверсии приоритетов (менее приоритетные потоки управления в силу использования средств синхронизации мешают выполнению более приоритетного потока).