В информатике семафор — это переменный или абстрактный тип данных, используемый для управления доступом к общему ресурсу несколькими потоками и предотвращения проблем с критическими секциями в параллельной системе, такой как многозадачная операционная система. Семафоры — это тип примитива синхронизации . Тривиальный семафор — это простая переменная, которая изменяется (например, увеличивается, уменьшается или переключается) в зависимости от условий, определенных программистом.
Полезный способ представить себе семафор, используемый в реальной системе, — это запись о том, сколько единиц определенного ресурса доступно, в сочетании с операциями по безопасной настройке этой записи (т. е. во избежание условий гонки ), поскольку единицы приобрести или стать свободным, и при необходимости дождаться, пока единица ресурса станет доступной.
Семафоры — полезный инструмент для предотвращения состояний гонки; однако их использование не является гарантией того, что программа свободна от этих проблем. Семафоры, которые допускают произвольный подсчет ресурсов, называются счетными семафорами , а семафоры, которые ограничены значениями 0 и 1 (или заблокированы/разблокированы, недоступны/доступны), называются двоичными семафорами и используются для реализации блокировок .
Концепция семафора была изобретена голландским ученым-компьютерщиком Эдсгером Дейкстра в 1962 или 1963 году [2] , когда Дейкстра и его команда разрабатывали операционную систему для Electrologica X8 . Эта система в конечном итоге стала известна как система мультипрограммирования .
Предположим, что в физической библиотеке есть 10 одинаковых учебных комнат, которыми одновременно может пользоваться один студент. Студенты должны запросить комнату на стойке регистрации, если они хотят использовать учебную комнату. Если свободных комнат нет, студенты ждут за столом, пока кто-нибудь не освободит комнату. Когда студент закончил пользоваться комнатой, он должен вернуться к парте и указать, что одна комната стала свободной.
В простейшей реализации служащий на стойке регистрации знает только количество доступных свободных комнат, и он узнает это правильно только в том случае, если все студенты действительно используют свои комнаты, когда они записались на них, и возвращают их, когда они закончат. Когда студент просит комнату, клерк уменьшает это число. Когда студент освобождает комнату, клерк увеличивает это число. Комнату можно использовать сколько угодно долго, поэтому забронировать ее заранее невозможно.
В этом сценарии держатель счетчика на стойке регистрации представляет собой счетный семафор, комнаты — это ресурс, а студенты — процессы/потоки. Значение семафора в этом сценарии изначально равно 10, при этом все комнаты пусты. Когда студент запрашивает комнату, ему предоставляется доступ, а значение семафора меняется на 9. После прихода следующего студента оно падает до 8, затем до 7 и так далее. Если кто-то запрашивает комнату и текущее значение семафора равно 0, [3] он вынужден ждать, пока комната не освободится (когда счетчик увеличивается с 0). Если одна из комнат освободилась, но ее ждут несколько студентов, то для выбора того, кто займет комнату, можно использовать любой метод (например, FIFO или случайный выбор). И конечно, студенту необходимо сообщить секретарю об освобождении своей комнаты только после того, как он действительно выйдет из нее, иначе может возникнуть неловкая ситуация, когда такой студент уже выходит из комнаты (упаковывает учебники и т. д.). и еще один студент входит в комнату, прежде чем они ее покидают.
При использовании семафора для управления доступом к пулу ресурсов он отслеживает только количество свободных ресурсов; он не отслеживает, какие из ресурсов свободны. Для выбора конкретного свободного ресурса может потребоваться какой-то другой механизм (возможно, с использованием большего количества семафоров).
Эта парадигма особенно эффективна, поскольку подсчет семафоров может служить полезным триггером для ряда различных действий. Библиотекарь, указанный выше, может выключить свет в учебном зале, когда в нем не осталось студентов, или может разместить табличку с надписью, что комнаты очень заняты, когда большинство комнат занято.
Успех протокола требует, чтобы приложения правильно ему следовали. Справедливость и безопасность, скорее всего, будут поставлены под угрозу (что практически означает, что программа может вести себя медленно, действовать беспорядочно, зависать или аварийно завершать работу ), если хотя бы один процесс действует неправильно. Это включает в себя:
Даже если все процессы следуют этим правилам, взаимоблокировка нескольких ресурсов все равно может возникнуть, когда существуют разные ресурсы, управляемые разными семафорами, и когда процессам необходимо использовать более одного ресурса одновременно, как иллюстрирует проблема обедающих философов .
Счетные семафоры оснащены двумя операциями, исторически обозначаемыми как P и V (альтернативные названия см. в § Названия операций). Операция V увеличивает семафор S , а операция P уменьшает его.
Значение семафора S — это количество единиц ресурса, доступных в данный момент. Операция P тратит время или находится в режиме ожидания до тех пор, пока ресурс, защищенный семафором, не станет доступным, после чего ресурс немедленно запрашивается. Операция V является обратной: она снова делает ресурс доступным после того, как процесс завершил его использование. Одним из важных свойств семафора S является то, что его значение нельзя изменить, кроме как с помощью операций V и P.
Простой способ понять операции ожидания (P) и сигнала (V):
Многие операционные системы предоставляют эффективные примитивы семафоров, которые разблокируют процесс ожидания при увеличении семафора. Это означает, что процессы не тратят время на проверку значения семафора без необходимости.
Концепция счетного семафора может быть расширена за счет возможности запрашивать или возвращать из семафора более одной «единицы» - метод, реализованный в Unix . Модифицированные операции V и P заключаются в следующем: в квадратных скобках обозначаются атомарные операции , то есть операции, которые кажутся неделимыми с точки зрения других процессов:
функция V(семафор S, целое число I): [С ← С + Я]функция P(семафор S, целое число I): повтор: [ если S ≥ I: С ← С - Я перерыв ]
Однако оставшаяся часть этого раздела относится к семафорам с унарными операциями 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гарантирует, что целостность состояния самой очереди не будет нарушена, например, если два производителя одновременно попытаются добавить элементы в пустую очередь, тем самым повредив ее внутреннее состояние. В качестве альтернативы вместо двоичного семафора можно использовать мьютекс .
Первоначально emptyCountN ,fullCount первоначально 0 и первоначально useQueue1.
Продюсер неоднократно делает следующее:
производить: P(пустойсчет) P(useQueue) putItemIntoQueue (пункт) В (useQueue) В (полное количество)
Потребитель неоднократно делает следующее
потреблять: P(полное количество) P(useQueue) элемент ← getItemFromQueue() В (useQueue) В(пустойсчет)
Ниже приведен содержательный пример:
fullCountзначение равно 0, потребитель блокируется.emptyCountограничения их входа.useQueueи помещают в нее элементы.fullCountон увеличивается, позволяя одному потребителю войти в свою критическую секцию.Обратите внимание, что оно emptyCountможет быть намного меньше фактического количества пустых мест в очереди, например, в случае, когда многие производители уменьшили его, но ждут своей очереди, useQueueпрежде чем заполнять пустые места. Обратите внимание, что это правило всегда выполняется с равенством тогда и только тогда, когда ни один производитель или потребитель не выполняет свои критические секции.emptyCount + fullCount ≤ N
Шаблон «Передача эстафеты» [4] [5] [6], предложенный Грегори Р. Эндрюсом, представляет собой общую схему для решения многих сложных задач параллельного программирования, в которых несколько процессов конкурируют за один и тот же ресурс со сложными условиями доступа (например, выполнением конкретные критерии приоритета или предотвращение голодания). Учитывая общий ресурс, шаблон требует частного семафора «priv» (инициализированного нулем) для каждого задействованного процесса (или класса процессов) и одного семафора взаимного исключения «мьютекса» (инициализированного единицей). Псевдокод для каждого процесса:
недействительный процесс ( int proc_id , int res_id ) { resource_acquire ( proc_id , res_id ); < использовать ресурс res_id > ; _ ресурс_релиз ( proc_id , res_id ); } Псевдокод примитивов получения и освобождения ресурсов:
void resources_acquire ( int proc_id , int res_id ) { P ( мьютекс ); if ( < условие доступа к res_id не проверено для proc_id > ) { < указывает , что proc_id приостановлен для res_id > ; _ _ В ( мьютекс ); P ( priv [ proc_id ]); < указывает , что proc_id больше не приостановлен для res_id > ; } < указывает , что proc_id обращается к ресурсу > ; передать_эстафету (); // См. ниже } void resources_release ( int proc_id , int res_id ) { P ( мьютекс ); < указывает , что proc_id больше не обращается к ресурсу res_id > ; передать_эстафету (); // См. ниже } Оба примитива, в свою очередь, используют метод pass_the_baton, псевдокод которого:
void pass_the_baton ( int res_id ) { if < условие доступа к res_id истинно хотя бы для одного приостановленного процесса > { int p = < выберите процесс для пробуждения > ; _ _ _ В ( прив [ п ]); } Еще { V ( мьютекс ); } } Примечания
Этот шаблон называется «передачей эстафеты», потому что процесс, который освобождает ресурс, а также только что реактивированный процесс активируют не более одного приостановленного процесса, то есть должны «передать ему эстафету». Мьютекс освобождается только тогда, когда процесс собирается приостановить себя (resource_acquire) или когда pass_the_baton не может повторно активировать другой приостановленный процесс.
Канонические имена V и P происходят от инициалов голландских слов. V обычно объясняется как verhogen («увеличение»). Для P было предложено несколько объяснений, в том числе проберен («проверить» или «попробовать»), [7] пассерен («пройти») и паккен («схватить»). Самая ранняя статья Дейкстры по этому вопросу [2] дает passing («прохождение») как значение для P и vrijgave («выпуск») как значение для V. В ней также упоминается, что терминология взята из той, которая используется в железнодорожных сигналах. Впоследствии Дейкстра писал, что он намеревался использовать P для prolaag , [8] сокращенного от Probeer te verlagen , буквально «попытаться уменьшить», или, если сравнить с терминами, используемыми в другом случае, «попытаться уменьшить». [9] [10] [11]
В АЛГОЛе 68 , ядре Linux , [12] и в некоторых учебниках английского языка операции V и P называются соответственно up и down . В практике разработки программного обеспечения их часто называют signal and wait , [13] Release and Acquire [13] (стандартная библиотека Java ), [14] или post and pend . В некоторых текстах они называются «освободить» и «обеспечить» , чтобы соответствовать оригинальным голландским инициалам. [15] [16]
Мьютекс — это механизм блокировки , который иногда использует ту же базовую реализацию , что и двоичный семафор. Различия между ними заключаются в том, как они используются. Хотя двоичный семафор в просторечии можно назвать мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение: только задача, которая заблокировала мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:
java.util.concurrent.Semaphore