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

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

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

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

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

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

Что такое Mutex?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки Mutex

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

Источник

Недостаточно знать, что такое Mutex, Semaphore и async/await. Надо знать всё, начиная с квантов

А в конце статьи развлечения ради предложу пройти парочку QUIZов по многопоточке.

Небольшой сценарий с семинара

Самое важное, что исходит от операционной системы — это планирование потоков. Ведь они могут работать как в параллели друг с другом (когда в данный момент исполняются на разных ядрах), так и что чаще (если речь идёт об одних и тех же потоках) — последовательно. Ведь ОС даёт не так много времени на исполнение — каждому, после чего отдает время другим. Второе — для этого отрезка — кванта — может быть выделено разное количество времени. Например, в зависимости от того, какой версией ОС мы пользуемся: серверной или пользовательской, является ли поток UI потоком процесса с текущим активным окном. Третье — есть приоритеты и понятие «вытесняющая многозадачность», когда ваш поток, только получив заветный квант может его потерять, т.к. образовался другой поток с более высоким приоритетом. Получается, что наше приложение сильно зависит от того, в каком окружении оно работает. Например, какой-нибудь расчётный сервис лучше всего будет себя чувствовать на серверном варианте ОС (либо с соответствующими настройками производительности), когда на машине нет вообще никаких других сервисов: кванты будут длинными, квантового времени будет предоставлено много.

Но тут встаёт другой вопрос: если наш поток на такой конфигурации устанавливает блокировку уровня ядра (например, Semaphore(1) ), второй поток дойдя до установки блокировки у себя в эту блокировку встаёт, то стоять он в серверной ОС будет намного дольше, чем стоял бы в пользовательской. Почему? Да потому что квант времени серверной в 6 раз длиннее, чем у клиентской и этому потоку придется сначала подождать, когда первый поток дойдёт до места снятия блокировки, а потом — когда ему выдадут новый квант.

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

CLRium 6

Эти три абзаца — это сжатые 5% от 4-го доклада. А он уже богат на информацию, которой можно воспользоваться на всех уровнях: от работы с примитивами синхронизации до работы с высокоуровневыми библиотеками. А программа у нас такая:

Немного статистики

Мы — крупнейший семинар страны и в общем не являемся конференцией только потому, что нам нравится наш формат. Вы не выбираете среди докладов, на которые вы не пойдёте. Вы идёте на все. При этом вы заранее понимаете, что все темы семинара вам интересны, т.к. тема едина. На CLRium 6 будет поставлен очередной рекорд: в обоих городах будет присутствовать 700 человек. Около 700 человек прокачают свои навыки в параллелизации и работой с конкурентностью. И пойдут на собеседования. Приходите и вы к нам :).

Источник

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

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

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

Источник

Я слышал эти слова, связанные с параллельным программированием, но какая разница между ними?

8 ответов

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

A семафор делает то же самое, что и мьютекс, но позволяет вводить x количество потоков, это может быть использовано, например, для ограничения количества cpu, io или RAM интенсивных задач, выполняемых одновременно.

У вас также есть блокировки чтения/записи это позволяет неограниченное количество читателей или 1 писатель в любой момент времени.

есть много неправильных представлений относительно этих слов.

Это из предыдущего сообщения (https://stackoverflow.com/a/24582076/3163691) который подходит превосходно здесь:

1) Критический Раздел= объект пользователя, используемый для разрешения выполнения just один активный поток до в рамках одного процесса. Другие не выбранные потоки помещаются в сон.

[нет возможности межпроцесса, очень примитивный объект].

2) семафор мьютекса (он же мьютекс)= объект ядра, используемый для разрешения выполнения just один активный поток от многих других, среди различных процессов. Другие не выбранные потоки помещаются в сон. Этот объект поддерживает владение потоком, thread уведомление о прекращении, рекурсия (несколько вызовов «приобретения» из одного потока) и «предотвращение инверсии приоритета».

[возможность межпроцессного взаимодействия, очень безопасная в использовании, своего рода объект синхронизации «высокого уровня»].

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

[возможность Межпроцесса, однако, не очень безопасна в использовании, потому что ей не хватает следующих атрибутов «мьютекса»: уведомление о завершении потока, рекурсия?, «предотвращение инверсии приоритета»?, п.]

4) и теперь, говоря о «spinlocks», сначала некоторые определения:

критическая область= область памяти, разделяемая 2 или более процессами.

Lock= переменная, значение которой позволяет или запрещает вход в критическую область. (Он может быть реализован как простой ‘флаг’).

Busy waiting= непрерывное тестирование переменной до появления некоторого значения.

Spin-lock (он же Spinlock)= A замок использует напряженного ожидания. (Приобретение замок производится xchg или похожие атомарные операции).

[нет спящего потока, в основном используется только на уровне ядра. Ineffcient для код уровня пользователя].

в качестве последнего комментария я не уверен, но могу поспорить на несколько больших баксов, что вышеупомянутые первые 3 синхронизирующих объекта (#1, #2 и #3) используют этот простой зверь (#4) как часть их реализации.

ссылки:

-В Реальном Времени Концепции для встроенных систем Цин Ли с Кэролайн Яо (CMP Books).

-современные операционные системы (3rd) Эндрю Таненбаум (Pearson Education International).

-Программирование приложений для Microsoft Windows (4th) Джеффри Рихтера (Microsoft Programming Series).

В разделе Синхронизация Между Потоками, он объясняет различия между event, lock, mutex, semaphore, waitable timer

A мьютекс может принадлежать только одному потоку за один раз, позволяя потокам координировать взаимоисключающий доступ к общему ресурсу

критические секции обеспечить синхронизация аналогично предоставляется объектами mutex, за исключением объектов критического сечения используется только потоками одного процесса

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

Я постараюсь охватить его примерами:

замок: один пример, где вы бы использовали lock будет общим словарем, в который добавляются элементы (которые должны иметь уникальные ключи).
Блокировка гарантирует, что один поток не входит в механизм кода, который проверяет наличие элемента в словаре, в то время как другой поток (который находится в критическом разделе) уже прошел эту проверку и добавляет элемент. Если другой поток пытается ввести заблокированный код, он будет ждать (будет заблокирован), пока объект не будет выпущен.

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

мьютекс это Semaphore(1,1) и часто используется во всем мире (широкое применение в противном случае, возможно, lock более уместен). Один будет использовать global Mutex при удалении узла из глобально доступного списка (последнее, что вы хотите, чтобы другой поток что-то делал во время удаления узла). Когда вы приобретаете Mutex если другой поток пытается получить то же Mutex он будет спать до той же нити, которая приобрела Mutex выпустить его.

затем использовать как:

надеюсь, это сэкономит вам время.

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

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

важные изменения к считать:

это зависит от вашей книги / лектора / языка / библиотеки / среды.
Вот краткий обзор того, как некоторые языки отвечают на эти детали.

Источник