Понятие семафора. Двоичный семафор
Дейкстра предложил использовать целочисленную переменную для подсчета количества активизаций, отложенных на будущее. Он предложил учредить новый тип переменной — семафор (semaphore). Значение семафора может быть равно 0, что будет свидетельствовать об отсутствии сохраненных активизаций, или иметь какое-нибудь положительное значение, если ожидается не менее одной активизации. Дейкстра предложил использовать две операции с семафорами, которые сейчас обычно называют down и up (обобщения sleep и wakeup соответственно). Операция down выясняет, отличается ли значение семафора от 0. Если отличается, она уменьшает это значение на 1 (то есть использует одну сохраненную активизацию) и продолжает свою работу. Если значение равно 0, процесс приостанавливается, не завершая в этот раз операцию down. И проверка значения, и его изменение, и, возможно, приостановка процесса осуществляются как единое и неделимое атомарное действие. Тем самым гарантируется, что с началом семафорной операции никакой другой процесс не может получить доступ к семафору до тех пор, пока операция не будет завершена или заблокирована.
Атомарность является абсолютно необходимым условием для решения проблем синхронизации и исключения состязательных ситуаций. Атомарные действия, в которых группа взаимосвязанных операций либо выполняется без каких-либо прерываний, либо вообще не выполняется, приобрели особую важность и во многих других областях информатики. Операция up увеличивает значение, адресуемое семафором, на 1. Если с этим семафором связаны один или более приостановленных процессов, способных завершить ранее начатые операции down, система выбирает один из них (к примеру, произвольным образом) и позволяет ему завершить его операцию down. Таким образом, после применения операции up в отношении семафора, с которым были связаны приостановленные процессы, значение семафора так и останется нулевым, но количество приостановленных процессов уменьшится на 1.
|
|
|
Операция увеличения значения семафора на 1 и активизации одного из процессов также является неделимой. Ни один из процессов не может быть заблокирован при выполнении операции up, равно как ни один из процессов не может быть заблокирован при выполнении wakeup в предыдущей модели.
Семафоры, инициализированные значением 1 и используемые двумя или более процессами для исключения их одновременного нахождения в своих критических областях, называются двоичными семафорами. Взаимное исключение гарантируется в том случае, если каждый процесс совершает операцию down непосредственно перед входом в свою критическую область и операцию up сразу же после выхода из нее.
|
|
|
Объект ядра “семафор” используются для учёта ресурсов и служат для ограничения одновременного доступа к ресурсу нескольких потоков. Используя семафор, можно организовать работу программы таким образом, что к ресурсу одновременно смогут получить доступ несколько потоков, однако количество этих потоков будет ограничено. Создавая семафор, указывается максимальное количество потоков, которые одновременно смогут работать с ресурсом. Каждый раз, когда программа обращается к семафору, значение счетчика ресурсов семафора уменьшается на единицу. Когда значение счетчика ресурсов становится равным нулю, семафор недоступен. создание CreateSemaphore, открытие OpenSemaphore, занять WaitForSingleObject, освобождение ReleaseSemaphore.
Главной проблемой при разделяемом доступе к ресурсам становится проблема синхронизации. Конкурирующие процессы находятся в состоянии гонки за ресурсы, а в силу неатомарности действий, совершаемых над ними, состояние ресурса может быть разрушено из-за несогласованных действий двух или более процессов. Поэтому появилась потребность в механизмах синхронизации, в частности, в механизмах поддержки критических секций — последовательностей действий, которые не могут быть прерваны действиями другого процесса из той же критической секции.
|
|
|
Семантика семафоров заключается в определении двух операций: блокирования семафора и освобождения семафора. В каждый момент времени только один процесс может владеть семафором (блокировать его). Если другие процессы попытаются заблокировать процесс до того, как он будет освобожден, они сами будут заблокированы. После того, как семафор освобождается, он захватывается одним из ожидающих освобождения процессов (если таковые имеются), которому возвращается управление. Связанные критические секции разных процессов могут привязываться к одному семафору и располагаться между операциями блокирования и освобождения семафора.
Реализация идеи критических секций — не единственный метод синхронизации, для которого могут применяться семафоры. Другой пример — идея барьера, точки управления, на которой замирают все процессы до тех пор, пока их не наберется заданное число (обычно все синхронизируемые процессы).
Другой пример: реализация доступа к ресурсу ограниченному числу процессов более одного. Процессы сверх этого количества должны быть заблокированы до момента, пока один из процессов, уже владеющих ресурсом, не освободит его.
|
|
|
Все эти и другие методы синхронизации могут быть реализованы с помощью семафоров. Более формально, семафор можно определить, как целое число, а операции блокирования и освобождения — как операции уменьшения и увеличения данного числа на единицу. При этом, если семафор блокируется, процесс захватывает семафор только если его значение положительно. Освобождение семафора эквивалентно его увеличению на единицу. При этом, если значение семафора отрицательно, одному из ожидающих семафора процессов возвращается управление. Данные операции могут вызываться в произвольном порядке и нет такого ограничения, что освобождать семафор должен тот же самый процесс, что его блокировал, или что семафор нельзя освобождать (увеличивать) до того, как он был заблокирован.
Двоичный семафор (binary semaphore) – переменная S, которая может находиться в двух состояниях: "открыт" и "закрыт"; над S определены две операции:
("семафорные скобки"): P(S) – закрыть, V(S) – открыть. При попытке закрыть уже закрытый семафор происходит прерывание, и ОС добавляет текущий процесс в очередь к закрытому семафору. Операция V(S) активизирует первый стоящий в очереди к S процесс, который успешно завершает операцию P(S). Если семафор S уже открыт, операция V(S) не имеет никакого эффекта.
Дата добавления: 2018-08-06; просмотров: 1644; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!