что такое семафор в программировании

Семафор на событиях C++

Сегодня коротко расскажу о том, как я реализовывал семафор на основании объекта синхронизации «Событие».

Сначала пройдусь по определениям.

1. Что такое синхронизация и зачем она нужна?

Очевидно, что набор действий мы можем выполнять несколькими способами. Самые простые — последовательно и параллельно. Параллельности выполнения определенных действий можно достигнуть за счет запуска различных потоков (threads). Идея простая: назначаем каждому потоку какое-то элементарное (или не очень) действие и запускаем их в определенном порядке. Вообще говоря, запустить мы их можем и все одновременно — выигрыш по времени мы, конечно, получим. Это понятно: одно дело вывести 10 000 слов одно за другим, а другое дело одновременно выводить, например, 100 слов. 100-кратный выигрыш по времени (плюс-минус, без учета задержек и проч.). Но исходная задача может предполагать строгую последовательность действий.

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

2. Инструменты для синхронизации потоков

В windows.h реализовано достаточно много штатных инструментов синхронизации (так называемые «объекты синхронизации»). Среди основных: критическая область, событие, мьютекс, семафор. Да-да, для семафора уже есть реализация в windows.h. «Так зачем же его программировать?» — спросите Вы. Ну, во-первых, чтобы лучше прочувствовать, как он устроен. И, во-вторых, лишняя практика C++ никому еще не помешала 🙂

Учитывая, что мы будем использовать События, поясним, что это и как это использовать.

События используют, чтобы уведомлять ожидающие потоки. Т.е., фактически, это некоторый сигнал для потока — можно сработать или пока еще нет. Из самого смысла этого объекта вытекает, что он обладает некоторым сигнальным состоянием и возможностью его регулировки (сброс/«включение»).

Итак, после подключения windows.h мы можем создать событие с помощью:

Если функция завершилась успешно, то вернется дескриптор события. Если объект не удалось создать, вернется NULL.

Чтобы поменять состояние события на сигнальное, воспользуемся функцией:

В случае успеха вернет ненулевое значение.

Теперь про семафор. Семафор призван регулировать количество одновременно запущенных потоков. Допустим, у нас 1000 потоков, но одновременно могут работать только 2. Вот такого типа регулировка и происходит с помощью семафора. А какие функции реализованы для работы с этим объектом синхронизации?

Для создания семафора, по аналогии с event-ами:

При успешном выполнении получим указатель на семафор, при неудаче — NULL.

Счетчик семафора у нас постоянно меняется (поток выполняется и появляется вакантное место), поэтому состояние семафора нужно периодически менять. Делается это с помощью этой функции:

В случае успеха возвращаемое значение — не ноль.

Также стоит обратить внимание на функцию:

Из возвращаемых значений нас особенно интересуют 2: WAIT_OBJECT_0 — значит, что состояние нашего объекта сигнальное; WAIT_TIMEOUT — сигнального состояния от объекта за отведенное время мы не дождались.

3. Непосредственно задача

Итого, наше задание заключается в том, чтобы написать свои аналоги на штатные функции. Не будем сильно усложнять задачу, сделаем «реализацию в первом приближении». Главное, сохранить количественные характеристики стандартного семафора. Код с комментариями можно найти на GitHub.

В силу простоты самой задачи, особо усложнять статью не будем, но кому-то может пригодиться 🙂

Источник

Что такое семафоры в программировании и зачем они нужны?

У семафоров них есть две основные операции:

Есть два типа семафоров:

Но на самом деле семафор — это сигнальный механизм, а мьютекс — это механизм блокировки.

Работа семафоров на примерах из жизни

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

Работа семафора на примере очереди в банкомат / media.geeksforgeeks.org

Ситуация вторая: у входа в ресторан стоят 20 человек. В этом случае количество семафоров совпадает с количеством ресурсов (свободных столиков), равным 10. Чтобы клиент мог войти в ресторан, он должен получить разрешение. После этого посетитель выбирает один из доступных столов. Как только его заказ будет выполнен, он освобождает ресурс, делая его доступным для других клиентов в очереди. В этом случае семафор гарантирует, что одновременно только 10 клиентов могут войти в ресторан и сделать заказ.

Работа семафора на примере очереди в ресторан / media.geeksforgeeks.org

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

Наглядная схема работы семафора / media.geeksforgeeks.org

Пример кода с использованием семафоров

Давайте посмотрим, как семафоры работают в коде C++:

В результате получим:

Источник

Такие удивительные семафоры

От переводчика: Джефф Прешинг (Jeff Preshing) — канадский разработчик программного обеспечения, последние 12 лет работающий в Ubisoft Montreal. Он приложил руку к созданию таких известных франшиз как Rainbow Six, Child of Light и Assassin’s Creed. У себя в блоге он часто пишет об интересных аспектах параллельного программирования, особенно применительно к Game Dev. Сегодня я бы хотел представить на суд общественности перевод одной из статей Джеффа.

Поток должен ждать. Ждать до тех пор, пока не удастся получить эксклюзивный доступ к ресурсу или пока не появятся задачи для исполнения. Один из механизмов ожидания, при котором поток не ставится на исполнение планировщиком ядра ОС, реализуется при помощи семафора.

Семафор-вышибала

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

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

Вышибала, т.е. семафор, должен уметь делать только одну операцию. Дейкстра назвал эту операцию V. На сегодняшний день нет согласия в том, как именовать эту операцию. Как правило, можно встретить функции post, release или signal. Я предпочитаю signal. При вызове этого метода семафор «отпускает» из очереди один из ожидающих потоков. (Совсем не обязательно это будет тот же поток, который вызвал wait раньше других.)

А что происходит, если кто-то вызовет signal, когда в очереди нет потоков? Нет проблем: когда какой-либо из потоков вызовет wait, семафор сразу же пропустит этот поток без блокировки. Более того, если signal вызовут 3 раза подряд при пустой очереди, то семафор разрешит следующим трем потокам, вызвавшим wait, миновать очередь без ожидания.

Само собой разумеется, что семафор должен подсчитывать количество вызовов signal при пустой очереди. Поэтому каждый семафор снабжен внутренним счетчиком, значение которого увеличивается при вызове signal и уменьшается при вызове wait.

Прелесть такого подхода в том, что вне зависимости от того в какой очередности вызываются wait и signal, результат всегда будет одним и тем же: семафор всегда пропустит на исполнение одинаковое количество потоков, и в очереди всегда останется одно и то же количество ожидающих.

1. Легковесный мьютекс

Я уже рассказывал, как можно реализовать собственный легковесный мьютекс в одной из предыдущих статей. В то время я не знал, что это только один из примеров применения общего паттерна, основная идея которого заключается в том, чтобы делегировать принятие решений о блокировке потоков некоторой новой сущности — box office. Должен ли текущий поток ждать в очереди? Должен ли он пройти семафор без ожидания? Должны ли мы разбудить какой-то другой поток?

Box office ничего не знает о количестве потоков, ожидающих в очереди, как не знает он и текущее значение внутреннего счетчика семафора. Вместо этого он должен каким-то образом хранить историю собственных состояний. Если мы говорим о реализации легковесного мьютекса, то для хранения истории достаточно одного счетчика с атомарными операциями инкремента и декремента. Я назвал этот счетчик m_contention, т.к. он хранит информацию о том, сколько потоков одновременно желают захватить мьютекс.

Когда поток хочет захватить мьютекс, он обращается к box office, который в свою очередь увеличивает значение m_contention.

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

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

Когда поток освобождает мьютекс, box office уменьшает значение внутреннего счетчика на единицу:

Если значение счетчика до декремента было меньше 1, значит в очереди нет ожидающих потоков и значение m_contention просто остается равным 0.

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

Каждое обращение к box office — это атомарная операция. Таким образом, даже если несколько потоков будут вызывать lock и unlock параллельно, они всегда будут обращаться к box office последовательно. Более того, поведение мьютекса полностью определяется внутренним состоянием box office. После обращения к box office, потоки могут вызывать методы семафора в любом порядке, и это никоим образом не нарушит согласованности исполнения. (В худшем случае потоки поборются за место в очереди семафора.)

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

2. Легковесная условная переменная

Прим. пер.: в оригинале автор назвал этот примитив Auto-Reset Event Object, однако поисковики по такому запросу выдают ссылки на C# класс AutoResetEvent, поведение которого можно с небольшими допущениями сравнивать с std::condition_variable.

На CppCon 2014 я отметил для себя, что условные переменные широко используются при созднии игровых движков, чаще всего — для уведомления одним потоком другого (возможно находящегося в режиме ожидания) о наличии для него некоторой работы (прим.пер.: в качестве такой работы может выступать задача распаковки графических ресурсов и загрузка их в GL context).

Другими словами, сколько бы раз не вызывался метод signal, внутренний счетчик условной переменной не должен становиться больше 1. На практике это означает, что можно ставить задачи в очередь на исполнение, каждый раз вызывая метод signal. Этот подход работает, даже если для назначения задач на исполнение используется структура данных отличная от queue.

Некоторые ОС предоставляют системные средства для организации условных переменных или их аналогов. Однако, если вы добавляете в очередь несколько тысяч задач за раз, то вызовы метода signal могут сильно повлиять на быстродействие всего приложения.

К счастью, паттерн box office позволяет значительно снизить накладные расходы, связанные с вызовом метода signal. Логика может быть реализована внутри сущности box office при помощи атомарных операций так, чтобы обращение к семафору осуществлялось только тогда, когда необходимо заставить поток ожидать своей очереди.

Я реализовал этот примитив и назвал его AutoResetEvent. На этот раз box office использует другой способ учета количества потоков, ожидающих в очереди. При отрицательном m_status, его абсолютное значение показывает количество потоков ожидающих на семафоре:

В методе signal мы атомарно увеличиваем значение переменной m_status, пока ее значение не достигнет 1:

3. Легковесная read-write блокировка

Используя все тот же паттерн box office мы можем реализовать примитив для read-write блокировок.

Данный примитив не блокирует потоки в отсутствие писателей. Кроме того, он является starvation-free и для писателей и для читателей, и, как и другие примитивы, может временно захватывать spin lock перед тем как заблокировать исполнение текущего потока. Для реализации этого примитива требуются два семафора: один для ожидающих читателей, другой — для писателей.

4. Проблема обедающих философов

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

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

Я предложил целых две реализации. Одна из них DiningPhilosophers, которая реализует box office, используя мьютекс. Вторая — LockReducedDiningPhilosophers, в которой каждое обращение к box office реализовано в виде lock-free алгоритма.

5. Легковесный семафор

Да, все верно: при помощи паттерна box office и семафора мы можем реализовать… другой семафор.

Зачем нам это делать? Потому что тогда мы получим LightweightSemaphore. У такого семафора очень дешевая операция signal, когда в очереди нет ожидающих потоков. К тому же она не зависит от реализации семафора, предоставляемого ОС. При вызове signal, box office увеличивает значение собственного внутреннего счетчика, не обращаясь к нижележащему семафору.

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

В GitHub репозитории все примитивы реализованы на основе LightweightSemaphore. Этот класс реализован на основе Semaphore, который в свою очередь реализован на базе семафоров, предоставляемых конкретной ОС.

Я прогнал несколько тестов для сравнения скорости работы представленных примитивов при использвании LightweightSemaphore и Semaphore на моем PC под управлением Windows. Соответствующие результаты приведены в таблице:

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

Сравнение семафоров и условных переменных

Семафоры оказались гораздо более полезными примитивами, чем я ожидал. Почему же тогда они отсутствуют в C++11 STL? По той же причине, по которой они отсутствовали в Boost: предпочтение отдали мьютексам и условным переменным. С точки зрения разработчиков библиотеки, применение традиционных семафоров слишком часто приводит к ошибкам.

Если подумать, то паттерн box office это всего лишь оптимизация обычных условных переменных для случая, когда все операции над условными переменными исполняются в конце критической секции. Рассмотрим класс AutoResetEvent. Я реализовал класс AutoResetEventCondVar с таким же поведением, но при помощи std:condition_variable. Все операции над условной переменной выполняются в конце критической секции.

На моем PC под управлением Windows простая замена AutoResetEventCondVar на AutoResetEvent увеличивает скорость работы алгоритма в 10 раз.

От переводчика: я давно ничего не переводил, так что буду благодарен за исправления и уточнения.

Источник

2) Что такое семафор?

Что такое семафор?

Семафор — это просто переменная, которая неотрицательна и разделена между потоками. Семафор — это механизм сигнализации, и поток, ожидающий семафора, может быть сигнализирован другим потоком. Он использует две атомарные операции: 1) ожидание и 2) сигнал для синхронизации процесса.

Семафор разрешает или запрещает доступ к ресурсу, который зависит от того, как он настроен.

В этом руководстве по операционной системе (ОС) вы изучите:

Характеристика семафора

Здесь характерны семафоры:

Типы семафоров

Два распространенных вида семафоров

Подсчет семафоров

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

Однако, если счетчик> 0, семафор создается в доступном состоянии, и количество токенов в нем равно его количеству.

Бинарные семафоры

Бинарные семафоры очень похожи на подсчет семафоров, но их значение ограничено 0 и 1. В этом типе семафора операция ожидания работает только в том случае, если семафор = 1, а сигнальная операция завершается успешно, когда семафор = 0. Легко реализовать, чем считать семафоры.

Пример семафора

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

Ожидание и сигнальные операции в семафорах

Обе эти операции используются для реализации синхронизации процесса. Цель этой операции семафора — получить взаимное исключение.

Ждать операции

Этот тип операции семафора помогает вам контролировать ввод задачи в критическую секцию. Однако, если значение ожидания положительное, то значение аргумента ожидания X уменьшается. В случае отрицательного или нулевого значения, никакая операция не выполняется. Это также называется операцией P (S).

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

Сигнальная операция

Этот тип операции семафора используется для управления выходом задачи из критического раздела. Это помогает увеличить значение аргумента на 1, который обозначается как V (S).

Подсчет семафора против двоичного семафора

Вот некоторые основные различия между счетным и двоичным семафором:

Разница между семафором и мьютексом

Преимущества семафоров

Вот плюсы / преимущества использования семафора:

Недостаток семафоров

Вот минусы / минусы семафора

Источник

Семафоры: введение

Семафоры

С емафор – это объект, который используется для контроля доступа нескольких потоков до общего ресурса. В общем случае это какая-то переменная, состояние которой изменяется каждым из потоков. Текущее состояние переменной определяет доступ к ресурсам.

Замечание: иногда мьютекс называют двоичным семафором, указывая не то, что мьютекс может находиться в двух состояниях. Но здесь есть важное отличие: разблокировать мьютекс может только тот поток, который его заблокировал, семафор же может «разблокировать» любой поток.

Семафоры описаны в библиотеке semaphore.h. Работа с семаформаи похожа на работу с мьютексами. Сначала необходимо инициализировать семафор с помощью функции

Далее, для ожидания доступа используется функция

Если значение семафора отрицательное, то вызывающий поток блокируется до тех пор, пока один из потоков не вызовет sem_post

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

Кроме тго, можно получить текущее значение семаформа

Здесь в переменную valp будет помещено значение счётчика.

Обратимся опять к старому примеру. Два потока изменяют одну переменную, копируя её в локальную переменную. Один поток увеличивает значение, а второй уменьшает 100 раз. Таким образом, в конце должен быть 0. Из-за совместного доступа к переменной получаем каждый раз разное значение

Синхронизируем теперь их с помощью семафора. Рассмотрим сначала пример, когда счётчик равен 1, значит, после того, как один из потоков уменьшит значение семафора, то второй вынужден будет ждать доступа к ресурсу (в данном случае, это тело функции worker1 или worker2 )

Здесь всё совершено понятно. Увеличим теперь значение счётчика до 3, например. Заменим

Мьютексы и семафоры

Рассмотрим аналогию: мьютекс можно сравнить с ключом от туалета на заправке. Если у вас есть ключ, то вы можете зайти в туалет, и туда больше никто не зайдёт. Если у вас нет ключа, то надо ждать, и в туалет вы зайти не можете. Мьютекс ограничивает доступ к общему ресурсу и позволяет в один момент времени пользоваться этим ресурсом только одному потоку.

Этот подход, к сожалению, не масштабируется на два туалета. И семафор не может разрешить проблему: по аналогии, мы имели бы на заправке два одинаковых ключа для двух одинаковых туалетов. Если один человек уже зашёл в туалет, то у второго оказался бы дубликат, способный открыть дверь туалета (свободного или занятого). Для предупреждения такой ситуации необходимо вводить флаг «туалет занят» (а это два мьютекса…), или же с самого начала использовать два разных ключа (т.е., два мьютекса). Семафор не помогает нам решать проблему доступа до набора идентичных ресурсов.

Цель использования семафора – оповещение одним потоком другого. Когда мы используем мьютекс, сначала мы его захватываем, потом используем ресурс, потом отдаём, и поступаем так всегда, потому что это обеспечивает защиту ресурса. В противоположность этому, потоки, которые используют семафор, либо ждут, либо сигналят, но не делают того и другого вместе. Например, один поток «нажимает» на кнопку, а второй отвечает на нажатие выводом сообщения.

Мьютекс:
//Поток 1
захватить_мьютекс(ключи_от_уборной)
использовать_ресурс
отдать_мьютекс(ключи_от_уборной)

//Поток 2
захватить_мьютекс(ключи_от_уборной)
использовать_ресурс
отдать_мьютекс(ключи_от_уборной)

Семафор
//Поток 1
послать_сигнал(состояние_кнопки)

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

Рассмотрим следующий пример. Есть три потока. Все три создаются одновременно, но второй должен работать только после того, как отработает первый, а третий после того, как отработает второй.

Источник