stringtranslate.com

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

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

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

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

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

Библиотечная аналогия

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

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

В этом сценарии держатель счетчика на стойке регистрации представляет собой счетный семафор, комнаты являются ресурсом, а студенты представляют собой процессы/потоки. Значение семафора в этом сценарии изначально равно 10, при этом все комнаты пусты. Когда студент запрашивает комнату, ему предоставляется доступ, и значение семафора изменяется на 9. После того, как приходит следующий студент, оно падает до 8, затем до 7 и т. д. Если кто-то запрашивает комнату, а текущее значение семафора равно 0, [2] он вынужден ждать, пока комната не освободится (когда счетчик увеличивается с 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 ) прямо перед железнодорожной станцией ( A ). В этом случае, если сигнал зеленый, то можно въехать на железнодорожную станцию. Если он желтый или красный (или любого другого цвета), то на железнодорожную станцию ​​попасть нельзя.

Очередь входа

Рассмотрим систему, которая может поддерживать только десять пользователей (S=10). Всякий раз, когда пользователь входит в систему, вызывается P, уменьшая семафор S на 1. Всякий раз, когда пользователь выходит из системы, вызывается V, увеличивая S на 1, представляя слот входа, который стал доступен. Когда S равен 0, любые пользователи, желающие войти в систему, должны ждать, пока S увеличится. Запрос на вход ставится в очередь FIFO, пока слот не освободится. Взаимное исключение используется для обеспечения того, чтобы запросы ставились в очередь в порядке. Всякий раз, когда S увеличивается (доступны слоты входа), запрос на вход снимается с очереди, и пользователю, владеющему запросом, разрешается войти в систему. Если S уже больше 0, то запросы на вход немедленно снимаются с очереди.

Проблема производитель-потребитель

В проблеме производитель-потребитель один процесс (производитель) генерирует элементы данных, а другой процесс (потребитель) получает и использует их. Они взаимодействуют с помощью очереди максимального размера N и подчиняются следующим условиям:

Решение семафора для проблемы производителя-потребителя отслеживает состояние очереди с помощью двух семафоров: emptyCount, количество пустых мест в очереди, и fullCount, количество элементов в очереди. Для поддержания целостности emptyCountможет быть ниже (но никогда не выше) фактического количества пустых мест в очереди и fullCountможет быть ниже (но никогда не выше) фактического количества элементов в очереди. Пустые места и элементы представляют два вида ресурсов, пустые ящики и полные ящики, а семафоры emptyCountи fullCountподдерживают контроль над этими ресурсами.

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

Первоначально emptyCountN , изначально 0 и изначально 1.fullCountuseQueue

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

производить: P(пустоеКоличество) P(использоватьОчередь) putItemIntoQueue(элемент) V(использоватьОчередь) V(полноеКоличество)

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

потреблять: P(полноеКоличество) P(использоватьОчередь) элемент ← getItemFromQueue() V(использоватьОчередь) V(пустоеКоличество)

Ниже приведен наглядный пример:

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

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

Схема передачи эстафетной палочки

Шаблон "Передача эстафеты" [3] [4] [5], предложенный Грегори Р. Эндрюсом, является общей схемой для решения многих сложных проблем параллельного программирования, в которых несколько процессов конкурируют за один и тот же ресурс со сложными условиями доступа (такими как удовлетворение определенных критериев приоритета или избежание голодания). При наличии общего ресурса шаблон требует частного семафора "priv" (инициализированного нулем) для каждого вовлеченного процесса (или класса процессов) и одного взаимно исключающего семафора "mutex" (инициализированного единицей). Псевдокод для каждого процесса следующий:

void process ( int proc_id , int res_id ) { resource_acquire ( proc_id , res_id ) ; < использовать ресурс res_id > ; resource_release ( proc_id , res_id ); }

Псевдокод примитивов получения и освобождения ресурсов:

void resource_acquire ( int proc_id , int res_id ) { P ( mutex ); if ( < условие доступа к res_id не проверено для proc_id > ) { < указать , что proc_id приостановлен для res_id > ; V ( mutex ); P ( priv [ proc_id ]); < указать , что proc_id больше не приостановлен для res_id > ; } < указать , что proc_id обращается к ресурсу > ; pass_the_baton ( ); // См . ниже }                                  
void resource_release ( int proc_id , int res_id ) { P ( mutex ); < указывает , что proc_id больше не обращается к ресурсу res_id > ; pass_the_baton ( ); // См. ниже }

Оба примитива в свою очередь используют метод «pass_the_baton», псевдокод которого выглядит так:

void pass_the_baton ( int res_id ) { if < условие доступа к res_id истинно хотя бы для одного приостановленного процесса > { int p = < выбор процесса для пробуждения > ; V ( priv [ p ] ) ; } else { V ( mutex ) ; } }

Замечания

Шаблон называется «передача эстафеты», потому что процесс, который освобождает ресурс, а также недавно реактивированный процесс активируют максимум один приостановленный процесс, то есть должны «передать ему эстафету». Мьютекс освобождается только тогда, когда процесс собирается приостановить себя (resource_acquire) или когда pass_the_baton не может реактивировать другой приостановленный процесс.

Названия операций

Канонические названия V и P происходят от начальных букв голландских слов. V обычно объясняется как verhogen («увеличивать»). Было предложено несколько объяснений для P, включая proberen («проверять» или «пытаться»), [6] passeren («проходить») и pakken («схватывать»). Самая ранняя статья Дейкстры на эту тему [1] дает passering («прохождение») как значение для P и vrijgave («отпускать») как значение для V. В ней также упоминается, что терминология взята из той, что используется в железнодорожных сигналах. Впоследствии Дейкстра писал, что он намеревался использовать P для обозначения prolaag [7] , сокращенно от probeer te verlagen , буквально «пытаться уменьшить» или для параллели с терминами, используемыми в другом случае, «пытаться уменьшить». [8] [9] [10]

В ALGOL 68 , ядре Linux , [11] и в некоторых английских учебниках операции V и P называются, соответственно, up и down . В практике разработки программного обеспечения их часто называют signal и wait , [12] release и acquire [12] (стандартная библиотека Java ) , [13] или post и pend . В некоторых текстах их называют vacate и procure , чтобы соответствовать оригинальным голландским инициалам. [14] [15]

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

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

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

Смотрите также

Ссылки

  1. ^ аб Дейкстра, Эдсгер В. О последовательном процессе обработки (EWD-35) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине .(транскрипция) (без даты, 1962 или 1963)
  2. ^ Маленькая книга семафоров Аллен Б. Дауни
  3. ^ Эндрюс, Грегори Р. (1999). Основы многопоточного, параллельного и распределенного программирования . Addison-Wesley.
  4. ^ Карвер, Ричард Х.; Тай, Куо-Чунг (2005). Современная многопоточность: реализация, тестирование и отладка многопоточных программ Java и C++/Pthreads/Win32 . Wiley.
  5. ^ Маурер, Кристиан (2021). Непоследовательное и распределенное программирование на Go . Springer.
  6. ^ Зильбершатц, Абрахам; Гэлвин, Питер Бэр; Ганье, Грег (2008), Концепции операционных систем (8-е изд.), John Wiley & Sons. Inc, стр. 234, ISBN 978-0-470-12872-5
  7. ^ Дейкстра, Эдсгер В. EWD-74 (PDF) . Архив Э. В. Дейкстры. Центр американской истории, Техасский университет в Остине .(транскрипция)
  8. ^ Дейкстра, Эдсгер В. МУЛЬТИПРОГРАММИРОВАНИЕ В X8 (EWD-51) (PDF) . Архив Э. В. Дейкстры. Центр американской истории, Техасский университет в Остине .(транскрипция) (на голландском )
  9. ^ Собственный перевод Дейкстры звучит как «попробуй- и -уменьши», хотя эта фраза может сбить с толку тех, кто не знаком с разговорным «попробуй-и...».
  10. ^ (ИСПРАВЛЕНИЕ 1/19) MUTEX: Введение простой реализации мьютекса. Почтовая рассылка ядра Linux, 19 декабря 2005 г.
  11. ^ Linux Kernel hacking HOWTO Архивировано 28.05.2010 на Wayback Machine LinuxGrill.com
  12. ^ ab Mullender, Sape; Cox, Russ (2008). Семафоры в Plan 9 (PDF) . 3-й международный семинар по Plan 9 .
  13. ^ java.util.concurrent.Semaphore
  14. ^ "exec.library/Procure". amigadev.elowar.com . Получено 2016-09-19 .
  15. ^ "exec.library/Vacate". amigadev.elowar.com . Получено 2016-09-19 .

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

Введения

Ссылки