Для чего нужен семафор

Вся правда об ОСРВ. Статья #19. Семафоры: введение и базовые службы

Использование семафоров

В Nucleus SE семафоры определяются на этапе сборки. Приложение может иметь до 16 семафоров. Если семафоры не заданы, код служебных вызовов и структур данных не включается в приложение.

Семафор представляет из себя счетчик типа U8, доступ к которому управляется таким образом, чтобы им могли пользоваться несколько задач. Задача может уменьшить значение счетчика семафора (захватить) или увеличить его (освободить). Попытка захватить семафор с нулевым значением может привести к ошибке или к приостановке задачи, в зависимости от выбранных параметров вызова API и конфигурации Nucleus SE.

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

Количество семафоров

Как и в большинстве объектов Nucleus SE, настройка семафоров определяется директивами #define в nuse_config.h. Основным параметром является NUSE_SEMAPHORE_NUMBER, определяющий количество семафоров в приложении. По умолчанию параметр установлен в 0 (семафоры в приложении не используются) и может принимать любые значения вплоть до 16. Некорректное значение приведет к ошибке при компиляции, которая будет сгенерирована проверкой в nuse_config_check.h (этот файл включен в nuse_config.c, а значит компилируется вместе с этим модулем), в результате сработает директива #error.

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

Активация вызовов API

Каждая функция API (служебный вызов) в Nucleus SE активируется директивой #define в nuse_config.h. Для семафоров к ним относятся:

NUSE_SEMAPHORE_OBTAIN
NUSE_SEMAPHORE_RELEASE
NUSE_SEMAPHORE_RESET
NUSE_SEMAPHORE_INFORMATION
NUSE_SEMAPHORE_COUNT

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

Ниже приведена выдержка из файла nuse_config.h по умолчанию.

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

Служебные вызовы семафоров

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

Служебные вызовы захвата и освобождения семафоров

Фундаментальные операции, которые можно выполнять над семафорами – захват и освобождение (уменьшение и увеличение значения). Nucleus RTOS и Nucleus SE предоставляют два базовых вызова API для этих операций.

Захват семафора

Служебный вызов Nucleus RTOS для захвата семафора очень гибкий и позволяет приостанавливать задачи неявным образом или с определенным таймаутом, если операция не может быть выполнена в данный момент, например, если вы попытаетесь захватить семафор с нулевым значением. Nucleus SE предоставляет те же функции, только приостановка задач опциональна, а таймаут не реализован.

Вызов для захвата семафора в Nucleus RTOS
Прототип служебного вызова:
STATUS NU_Obtain_Semaphore(NU_SEMAPHORE *semaphore, UNSIGNED suspend);

semaphore – указатель на предоставленный пользователем блок управления семафором;
suspend – параметр приостановки задачи, может принимать значения NU_NO_SUSPEND или NU_SUSPEND, а также значение таймаута.

NU_SUCCESS – вызов был успешно завершен;
NU_UNAVAILABLE – семафор имел нулевое значение;
NU_INVALID_SEMAPHORE – некорректный указатель на семафор;
NU_INVALID_SUSPEND – попытка выполнить приостановку из не связанного с задачей потока;
NU_SEMAPHORE_WAS_RESET – семафор был сброшен, пока задача была приостановлена.

Вызов для захвата семафора в Nucleus SE
Этот вызов API поддерживает ключевой функционал Nucleus RTOS API.

Прототип служебного вызова:

STATUS NUSE_Semaphore_Obtain(NUSE_SEMAPHORE semaphore, U8 suspend);

semaphore – индекс (ID) используемого семафора;
suspend – параметр приостановки задачи, может принимать значение NUSE_NO_SUSPEND или NUSE_SUSPEND.

NUSE_SUCCESS – вызов был успешно завершен;
NUSE_UNAVAILABLE – семафор имел нулевое значение;
NUSE_INVALID_SEMAPHORE – некорректный индекс семафора;
NUSE_INVALID_SUSPEND – попытка выполнить приостановку из не связанного с задачей потока или при отключенной функциональности блокировки API;
NUSE_SEMAPHORE_WAS_RESET – семафор был сброшен, пока задача была приостановлена;

Реализация захвата семафоров в Nucleus SE
Вариант кода функции NUSE_Semaphore_Obtain() (после проверки параметров) выбирается при помощи условной компиляции в зависимости от того, активирована поддержка блокировки (приостановки) задач или нет. Рассмотрим оба варианта.

Если блокировка не активирована, логика этого вызова API довольно проста:

Значение счетчика семафора проверяется, и, если оно не равно нулю, уменьшается.

Если блокировка задач активирована, логика становится более сложной:

Некоторые пояснения могут быть полезными.

Код помещен в цикл do…while, который выполняется, пока параметр suspend имеет значение NUSE_SUSPEND.

Если семафор имеет ненулевое значение, оно уменьшается. Переменной suspend присваивается значение NUSE_NO_SUSPEND, а вызов API завершается и возвращает значение NUSE_SUCESS.

Если семафор имеет нулевое значение, а переменной suspend присвоено значение NUSE_NO_SUSPEND, вызов API возвращает значение NUSE_UNAVAILABLE. Если приостановке было присвоено значение NUSE_SUSPEND, задача приостанавливается. После завершения вызова (например, когда задача возобновляется), если возвращаемое значение равно NUSE_SUCCESS (которое говорит о том, что задача была возобновлена после освобождения семафора, а не после сброса), цикл начинается с начала.

Освобождение семафора

Служебный вызов Nucleus RTOS API для освобождения семафора довольно прост: значение счетчика семафора увеличивается и возвращается сообщение об успехе. Nucleus SE предоставляет те же возможности, только с дополнительной проверкой на переполнение.

Вызов для освобождения семафоров в Nucleus RTOS
Прототип служебного вызова:

STATUS NU_Release_Semaphore(NU_SEMAPHORE *semaphore);

semaphore – указатель на предоставленный пользователем блок управления семафором.

NU_SUCCESS – вызов был успешно завершен;
NU_INVALID_SEMAPHORE – некорректный указатель на семафор.

Вызов для освобождения семафора в Nucleus SE
Этот вызов API поддерживает основной функционал Nucleus RTOS API.

Прототип служебного вызова:

STATUS NUSE_Semaphore_Release(NUSE_SEMAPHORE semaphore);

semaphore – индекс (ID) освобождаемого семафора.

NUSE_SUCCESS – вызов был успешно завершен;
NUSE_INVALID_SEMAPHORE – некорректный индекс семафора;
NUSE_UNAVAILABLE – семафор имеет значение 255, и его нельзя увеличить.

Реализация освобождения семафоров в Nucleus SE
Код функции NUSE_Semaphore_Release() (после проверки параметров) общий, вне зависимости от того, активирована блокировка задач или нет. Значение счетчика семафора проверяется, и, если оно меньше 255, увеличивается.

Дальнейший код выбирается при помощи условной компиляции, если поддержка вызовов API блокировки (приостановки задач) активирована:

Если на данном семафоре приостановлены какие-либо задачи, первая из них возобновляется.

В следующей статье будут описаны дополнительные вызовы API, связанные с семафорами, и их структуры данных.

Источник

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

От переводчика: Джефф Прешинг (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 раз.

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

Источник

masterok

Мастерок.жж.рф

Хочу все знать

Да! Точно, точно! По теме железной дороги часто слышал про семафор. У Сергея Михалкова в стихотворении про Дядю Степу машинист у полустанка кочегару говорит: «От вокзала до вокзала сделал рейсов я немало, но готов идти на спор – это новый семафор».

Обратите внимание: не «светофор», а именно «семафор». Так что же, на железных дорогах все таки семафоры?

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

Одним из таких участков является Соблаго – Кувшиново в Тверской области, объявленный в 2013 году заповедной зоной, где на трех небольших станциях Скакулино, Селижарово и Ранцево продолжают и сегодня применяться двукрылые входные семафоры.

Как устроен семафор и как он работает

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

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

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

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

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

Грузовой поезд прибывает на станцию Селижарово. Поезд следует по открытому на два крыла сигналу семафору на боковой путь. Тверская обл., ОКТ ж.д. Фото: Алексей Алексеев

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

Входной поднятый на одно крыло семафор на станции Ранцево, Тверская обл., ОКТ ж.д. Фото: Дмитрий Чернов

Горизонтальное положение верхнего крыла, второе в вертикальном положении параллельно мачте днем, ночью – один красный огонь: «стой, запрещается проезжать» сигнал.

Входной двукрылый семафор в закрытом сигнальном положении на станции Ранцево, Тверская обл., ОКТ ж.д. Фото: Алексей Алексеев

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

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

Стрелочный пост на станции Селижарово и приводной рычаг входного семафора. Фото: Алексей Алексеев

Централизатор с ключами на стрелочном посту. Фото из открытых источников.

Приводной рычаг входного семафора с «убегающими» далеко вдаль к семафору гибкими тягами и замком Мелентьева под крышкой с литерой «Н». Станция Скакулино, Тверская обл. ОКТ ж.д. Фото: Алексей Алексеев

Гибкие тяги приводного механизма семафора. Станция Селижарово, Тверская обл., ОКТ ж.д. Фото: Алексей Алексеев

Компенсатор привода гибких семафорных тяг. Станция Селижарово, Тверская обл., ОКТ ж.д. Фото: Алексей Алексеев

Источник