Семафор (программирование)
В информатике семафор — это переменный или абстрактный тип данных , используемый для управления доступом к общему ресурсу несколькими потоками и предотвращения проблем с критическими секциями в параллельной системе, такой как многозадачная операционная система. Семафоры — это тип примитива синхронизации . Тривиальный семафор — это простая переменная, которая изменяется (например, увеличивается, уменьшается или переключается) в зависимости от условий, определенных программистом.
Полезный способ представить себе семафор, используемый в реальной системе, — это запись о том, сколько единиц определенного ресурса доступно, в сочетании с операциями по безопасной настройке этой записи (т. е. во избежание условий гонки ), поскольку единицы приобрести или стать свободным, и при необходимости дождаться, пока единица ресурса станет доступной.
Хотя семафоры полезны для предотвращения состояний гонки, они не гарантируют их отсутствие. Семафоры, допускающие произвольный подсчет ресурсов, называются счетными семафорами , а семафоры, которые ограничены значениями 0 и 1 (или заблокированы/разблокированы, недоступны/доступны), называются двоичными семафорами и используются для реализации блокировок .
Концепция семафора была изобретена голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1962 или 1963 году. [1] когда Дейкстра и его команда разрабатывали операционную систему для Electrologica X8 . Эта система в конечном итоге стала известна как система мультипрограммирования .
Аналогия с библиотекой
[ редактировать ]Предположим, что в физической библиотеке есть десять одинаковых учебных комнат, которыми одновременно может пользоваться один студент. Студенты должны запросить комнату на стойке регистрации. Если свободных комнат нет, студенты ждут за столом, пока кто-нибудь не освободит комнату. Когда студент закончил пользоваться комнатой, он должен вернуться к столу и указать, что комната свободна.
В простейшем случае служащий на стойке регистрации знает только количество свободных номеров. Для этого необходимо, чтобы все учащиеся использовали свою комнату, пока они на нее подписались, и возвращали ее, когда закончат. Когда студент просит комнату, клерк уменьшает это число. Когда студент освобождает комнату, клерк увеличивает это число. Комнату можно использовать столько, сколько пожелаете, поэтому забронировать ее заранее невозможно.
В этом сценарии держатель счетчика на стойке регистрации представляет собой счетный семафор, комнаты — это ресурс, а учащиеся — процессы/потоки. Значение семафора в этом сценарии изначально равно 10, при этом все комнаты пусты. Когда студент запрашивает комнату, ему предоставляется доступ, а значение семафора меняется на 9. После прихода следующего студента оно падает до 8, затем до 7 и так далее. Если кто-то запрашивает комнату и текущее значение семафора равно 0, [2] они вынуждены ждать, пока освободится комната (когда счетчик увеличивается с 0). Если одна из комнат освободилась, но ее ждут несколько студентов, то для выбора того, кто займет комнату, можно использовать любой метод (например, FIFO или случайный выбор). И конечно, студент должен сообщить служащему об освобождении своей комнаты только после того, как действительно ее покинет.
Важные наблюдения
[ редактировать ]При использовании семафора для управления доступом к пулу ресурсов он отслеживает только количество свободных ресурсов. Он не отслеживает, какие из ресурсов свободны. Для выбора конкретного свободного ресурса может потребоваться какой-то другой механизм (возможно, с использованием большего количества семафоров).
Эта парадигма особенно эффективна, поскольку подсчет семафоров может служить полезным триггером для ряда различных действий. Библиотекарь, указанный выше, может выключить свет в учебном зале, когда в нем не осталось студентов, или может разместить табличку с сообщением о том, что комнаты очень заняты, когда большинство комнат занято.
Успех протокола требует, чтобы приложения правильно ему следовали. Справедливость и безопасность, скорее всего, будут поставлены под угрозу (что практически означает, что программа может вести себя медленно, работать беспорядочно, зависать или аварийно завершать работу ), если хотя бы один процесс действует неправильно. Это включает в себя:
- запросил ресурс и забыл его освободить;
- освобождение ресурса, который никогда не запрашивался;
- удержание ресурса в течение длительного времени без необходимости в нем;
- использование ресурса без предварительного запроса (или после его освобождения).
Даже если все процессы следуют этим правилам, нескольких ресурсов взаимоблокировка все равно может возникнуть, когда существуют разные ресурсы, управляемые разными семафорами, и когда процессам необходимо использовать более одного ресурса одновременно, как иллюстрирует проблема обедающих философов .
Семантика и реализация
[ редактировать ]Счетные семафоры оснащены двумя операциями, исторически обозначаемыми как P и V ( см. в § Названия операций альтернативные названия ). Операция V увеличивает семафор S , а операция P уменьшает его.
Значение семафора S — это количество единиц ресурса, доступных в данный момент. Операция P тратит время или находится в режиме ожидания до тех пор, пока ресурс, защищенный семафором, не станет доступным, после чего ресурс немедленно запрашивается. Операция V является обратной: она снова делает ресурс доступным после того, как процесс завершил его использование. Одним из важных свойств семафора S является то, что его значение нельзя изменить, кроме как с помощью операций V и P.
Простой способ понять подожди (P) и сигнал (V) операции:
- wait : Уменьшает значение переменной семафора на 1. Если новое значение переменной семафора отрицательное, выполняется процесс. wait блокируется (т.е. добавляется в очередь семафора). В противном случае процесс продолжает выполнение, использовав единицу ресурса.
- signal : увеличивает значение переменной семафора на 1. После увеличения, если значение предварительного приращения было отрицательным (это означает, что есть процессы, ожидающие ресурса), он переносит заблокированный процесс из очереди ожидания семафора в очередь готовности.
Многие операционные системы предоставляют эффективные примитивы семафоров, которые разблокируют процесс ожидания при увеличении семафора. Это означает, что процессы не тратят время на проверку значения семафора без необходимости.
Концепция счетного семафора может быть расширена за счет возможности запрашивать или возвращать из семафора более одной «единицы» - метод, реализованный в Unix . Модифицированные операции V и P выглядят следующим образом: квадратные скобки используются для обозначения атомарных операций , то есть операций, которые кажутся неделимыми для других процессов:
function V(semaphore S, integer I):
[S ← S + I]
function P(semaphore S, integer I):
repeat:
[if S ≥ I:
S ← S − I
break]
Однако остальная часть этого раздела относится к семафорам с унарными операциями V и P, если не указано иное.
Чтобы избежать голодания , с семафором связана очередь процессов (обычно с семантикой FIFO ). Если процесс выполняет операцию P над семафором, имеющим нулевое значение, процесс добавляется в очередь семафора, и его выполнение приостанавливается. Когда другой процесс увеличивает семафор, выполняя операцию V, и в очереди есть процессы, один из них удаляется из очереди и возобновляет выполнение. Когда процессы имеют разные приоритеты, очередь может быть упорядочена таким образом, что процесс с наивысшим приоритетом выбирается из очереди первым.
Если реализация не обеспечивает атомарность операций увеличения, уменьшения и сравнения, существует риск того, что приращение или уменьшение будет забыто или значение семафора станет отрицательным. Атомарность может быть достигнута с помощью машинной инструкции, которая может читать, изменять и записывать семафор за одну операцию. Без такой аппаратной инструкции атомарная операция может быть синтезирована с использованием программного алгоритма взаимного исключения . В однопроцессорных системах атомарные операции можно обеспечить путем временной приостановки вытеснения или отключения аппаратных прерываний . Этот подход не работает в многопроцессорных системах, где две программы, использующие один семафор, могут одновременно работать на разных процессорах. Чтобы решить эту проблему в многопроцессорной системе, можно использовать блокирующую переменную для управления доступом к семафору. Переменная блокировки управляется с помощью команды test-and-set-lock .
Примеры
[ редактировать ]Тривиальный пример
[ редактировать ]Рассмотрим переменную A логическую переменную S. и Доступ к A возможен только тогда, когда S помечено как true. образом, S является семафором для A. Таким
Можно представить себе сигнал светофора ( S ) прямо перед железнодорожной станцией ( А ). В этом случае, если сигнал зеленый, то можно войти на вокзал. Если он желтый или красный (или любой другой цвет), доступ к вокзалу невозможен.
Очередь входа
[ редактировать ]Рассмотрим систему, которая может поддерживать только десять пользователей (S=10). Каждый раз, когда пользователь входит в систему, вызывается P, уменьшающий семафор S на 1. Всякий раз, когда пользователь выходит из системы, вызывается V, увеличивающий S на 1, обозначая освободившийся слот входа. Когда S равно 0, любые пользователи, желающие войти в систему, должны дождаться, пока S увеличится. Запрос на вход ставится в очередь FIFO до тех пор, пока не освободится слот. Взаимное исключение используется для обеспечения правильной постановки запросов в очередь. Всякий раз, когда S увеличивается (доступны слоты для входа), запрос на вход выводится из очереди, и пользователю, владеющему запросом, разрешается войти в систему. Если S уже больше 0, запросы на вход немедленно выводятся из очереди.
Проблема производителя и потребителя
[ редактировать ]В задаче производитель-потребитель один процесс (производитель) генерирует элементы данных, а другой процесс (потребитель) их получает и использует. Они взаимодействуют, используя очередь максимального размера N , и подчиняются следующим условиям:
- потребитель должен дождаться, пока производитель что-то произведет, если очередь пуста;
- производитель должен дождаться, пока потребитель что-то потребит, если очередь заполнена.
Семафорное решение проблемы производитель-потребитель отслеживает состояние очереди с помощью двух семафоров: emptyCount, количество пустых мест в очереди и fullCount, количество элементов в очереди. Чтобы сохранить целостность, emptyCount может быть меньше (но не выше), чем фактическое количество пустых мест в очереди, и fullCount может быть меньше (но не выше), чем фактическое количество элементов в очереди. Пустые места и элементы представляют собой два вида ресурсов: пустые ящики и полные ящики, а также семафоры. emptyCount и fullCount сохранять контроль над этими ресурсами.
Бинарный семафор useQueue гарантирует, что целостность состояния самой очереди не будет нарушена, например, если два производителя одновременно попытаются добавить элементы в пустую очередь, тем самым повредив ее внутреннее состояние. В качестве альтернативы мьютекс вместо двоичного семафора можно использовать .
The emptyCount изначально N , fullCount изначально равен 0, и useQueue изначально равен 1.
Продюсер неоднократно делает следующее:
produce:
P(emptyCount)
P(useQueue)
putItemIntoQueue(item)
V(useQueue)
V(fullCount)
Потребитель неоднократно делает следующее
consume:
P(fullCount)
P(useQueue)
item ← getItemFromQueue()
V(useQueue)
V(emptyCount)
Ниже приведен содержательный пример:
- Одиночный потребитель входит в свою критическую секцию. С
fullCountравно 0, потребитель блокируется. - Несколько производителей входят в критическую секцию производителей. не более N производителей из-за В критическую секцию могут войти
emptyCountограничение их входа. - Производители по одному получают доступ к очереди через
useQueueи помещать элементы в очередь. - Как только первый производитель выходит из своей критической секции,
fullCountувеличивается, позволяя одному потребителю войти в свою критическую секцию.
Обратите внимание, что emptyCount может быть намного меньше фактического количества пустых мест в очереди, например, когда многие производители уменьшили его, но ждут своей очереди useQueue прежде чем заполнить пустые места. Обратите внимание, что emptyCount + fullCount ≤ N всегда выполняется с равенством тогда и только тогда, когда ни один производитель или потребитель не выполняют свои критические участки.
Передача эстафеты
[ редактировать ]Схема «Передача эстафеты». [3] [4] [5] предложенная Грегори Р. Эндрюсом, представляет собой общую схему для решения многих сложных задач одновременного программирования, в которых несколько процессов конкурируют за один и тот же ресурс со сложными условиями доступа (например, удовлетворение определенных критериев приоритета или предотвращение голодания). Учитывая общий ресурс, шаблон требует частного семафора «priv» (инициализированного нулем) для каждого задействованного процесса (или класса процессов) и одного семафора взаимного исключения «мьютекса» (инициализированного единицей). Псевдокод для каждого процесса:
void process(int proc_id, int res_id)
{
resource_acquire(proc_id, res_id);
<use the resource res_id>;
resource_release(proc_id, res_id);
}
Псевдокод примитивов получения и освобождения ресурсов:
void resource_acquire(int proc_id, int res_id)
{
P(mutex);
if(<the condition to access res_id is not verified for proc_id>)
{
<indicate that proc_id is suspended for res_id>;
V(mutex);
P(priv[proc_id]);
<indicate that proc_id is not suspended for res_id anymore>;
}
<indicate that proc_id is accessing the resource>;
pass_the_baton(); // See below
}
void resource_release(int proc_id, int res_id)
{
P(mutex);
<indicate that proc_id is not accessing the resource res_id anymore>;
pass_the_baton(); // See below
}
Оба примитива, в свою очередь, используют метод pass_the_baton, псевдокод которого:
void pass_the_baton(int res_id)
{
if <the condition to access res_id is true for at least one suspended process>
{
int p = <choose the process to wake>;
V(priv[p]);
}
else
{
V(mutex);
}
}
Примечания
Этот шаблон называется «передачей эстафеты», потому что процесс, который освобождает ресурс, а также только что реактивированный процесс активируют не более одного приостановленного процесса, то есть должны «передать ему эстафету». Мьютекс освобождается только тогда, когда процесс собирается приостановить себя (resource_acquire) или когда pass_the_baton не может повторно активировать другой приостановленный процесс.
Названия операций
[ редактировать ]Канонические имена V и P происходят от инициалов голландских слов. V обычно объясняется как verhogen («увеличение»). Было предложено несколько объяснений P, в том числе проберен («проверить» или «попробовать»), [6] пассерен («пройти») и паккен («схватить»). Самая ранняя статья Дейкстры на эту тему. [1] дает passering («прохождение») как значение P и vrijgave («выпуск») как значение V. В нем также упоминается, что терминология взята из той, которая используется в железнодорожных сигналах. Впоследствии Дийкстра писал, что он намеревался , чтобы P выступал за пролааг . [7] сокращение от «probeer te verlagen» , буквально «попытаться уменьшить», или, если использовать термины, используемые в другом случае, «попытаться уменьшить». [8] [9] [10]
В АЛГОЛе ядро Linux 68 [11] а в некоторых учебниках английского языка операции V и P называются соответственно up и down . В практике разработки программного обеспечения их часто называют сигналом и ожиданием , [12] выпустить и приобрести [12] (стандартная библиотека Java ), [13] или опубликуйте и ждите . В некоторых текстах они называются «освободить» и «обеспечить», чтобы соответствовать оригинальным голландским инициалам. [14] [15]
Семафоры против мьютексов
[ редактировать ]Мьютекс , который иногда использует ту же базовую реализацию , — это механизм блокировки что и двоичный семафор. Однако они различаются по способу использования. Хотя двоичный семафор в просторечии можно назвать мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение: только задача, которая заблокировала мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:
- Инверсия приоритета : если мьютекс знает, кто его заблокировал, и должен его разблокировать, можно повысить приоритет этой задачи всякий раз, когда задача с более высоким приоритетом начинает ожидать мьютекса.
- Преждевременное завершение задачи. Мьютексы также могут обеспечивать безопасность удаления, когда задача, содержащая мьютекс, не может быть случайно удалена. [ нужна ссылка ]
- Взаимная блокировка завершения: если задача, удерживающая мьютекс, завершается по какой-либо причине, ОС может освободить мьютекс и сигнализировать об ожидающих задачах этого условия.
- Тупик рекурсии: задаче разрешено блокировать повторно входящий мьютекс несколько раз, поскольку она разблокирует его равное количество раз.
- Случайное освобождение: при освобождении мьютекса возникает ошибка, если задача освобождения не является его владельцем.
См. также
[ редактировать ]- Флаг (программирование)
- Синхронизация (информатика)
- Проблема курильщиков сигарет
- Проблема обедающих философов
- Проблема читателей-писателей
- Проблема со спящим парикмахером
- Монитор
- Ложное пробуждение
Ссылки
[ редактировать ]- ^ Jump up to: а б Дейкстра, Эдсгер В. О последовательности описаний процессов (EWD-35) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция ) (без даты, 1962 или 1963 г.)
- ^ Маленькая книга семафоров Аллен Б. Дауни
- ^ Эндрюс, Грегори Р. (1999). Основы многопоточного, параллельного и распределенного программирования . Аддисон-Уэсли.
- ^ Карвер, Ричард Х.; Тайский, Куо-Чунг (2005). Современная многопоточность: реализация, тестирование и отладка многопоточных программ на Java и C++/Pthreads/Win32 . Уайли.
- ^ Маурер, Кристиан (2021). Непоследовательное и распределенное программирование на Go . Спрингер.
- ^ Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (2008), Концепции операционной системы (8-е изд.), John Wiley & Sons. Инк, с. 234, ISBN 978-0-470-12872-5
- ^ Дейкстра, Эдсгер В. EWD-74 (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
- ^ Дейкстра, Эдсгер В. МУЛЬТИПРОГАММИРОВАНИЕ EN DE X8 (EWD-51) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция ) (на голландском языке )
- ↑ Собственный перевод Дейкстры гласит «попробуй и уменьши», хотя эта фраза может сбить с толку тех, кто не знает разговорного «попробуй и…».
- ^ (ИСПРАВЛЕНИЕ 1/19) MUTEX: введение простой реализации мьютекса. Список рассылки ядра Linux, 19 декабря 2005 г.
- ^ HOWTO по взлому ядра Linux. Архивировано 28 мая 2010 г. на Wayback Machine LinuxGrill.com.
- ^ Jump up to: а б Мюлендер, Сапе; Кокс, Расс (2008). Семафоры в Плане 9 (PDF) . 3-й международный семинар по Плану 9 .
- ^
java.util.concurrent.Semaphore - ^ "exec.library/Procure" . amigadev.elowar.com . Проверено 19 сентября 2016 г.
- ^ "exec.library/Освободить" . amigadev.elowar.com . Проверено 19 сентября 2016 г.
Внешние ссылки
[ редактировать ]Введение
[ редактировать ]- Хильшаймер, Волкер (2004). « Реализация мьютекса чтения/записи » (веб-страница). Qt Quarterly , выпуск 11 – 3 квартал 2004 г.
- Зеленский, Джули; Парланте, Ник. «Примеры потоков и семафоров» (PDF) . Раздаточный материал . CS107 Парадигмы программирования. Весна 2008 г. (23). Стэнфордский инженерный институт Everwhere (SEE).
Ссылки
[ редактировать ]- Дейкстра, Эдсгер В. Сотрудничающие последовательные процессы (EWD-123) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция ) (сентябрь 1965 г.)
- «semaphore.h — семафоры (РЕАЛЬНОЕ ВРЕМЯ)». Базовые спецификации открытой группы, выпуск 6 IEEE Std 1003.1, издание 2004 г. Открытая группа. 2004.
- Дауни, Аллен Б. (2016) [2005]. «Маленькая книга семафоров» (2-е изд.). Пресс для зеленого чая.
- Леппяярви, Йоуни (11 мая 2008 г.). «Прагматичный, исторически ориентированный обзор универсальности примитивов синхронизации» (PDF) . Университет Оулу, Финляндия.
