Войти
Семафор (голландский : 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.
Простой способ понять операции wait (P) и signal (V):
Многие операционные системы предоставляют эффективные примитивы семафоров, которые разблокируют ожидающий процесс при увеличении семафора. Это означает, что процессы не тратят время на ненужную проверку значения семафора.
Концепция счетного семафора может быть расширена за счет возможности запрашивать или возвращать более одной «единицы» из семафора, метод, реализованный в Unix. Ниже приведены модифицированные операции V и P, в которых квадратные скобки используются для обозначения атомарных операций, т. Е. Операций, которые кажутся неделимыми с точки зрения других процессов:
функция V (семафор S, целое число I): [S ← S + I] функция P (семафор S, целое число I): повтор: [ifS ≥ 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.
Производитель делает несколько раз следующее:
произвести: P (emptyCount) P (useQueue) putItemIntoQueue (item) V (useQueue) V (fullCount)
Потребитель многократно выполняет следующее
потребляет: P (fullCount) P (useQueue) item ← getItemFromQueue () V (useQueue) V (emptyCount)
Ниже приведен существенный пример:
fullCountравно 0, потребитель блокируется.emptyCount, ограничивающего их запись.useQueueи помещать элементы в очередь.fullCountувеличивается на единицу, позволяя одному потребителю войти в свою критическую секцию.Обратите внимание, что emptyCountможет быть намного меньше, чем фактическое количество пустых мест в очереди, например, в случае, когда многие производители уменьшили его, но ожидают своей очереди на useQueueперед заполнением пустых мест. Обратите внимание, что emptyCount + fullCount ≤ Nвсегда выполняется, с равенством тогда и только тогда, когда никакие производители или потребители не выполняют свои критические секции.
Канонические имена V и P происходят от инициалов голландских слов. V обычно объясняется как вероген («увеличение»). Для P было предложено несколько объяснений, в том числе проберен («проверить» или «попробовать»), Passeren («пройти») и «паккен» («схватить»). Самая ранняя статья Дейкстры по этому вопросу дает прохождение («прохождение») как значение для P и vrijgave («освобождение») как значение для V. В нем также упоминается, что терминология взята из терминологии, используемой в железнодорожных сигналах. Впоследствии Дейкстра писал, что он намеревался обозначать P для обозначения portmanteau prolaag, сокращенно от probeer te verlagen, буквально «пытаться уменьшить» или, параллельно с терминами, используемыми в другом случае, «пытаться уменьшить».
В АЛГОЛе 68, ядре Linux и в некоторых учебниках английского языка операции V и P вызываются соответственно вверх и вниз. В практике разработки программного обеспечения их часто называют сигналом и ожиданием, выпуском и получением (что используется в стандартной библиотеке Java ) или отправкой и отложением. Некоторые тексты призывают их освободить и закупить, чтобы они соответствовали оригинальным голландским инициалам.
A мьютекс - это механизм блокировки, который иногда использует ту же базовую реализацию, что и двоичный семафор. Различия между ними в том, как они используются. В то время как двоичный семафор может в просторечии называться мьютексом, настоящий мьютекс имеет более конкретный вариант использования и определение, в котором предполагается, что только задача, заблокировавшая мьютекс, должна его разблокировать. Это ограничение направлено на решение некоторых потенциальных проблем использования семафоров:
