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

Семафор (Голландский: Seinpaal, термин, использованный в первоначальном описании Дейкстры^[1]).

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

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

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

Концепция семафоров была изобретена Голландский специалист в области информатики Эдсгер Дейкстра в 1962 или 1963,^[2] когда Дейкстра и его команда разрабатывали Операционная система для Electrologica X8. Эта система в конечном итоге стала известна как Мультипрограммная система.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако оставшаяся часть этого раздела относится к семафорам с унарными операциями V и P, если не указано иное.

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

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

Примеры

Тривиальный пример

Рассмотрим переменную А и логическая переменная S. А доступен только когда S помечено как истина. Таким образом, S семафор для А.

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

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

Рассмотрим систему, которая может поддерживать только десять пользователей (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 (элемент) V (useQueue) V (fullCount)

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

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

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

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

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

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

Канонические имена V и P происходят от инициалов Голландский слова. V обычно объясняется как Verhogen ("увеличивать"). Было предложено несколько объяснений P, в том числе проберен («проверить» или «попробовать»),^[4] Passeren ("пройти"), и паккен ("схватить"). Самая ранняя статья Дейкстры по этому вопросу^[2] дает прохождение ("переход") как значение для п, и Vrijgave («выпуск») как значение для V. Также упоминается, что терминология взята из терминологии, используемой в железнодорожных сигналах. Впоследствии Дейкстра писал, что намеревался п стоять за чемодан пролааг,^[5] Короче для probeer te verlagen, буквально «попытаться уменьшить», или, в соответствии с терминами, используемыми в другом случае, «попытаться уменьшить».^[6][7][8]

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

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

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

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

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

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

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

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

Введения

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

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

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