Лекция
Привет, Вы узнаете о том , что такое семафор в многопоточных приложениях, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое семафор в многопоточных приложениях, семафор , настоятельно рекомендую прочитать все из категории Операционные системы и системное программировние.
семафор (англ. semaphore) — объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Определение введено Эдсгером Дейкстрой. Семафоры используются для синхронизации и защиты передачи данных через разделяемую память, а также для синхронизации работы процессов и потоков.
Семафор — это объект, над которым можно выполнить три операции.
Инициализация семафора (задать начальное значение счетчика):
init(n):
счетчик := n
Захват семафора (ждать пока счетчик станет больше 0, после этого уменьшить счетчик на единицу):
enter():
счетчик := счетчик - 1
Освобождение семафора (увеличить счетчик на единицу):
leave():
счетчик := счетчик + 1
Предположим, что есть такой участок кода:
semaphore.init(5);
// .....
// .....
void DoSomething()
{
semaphore.enter();
// .......
semaphore.leave();
}
Тогда не более пяти потоков могут одновременно выполнять функцию DoSomething().
В более сложных семафорах может использоваться очередь; при этом потоки, ожидающие освобождения семафора, будут проходить через семафор именно в том порядке, в котором они вызывали enter().
Некоторые из проблем, которые могут решать семафоры:
Следующий пример показывает, как наладить поочередный доступ к консоли.
semaphore.init(1);
// Поток 1:
semaphore.enter();
cout << "Состояние массива: ";
for (int i=0; i
Этот код поможет предотвратить появление вывода наподобие
Состояние массива: 1 2 3 Нажато Esc. 4 5 6
Во-первых, можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave().
Во-вторых, семафоры чреваты взаимной блокировкой потоков. В частности, опасен такой код:
// Поток 1:
semaphore1.enter();
semaphore2.enter();
// ...
semaphore2.leave();
semaphore1.leave();
// Поток 2:
semaphore2.enter();
semaphore1.enter();
// ...
semaphore1.leave();
semaphore2.leave();
Джефф Прешинг (Jeff Preshing) — канадский разработчик программного обеспечения, последние 12 лет работающий в Ubisoft Montreal. Он приложил руку к созданию таких известных франшиз как Rainbow Six, Child of Light и Assassin’s Creed. У себя в блоге он часто пишет об интересных аспектах параллельного программирования, особенно применительно к Game Dev. Сегодня я бы хотел представить на суд общественности перевод одной из статей Джеффа.
Поток должен ждать. Ждать до тех пор, пока не удастся получить эксклюзивный доступ к ресурсу или пока не появятся задачи для исполнения. Один из механизмов ожидания, при котором поток не ставится на исполнение планировщиком ядра ОС, реализуется при помощи семафора.
Раньше я думал, что семафоры давно устарели. В 1960‑х, когда еще мало кто писал многопоточные программы, или любые другие программы, Эдсгер Дейкстра предложил идею нового механизма синхронизации — семафор. Я знал, что при помощи семафоров можно вести учет числа доступных ресурсов или создать неуклюжий аналог мьютекса, но этим, как я считал, область их применения ограничивается.
Мое мнение изменилось, когда я понял, что, используя только семафоры и атомарные операции, можно создать все остальные примитивы синхронизации:
Все эти примитивы являются легковесными в том смысле, что некоторые операции над ними исполняются полностью в userspace, и они могут (это необязательное условие) некоторое время крутиться в цикле, перед тем как запросить блокировку потока у операционной системы (примеры доступны на GitHub.) В моей библиотеке примитивов реализован класс Semaphore, который является оберткой над системными семафорами Windows, MacOS, iOS, Linux и других POSIX-совместимых ОС. Вы можете легко добавить любой из этих примитивов в свой проект.
Представьте себе множество потоков ожидающих исполнения, выстроенных в очередь, прямо как очередь перед входом в модный ночной клуб. Семафор — это вышибала перед входом. Он позволяет пройти внутрь клуба только когда ему дают соответствующее указание.
Каждый поток сам решает когда встать в эту очередь. Дейкстра назвал эту операцию P, что наверняка являлось отсылкой к какому-то забавно звучащему голландскому термину, но в современных реализациях семафоров вы, скорее всего, обнаружите только операцию wait. По сути, когда поток вызывает метод wait, он становится в очередь.
Вышибала, т.е. семафор, должен уметь делать только одну операцию. Дейкстра назвал эту операцию V. На сегодняшний день нет согласия в том, как именовать эту операцию. Как правило, можно встретить функции post, release или signal. Я предпочитаю signal. При вызове этого метода семафор «отпускает» из очереди один из ожидающих потоков. (Совсем не обязательно это будет тот же поток, который вызвал wait раньше других.)
А что происходит, если кто-то вызовет signal, когда в очереди нет потоков? Нет проблем: когда какой-либо из потоков вызовет wait, семафор сразу же пропустит этот поток без блокировки. Более того, если signal вызовут 3 раза подряд при пустой очереди, то семафор разрешит следующим трем потокам, вызвавшим wait, миновать очередь без ожидания.
Само собой разумеется, что семафор должен подсчитывать количество вызовов signal при пустой очереди. Об этом говорит сайт https://intellect.icu . Поэтому каждый семафор снабжен внутренним счетчиком, значение которого увеличивается при вызове signal и уменьшается при вызове wait.
Прелесть такого подхода в том, что вне зависимости от того в какой очередности вызываются wait и signal, результат всегда будет одним и тем же: семафор всегда пропустит на исполнение одинаковое количество потоков, и в очереди всегда останется одно и то же количество ожидающих.
Я уже рассказывал, как можно реализовать собственный легковесный мьютекс в одной из предыдущих статей. В то время я не знал, что это только один из примеров применения общего паттерна, основная идея которого заключается в том, чтобы делегировать принятие решений о блокировке потоков некоторой новой сущности — box office. Должен ли текущий поток ждать в очереди? Должен ли он пройти семафор без ожидания? Должны ли мы разбудить какой-то другой поток?
Box office ничего не знает о количестве потоков, ожидающих в очереди, как не знает он и текущее значение внутреннего счетчика семафора. Вместо этого он должен каким-то образом хранить историю собственных состояний. Если мы говорим о реализации легковесного мьютекса, то для хранения истории достаточно одного счетчика с атомарными операциями инкремента и декремента. Я назвал этот счетчик m_contention, т.к. он хранит информацию о том, сколько потоков одновременно желают захватить мьютекс.
class LightweightMutex
{
private:
std::atomic m_contention; // The "box office"
Semaphore m_semaphore; // The "bouncer"
Когда поток хочет захватить мьютекс, он обращается к box office, который в свою очередь увеличивает значение m_contention.
public:
void lock()
{
if (m_contention.fetch_add(1, std::memory_order_acquire) > 0) // Visit the box office
{
m_semaphore.wait(); // Enter the wait queue
}
}
Если значение счетчика равно нулю, значит мьютекс находится в неотмеченном состоянии. В этом случае текущий поток автоматически становится владельцем мьютекса, минует семафор без ожидания и продолжает работу в секции кода, защищенной мьютексом.
Если же мьютекс уже захвачен другим потоком, то значение счетчика будет больше нуля и текущий поток должен ожидать своей очереди для входа в критическую секцию.
Когда поток освобождает мьютекс, box office уменьшает значение внутреннего счетчика на единицу:
void unlock()
{
if (m_contention.fetch_sub(1, std::memory_order_release) > 1) // Visit the box office
{
m_semaphore.signal(); // Release a waiting thread from the queue
}
}
Если значение счетчика до декремента было меньше 1, значит в очереди нет ожидающих потоков и значение m_contention просто остается равным 0.
Если же значение счетчика было больше 1, значит другой поток или несколько потоков пытались захватить мьютекс, и, следовательно, ожидают своей очереди войти в критическую секцию. В этом случае мы вызываем signal, чтобы семафор разбудил один из потоков и дал ему возможность захватить мьютекс.
Каждое обращение к box office — это атомарная операция. Таким образом, даже если несколько потоков будут вызывать lock и unlock параллельно, они всегда будут обращаться к box office последовательно. Более того, поведение мьютекса полностью определяется внутренним состоянием box office. После обращения к box office, потоки могут вызывать методы семафора в любом порядке, и это никоим образом не нарушит согласованности исполнения. (В худшем случае потоки поборются за место в очереди семафора.)
Данный примитив можно назвать «легковесным», так как он позволяет потоку захватить мьютекс без обращения к семафору, т.е. без совершения системного вызова. Я опубликовал код мьютекса на GitHub под названием NonRecursiveBenaphore, там же есть и рекурсивная версия легковесного мьютекса. Тем не менее, нет предпосылок использовать этим примитивы на практике, т.к. большинство известных реализаций мьютексов и так являются легковесными. Тем не менее, этот код служит необходимой иллюстрацией подхода, который используется для всех прочих примитивов, описанных в данной статье.
Прим. пер.: в оригинале автор назвал этот примитив 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, его абсолютное значение показывает количество потоков ожидающих на семафоре:
class AutoResetEvent
{
private:
// m_status == 1: Event object is signaled.
// m_status == 0: Event object is reset and no threads are waiting.
// m_status == -N: Event object is reset and N threads are waiting.
std::atomic m_status;
Semaphore m_sema;
В методе signal мы атомарно увеличиваем значение переменной m_status, пока ее значение не достигнет 1:
public:
void signal()
{
int oldStatus = m_status.load(std::memory_order_relaxed);
for (;;) // Increment m_status atomically via CAS loop.
{
assert(oldStatus <= 1);
int newStatus = oldStatus < 1 ? oldStatus + 1 : 1;
if (m_status.compare_exchange_weak(oldStatus, newStatus,
std::memory_order_release,
std::memory_order_relaxed))
break;
// The compare-exchange failed, likely because another thread changed m_status.
// oldStatus has been updated. Retry the CAS loop.
}
if (oldStatus < 0)
m_sema.signal(); // Release one waiting thread.
}
Используя все тот же паттерн box office мы можем реализовать примитив для read-write блокировок.
Данный примитив не блокирует потоки в отсутствие писателей. Кроме того, он является starvation-free и для писателей и для читателей, и, как и другие примитивы, может временно захватывать spin lock перед тем как заблокировать исполнение текущего потока. Для реализации этого примитива требуются два семафора: один для ожидающих читателей, другой — для писателей.
При помощи паттерна box office можно решить проблему обедающих философов, причем довольно необычным способом, который мне раньше нигде не встречался. Я не очень-то верю, что предложенное решение окажется полезным для кого-то, так что я не буду вдаваться в детали реализации. Я включил описание этого примитива только для того, чтобы продемонстрировать универсальность семафоров.
Итак, мы назначаем каждому философу (потоку) свой собственный семафор. Box office следит за тем, кто из философов в данный момент принимает пищу, кто из философов попросил начать трапезу и за очередностью этих запросов. Этой информации достаточно, чтобы box office мог провести всех философов через прикрепленные к ним семафоры оптимальным способом.
Я предложил целых две реализации. Одна из них DiningPhilosophers, которая реализует box office, используя мьютекс. Вторая — LockReducedDiningPhilosophers, в которой каждое обращение к box office реализовано в виде lock-free алгоритма.
Да, все верно: при помощи паттерна box office и семафора мы можем реализовать… другой семафор.
Зачем нам это делать? Потому что тогда мы получим LightweightSemaphore. У такого семафора очень дешевая операция signal, когда в очереди нет ожидающих потоков. К тому же она не зависит от реализации семафора, предоставляемого ОС. При вызове signal, box office увеличивает значение собственного внутреннего счетчика, не обращаясь к нижележащему семафору.
Кроме того, можно заставить поток некоторое время ожидать в цикле, и лишь потом блокировать его. Этот трюк позволяет снизить накладные расходы связанные с системным вызовом, если время ожидание меньше какого-то наперед заданного значения.
В GitHub репозитории все примитивы реализованы на основе LightweightSemaphore. Этот класс реализован на основе Semaphore, который в свою очередь реализован на базе семафоров, предоставляемых конкретной ОС.
Я прогнал несколько тестов для сравнения скорости работы представленных примитивов при использвании LightweightSemaphore и Semaphore на моем PC под управлением Windows. Соответствующие результаты приведены в таблице:
| LightweightSemaphore | Semaphore | |
|---|---|---|
| testBenaphore | 375 мс | 5503 мс |
| testRecursiveBenaphore | 393 мс | 404 мс |
| testAutoResetEvent | 593 мс | 4665 мс |
| testRWLock | 598 мс | 7126 мс |
| testDiningPhilosophers | 309 мс | 580 мс |
Как вы можете видеть, время работы отличается иногда на порядок. Надо сказать, я отдаю себе отчет в том, что далеко не в каждом окружении будут такие же или похожие результаты. В текущей реализации поток ждет в течение 10 000 итераций цикла перед тем как заблокироваться на семафоре. Я бегло рассматривал возможность использования адаптивного алгоритма, но наилучший способ показался мне неочевидным. Так что я открыт для предложений.
Семафоры оказались гораздо более полезными примитивами, чем я ожидал. Почему же тогда они отсутствуют в C++11 STL? По той же причине, по которой они отсутствовали в Boost: предпочтение отдали мьютексам и условным переменным. С точки зрения разработчиков библиотеки, применение традиционных семафоров слишком часто приводит к ошибкам.
Если подумать, то паттерн box office это всего лишь оптимизация обычных условных переменных для случая, когда все операции над условными переменными исполняются в конце критической секции. Рассмотрим класс AutoResetEvent. Я реализовал класс AutoResetEventCondVar с таким же поведением, но при помощи std:condition_variable. Все операции над условной переменной выполняются в конце критической секции.
void AutoResetEventCondVar::signal()
{
// Increment m_status atomically via critical section.
std::unique_lock lock(m_mutex);
int oldStatus = m_status;
if (oldStatus == 1)
return; // Event object is already signaled.
m_status++;
if (oldStatus < 0)
m_condition.notify_one(); // Release one waiting thread.
}
Мы можем оптимизировать этот метод за два итерации:
После этих двух простых оптимизаций мы получим AutoResetEvent.
На моем PC под управлением Windows простая замена AutoResetEventCondVar на AutoResetEvent увеличивает скорость работы алгоритма в 10 раз.
Прочтение данной статьи про семафор в многопоточных приложениях позволяет сделать вывод о значимости данной информации для обеспечения качества и оптимальности процессов. Надеюсь, что теперь ты понял что такое семафор в многопоточных приложениях, семафор и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Операционные системы и системное программировние
Комментарии
Оставить комментарий
Операционные системы и системное программировние
Термины: Операционные системы и системное программировние