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

Семафора ( голландский : seinpaal , термин , используемый в первоначальном описании Дейкстров).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • wait : уменьшает значение переменной семафора на 1. Если новое значение переменной семафора отрицательное, процесс, выполняющий ожидание , блокируется (т. е. добавляется в очередь семафора). В противном случае процесс продолжает выполнение, использовав единицу ресурса.
  • 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 помечено как истинное. Таким образом, S представляет собой семафор для A .

Можно представить себе сигнал светофора ( S ) прямо перед вокзалом ( A ). В этом случае, если сигнал зеленый, то можно попасть на вокзал. Если он желтого или красного цвета (или любого другого цвета), доступ к вокзалу невозможен.

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

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

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

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

  • потребитель должен ждать, пока производитель что-то произведет, если очередь пуста;
  • производитель должен ждать, пока потребитель что-то потребит, если очередь заполнена.

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

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

Первоначально он 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)

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

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

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

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

Канонические имена V и P приходят из инициалов голландских слов. V обычно объясняется как вероген («увеличение»). Для P было предложено несколько объяснений, в том числе проберен («проверить» или «попытаться»), Passeren («пройти») и « паккен» («схватить»). Ранняя статья Дейкстров по этому вопросу дает passering ( «прохождение») в качестве значения для P и vrijgave ( «освобождение») в качестве значения для V. Он также отмечает , что терминология взята от используемых в железнодорожных сигналах. Впоследствии Дийкстра писал, что он намеревался обозначать P как prolaag , сокращенно от probeer te verlagen , буквально «пытаться уменьшить», или в параллель с терминами, используемыми в другом случае, «пытаться уменьшить».

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

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

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

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

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

использованная литература

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

Введения

использованная литература