Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Семафор ( голландский : seinpaal , термин, использованный в первоначальном описании Дейкстры [1] ).

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

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

Семафоры - полезный инструмент для предотвращения состояний гонки; однако их использование ни в коем случае не является гарантией отсутствия в программе этих проблем. Семафоры, которые позволяют произвольно подсчитывать ресурсы, называются семафорами подсчета , в то время как семафоры, которые ограничены значениями 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):

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

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

Концепция счетного семафора может быть расширена возможностью запрашивать или возвращать более одной «единицы» из семафора, метод, реализованный в Unix . Ниже приведены модифицированные операции V и P, в которых квадратные скобки используются для обозначения атомарных операций , т. Е. Операций, которые кажутся неделимыми с точки зрения других процессов:

функция V (семафор S, целое число I): [S ← S + I]функция P (семафор S, целое число I): повторение: [ если S ≥ I: S ← S - I перерыв ]

Однако оставшаяся часть этого раздела относится к семафорам с унарными операциями 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 (пустое число) P (useQueue) putItemIntoQueue (элемент) V (useQueue) V (полный счет)

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

потреблять: P (fullCount) P (useQueue) элемент ← getItemFromQueue () V (useQueue) V (пустое число)

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

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

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

Названия операций [ править ]

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

В Алголе 68 , в ядре Linux , [9] и в некоторых английских учебниках, то V и P операции называются, соответственно, вверх и вниз . В инженерной практике программного обеспечения, они часто называют сигналом и ждать , [10] выпуск и приобретать [10] (что стандартный Java библиотека [11] использует), или пост и ПЭНД . Некоторые тексты [12] [13] призывают их освободить и закупить чтобы соответствовать оригинальным голландским инициалам.

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Дейкстра, Эдсгер W. За seinpalen (EWD-74) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине .( транскрипция )
  2. ^ a b Дейкстра, Эдсгер В. Более последовательная работа с процессами (EWD-35) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине . ( транскрипция ) (без даты, 1962 или 1963)
  3. ^ Маленькая книга семафоров Аллен Б. Дауни
  4. ^ Silberschatz, Гальвин и Ганье 2008 , стр. 234
  5. ^ Дейкстра, Эдсгер В. EWD-74 (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине . ( транскрипция )
  6. ^ Дейкстра, Эдсгер В. MULTIPROGAMMERING EN DE Х8 (EWD-51) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине . ( транскрипция ) (на голландском )
  7. ^ Собственный перевод Дейкстры гласит «попробуй и уменьшь», хотя эта фраза может сбить с толку тех, кто не знает разговорного «попробуй и ...»
  8. ^ (ПАТЧ 1/19) MUTEX: Представляем простую реализацию мьютекса. Список рассылки ядра Linux, 19 декабря 2005 г.
  9. ^ Взлом ядра Linux HOWTO LinuxGrill.com
  10. ^ a b Маллендер, Сапе; Кокс, Расс (2008). Семафоры в Plan 9 (PDF) . 3-й международный семинар по плану 9 .
  11. ^ java.util.concurrent.Semaphore
  12. ^ "exec.library / Procure" . amigadev.elowar.com . Проверено 19 сентября 2016 .
  13. ^ "exec.library / Vacate" . amigadev.elowar.com . Проверено 19 сентября 2016 .

Внешние ссылки [ править ]

Представления [ править ]

  • Хилшеймер, Фолькер (2004). « Реализация мьютекса чтения / записи » (веб-страница). Qt Quarterly , выпуск 11 - третий квартал 2004 г.
  • Зеленский, Юлия; Парланте, Ник. «Примеры потоков и семафоров» (pdf) . Раздаточный материал . CS107 Парадигмы программирования. Stanford Engineering Everwhere (SEE). Весна 2008 (23).

Ссылки [ править ]

  • Дейкстра, Эдсгер В. Взаимодействующие последовательные процессы (EWD-123) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине .( транскрипция ) (сентябрь 1965)
  • "semaphore.h - семафоры (РЕАЛЬНОЕ ВРЕМЯ)" . Интерфейс программирования . Базовые характеристики. Открытая группа. IEEE Std 1003.1 (выпуск 6). 2004 г.
  • Дауни, Аллен Б. (2016) [2005]. "Маленькая книга семафоров" (2-е изд.). Пресс для зеленого чая.
  • Леппяярви, Йоуни (11 мая 2008 г.). «Прагматичный, исторически ориентированный обзор универсальности примитивов синхронизации» (pdf) . Университет Оулу, Финляндия.