Меню
Главная
Случайная статья
Настройки
|
Семафор (англ. semaphore) — примитив синхронизации[1] работы процессов и потоков, в основе которого лежит счётчик, над которым можно производить две атомарные операции: увеличение и уменьшение значения на единицу, при этом операция уменьшения для нулевого значения счётчика является блокирующейся[2]. Служит для построения более сложных механизмов синхронизации[1] и используется для синхронизации параллельно работающих задач, для защиты передачи данных через разделяемую память, для защиты критических секций, а также для управления доступом к аппаратному обеспечению.
Вычислительные семафоры используются для контроля над ограниченными ресурсами[3]. Двоичные семафоры обеспечивают взаимное исключение исполнения критических секций[4], а их упрощённой реализацией являются мьютексы, которые более ограничены в использовании[5]. Помимо взаимного исключения в общем случае семафоры и мьютексы могут использоваться во множестве других типовых алгоритмов, включая сигнализирование другим задачам[6], разрешение прохождения определённых контрольных точек только для одной задачи единовременно по аналогии с турникетом[7], задачу производителя и потребителя, подразумевающую передачу данных от одних задач другим[8], барьеры, позволяющие синхронизировать группы задач в определённых контрольных точках[9], условные переменные для оповещения других задач о каких-либо событиях[3] и блокировки чтения и записи, разрешающие одновременное чтение данных, но запрещающих их одновременное изменение[10].
Типовыми проблемами использования семафоров являются одновременное блокирование двух задач в ожидании друг друга[11] и ресурсное голодание, в результате чего ресурс может быть периодически недоступен для одних задач из-за его использования другими задачами[12]. При использовании в процессах с приоритетом реального времени может возникнуть инверсия приоритетов, которая может привести к неограниченной по времени блокировке процесса с более высоким приоритетом из-за захвата семафора процессом с более низким приоритетом, в то время как процессорное время отдаётся процессу со средним приоритетом[13], решением чего является наследование приоритетов[14].
Содержание
Общие сведения
Понятие семафора было введено в 1965 году нидерландским учёным Эдсгером Дейкстрой[15], а в 1968 году он предложил использовать два семафора для решения задачи производителя и потребителя[8].
Семафор представляет собой счётчик, над которым можно выполнять две операции: увеличение на 1 (англ. up) и уменьшение на 1 (англ. down). При попытке уменьшения семафора, значение которого равно нулю, задача, запросившая данное действие, должна блокироваться до тех пор, пока не станет возможным уменьшение значения семафора до неотрицательного значения, то есть пока другой процесс не увеличит значение семафора[16]. Под блокированием задачи понимается изменение состояния процесса или потока планировщиком задач на такое, при котором задача приостановит своё исполнение[17].
Операции уменьшения и увеличения значения семафора первоначально обозначались буквами P (от нидерл. proberen — пытаться) и V (от нидерл. verhogen — поднимать выше) соответственно. Данные обозначения дал операциям над семафорами Дейкстра, но так как они не понятны для людей, говорящих на других языках, на практике обычно используются другие обозначения. Обозначения up и down впервые начали использоваться в языке Алгол 68[18].
Операции увеличения и уменьшения значения семафора вместе со всеми проверками должны быть атомарными. Если в момент увеличения значения семафора есть более одного заблокированного по данному семафору процесса, то операционная система выбирает один из них и разрешает ему закончить операцию уменьшения значения семафора[16].
Принято считать, что значение семафора является неотрицательным, но существует и другой подход к определению семафора, при котором под отрицательным значением понимается количество заблокированных задач с отрицательным знаком. При таком подходе уменьшение семафора является блокирующимся, если результат операции стал отрицательным[17].
Основным назначением семафора является разрешение или временный запрет на выполнение каких-либо действий, поэтому если значение счётчика семафора больше нуля, то говорят, что он находится в сигнальном состоянии, если же значение равно нулю — в несигнальном состоянии[19]
В общем виде семафор можно представить как объект, состоящий из[22]:
- переменной-счётчика, хранящей текущее значение семафора;
- списка заблокированных в ожидании сигнального значения семафора задач;
- функций атомарного увеличения и уменьшения значения семафора.
Концепция семафора хорошо подходит для синхронизации потоков, может использоваться для синхронизации процессов, однако совершенно не подходит для синхронизации взаимодействия компьютеров. Семафор является низкоуровневым примитивом синхронизации, поэтому, за исключением защиты критических секций, сам по себе может быть сложен в использовании[23]. Другим, более низкоуровневым, примитивом синхронизации является фьютекс. Он может предоставляться операционной системой и хорошо подходит для реализации семафоров на прикладном уровне при использовании атомарных операций над разделяемым счётчиком[24].
Виды семафоров
Семафоры могут быть двоичными и вычислительными[3]. Вычислительные семафоры могут принимать целочисленные неотрицательные значения и используются для работы с ресурсами, количество которых ограничено[3], либо участвуют в синхронизации параллельно исполняемых задач. Двоичные семафоры могут принимать только значения 0 и 1[3] и используются для взаимного исключения одновременного нахождения двух или более процессов в своих критических секциях[4].
Мьютексные семафоры[3] (мьютексы) являются упрощённой реализацией семафоров, аналогичной двоичным семафорам с тем отличием, что мьютексы должны отпускаться тем же процессом или потоком, который осуществляет их захват[25], однако в зависимости от типа и реализации попытка освобождения другим потоком может как освободить мьютекс, так и вернуть ошибку[26]. Наряду с двоичными семафорами используются в организации критических участков кода[27][28]
Легковесными семафорами называются семафоры, использующие активный цикл ожидания перед выполнением блокировки. Активный цикл ожидания в ряде случаев позволяет уменьшить количество системных вызовов[3].
Алгоритмы использования
Типовые алгоритмы
Сигнализирование, также называемое уведомлением, является базовым назначением семафоров, оно гарантирует исполнение участка кода одной задачи после исполнения участка кода другой задачи[6]. Сигнальное использование семафора обычно предполагает установку его начального значения в 0, чтобы ожидающие сигнального состояния задачи могли блокироваться до наступления события. Сигнализирование выполняется через увеличение значения семафора, а ожидание — через уменьшение значения[29].
Пример сигнализирования семафором
| Основной поток
|
- Инициализировать семафор А (А 0)
|
| Поток 1
|
Поток 2
|
- Выполнить подготовку ресурса
- Сигнализировать семафором А (А 1)
- Разблокировка потока 2
- Действия над общим ресурсом
|
- Поток 2 первым получил процессорное время
- Ожидать сигнального состояния А (блокировка)
- Разблокировка, А 0
- Действия над общим ресурсом
|
Семафоры хорошо подходят для сигнализирования одной или нескольким задачам, количество которых заранее известно. Если количество ожидающих сигнального состояния задач заранее неизвестно, то обычно используются условные переменные
В многопоточных приложениях часто требуется, чтобы отдельные участки кода, называемые критическими секциями, не могли работать параллельно, например, при доступе к какому-либо неразделяемому ресурсу или при изменении общих ячеек памяти. Для защиты таких участков можно использовать двоичный семафор или мьютекс[3]. Мьютекс является более безопасным в использовании, поскольку может быть отпущен только тем процессом или потоком, который его захватил[5]. Также использование мьютекса вместо семафора может быть более производительным за счёт оптимизации под два значения на уровне реализации ассемблерного кода.
Начальным значением семафора выставляется единица, означая, что он не захвачен — в критическую секцию пока никто не вошёл. Входом (англ. enter) в критическую секцию является захват семафора — его значение уменьшается до 0, что делает повторную попытку входа в критическую секцию блокирующейся. При выходе (англ. leave) из критической секции семафор отпускается, и его значения становится равным 1, разрешая снова входить в критическую секцию, в том числе и другим потокам или процессам
Для разных ресурсов могут быть разные семафоры, отвечающие за критические секции. Таким образом, критические секции, защищённые разными семафорами, могут работать параллельно.
Пример работы критической секции на основе семафора
| Основной поток
|
- Инициализировать семафор А (А 1)
|
| Поток 1
|
Поток 2
|
- Поток 1 первым получил процессорное время
- Захватить семафор А (А 0)
- Выполнить действия над ресурсом
- Отпустить семафор А (А 1)
- Разблокировка потока 2
|
- А захвачен в потоке 1
- Захватить семафор А (блокировка)
- Разблокировка, А 0
- Выполнить действия над ресурсом
- Отпустить семафор А (А 1)
|
Помимо семафоров, взаимное исключение может быть организовано и через другие способы синхронизации, например, через мониторы, если они поддерживаются используемым языком программирования. Мониторы позволяют защитить набор данных, скрывая от программиста детали синхронизации и предоставляя доступ к защищаемым данных только процедурам монитора, а реализация мониторов возлагается на компилятор и обычно основана на мьютексе или двоичном семафоре. По сравнению с семафорами мониторы позволяют уменьшить количество ошибок в программах, но несмотря на удобство использования, количество языков с поддержкой мониторов — небольшое[31].
Частой бывает задача разрешения или запрета для одной или более задач прохождения через определённые контрольные точки. Для решения данной задачи используется алгоритм на основе двух семафоров, который по своей работе напоминает турникет, поскольку позволяет единовременно пропускать только одну задачу. Турникет основывается на семафоре, который в контрольных точках захватывается и сразу же освобождается. Если требуется закрыть турникет, то семафор необходимо захватить, в результате чего все задачи, проходящие через турникет будут блокироваться. Если требуется снова разрешить задачам проходить через турникет, то достаточно отпустить семафор, после чего задачи будут по очереди продолжать исполнение[7].
У поочерёдного прохождения через турникет есть большой недостаток — на каждое прохождение может происходить лишнее переключение контекста между задачами, в результате чего будет снижаться производительность алгоритма. В некоторых случаях решением может быть использование многоместного турникета, который разблокирует сразу несколько задач, что может осуществляться, например, циклическим отпусканием семафора, если используемая реализация семафора не поддерживает увеличение на произвольное число[32].
| Инициализация
|
Турникет
|
Блокировка
|
Разблокировка
|
|
захватить(турникет)
отпустить(турникет)
|
|
|
Турникеты на основе семафоров могут использоваться, например, в механизмах организации барьеров[33] или блокировок чтения и записи[34].
Ещё одним типовым алгоритмом на основе семафоров является реализация выключателя. Задачи могут захватывать выключатель и освобождать его. Первая задача, которая захватывает выключатель, включает его. А последняя задача, которая его освобождает, — выключает. Для данного алгоритма можно провести аналогию с выключателем света в комнате. Первый, кто входит в комнату, — включает свет, а последний, кто выходит, — выключает[35].
Алгоритм может реализовываться на основе счётчика захвативших выключатель задач и семафора выключателя, операции над которыми должны защищаться мьютексом. При захвате выключателя счётчик увеличивается на 1, а если его значение изменилось с нуля на один, то семафор выключателя захватывается, что равносильно включению выключателя. При этом увеличение счётчика вместе с проверкой и захватом семафора являются атомарной операцией, защищаемой мьютексом. При отпускании выключателя счётчик уменьшается, а если его значения стало нулевым, то семафор выключателя отпускается, то есть выключатель переводится в выключенное состояние. Уменьшение счётчика вместе с его проверкой и отпусканием семафора тоже должны быть атомарной операцией[35].
|
|