Семафор (программирование)

Эта статья о термине компьютерного программирования. Чтобы узнать о других значениях, см. Семафор (значения) .

В информатике семафор используемый — это переменный или абстрактный тип данных, для управления доступом к общему ресурсу несколькими потоками и предотвращения критическими секциями проблем с в параллельной системе, такой как многозадачная операционная система. Семафоры — это тип примитива синхронизации . Тривиальный семафор — это простая переменная, которая изменяется (например, увеличивается, уменьшается или переключается) в зависимости от условий, определенных программистом.

Полезный способ представить себе семафор, используемый в реальной системе, — это запись о том, сколько единиц определенного ресурса доступно, в сочетании с операциями по безопасной настройке этой записи (т. е. во избежание условий гонки ), поскольку единицы приобрести или стать свободным, и при необходимости дождаться, пока единица ресурса станет доступной.

Хотя семафоры полезны для предотвращения состояний гонки, они не гарантируют их отсутствие. Семафоры, допускающие произвольный подсчет ресурсов, называются счетными семафорами , а семафоры, которые ограничены значениями 0 и 1 (или заблокированы/разблокированы, недоступны/доступны), называются двоичными семафорами и используются для реализации блокировок .

Концепция семафора была изобретена голландским ученым-компьютерщиком Эдсгером Дейкстрой в 1962 или 1963 году. когда Дейкстра и его команда разрабатывали операционную систему для Electrologica X8 . Эта система в конечном итоге стала известна как система мультипрограммирования .

Аналогия с библиотекой

Предположим, что в физической библиотеке есть десять одинаковых учебных комнат, которыми одновременно может пользоваться один студент. Студенты должны запросить комнату на стойке регистрации. Если свободных комнат нет, студенты ждут за столом, пока кто-нибудь не освободит комнату. Когда студент закончил пользоваться комнатой, он должен вернуться к столу и указать, что комната свободна.

В простейшем случае служащий на стойке регистрации знает только количество свободных номеров. Для этого необходимо, чтобы все учащиеся использовали свою комнату, пока они на нее подписались, и возвращали ее, когда закончат. Когда студент просит комнату, клерк уменьшает это число. Когда студент освобождает комнату, клерк увеличивает это число. Комнату можно использовать столько, сколько пожелаете, поэтому забронировать ее заранее невозможно.

В этом сценарии держатель счетчика на стойке регистрации представляет собой счетный семафор, комнаты — это ресурс, а студенты — процессы/потоки. Значение семафора в этом сценарии изначально равно 10, при этом все комнаты пусты. Когда студент запрашивает комнату, ему предоставляется доступ, а значение семафора меняется на 9. После прихода следующего студента оно падает до 8, затем до 7 и так далее. Если кто-то запрашивает комнату и текущее значение семафора равно 0, они вынуждены ждать, пока освободится комната (когда счетчик увеличивается с 0). Если одна из комнат освободилась, но ее ждут несколько студентов, то для выбора того, кто займет комнату, можно использовать любой метод (например, FIFO или случайный выбор). И конечно, студент должен сообщить служащему об освобождении своей комнаты только после того, как действительно ее покинет.

Важные наблюдения

При использовании семафора для управления доступом к пулу ресурсов он отслеживает только количество свободных ресурсов. Он не отслеживает, какие из ресурсов свободны. Для выбора конкретного свободного ресурса может потребоваться какой-то другой механизм (возможно, с использованием большего количества семафоров).

Эта парадигма особенно эффективна, поскольку подсчет семафоров может служить полезным триггером для ряда различных действий. Библиотекарь, указанный выше, может выключить свет в учебном зале, когда в нем не осталось студентов, или может разместить табличку с сообщением о том, что комнаты очень заняты, когда большинство комнат занято.

Успех протокола требует, чтобы приложения правильно ему следовали. Справедливость и безопасность, скорее всего, будут поставлены под угрозу (что практически означает, что программа может вести себя медленно, действовать беспорядочно, зависать или аварийно завершать работу ), если хотя бы один процесс действует неправильно. Это включает в себя:

• запросил ресурс и забыл его освободить;
• освобождение ресурса, который никогда не запрашивался;
• удержание ресурса в течение длительного времени без необходимости в нем;
• использование ресурса без предварительного запроса (или после его освобождения).

Даже если все процессы следуют этим правилам, нескольких ресурсов взаимоблокировка все равно может возникнуть, когда существуют разные ресурсы, управляемые разными семафорами, и когда процессам необходимо использовать более одного ресурса одновременно, как иллюстрирует проблема обедающих философов .

Семантика и реализация

Счетные семафоры оснащены двумя операциями, исторически обозначаемыми как P и V ( § Названия операций альтернативные названия см. в ). Операция V увеличивает семафор S , а операция P уменьшает его.

Значение семафора S — это количество единиц ресурса, доступных в данный момент. Операция P тратит время или находится в режиме ожидания до тех пор, пока ресурс, защищенный семафором, не станет доступным, после чего ресурс немедленно запрашивается. Операция V является обратной: она снова делает ресурс доступным после того, как процесс завершил его использование. Одним из важных свойств семафора S является то, что его значение нельзя изменить, кроме как с помощью операций V и P.

Простой способ понять подожди (P) и сигнал (V) операции:

• wait : Уменьшает значение переменной семафора на 1. Если новое значение переменной семафора отрицательное, выполняется процесс. wait блокируется (т.е. добавляется в очередь семафора). В противном случае процесс продолжает выполнение, израсходовав единицу ресурса.
• signal : увеличивает значение переменной семафора на 1. После увеличения, если значение предварительного приращения было отрицательным (это означает, что есть процессы, ожидающие ресурса), он переносит заблокированный процесс из очереди ожидания семафора в очередь готовности.

Многие операционные системы предоставляют эффективные примитивы семафоров, которые разблокируют процесс ожидания при увеличении семафора. Это означает, что процессы не тратят время на проверку значения семафора без необходимости.

Концепция счетного семафора может быть расширена за счет возможности запрашивать или возвращать из семафора более одной «единицы» - метод, реализованный в 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гарантирует, что целостность состояния самой очереди не будет нарушена, например, если два производителя одновременно попытаются добавить элементы в пустую очередь, тем самым повредив ее внутреннее состояние. В качестве альтернативы мьютекс вместо двоичного семафора можно использовать .

The emptyCount изначально N , fullCount изначально равен 0, и useQueue изначально равен 1.

Продюсер неоднократно делает следующее:

производить: 
      P(пустойсчет) 
      P(useQueue) 
      putItemIntoQueue (пункт) 
      В (useQueue) 
      5 (полный счет) 
 

Потребитель неоднократно делает следующее

потреблять: 
      P(полное количество) 
      P(useQueue) 
      элемент ← getItemFromQueue() 
      В (useQueue) 
      В(пустойсчет) 
 

Ниже приведен содержательный пример:

1. Одиночный потребитель входит в свою критическую секцию. С fullCount равно 0, потребитель блокируется.
2. Несколько производителей входят в критическую секцию производителей. не более N производителей из-за В критическую секцию могут войти emptyCount ограничение их входа.
3. Производители по одному получают доступ к очереди через useQueue и помещать элементы в очередь.
4. Как только первый производитель выходит из своей критической секции, fullCount увеличивается, позволяя одному потребителю войти в свою критическую секцию.

Обратите внимание, что emptyCount может быть намного меньше фактического количества пустых мест в очереди, например, когда многие производители уменьшили его, но ждут своей очереди useQueueпрежде чем заполнять пустые места. Обратите внимание, что emptyCount + fullCount ≤ N всегда выполняется с равенством тогда и только тогда, когда ни один производитель или потребитель не выполняют свои критические участки.

Передача эстафеты

Схема «Передача эстафеты». предложенная Грегори Р. Эндрюсом, представляет собой общую схему для решения многих сложных задач одновременного программирования, в которых несколько процессов конкурируют за один и тот же ресурс со сложными условиями доступа (например, удовлетворение определенных критериев приоритета или предотвращение голодания). Учитывая общий ресурс, шаблон требует частного семафора «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, в том числе проберен («проверить» или «попробовать»), пассерен («пройти») и паккен («схватить»). Самая ранняя статья Дейкстры на эту тему. дает passering («прохождение») как значение P и vrijgave («выпуск») как значение V. В нем также упоминается, что терминология взята из той, которая используется в железнодорожных сигналах. Впоследствии Дейкстра писал, что он намеревался, чтобы P выступал за пролааг . сокращение от «probeer te verlagen» , буквально «попытаться уменьшить», или, если использовать термины, используемые в другом случае, «попытаться уменьшить».

В АЛГОЛе ядро ​​Linux 68 а в некоторых учебниках английского языка операции V и P называются соответственно up и down . В практике разработки программного обеспечения их часто называют сигналом и ожиданием . выпустить и приобрести (стандартная библиотека Java ), или опубликуйте и ждите . В некоторых текстах они называются «освободить» и «обеспечить» , чтобы соответствовать оригинальным голландским инициалам.

Семафоры против мьютексов

Мьютекс , — это механизм блокировки который иногда использует ту же базовую реализацию, что и двоичный семафор. Однако они различаются по способу использования. Хотя двоичный семафор в просторечии можно назвать мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение: только задача, которая заблокировала мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:

1. Инверсия приоритета : если мьютекс знает, кто его заблокировал, и должен его разблокировать, можно повысить приоритет этой задачи всякий раз, когда задача с более высоким приоритетом начинает ожидать мьютекса.
2. Преждевременное завершение задачи. Мьютексы также могут обеспечивать безопасность удаления, когда задача, содержащая мьютекс, не может быть случайно удалена.
3. Взаимная блокировка завершения: если задача, удерживающая мьютекс, завершается по какой-либо причине, ОС может освободить мьютекс и сигнализировать об ожидающих задачах этого условия.
4. Тупик рекурсии: задаче разрешено блокировать повторно входящий мьютекс несколько раз, поскольку она разблокирует его равное количество раз.
5. Случайное освобождение: при освобождении мьютекса возникает ошибка, если задача освобождения не является его владельцем.

См. также

• Флаг (программирование)
• Синхронизация (информатика)
• Проблема курильщиков сигарет
• Проблема обедающих философов
• Проблема читателей-писателей
• Проблема со спящим парикмахером
• Монитор
• Ложное пробуждение

Внешние ссылки

Введение

• Хильшаймер, Волкер (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) . Университет Оулу, Финляндия.