Loading AI tools
Семафо́р (англ. 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]. Уменьшение значения семафора также иногда называют захватом (англ. acquire[20]), а увеличение значения — отпусканием или освобождением (англ. release[20])[21], что позволяет сделать описание работы семафора более понятным в контексте контроля использования какого-либо ресурса или при использовании в критических секциях.
В общем виде семафор можно представить как объект, состоящий из[22]:
- переменной-счётчика, хранящей текущее значение семафора;
- списка заблокированных в ожидании сигнального значения семафора задач;
- функций атомарного увеличения и уменьшения значения семафора.
Концепция семафора хорошо подходит для синхронизации потоков, может использоваться для синхронизации процессов, однако совершенно не подходит для синхронизации взаимодействия компьютеров. Семафор является низкоуровневым примитивом синхронизации, поэтому, за исключением защиты критических секций, сам по себе может быть сложен в использовании[23]. Другим, более низкоуровневым, примитивом синхронизации является фьютекс. Он может предоставляться операционной системой и хорошо подходит для реализации семафоров на прикладном уровне при использовании атомарных операций над разделяемым счётчиком[24].
Семафоры могут быть двоичными и вычислительными[3]. Вычислительные семафоры могут принимать целочисленные неотрицательные значения и используются для работы с ресурсами, количество которых ограничено[3], либо участвуют в синхронизации параллельно исполняемых задач. Двоичные семафоры могут принимать только значения 0 и 1[3] и используются для взаимного исключения одновременного нахождения двух или более процессов в своих критических секциях[4].
Мьютексные семафоры[3] (мьютексы) являются упрощённой реализацией семафоров, аналогичной двоичным семафорам с тем отличием, что мьютексы должны отпускаться тем же процессом или потоком, который осуществляет их захват[25], однако в зависимости от типа и реализации попытка освобождения другим потоком может как освободить мьютекс, так и вернуть ошибку[26]. Наряду с двоичными семафорами используются в организации критических участков кода[27][28]. В отличие от двоичных семафоров, начальное состояние мьютекса не может быть захваченным[29] и они могут поддерживать наследование приоритетов[30].
Легковесными семафорами называются семафоры, использующие активный цикл ожидания перед выполнением блокировки. Активный цикл ожидания в ряде случаев позволяет уменьшить количество системных вызовов[3].
Типовые алгоритмы
Сигнализирование
Сигнализирование, также называемое уведомлением, является базовым назначением семафоров, оно гарантирует исполнение участка кода одной задачи после исполнения участка кода другой задачи[6]. Сигнальное использование семафора обычно предполагает установку его начального значения в 0, чтобы ожидающие сигнального состояния задачи могли блокироваться до наступления события. Сигнализирование выполняется через увеличение значения семафора, а ожидание — через уменьшение значения[29].
| Основной поток | |
|---|---|
| |
| Поток 1 | Поток 2 |
|
|
Семафоры хорошо подходят для сигнализирования одной или нескольким задачам, количество которых заранее известно. Если количество ожидающих сигнального состояния задач заранее неизвестно, то обычно используются условные переменные.
Взаимное исключение
В многопоточных приложениях часто требуется, чтобы отдельные участки кода, называемые критическими секциями, не могли работать параллельно, например, при доступе к какому-либо неразделяемому ресурсу или при изменении общих ячеек памяти. Для защиты таких участков можно использовать двоичный семафор или мьютекс[3]. Мьютекс является более безопасным в использовании, поскольку может быть отпущен только тем процессом или потоком, который его захватил[5]. Также использование мьютекса вместо семафора может быть более производительным за счёт оптимизации под два значения на уровне реализации ассемблерного кода.
Начальным значением семафора выставляется единица, означая, что он не захвачен — в критическую секцию пока никто не вошёл. Входом (англ. enter) в критическую секцию является захват семафора — его значение уменьшается до 0, что делает повторную попытку входа в критическую секцию блокирующейся. При выходе (англ. leave) из критической секции семафор отпускается, и его значения становится равным 1, разрешая снова входить в критическую секцию, в том числе и другим потокам или процессам.
Для разных ресурсов могут быть разные семафоры, отвечающие за критические секции. Таким образом, критические секции, защищённые разными семафорами, могут работать параллельно.
| Основной поток | |
|---|---|
| |
| Поток 1 | Поток 2 |
|
|
Помимо семафоров, взаимное исключение может быть организовано и через другие способы синхронизации, например, через мониторы, если они поддерживаются используемым языком программирования. Мониторы позволяют защитить набор данных, скрывая от программиста детали синхронизации и предоставляя доступ к защищаемым данных только процедурам монитора, а реализация мониторов возлагается на компилятор и обычно основана на мьютексе или двоичном семафоре. По сравнению с семафорами мониторы позволяют уменьшить количество ошибок в программах, но несмотря на удобство использования, количество языков с поддержкой мониторов — небольшое[31].
Турникет
Частой бывает задача разрешения или запрета для одной или более задач прохождения через определённые контрольные точки. Для решения данной задачи используется алгоритм на основе двух семафоров, который по своей работе напоминает турникет, поскольку позволяет единовременно пропускать только одну задачу. Турникет основывается на семафоре, который в контрольных точках захватывается и сразу же освобождается. Если требуется закрыть турникет, то семафор необходимо захватить, в результате чего все задачи, проходящие через турникет будут блокироваться. Если требуется снова разрешить задачам проходить через турникет, то достаточно отпустить семафор, после чего задачи будут по очереди продолжать исполнение[7].
У поочерёдного прохождения через турникет есть большой недостаток — на каждое прохождение может происходить лишнее переключение контекста между задачами, в результате чего будет снижаться производительность алгоритма. В некоторых случаях решением может быть использование многоместного турникета, который разблокирует сразу несколько задач, что может осуществляться, например, циклическим отпусканием семафора, если используемая реализация семафора не поддерживает увеличение на произвольное число[32].
| Инициализация | Турникет | Блокировка | Разблокировка |
|---|---|---|---|
турникет = Семафор(1)
| захватить(турникет)
отпустить(турникет)
| захватить(турникет)
| отпустить(турникет)
|
Псевдокод турникета
Турникеты на основе семафоров могут использоваться, например, в механизмах организации барьеров[33] или блокировок чтения и записи[34].
Выключатель
Ещё одним типовым алгоритмом на основе семафоров является реализация выключателя. Задачи могут захватывать выключатель и освобождать его. Первая задача, которая захватывает выключатель, включает его. А последняя задача, которая его освобождает, — выключает. Для данного алгоритма можно провести аналогию с выключателем света в комнате. Первый, кто входит в комнату, — включает свет, а последний, кто выходит, — выключает[35].
Алгоритм может реализовываться на основе счётчика захвативших выключатель задач и семафора выключателя, операции над которыми должны защищаться мьютексом. При захвате выключателя счётчик увеличивается на 1, а если его значение изменилось с нуля на один, то семафор выключателя захватывается, что равносильно включению выключателя. При этом увеличение счётчика вместе с проверкой и захватом семафора являются атомарной операцией, защищаемой мьютексом. При отпускании выключателя счётчик уменьшается, а если его значения стало нулевым, то семафор выключателя отпускается, то есть выключатель переводится в выключенное состояние. Уменьшение счётчика вместе с его проверкой и отпусканием семафора тоже должны быть атомарной операцией[35].
| Тип данных | Инициализация | Использование |
|---|---|---|
Выключатель:
количество = 0
мьютекс = Семафор(1)
Выключатель,
заблокировать(целевой-семафор):
захватить(мьютекс)
количество += 1
если количество == 1:
захватить(целевой-семафор)
освободить(мьютекс)
Выключатель,
разблокировать(целевой-семафор):
захватить(мьютекс)
количество -= 1
если количество == 0:
освободить(целевой-семафор)
освободить(мьютекс)
| выключатель = Выключатель()
семафор = Семафор(1)
| заблокировать(выключатель, семафор)
// Критическая секция выключателя,
// семафор заблокирован
разблокировать(выключатель, семафор)
|
Псевдокод алгоритма работы выключателя
Алгоритм выключателя используется в более сложном механизме — блокировках чтения и записи[35].
Задача производителя и потребителя
Задача производителя потребителя предполагает производство какой-либо информации одной задачей и передачу этой информации другой задаче для обработки. В многопоточных системах одновременное производство и потребление может приводить к состоянию гонки, что требует использования критических секций или других способов синхронизации. Семафор является наиболее простым примитивом синхронизации, с помощью которого можно решать задачу производителя и потребителя.
Передача данных через кольцевой буфер
Кольцевой буфер представляет собой буфер с фиксированным количеством элементов, данные в который заносятся и обрабатываются в порядке очереди (FIFO). В однопоточном варианте исполнения для организации такого буфера достаточно 4-х ячеек памяти:
- общее количество элементов в буфере,
- количество занятых или количество свободных элементов в буфере,
- порядковый номер текущего элемента,
- порядковый номер следующего элемента.
В многозадачной реализации алгоритм усложняется необходимостью синхронизации задач. Для случая двух задач (производитель и потребитель) можно ограничиться двумя ячейками памяти и двумя семафорами[8]:
- индекс следующего элемента, доступного на чтение,
- индекс следующего элемента, доступного на запись,
- семафор, разрешающий чтение очередного элемента,
- семафор, разрешающий запись очередного свободного элемента буфера.
Начальное значение семафора, отвечающего за чтение, устанавливается в 0, потому что очередь пуста. А значение семафора, отвечающего за запись, выставляется равным общему размеру буфера, то есть весь буфер доступен для заполнения. Перед заполнением очередного элемента в буфере семафор на запись уменьшается на 1, резервируя очередной элемент очереди для записи данных, после чего изменяется индекс на запись, а семафор на чтение увеличивается на 1, разрешая чтение добавленного в очередь элемента. Читающая задача, наоборот, захватывает семафор на чтение, после чего считывает очередной элемент из буфера и изменяет индекс следующего элемента на чтение, а затем отпускает семафор на запись, разрешая запись пишущей задаче в освободившийся элемент[8].
| Инициализация | Использование |
|---|---|
размер-буфера = N
разрешение-записи = Семафор(размер-буфера)
разрешение-чтения = Семафор(0)
на-запись = 0
на-чтение = 0
буфер = Массив(размер-буфера)
| // Пишущая задача
произведённый-элемент = произвести-элемент()
захватить(разрешение-записи)
буфер[на-запись] = произведённый-элемент
на-запись += 1
если на-запись >= размер-буфера:
на-запись = 0
отпустить(разрешение-чтения)
// Читающая задача
захватить(разрешение-чтения)
прочитанный-элемент = буфер[на-чтение]
на-чтение += 1
если на-чтение >= размер-буфера:
на-чтение = 0
отпустить(разрешение-записи)
обработать(прочитанный-элемент)
|
Псевдокод кольцевого буфера
Если кольцевой буфер реализуется для множества пишущих и читающих задач, то к реализации добавляется мьютекс, который блокирует буфер при записи в него или чтении из него[36].
Передача данных через произвольный буфер
Помимо передачи данных через кольцевой буфер, возможна передача и через произвольный, но в таком случае запись и чтение данных требуется защищать мьютексом, а семафор используется для оповещения читающей задачи о наличии очередного элемента в буфере. Пишущая задача добавляет в буфер элемент под защитой мьютекса, а затем сигнализирует о его наличии. Читающая же задача захватывает семафор, а затем, под защитой мьютекса, — получает очередной элемент. Стоит упомянуть, что попытка захвата семафора под защитой мьютекса может приводить к взаимоблокировке в случае попытки чтения из пустого буфера, а отпускание семафора внутри критической секции может слегка снизить производительность. Данный алгоритм, как и в случае с кольцевым буфером, защищённым мьютексом, позволяет писать и читать одновременно нескольким задачам[37].
В механизмах синхронизации
Барьер
Барьер представляет собой механизм синхронизации критических точек у группы задач. Задачи могут пройти через барьер только все сразу. Перед входом в критические точки задачи группы должны блокироваться, пока входа в критическую точку не достигнет последняя задача из группы. Как только все задачи окажутся перед входом в свои критические точки, они должны продолжить своё исполнение[9].
Самое простое решение для организации барьера в случае двух задач основывается на двух бинарных семафорах А и Б, инициализируемых нулевым значением. В критической точке первой задачи необходимо перевести в сигнальное состояние семафор Б, а затем захватить семафор А. В критической точке второй задачи необходимо сначала перевести в сигнальное состояние семафор А, а затем — захватить Б. Какая бы задача не дошла до критической точки первой, она просигнализирует другой задаче, разрешив её исполнение. Как только обе задачи достигнут своих критических точек, их семафоры окажутся в сигнальном состоянии, что позволит им продолжить своё исполнение[38].
| Инициализация | Задача, использующая барьер |
|---|---|
целевое-количество = N
количество = 0
мьютекс = Семафор(1)
входной-турникет = Семафор(0)
| // Первая фаза барьера
захватить(мьютекс)
количество += 1
если количество == количество-задач:
отпустить(входной-турникет)
отпустить(мьютекс)
захватить(входной-турникет)
отпустить(входной-турникет)
// Критическая точка
|
Псевдокод простого барьера
Подобная реализация — однопроходная, поскольку барьер не возвращается в исходное состояние, также у неё низкая производительность из-за использования одноместного турникета, что требует переключения контекста для каждой задачи, поэтому на практике данное решение малоприменимо[32].
Двухфазный барьер
Особенностью двухфазного барьера является то, что при его использовании каждая задача останавливается на барьере дважды — до критической точки и после. Два останова позволяют сделать барьер реентерабельным, поскольку второй останов позволяет вернуть барьер в изначальное состояние[39].
Универсальный реентерабельный алгоритм механизма двухфазного барьера может быть основан на использовании счётчика дошедших до критической точки задач и двух многоместных турникетов. Операции над счётчиком и управление турникетами должны быть защищены мьютексом. При этом должно быть заранее известно общее количество задач. Первый турникет пропускает задачи к критической точке и изначально должен быть заблокирован. Второй — пропускает задачи, которые только что прошли критическую точку, и изначально тоже должен быть заблокирован. Перед подходом к критической точке счётчик дошедших задач увеличивается на 1, а как только он достигает общего количества задач, то первый турникет разблокируется для всех задач, пропуская их к критической точке, что происходит атомарно через мьютекс вместе с увеличением счётчика и его проверкой. После критической точки, но до второго турникета, счётчик количества задач уменьшается на 1. По достижении нулевого значения второй турникет разблокируется для всех задач, при этом операции над вторым турникетом тоже происходят атомарно вместе с уменьшением счётчика и его проверкой. В результате все задачи останавливаются сначала перед критической точкой, а затем — после. После прохождения барьера состояния счётчика и турникетов оказываются в изначальных значениях[32].
| Инициализация | Задача, использующая барьер |
|---|---|
мьютекс = Семафор(1)
количество = 0
входной-турникет = Семафор(0)
выходной-турникет = Семафор(0)
| // Первая фаза барьера
захватить(мьютекс)
количество += 1
если количество == количество-задач:
освободить(входной-турникет, количество)
освободить(мьютекс)
захватить(входной-турникет)
// Критическая точка
// Вторая фаза барьера
захватить(мьютекс)
количество -= 1
если количество == 0:
освободить(выходной-турникет, количество)
освободить(мьютекс)
захватить(выходной-турникет)
|
Псевдокод реентерабельного алгоритма двухфазного барьера
Условная переменная
Условная переменная представляет собой способ оповещения ожидающих задач о возникновении какого-либо события[3]. Механизм условной переменной на прикладном уровне обычно строится на основе фьютекса и предусматривает функции ожидания события и отправки сигнала о его возникновении, но отдельные части этих функций должны защищаться мьютексом или семафором, поскольку помимо фьютекса в механизме условной переменной обычно присутствуют дополнительные разделяемые данные[40]. В простых реализациях фьютекс можно заменить семафором, который при оповещении необходимо будет отпустить столько раз, сколько задач подписалось на условную переменную, однако при большом количестве подписчиков оповещение может стать узким местом[41].
Механизм условной переменной предполагает наличие трёх операций: ожидание события, сигнализирование о событии одной задаче и оповещение всех задач о событии. Для реализации алгоритма на основе семафоров потребуются: мьютекс или двоичный семафор для защиты, собственно, самой условной переменной, счётчик количества ожидающих задач, мьютекс для защиты счётчика, семафор А для блокировки ожидающих задач и дополнительный семафор Б для своевременного пробуждения очередной ожидающей задачи[42].
При подписке на события счётчик подписавшихся задач атомарно увеличивается на 1, после чего отпускается предварительно захваченный мьютекс условной переменной. Затем захватывается семафор А для ожидания наступления события. По наступлении события сигнализирующая задача атомарно проверяет счётчик подписавшихся задач и оповещает очередную задачу о наступлении события, отпуская семафор А, а затем блокируется по семафору Б в ожидании подтверждения разблокировки. Получившая оповещение задача отпускает семафор Б и снова захватывает мьютекс условной переменной для возврата в изначальное состояние. Если же делается широковещательное оповещение всех подписанных задач, то семафор заблокированных задач А отпускается в цикле по количеству подписанных задач в счётчике. При этом оповещение происходит атомарно под защитой мьютекса счётчика, чтобы счётчик не мог измениться во время оповещения[42].
| Объявление типа | Использование |
|---|---|
Условная-переменная():
количество = 0
мьютекс = Семафор(1)
ожидание-события = Семафор(0)
получение-события = Семафор(0)
Условная-переменная,
ожидать(целевой-мьютекс):
захватить(мьютекс)
количество += 1
отпустить(мьютекс)
отпустить(целевой-мьютекс)
захватить(ожидание-события)
отпустить(получение-события)
захватить(целевой-мьютекс)
Условная-переменная,
оповестить():
захватить(мьютекс)
если количество > 0:
количество -= 1
отпустить(ожидание-события)
захватить(получение-события)
отпустить(мьютекс)
Условная-переменная,
опосестить-всех():
захватить(мьютекс)
если количество > 0:
отпустить(ожидание-события, количество)
захватить(получение-события, количество)
количество = 0
отпустить(мьютекс)
| // Инициализация
событие = Условная-переменная()
мьютекс = Семафор(1)
// Ожидание события
захватить(мьютекс)
ожидать(событие)
// Критическая секция события
отпустить(мьютекс)
// Оповещение одной задачи
оповестить(событие)
// Оповещение всех задач
оповестить-всех(событие)
|
Псевдокод условной переменной
У решения на семафорах есть одна значимая проблема — два переключения контекста по сигнализированию, что сильно снижает производительность алгоритма, поэтому как минимум на уровне операционных систем оно обычно не применяется[42].
Интересным фактом является то, что сам семафор легко реализуется на основе условной переменной и мьютекса[24], а реализация условной переменной на основе семафоров — намного сложнее[42].
Блокировки чтения и записи
Одной из классических проблем является синхронизация доступа к ресурсу, доступному одновременно на чтение и на запись. Блокировки чтения и записи призваны решить эту проблему и позволяют организовать раздельную блокировку ресурса на чтение и на запись, разрешая одновременное чтение, но запрещая одновременную запись. Запись также блокирует любое чтение[10]. Эффективный механизм не может быть построен на базе одного лишь фьютекса, счётчик количества читателей может изменяться без разблокирования каких-либо задач[24]. Блокировки чтения и записи могут быть реализованы на основе комбинации мьютексов и семафоров или мьютексов и условной переменной.
Универсальный алгоритм, лишённый проблемы ресурсного голодания пишущих задач, включает в себя выключатель бинарного семафора А для организации критической секции читающих задач и турникет для блокировки новых читающих задач при наличии ожидающих пишущих. При появлении первой читающей задачи она захватывает семафор А с помощью выключателя, запрещая запись. Для пишущих задач семафор А защищает критическую секцию записи, поэтому, если он захвачен читающими задачами, все пишущие задачи блокируются при входе в свою критическую секцию. Однако захват пишущими задачами семафора А с последующей записью защищается семафором турникета. Поэтому, если произошла блокировка пишущей задачи из-за наличия читающих, турникет блокируется вместе с новыми читающими задачами. Как только последняя читающая заканчивает свою работу, семафор выключателя отпускается, и первая в очереди пишущая задача разблокируется. По окончании своей работы она отпускает семафор турникета, снова разрешая работу читающих задач[34].
| Инициализация | Читающая задача | Пишущая задача |
|---|---|---|
выключатель = Выключатель()
разрешение-записи = Семафор(1)
турникет = Семафор(1)
| захватить(турникет)
освободить(турникет)
заблокировать(выключатель, разрешение-записи)
// Критическая секция читающей задачи
разблокировать(выключатель, разрешение-записи)
| захватить(турникет)
захватить(разрешение-записи)
// Критическая секция пишущей задачи
отпустить(турникет)
отпустить(разрешение-записи)
|
Псевдокод универсального алгоритма блокировок чтения-записи
На уровне операционных систем существуют реализации семафоров чтения и записи, которые специальным образом модифицируются для повышения эффективности при массовом использовании[43].
В классических задачах
Обедающие философы
Одной из классических задач синхронизации является задача об обедающих философах. Задача включает в себя 5 обедающих за круглым столом философов, 5 тарелок, 5 вилок и общее блюдо с макаронами посреди стола. Перед каждым философом есть тарелка, а справа и слева — по одной вилке, но каждая вилка является общей между двумя соседними философами, а есть макароны можно только двумя вилками одновременно. При этом каждый из философов может или думать, или есть макароны[44].
Философами представлены взаимодействующие в программе потоки, а решение задачи включает в себя ряд условий[44]:
- между философами не должно быть взаимоблокировок;
- ни один философ не должен голодать, ожидая освобождение вилки;
- должно быть возможным, чтобы одновременно ели хотя бы два философа.
Для решения задачи каждой вилке можно назначить двоичный семафор. Когда философ пытается взять вилку, семафор захватывается, а как только он заканчивает есть, семафоры вилок отпускаются. Проблема заключается в том, что вилку уже мог взять сосед, тогда философ блокируется до тех пор, пока его сосед не поест. Если одновременно все философы начнут приём пищи, то возможна взаимоблокировка[44].
Решением взаимоблокировки может быть ограничение количества одновременно обедающих философов до 4-х. В таком случае по крайней мере один философ сможет обедать, пока остальные ожидают. Ограничение можно реализовать через семафор с начальным значением 4. Каждый из философов будет захватывать данный семафор перед тем как взять вилки, а после приёма пищи — отпускать. Также данное решение гарантирует отсутствие голодания у философов, поскольку, если философ ожидает освобождения вилки соседом, тот рано или поздно её отпустит[44].
Существует и более простое решение. Взаимоблокировка возможна, если одновременно 5 философов держат вилку в одной и той же руке, например, если они все правши и вначале взяли правую вилку. Если же один из философов является левшой и берёт вначале левую вилку, то невозможны ни взаимоблокировка, ни голодание. Таким образом, достаточно, чтобы у одного из философов сначала захватывался семафор левой вилки, а затем — правой, в то время как у остальных философов — наоборот[44].
Американские горки
Другой классической задачей является задача об американских горках, согласно которой состав вагонеток полностью заполняется пассажирами, затем катает их по кругу и возвращается назад за новыми. По условиям задачи количество желающих пассажиров превышает количество мест в составе, таким образом, очередные пассажиры ожидают своей очереди, пока состав едет по кругу. Если состав имеет М мест, то сначала состав должен ожидать, пока на свои места не сядут М пассажиров, затем он должен прокатить их, подождать, пока они все выйдут и снова ожидать новых пассажиров[45].
Состав вагонеток вместе с пассажирами можно представить как взаимодействующие задачи. Каждый пассажир должен блокироваться в ожидании своей очереди, а сам состав должен блокироваться на этапах заполнения и освобождения мест. Для загрузки и выгрузки состава можно воспользоваться двумя семафорами с выключателями, защищёнными каждый своим мьютексом, а для блокирования пассажиров на загрузку и на выгрузку можно использовать два семафора, отвечающие за места в вагонетках. Ожидающие пассажиры захватывают семафор на загрузку, а состав семафором на загрузку оповещает M из них о наличии свободных мест. Затем состав блокируется по выключателю, пока последний усаживающийся пассажир не просигнализирует соответствующим семафором, после чего начинается поездка. Перед поездкой пассажиры блокируются по семафору на выгрузку, что не даёт им выйти из состава. После поездки состав оповещает M пассажиров семафором на выгрузку, разрешая им выйти, а затем блокируется по семафору выключателя на выгрузку, ожидая, пока все пассажиры не выйдут. Как только последний пассажир выйдет из состава, он просигнализирует семафором второго выключателя и разрешит составу снова набирать пассажиров[45].
Ограничения семафоров
Концепция семафора предусматривает лишь операции уменьшения и увеличения на 1. При этом задача, уменьшающая семафор, обычно не может узнать, будет ли она заблокирована по нему или нет. При сигнализировании же нет возможности узнать, есть ли заблокированные по семафору задачи, а если задача сигнализирует семафором другой, заблокированной, — то обе задачи продолжают работать параллельно и нет никакой возможности узнать, какая из них получит процессорное время следующей[17].
Несмотря на ограничения концепции семафоров, конкретные их реализации могут быть лишены тех или иных ограничений. Например, возможность увеличения значения семафора на произвольное число предусмотрена в реализациях Linux[46], Windows[41] и System V (POSIX)[47]. А семафоры POSIX позволяют определить, будет ли блокировка по захвату семафора[48].
Сильные и слабые семафоры
Помимо ограничений самой концепции семафора, существуют и ограничения, накладываемые операционной системой или конкретной реализацией семафора. За распределение процессорного времени между процессами и потоками обычно отвечает планировщик задач операционной системы. Использование семафоров предъявляет ряд требований к планировщику и самой реализации семафоров для предотвращения ресурсного голодания, которое недопустимо в многозадачных приложениях[49].
- Если есть хотя бы одна задача, готовая к исполнению, она должна исполняться[49].
- Если задача готова к исполнению, время до начала её исполнения должно быть конечным[49].
- Если происходит сигнализирование семафором, по которому есть заблокированные задачи, то, по крайней мере, одна из них должна перейти в состояние готовности к исполнению[49].
- Если задача заблокирована по семафору, то количество других задач, которые будут разблокированы по тому же семафору до заданной, должно быть конечным[49].
Первые два требования необходимы, чтобы любая задача могла получить процессорное время и не находилась бесконечно в состоянии готовности, что уже позволяет писать приложения без ресурсного голодания. Третье требование необходимо для предотвращения ресурсного голодания при взаимном исключении, построенном на семафорах. Если сигнализирование будет лишь увеличивать счётчик семафора, но не будет пробуждать заблокированную по нему задачу, то возможна ситуация, когда одна и та же задача бесконечно отпускает и захватывает семафор, а другие заблокированные задачи не успевают перейти в состояние готовности, либо переходят, но гораздо реже. Однако даже при соблюдении третьего требования в случае большого количества заблокированных задач возможно ресурсное голодание, если каждый раз разблокируются одни и те же задачи. Данную проблему решает четвёртое требование, которое соблюдается, например, если заблокированные по семафору задачи пробуждаются в порядке очереди[49].
Соблюдение первых трёх требований позволяет реализовать так называемые слабые семафоры, а соблюдение всех четырёх — сильные[49].
Взаимные блокировки
При неправильном использовании семафоров могут возникать взаимные блокировки[50] — ситуации, когда две или более параллельных задач оказываются заблокированными, ожидая события друг от друга[11]. В такой ситуации задачи не смогут нормально продолжить своё исполнение и обычно один или более процессов требуется завершить принудительно. Взаимные блокировки могут быть как результатом простых ошибок работы с семафорами или другими способами синхронизации, так и вследствие состояния гонки, которое является более сложным в отладке.
Типовой ошибкой является вызов внутри критической секции подпрограммы, использующей ту же самую критическую секцию[51].
Наглядным примером взаимной блокировки могут служить вложенные друг в друга захваты бинарных семафоров А и Б, защищающих разные ресурсы, при условии обратного порядка их захвата в одном из потоков, что может быть обусловлено, например, стилевыми отличиями в написании кода программы. Ошибкой подобной реализации является состояние гонки, из-за которого программа может работать большую часть времени, но в случае параллельного захвата ресурсов высоки шансы на взаимную блокировку[52].
| Основной поток | |
|---|---|
| |
| Поток 1 | Поток 2 |
|
|
Ресурсное голодание
Схожей с взаимной блокировкой является проблема ресурсного голодания, которая может и не приводить к полному прекращению работы, но может оказаться крайне негативной при реализации алгоритма. Суть проблемы заключается в периодических или частых отказах в получении ресурса из-за его захвата другими задачами[12].
Типичным случаем для данной проблемы является простая реализация блокировок чтения и записи, при которой происходит запрет ресурса на запись при осуществлении чтения. Периодическое появление новых читающих задач может привести к неограниченной блокировке ресурса на запись. При слабой нагрузке на систему проблема может не проявляться длительное время, однако при высокой нагрузке может возникнуть ситуация, когда в каждый момент времени есть по крайней мере одна читающая задача, что сделает блокировку на запись постоянной на время высокой нагрузки[12]. При наличии семафора, отпускаемого при опустении очереди читающих задач, простым решением может быть добавление двоичного семафора (или мьютекса) для защиты кода пишущих задач, который в то же время будет выступать в роли турникета для читающих задач. Пишущие задачи будут входить в критическую секцию и захватывать семафор пустой очереди, блокируясь по двум семафорам, пока есть читающие задачи. Читающие задачи будут блокироваться при входе в турникет, если пишущая задача ожидает окончания работы читающих. Как только последняя читающая задача закончит свою работу, она отпустит семафор пустой очереди, разблокировав ожидающую пишущую задачу[34].
Ресурсному голоданию может быть подвержено и взаимное исключение, если его реализация будет основана на слабых семафорах, однако существуют алгоритмы, позволяющие обходить ограничения слабых семафоров в данном случае[49].
Инверсия приоритетов
Другой проблемой может быть инверсия приоритетов, которая может проявиться при использовании семафоров процессами реального времени. Процессы реального времени могут быть прерваны операционной системой только для исполнения процессов с бо́льшим приоритетом. В этом случае процесс может заблокироваться по семафору в ожидании его отпускания процессом с меньшим приоритетом. Если в это время будет работать процесс со средним между двумя процессами приоритетом, то процесс с высоким приоритетом может оказаться заблокированным на неограниченный промежуток времени[13].
Проблема инверсии приоритетов решается наследованием приоритетов[14]. По возможности семафоры могут быть заменены на мьютексы, поскольку у мьютексов наследование приоритетов может быть заранее предусмотрено. Таким образом, при захвате мьютекса потоком с бо́льшим приоритетом произойдёт упреждающее повышение приоритета у задачи, владеющей мьютексом, для его скорейшего отпускания[30].
Повсеместное наследование приоритетов является крайне сложной в реализации задачей, поэтому поддерживающие её системы могут иметь лишь частичную реализацию. Также наследование приоритетов создаёт другие проблемы, например, к невозможности совмещения кода с наследованием приоритетов с кодом без наследования при использовании одной и той же критической секции[54].
При необходимости использования семафоров или при отсутствии поддержки наследования приоритетов алгоритмы могут модифицироваться для самостоятельного повышения приоритетов задачами[54].
Семафоры в POSIX
Стандарты POSIX на уровне операционных систем предоставляют API языка Си для работы с семафорами как на уровне потоков, так и на уровне процессов через разделяемую память. Стандарты определяют тип данных семафора sem_t и набор функций для работы с ним[55]. Семафоры POSIX доступны в Linux, macOS, FreeBSD и других POSIX-совместимых операционных системах.
| Функция | Описание |
|---|---|
sem_init()[док. 1] |
Инициализация семафора с заданием начального значения счётчика и флага использования на уровне процессов. |
sem_destroy()[док. 2] |
Освобождение семафора. |
sem_open()[док. 3] |
Создание нового или открытие существующего именованного семафора. |
sem_close()[док. 4] |
Закрытие семафора после окончания работы с ним. |
sem_unlink()[док. 5] |
Удаление имени у именованного семафора (не уничтожает его). |
sem_wait()[док. 6] |
Уменьшение значения семафора на 1. |
sem_timedwait()[док. 7] |
Уменьшение значения семафора на 1 с ограничением максимального времени блокировки, по истечении которого возвращается ошибка. |
sem_trywait()[док. 8] |
Попытка уменьшения значения семафора в неблокирующемся режиме, возвращает ошибку, если уменьшение без блокировки невозможно. |
sem_post()[док. 9] |
Увеличение значения семафора на 1. |
sem_getvalue()[док. 10] |
Получение текущего значения семафора. |
Одним из недостатков семафоров POSIX является способствующая ошибкам спецификация функции sem_timedwait(), которая оперирует часами реального времени (CLOCK_REALTIME)[56] вместо времени непрерывной работы системы (CLOCK_MONOTONIC), что может приводить к сбоям в работе программ при изменении системного времени и может оказаться критичным для встраиваемых устройств[57], но некоторые операционные системы реального времени предлагают аналоги данной функции, работающие с временем непрерывной работы системы[58]. Другим недостатком является отсутствие поддержки ожидания одновременно нескольких семафоров или семафора и файлового дескриптора.
В Linux семафоры POSIX реализованы в библиотеке Glibc на основе фьютекса[59].
Семафоры System V
Стандарты POSIX также определяют набор функций из стандарта X/Open System Interfaces (XSI) для межпроцессовой работы с семафорами в рамках операционной системы[60]. В отличие от обычных семафоров семафоры XSI можно увеличивать и уменьшать на произвольное число, они выделяются массивами, и их время жизни распространяется не на процессы, а на операционную систему. Таким образом, если забыть закрыть семафор XSI по завершении всех процессов приложения, то он продолжит существовать в операционной системе, что называется утечкой ресурса. В сравнении с семафорами XSI обычные семафоры POSIX намного проще в использовании, и у них может быть выше быстродействие[61].
Наборы семафоров XSI в рамках системы идентифицируются по числовому ключу типа key_t, однако можно создавать анонимные наборы семафоров для использования в рамках приложения, если указывать константу IPC_PRIVATE вместо числового ключа[62].
| Функция | Описание |
|---|---|
semget()[док. 11] |
Создаёт или получает идентификатор набора семафоров с заданным числовым ключом[62]. |
semop()[док. 12] |
Выполняет атомарные операции уменьшения и увеличения на заданное число счётчика семафора по его номеру из набора с заданным идентификатором, а также позволяет заблокироваться в ожидании нулевого значения счётчика семафора, если в качестве заданного числа указан 0[47]. |
semctl()[док. 13] |
Позволяет управлять семафором по его номеру из набора с заданным идентификатором, в том числе получать и устанавливать текущее значение счётчика; также отвечает за уничтожение набора семафоров[63]. |
Семафоры в Linux
Операционные системы семейства Linux поддерживают семафоры POSIX, но также предлагают альтернативу семафорам в виде счётчика, привязанного к файловому дескриптору через системный вызов eventfd()[док. 14] с флагом EFD_SEMAPHORE. При чтении такого счётчика через функцию read() он уменьшается на 1, если его значение было ненулевым. Если же значение было нулевым, то происходит блокировка (если не указан флаг EFD_NONBLOCK), как и в случае с обычными семафорами. Функция write() увеличивает значение счётчика на число, которое записывается по файловому дескриптору. Преимуществом такого семафора является возможность ожидания сигнального состояния семафора наряду с другими событиями с помощью системных вызовов select() или poll()[46].
Семафоры в Windows
Windows также предоставляет API языка Си для работы с семафорами. Потоки, заблокированные по семафору, выстраиваются в очередь FIFO, но могут перейти в конец очереди в случае прерывания потока для обработки других событий[19].
| Функция | Описание |
|---|---|
Группа функций CreateSemaphore[док. 15] |
Создание семафора с указанием начального значения счётчика, максимального значения и имени семафора. |
OpenSemaphoreW()[док. 15] |
Получение доступа к семафору по его имени, если он уже существует. |
CloseHandle()[док. 16] |
Закрытие семафора после окончания работы с ним. |
WaitForSingleObject()[док. 17] или WaitForMultipleObjects()[док. 18] |
Уменьшение значения семафора на 1 с блокировкой в случае нулевого значения счётчика; позволяет ограничивать максимальное время блокировки. |
ReleaseSemaphore()[док. 19] |
Увеличение значения семафора на указанную величину. |
Особенностями семафоров под Windows является возможность увеличивать семафор на произвольное число[41] и возможность ожидания его сигнального состояния вместе с блокирующим ожиданием других семафоров или объектов[64].
Поддержка в языках программирования
Семафоры обычно не поддерживаются на уровне языка программирования в явном виде, но часто предоставляются встроенными или сторонними библиотеками. В некоторых языках, таких как Ada[65] и Go[66], семафоры легко реализуются средствами языка.
| Язык | Модуль или библиотека | Тип данных |
|---|---|---|
| Ada | GNAT.Semaphores[док. 20] |
Counting_Semaphore, Binary_Semaphore |
| C++ | Boost |
boost::interprocess::interprocess_semaphore[док. 21] |
| C# | System.Threading[док. 22] |
Semaphore[док. 23] |
| D | core.sync.semaphore[док. 24] |
Semaphore[док. 25] |
| Go | golang.org/x/sync/semaphore[док. 26] |
Weighted |
| Java | java.util.concurrent[док. 27] |
java.util.concurrent.Semaphore[док. 28] |
| Python | threading[док. 29], asyncio[док. 30] |
threading.Semaphore[док. 31], asyncio.Semaphore[док. 32] |
Защита критической секции
Самым простым примером использования семафора может служить взаимное исключение возможности исполнения критических участков кода у потоков или процессов. Для организации взаимного исключения может служить двоичный семафор и две функции: входа в критическую секцию и выхода из неё. Для упрощения в пример не включена возможность запоминания идентификатора захватившего потока и идентификатора процесса, которому поток принадлежит. Также предполагается, что критическая секция имеет конечное не очень большое время исполнения, поэтому прерывания операции захвата семафора (EINTR) игнорируются, а обработку результатов прерывания можно осуществлять после критической секции. Сам семафор проабстрагирован в структуру для повышения читабельности кода.
В примере запускаются два потока, один из которых увеличивает счётчик, а другой — уменьшает. Поскольку счётчик является разделяемым ресурсом, доступ к нему должен быть взаимоисключающим, в противном случае один поток может перезаписывать результаты операций другого, а итоговое результирующее значение может оказаться ошибочным. Поэтому счётчик защищается проабстрагированным двоичным семафором, реализующим взаимное исключение.
Пример простой реализации критической секции на основе семафора на языке Си (POSIX)
#include <errno.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#ifndef __STDC_LIB_EXT1__
typedef int errno_t;
#endif
enum {
EOK = 0,
};
// Упрощённая реализация мьютекса
struct guard_t {
sem_t sem_guard;
};
typedef struct guard_t guard_t;
// Инициализация упрощённого мьютекса
errno_t guard_init(guard_t *guard, bool between_processes)
{
int r;
r = sem_init(&guard->sem_guard, between_processes, 1);
if (r == -1) {
return errno;
}
return EOK;
}
// Освобождение упрощённого мьютекса
void guard_free(guard_t *guard)
{
sem_destroy(&guard->sem_guard);
}
// Вход в критическую секцию
errno_t guard_enter(guard_t *guard)
{
int r;
do {
r = sem_wait(&guard->sem_guard);
} while ((r == -1) && (errno == EINTR));
if (r == -1) {
return errno;
}
return EOK;
}
// Выход из критической секции
errno_t guard_leave(guard_t *guard)
{
int r;
r = sem_post(&guard->sem_guard);
if (r == -1) {
return errno;
}
return EOK;
}
// Счётчик, защищённый упрощённым мьютексом
struct safe_counter_t {
guard_t lock;
int counter;
};
enum {
// Количество операций уменьшения/увеличения
OPERATIONS_COUNT = 100000,
};
// Поток, увеличивающий счётчик
void *thread_inc_func(void *thread_data)
{
struct safe_counter_t *safe_counter = thread_data;
for (int i = 0; i < OPERATIONS_COUNT; ++i) {
guard_enter(&safe_counter->lock);
++safe_counter->counter;
guard_leave(&safe_counter->lock);
}
}
// Поток, уменьшающий счётчик
void *thread_dec_func(void *thread_data)
{
struct safe_counter_t *safe_counter = thread_data;
for (int i = 0; i < OPERATIONS_COUNT; ++i) {
guard_enter(&safe_counter->lock);
--safe_counter->counter;
guard_leave(&safe_counter->lock);
}
}
// Вывод сообщения об ошибке согласно её коду
void print_error(errno_t errnum, const char *error_text)
{
errno = errnum;
perror(error_text);
}
int main(int argc, char **argv)
{
errno_t errnum;
// Инициализация
struct safe_counter_t safe_counter;
safe_counter.counter = 0;
guard_t lock;
errnum = guard_init(&safe_counter.lock, false);
if (errnum) {
print_error(errnum, "Ошибка инициализации взаимного исключения lock");
exit(EXIT_FAILURE);
}
// Запуск двух потоков
pthread_t thread_inc;
errnum = pthread_create(&thread_inc, NULL, thread_inc_func, &safe_counter);
if (errnum) {
print_error(errnum, "Ошибка создания потока thread_inc");
exit(EXIT_FAILURE);
}
pthread_t thread_dec;
errnum = pthread_create(&thread_dec, NULL, thread_dec_func, &safe_counter);
if (errnum) {
print_error(errnum, "Ошибка создания потока thread_dec");
exit(EXIT_FAILURE);
}
// Ожидание, пока потоки закончат исполнение
errnum = pthread_join(thread_inc, NULL);
if (errnum) {
print_error(errnum, "Ошибка ожидания потока thread_inc");
exit(EXIT_FAILURE);
}
errnum = pthread_join(thread_dec, NULL);
if (errnum) {
print_error(errnum, "Ошибка ожидания потока thread_dec");
exit(EXIT_FAILURE);
}
// Освобождение данных
guard_free(&lock);
// Вывод результата работы потоков, «0»
printf("Counter: %d\n", safe_counter.counter);
return EXIT_SUCCESS;
}
Пример синхронизации кольцевого буфера
Синхронизация кольцевого буфера выполняется немного сложнее, нежели защита критической секции: семафоров становится уже два и к ним добавляются дополнительные переменные. В примере приведены структура и основные функции, необходимые для синхронизации кольцевого буфера на языке Си, используя интерфейс POSIX. Данная реализация позволяет одному потоку циклически записывать данные в кольцевой буфер, а другому потоку — асинхронно циклически читать из него.
Пример реализации синхронизирующего примитива для кольцевого буфера с помощью семафоров на языке Си (POSIX)
#include <errno.h>
#include <semaphore.h>
#include <stdio.h>
#ifndef __STDC_LIB_EXT1__
typedef int errno_t;
#endif
enum {
EOK = 0,
};
struct ring_buffer_t {
size_t length;
size_t w_index;
size_t r_index;
sem_t sem_r;
sem_t sem_w;
};
errno_t ring_buffer_init(struct ring_buffer_t *rbuf, size_t length)
{
rbuf->length = length;
rbuf->r_index = 0;
rbuf->w_index = 0;
int r;
r = sem_init(&rbuf->sem_r, 1, 0);
if (r == -1) {
return errno;
}
errno_t errnum;
r = sem_init(&rbuf->sem_w, 1, length);
if (r == -1) {
errnum = errno;
goto aborting_sem_r;
}
return EOK;
aborting_sem_r:
sem_destroy(&rbuf->sem_r);
return errnum;
}
void ring_buffer_free(struct ring_buffer_t *rbuf)
{
sem_destroy(&rbuf->sem_w);
sem_destroy(&rbuf->sem_r);
}
errno_t ring_buffer_write_begin(struct ring_buffer_t *rbuf)
{
int r;
do {
r = sem_wait(&rbuf->sem_w);
} while ((r == -1) && (errno == EINTR));
if (r == -1) {
return errno;
}
return EOK;
}
errno_t ring_buffer_write_end(struct ring_buffer_t *rbuf)
{
++rbuf->w_index;
if (rbuf->w_index >= rbuf->length) {
rbuf->w_index = 0;
}
int r;
r = sem_post(&rbuf->sem_r);
if (r == -1) {
return errno;
}
return EOK;
}
errno_t ring_buffer_read_begin(struct ring_buffer_t *rbuf)
{
int r;
do {
r = sem_wait(&rbuf->sem_r);
} while ((r == -1) && (errno == EINTR));
if (r == -1) {
return errno;
}
return EOK;
}
errno_t ring_buffer_read_end(struct ring_buffer_t *rbuf)
{
++rbuf->r_index;
if (rbuf->r_index >= rbuf->length) {
rbuf->r_index = 0;
}
int r;
r = sem_post(&rbuf->sem_w);
if (r == -1) {
return errno;
}
return EOK;
}
В операционных системах
В общем виде операционные системы осуществляют атомарные операции чтения и записи значения счётчика семафора, но детали реализации могут различаться на разных архитектурах. При захвате семафора операционная система должна атомарно уменьшить значение счётчика, после чего процесс может продолжить свою работу. Если же в результате уменьшения счётчика значение может стать отрицательным, то операционная система должна приостановить выполнение процесса до тех пор, пока значение счётчика не станет таким, чтобы операция уменьшения привела к неотрицательному результату[16]. При этом в зависимости от архитектуры на уровне реализации может быть выполнена как попытка уменьшения значения семафора[67], так и его уменьшение с получением отрицательного результата[68]. На уровне прикладного интерфейса обычно условно считается, что минимальным значением семафора является 0[3]. При увеличении значения семафора, по которому были заблокированы процессы, происходит разблокировка очередного процесса, а значение семафора на прикладном уровне остаётся равным нулю.
Блокировка на уровне операционной системы обычно не предполагает физического ожидания на процессоре, а передаёт управление процессором другой задаче, в то время как ожидающая отпускания семафора — попадает в очередь заблокированных по данному семафору задач[69]. В случае же, если количество готовых к исполнению задач меньше количества процессоров, ядро операционной системы может перевести свободные процессоры в режим экономии энергопотребления до наступления каких-либо событий.
На уровне процессоров
В архитектурах x86 и x86_64
Для синхронизации работы процессоров в многопроцессорных системах существуют специальные инструкции, позволяющие защитить доступ к какой-либо ячейке. В архитектуру x86 компанией Intel для ряда инструкций процессора предусмотрен префикс LOCK, позволяющий выполнять атомарные операции над ячейками памяти. Операции над ячейкой, выполняемые с префиксом LOCK, блокируют доступ остальных процессоров к ячейке, что на примитивном уровне позволяет организовывать легковесные семафоры с активным циклом ожидания[70].
Атомарное уменьшение значения семафора на 1 может быть выполнено при помощи инструкции DECL с префиксом LOCK, которая выставляет флаг знака CS в случае, если результирующее значение оказывается меньше нуля. Особенностью такого подхода является то, что значение семафора может оказываться меньше нуля, поэтому после уменьшения счётчика флаг CS может проверяться с помощью инструкции JNS, и, если знак отрицательный, то операционная система может заблокировать текущую задачу[71].
Для атомарного увеличения значения семафора на 1 может использоваться инструкция LOCK INCL. Если результирующее значение оказывается отрицательным либо равным нулю, то это означает наличие ожидающих задач, в таком случае операционная система может разблокировать очередную задачу. Для пропуска разблокировки процессов может использоваться инструкция JG, которая осуществляет переход к метке, если флаги нулевого результата операции (ZF) и знака результата (SF) сброшены в 0, то есть если значение больше 0[72].
Во время блокировки в случаях отсутствия текущих задач может использоваться инструкция HLT, предназначенная для перевода процессора в режим низкого энергопотребления с ожиданием прерываний[73], которые необходимо предварительно разрешать с помощью инструкции STI. Однако в современных процессорах более оптимальным может быть использование инструкций MWAIT и MONITOR. Инструкция MWAIT аналогична HLT, но позволяет пробудить процессор по записи в ячейку памяти по адресу, указанному в MONITOR. NWAIT можно использовать для мониторинга изменения ячейки семафора, однако в многозадачных операционных системах эта инструкция используется для мониторинга флага необходимости запустить планировщик задач на заданном ядре[74].
Снижение энергопотребления во время активного цикла ожидания может достигаться с помощью инструкции PAUSE[75].
В архитектуре ARM
В архитектуре ARMv7 для синхронизации памяти между процессорами используются так называемые локальный и глобальный эксклюзивные мониторы, представляющие собой автоматы состояний, контролирующие атомарный доступ к ячейкам памяти[76][77]. Атомарное чтение ячейки памяти может осуществляться с помощью инструкции LDREX[78], а атомарная запись — через инструкцию STREX, которая также возвращает флаг успеха операции[79].
Для уменьшения значения семафора необходимо дождаться, пока его счётчик не станет больше нуля. Ожидание может быть реализовано разными способами:
- цикл активного ожидания в случае легковесного семафора, при котором периодически проверяется значение счётчика[80] с помощью инструкции
LDREX; - блокировка с переводом процессора в энергосберегающий режим ожидания с помощью инструкций ожидания прерывания
WFIили ожидания событияWFE[81][82]; - переключение контекста на исполнение другой задачи вместо блокировки процессора[83].
На уровне многозадачной операционной системы может использоваться комбинация перечисленных способов для обеспечения максимальной загрузки процессоров с переходом в энергосберегающий режим во время простоев.
Увеличение значения семафора может представлять собой циклическое чтение текущего значения счётчика через инструкцию LDREX с последующим увеличением копии значения и попыткой записи обратно в ячейку счётчика с помощью инструкции STREX[84]. После успешной записи счётчика, если его изначальное значение было нулевым, требуется возобновить исполнение заблокированных задач[84], что в случае переключения контекста может решаться средствами операционных систем[80]. Если процессор был заблокирован с помощью инструкции WFE, разблокировать его можно через инструкцию SEV, оповещающую о наличии какого-либо события[85].
После уменьшения или увеличения значения семафора выполняется инструкция DMB, обеспечивающую гарантию целостности памяти защищаемого семафором ресурса[86].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
