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

Классы Mutex и Semaphore

Mutex

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

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

У Mutex имеется несколько конструкторов. Ниже приведены два наиболее употребительных конструктора:

В первой форме конструктора создается мьютекс, которым первоначально никто не владеет. А во второй форме исходным состоянием мьютекса завладевает вызывающий поток, если параметр initiallyOwned имеет логическое значение true. В противном случае мьютексом никто не владеет.

Для того чтобы получить мьютекс, в коде программы следует вызвать метод WaitOne() для этого мьютекса. Метод WaitOne() наследуется классом Mutex от класса Thread.WaitHandle. Метод WaitOne() ожидает до тех пор, пока не будет получен мьютекс, для которого он был вызван. Следовательно, этот метод блокирует выполнение вызывающего потока до тех пор, пока не станет доступным указанный мьютекс. Он всегда возвращает логическое значение true.

Когда же в коде больше не требуется владеть мьютексом, он освобождается посредством вызова метода ReleaseMutex().

В приведенном ниже примере программы описанный выше механизм синхронизации демонстрируется на практике. В этой программе создаются два потока в виде классов IncThread и DecThread, которым требуется доступ к общему ресурсу: переменной SharedRes.Count. В потоке IncThread переменная SharedRes.Count инкрементируется, а в потоке DecThread — декрементируется. Во избежание одновременного доступа обоих потоков к общему ресурсу SharedRes.Count этот доступ синхронизируется мьютексом Mtx, также являющимся членом класса SharedRes:

Как следует из приведенного выше результата, доступ к общему ресурсу (переменной SharedRes.Count) синхронизирован, и поэтому значение данной переменной может быть одновременно изменено только в одном потоке.

Semaphore

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

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

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

Семафор реализуется в классе System.Threading.Semaphore, у которого имеется несколько конструкторов. Ниже приведена простейшая форма конструктора данного класса:

где initialCount — это первоначальное значение для счетчика разрешений семафора, т.е. количество первоначально доступных разрешений; maximumCount — максимальное значение данного счетчика, т.е. максимальное количество разрешений, которые может дать семафор.

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

Если коду больше не требуется владеть семафором, он освобождает его, вызывая метод Release(). Ниже приведены две формы этого метода:

В первой форме метод Release() высвобождает только одно разрешение, а во второй форме — количество разрешений, определяемых параметром releaseCount. В обеих формах данный метод возвращает подсчитанное количество разрешений, существовавших до высвобождения.

Источник

3) Мьютекс против семафора

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

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

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

В этом уроке вы узнаете:

Что такое Mutex?

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

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

В случае одного буфера мы можем разделить буфер 4 КБ на четыре буфера 1 КБ. Семафор может быть связан с этими четырьмя буферами. Это позволяет пользователям и производителям работать с разными буферами одновременно.

Использование Mutex

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

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

Общие факты о мьютексе и семафоре

Вот несколько распространенных фактов о Mutex и семафоре:

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

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

Преимущества Mutex

Здесь, важные плюсы / преимущества Mutex

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

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

Недостатки Mutex

Вот минусы / минусы Mutex

Источник

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

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

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

Источник

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

Каковы различия между Mutex против семафора? Когда использовать мьютекс, а когда использовать семафор?

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

Обратите внимание, что содержание является обобщенным объяснением. Практические детали меняются в зависимости от реализации.

Рассмотрим стандартную проблему производителя-потребителя. Предположим, у нас есть буфер длиной 4096 байт. Поток производителя собирает данные и записывает их в буфер. Поток потребителя обрабатывает собранные данные из буфера. Цель состоит в том, чтобы оба потока не запускались одновременно.

Используя Mutex:

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

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

Используя семафор:

Семафор — это обобщенный мьютекс. Вместо одного буфера мы можем разделить буфер 4 КБ на четыре буфера 1 КБ (идентичные ресурсы). Семафор может быть связан с этими четырьмя буферами. Потребитель и производитель могут работать с разными буферами одновременно.

Заблуждение:

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

Семафор — это сигнальный механизм ( сигнал типа «Я закончил, ты можешь продолжать»). Например, если вы слушаете песни (считаете, что это одна задача) на своем мобильном телефоне, и в то же время ваш друг звонит вам, вызывается прерывание, при котором подпрограмма обработки прерываний (ISR) сигнализирует о пробуждении задачи обработки вызова.

Общие вопросы:

1. Может ли поток получить более одной блокировки (Mutex)?

Да, возможно, что потоку требуется более одного ресурса, следовательно, блокировки. Если какая-либо блокировка недоступна, поток будет ждать (блокировать) блокировку.

2. Может ли мьютекс быть заблокирован более одного раза?

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

3. Что происходит, если нерекурсивный мьютекс заблокирован более одного раза.

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

4. Являются ли двоичный семафор и мьютекс одинаковыми?

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

Программист может предпочесть мьютекс, а не создавать семафор с номером 1.

5. Что такое мьютекс и критический раздел?

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

6. Что такое события?

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

7. Можем ли мы получить мьютекс / семафор в программе обработки прерываний?

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

8. Что мы подразумеваем под «блокировкой потоков на мьютексах / семафорах», когда они недоступны?

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

Источник