<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE en-note SYSTEM "http://xml.evernote.com/pub/enml2.dtd">
<en-note><div style="position:relative;"><div style="margin-bottom:10px;font-size:14px;line-height:22.4px;font-family:Verdana,sans-serif;overflow-x:hidden;overflow-y:hidden;">
      <i style="font-size:14px;"><b style="font-size:14px;">От переводчика:</b> Джефф Прешинг (Jeff Preshing) — канадский разработчик программного обеспечения, последние 12 лет работающий в Ubisoft Montreal. Он приложил руку к созданию таких известных франшиз как Rainbow Six, Child of Light и Assassin’s Creed. У себя в блоге он часто пишет об интересных аспектах параллельного программирования, особенно применительно к Game Dev. Сегодня я бы хотел представить на суд общественности перевод одной из статей Джеффа.</i><div/>
<div/>
Поток должен ждать. Ждать до тех пор, пока не удастся получить эксклюзивный доступ к ресурсу или пока не появятся задачи для исполнения. Один из механизмов ожидания, при котором поток не ставится на исполнение планировщиком ядра ОС, реализуется при помощи <b style="font-size:14px;font-style:normal;">семафора</b>.<div/>
<div/>
Раньше я думал, что семафоры давно устарели. В 1960‑х, когда еще мало кто писал многопоточные программы, или любые другие программы, Эдсгер Дейкстра предложил идею нового механизма синхронизации — семафор. Я знал, что при помощи семафоров можно вести учет числа доступных ресурсов или создать неуклюжий аналог мьютекса, но этим, как я считал, область их применения ограничивается.<div/>
<a name="habracut" href="http://habrahabr.ru/post/261273/null" style="border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);"/><div/>
Мое мнение изменилось, когда я понял, что, используя только семафоры и атомарные операции, можно создать все остальные примитивы синхронизации:<div/>
<ol style="margin-block-start:;margin-block-end:;-moz-padding-start:;margin-top:0px;margin-bottom:0px;font-size:14px;">
<li style="font-size:14px;">Легковесные мьютексы</li>
<li style="font-size:14px;">Легковесные условные переменные</li>
<li style="font-size:14px;">Легковесные read-write блокировки</li>
<li style="font-size:14px;">Примитив для решения проблемы обедающих философов</li>
<li style="font-size:14px;">Легковесный семафор</li>
</ol><div/>
Все эти примитивы являются легковесными в том смысле, что некоторые операции над ними исполняются полностью в userspace, и они могут (это необязательное условие) некоторое время крутиться в цикле, перед тем как запросить блокировку потока у операционной системы (примеры доступны <a href="https://github.com/preshing/cpp11-on-multicore" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">на GitHub</a>.) В моей библиотеке примитивов реализован класс <em style="font-size:14px;">Semaphore</em>, который является оберткой над системными семафорами Windows, MacOS, iOS, Linux и других POSIX-совместимых ОС. Вы можете легко добавить любой из этих примитивов в свой проект.<div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">Семафор-вышибала</b></h4><div/>
Представьте себе множество потоков ожидающих исполнения, выстроенных в очередь, прямо как очередь перед входом в модный ночной клуб. Семафор — это вышибала перед входом. Он позволяет пройти внутрь клуба только когда ему дают соответствующее указание. <div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="0b87cc9bbc9960f8e3b48a76e0c92ae4" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Каждый поток сам решает когда встать в эту очередь. Дейкстра назвал эту операцию <em style="font-size:14px;">P</em>, что наверняка являлось отсылкой к какому-то забавно звучащему голландскому термину, но в современных реализациях семафоров вы, скорее всего, обнаружите только операцию <em style="font-size:14px;">wait</em>. По сути, когда поток вызывает метод <em style="font-size:14px;">wait</em>, он становится в очередь.<div/>
<div/>
Вышибала, т.е. семафор, должен уметь делать только одну операцию. Дейкстра назвал эту операцию <em style="font-size:14px;">V</em>. На сегодняшний день нет согласия в том, как именовать эту операцию. Как правило, можно встретить функции <em style="font-size:14px;">post</em>, <em style="font-size:14px;">release</em> или <em style="font-size:14px;">signal</em>. Я предпочитаю <em style="font-size:14px;">signal</em>. При вызове этого метода семафор «отпускает» из очереди один из ожидающих потоков. (Совсем не обязательно это будет тот же поток, который вызвал <em style="font-size:14px;">wait</em> раньше других.)<div/>
<div/>
А что происходит, если кто-то вызовет <em style="font-size:14px;">signal</em>, когда в очереди нет потоков? Нет проблем: когда какой-либо из потоков вызовет <em style="font-size:14px;">wait</em>, семафор сразу же пропустит этот поток без блокировки. Более того, если <em style="font-size:14px;">signal</em> вызовут 3 раза подряд при пустой очереди, то семафор разрешит следующим трем потокам, вызвавшим <em style="font-size:14px;">wait</em>, миновать очередь без ожидания.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="2e0b0ecd429eda71df5e9f2fb5f95c60" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Само собой разумеется, что семафор должен подсчитывать количество вызовов <em style="font-size:14px;">signal</em> при пустой очереди. Поэтому каждый семафор снабжен внутренним счетчиком, значение которого увеличивается при вызове <em style="font-size:14px;">signal</em> и уменьшается при вызове <em style="font-size:14px;">wait</em>.<div/>
<div/>
Прелесть такого подхода в том, что вне зависимости от того в какой очередности вызываются <em style="font-size:14px;">wait</em> и <em style="font-size:14px;">signal</em>, результат всегда будет одним и тем же: семафор всегда пропустит на исполнение одинаковое количество потоков, и в очереди всегда останется одно и то же количество ожидающих.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="4ceca48fa7a570e769ffe9322626accc" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">1. Легковесный мьютекс</b></h4><div/>
Я уже рассказывал, как можно реализовать собственный легковесный мьютекс <a href="http://preshing.com/20120226/roll-your-own-lightweight-mutex/" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">в одной из предыдущих статей</a>. В то время я не знал, что это только один из примеров применения общего паттерна, основная идея которого заключается в том, чтобы делегировать принятие решений о блокировке потоков некоторой новой сущности — <b style="font-size:14px;font-style:normal;">box office</b>. Должен ли текущий поток ждать в очереди? Должен ли он пройти семафор без ожидания? Должны ли мы разбудить какой-то другой поток?<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="6241be4599fad8181ce93ff09742073a" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Box office ничего не знает о количестве потоков, ожидающих в очереди, как не знает он и текущее значение внутреннего счетчика семафора. Вместо этого он должен каким-то образом хранить историю собственных состояний. Если мы говорим о реализации легковесного мьютекса, то для хранения истории достаточно одного счетчика с атомарными операциями инкремента и декремента. Я назвал этот счетчик <em style="font-size:14px;">m_contention</em>, т.к. он хранит информацию о том, сколько потоков одновременно желают захватить мьютекс.<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;"><span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);"><span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">class</span> <span>LightweightMutex</span></span>
{
<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">private:</span>
    <span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">std:</span><span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">:atomic&lt;int&gt;</span> m_contention;         <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">The</span> <span style="border-top-color:rgb(51, 153, 0);border-bottom-color:rgb(51, 153, 0);outline-color:rgb(51, 153, 0);color:rgb(51, 153, 0);">"box office"</span>
    <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">Semaphore</span> m_semaphore;                 <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">The</span> <span style="border-top-color:rgb(51, 153, 0);border-bottom-color:rgb(51, 153, 0);outline-color:rgb(51, 153, 0);color:rgb(51, 153, 0);">"bouncer"</span>
</code></pre><div/>
Когда поток хочет захватить мьютекс, он обращается к box office, который в свою очередь увеличивает значение <em style="font-size:14px;">m_contention</em>.<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;"><span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">public</span>:
    <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">void</span> lock()
    {
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (m_contention<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.fetch_add</span>(<span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>, std::memory_order_acquire) &gt; <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">0</span>)  <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Visit the box office</span>
        {
            m_semaphore<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.wait</span>();     <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Enter the wait queue</span>
        }
    }
</code></pre><div/>
Если значение счетчика равно нулю, значит мьютекс находится в неотмеченном состоянии. В этом случае текущий поток автоматически становится владельцем мьютекса, минует семафор без ожидания и продолжает работу в секции кода, защищенной мьютексом.<div/>
<div/>
Если же мьютекс уже захвачен другим потоком, то значение счетчика будет больше нуля и текущий поток должен ожидать своей очереди для входа в критическую секцию.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="65ec5ec8d99a355dffec4a5adb806628" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Когда поток освобождает мьютекс, box office уменьшает значение внутреннего счетчика на единицу:<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;">    <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">void</span> unlock()
    {
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (m_contention<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.fetch_sub</span>(<span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>, std::memory_order_release) &gt; <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>)  <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Visit the box office</span>
        {
            m_semaphore<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.signal</span>();   <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Release a waiting thread from the queue</span>
        }
    }
</code></pre><div/>
Если значение счетчика до декремента было меньше 1, значит в очереди нет ожидающих потоков и значение <em style="font-size:14px;">m_contention</em> просто остается равным 0.<div/>
<div/>
Если же значение счетчика было больше 1, значит другой поток или несколько потоков пытались захватить мьютекс, и, следовательно, ожидают своей очереди войти в критическую секцию. В этом случае мы вызываем <em style="font-size:14px;">signal</em>, чтобы семафор разбудил один из потоков и дал ему возможность захватить мьютекс.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="b567c227a603b417a93f83f1f71170f0" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Каждое обращение к box office — это атомарная операция. Таким образом, даже если несколько потоков будут вызывать <em style="font-size:14px;">lock</em> и <em style="font-size:14px;">unlock</em> параллельно, они всегда будут обращаться к box office последовательно. Более того, поведение мьютекса полностью определяется внутренним состоянием box office. После обращения к box office, потоки могут вызывать методы семафора в любом порядке, и это никоим образом не нарушит согласованности исполнения. (В худшем случае потоки поборются за место в очереди семафора.)<div/>
<div/>
Данный примитив можно назвать «легковесным», так как он позволяет потоку захватить мьютекс без обращения к семафору, т.е. без совершения системного вызова. Я опубликовал код мьютекса на GitHub под названием <b style="font-size:14px;font-style:normal;">NonRecursiveBenaphore</b>, там же есть и рекурсивная версия легковесного мьютекса. Тем не менее, нет предпосылок использовать этим примитивы на практике, т.к. большинство известных реализаций мьютексов и так являются <a href="http://preshing.com/20111124/always-use-a-lightweight-mutex/" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">легковесными</a>. Тем не менее, этот код служит необходимой иллюстрацией подхода, который используется для всех прочих примитивов, описанных в данной статье.<div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">2. Легковесная условная переменная</b></h4><div/>
<i style="font-size:14px;"><b style="font-size:14px;">Прим. пер.:</b> в оригинале автор назвал этот примитив Auto-Reset Event Object, однако поисковики по такому запросу выдают ссылки на C# класс AutoResetEvent, поведение которого можно с небольшими допущениями сравнивать с std::condition_variable.</i><div/>
<div/>
На <a href="http://habrahabr.ru/company/infopulse/blog/241674/" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">CppCon 2014</a> я отметил для себя, что условные переменные широко используются при созднии игровых движков, чаще всего — для уведомления одним потоком другого (возможно находящегося в режиме ожидания) о наличии для него некоторой работы (<i style="font-size:14px;">прим.пер.: в качестве такой работы может выступать задача распаковки графических ресурсов и загрузка их в GL context</i>).<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="e937217439917ac460c5a856856a33cf" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Другими словами, сколько бы раз не вызывался метод <em style="font-size:14px;">signal</em>, внутренний счетчик условной переменной не должен становиться больше 1. На практике это означает, что можно ставить задачи в очередь на исполнение, каждый раз вызывая метод <em style="font-size:14px;">signal</em>. Этот подход работает, даже если для назначения задач на исполнение используется структура данных отличная от <i style="font-size:14px;">queue</i>.<div/>
<div/>
Некоторые ОС предоставляют системные средства для организации условных переменных или их аналогов. Однако, если вы добавляете в очередь несколько тысяч задач за раз, то вызовы метода <i style="font-size:14px;">signal</i> могут сильно повлиять на быстродействие всего приложения.<div/>
<div/>
К счастью, паттерн box office позволяет значительно снизить накладные расходы, связанные с вызовом метода <i style="font-size:14px;">signal</i>. Логика может быть реализована внутри сущности box office при помощи атомарных операций так, чтобы обращение к семафору осуществлялось только тогда, когда необходимо заставить поток ожидать своей очереди.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="ba6baf1ff59f5543b3fa57e14d502fb5" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Я реализовал этот примитив и назвал его <b style="font-size:14px;font-style:normal;">AutoResetEvent</b>. На этот раз box office использует другой способ учета количества потоков, ожидающих в очереди. При отрицательном <i style="font-size:14px;">m_status</i>, его абсолютное значение показывает количество потоков ожидающих на семафоре:<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;"><span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);"><span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">class</span> <span>AutoResetEvent</span></span>
{
private:
    <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> m_status == <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>: Event object <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">is</span> signaled.
    <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> m_status == <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">0</span>: Event object <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">is</span> reset <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">and</span> <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">no</span> threads are waiting.
    <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> m_status == -N: Event object <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">is</span> reset <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">and</span> N threads are waiting.
    std::atomic&lt;int&gt; m_status;
    Semaphore m_sema;
</code></pre><div/>
В методе <i style="font-size:14px;">signal</i> мы атомарно увеличиваем значение переменной <i style="font-size:14px;">m_status</i>, пока ее значение не достигнет 1:<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;"><span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">public</span>:
    <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">void</span> signal()
    {
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">int</span> oldStatus = m_status<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.load</span>(std::memory_order_relaxed);
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">for</span> (;;)    <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Increment m_status atomically via CAS loop.</span>
        {
            assert(oldStatus &lt;= <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>);
            <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">int</span> newStatus = oldStatus &lt; <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span> ? oldStatus + <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span> : <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>;
            <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (m_status<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.compare_exchange_weak</span>(oldStatus, newStatus, 
                                                                           std::memory_order_release, 
                                                                           std::memory_order_relaxed))
                <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">break</span>;
            <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// The compare-exchange failed, likely because another thread changed m_status.</span>
            <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// oldStatus has been updated. Retry the CAS loop.</span>
        }
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (oldStatus &lt; <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">0</span>)
            m_sema<span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">.signal</span>();    <span style="border-top-color:rgb(128, 128, 128);border-bottom-color:rgb(128, 128, 128);outline-color:rgb(128, 128, 128);color:rgb(128, 128, 128);">// Release one waiting thread.</span>
    }
</code></pre><div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">3. Легковесная read-write блокировка</b></h4><div/>
Используя все тот же паттерн box office мы можем реализовать примитив для read-write блокировок.<div/>
<div/>
Данный примитив не блокирует потоки в отсутствие писателей. Кроме того, он является starvation-free и для писателей и для читателей, и, как и другие примитивы, может временно захватывать spin lock перед тем как заблокировать исполнение текущего потока. Для реализации этого примитива требуются два семафора: один для ожидающих читателей, другой — для писателей.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="e1b7643069a7bfda82a65728b8df836d" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">4. Проблема обедающих философов</b></h4><div/>
При помощи паттерна box office можно решить проблему обедающих философов, причем довольно необычным способом, который мне раньше нигде не встречался. Я не очень-то верю, что предложенное решение окажется полезным для кого-то, так что я не буду вдаваться в детали реализации. Я включил описание этого примитива только для того, чтобы продемонстрировать универсальность семафоров.<div/>
<div/>
Итак, мы назначаем каждому философу (потоку) свой собственный семафор. Box office следит за тем, кто из философов в данный момент принимает пищу, кто из философов попросил начать трапезу и за очередностью этих запросов. Этой информации достаточно, чтобы box office мог провести всех философов через прикрепленные к ним семафоры оптимальным способом.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="1aa8ce009ca1e1791f5d2856d12b956c" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Я предложил целых две реализации. Одна из них <b style="font-size:14px;font-style:normal;">DiningPhilosophers</b>, которая реализует box office, используя мьютекс. Вторая — <b style="font-size:14px;font-style:normal;">LockReducedDiningPhilosophers</b>, в которой каждое обращение к box office реализовано в виде lock-free алгоритма.<div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">5. Легковесный семафор</b></h4><div/>
Да, все верно: при помощи паттерна box office и семафора мы можем реализовать… другой семафор.<div/>
<div/>
Зачем нам это делать? Потому что тогда мы получим <b style="font-size:14px;font-style:normal;">LightweightSemaphore</b>. У такого семафора очень дешевая операция <i style="font-size:14px;">signal</i>, когда в очереди нет ожидающих потоков. К тому же она не зависит от реализации семафора, предоставляемого ОС. При вызове <i style="font-size:14px;">signal</i>, box office увеличивает значение собственного внутреннего счетчика, не обращаясь к нижележащему семафору.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="3d78a31af6e25546a09ba542d22685ca" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Кроме того, можно заставить поток некоторое время ожидать в цикле, и лишь потом блокировать его. Этот трюк позволяет снизить накладные расходы связанные с системным вызовом, если время ожидание меньше какого-то наперед заданного значения.<div/>
<div/>
В <a href="https://github.com/preshing/cpp11-on-multicore/tree/master/common" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">GitHub репозитории</a> все примитивы реализованы на основе <b style="font-size:14px;font-style:normal;">LightweightSemaphore</b>. Этот класс реализован на основе <b style="font-size:14px;font-style:normal;">Semaphore</b>, который в свою очередь реализован на базе семафоров, предоставляемых конкретной ОС.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="8c243c0865769e74ba9170dd0ec09d0d" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
Я прогнал несколько тестов для сравнения скорости работы представленных примитивов при использвании <i style="font-size:14px;">LightweightSemaphore</i> и <i style="font-size:14px;">Semaphore</i> на моем PC под управлением Windows. Соответствующие результаты приведены в таблице:<div/>
<table style="writing-mode:;border-spacing:0px 0px;border-collapse:collapse;margin-top:21px;margin-bottom:21px;border-top-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;clear:both;width:1000px;">
<tbody style="vertical-align:baseline;font-size:14px;"><tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;"/>
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">LightweightSemaphore</th>
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">Semaphore</th>
</tr>
<tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">testBenaphore</th>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">375 мс</td>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">5503 мс</td>
</tr>
<tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">testRecursiveBenaphore</th>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">393 мс</td>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">404 мс</td>
</tr>
<tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">testAutoResetEvent</th>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">593 мс</td>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">4665 мс</td>
</tr>
<tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">testRWLock</th>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">598 мс</td>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">7126 мс</td>
</tr>
<tr style="vertical-align:baseline;font-size:14px;">
<th style="vertical-align:baseline;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">testDiningPhilosophers</th>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">309 мс</td>
<td style="vertical-align:baseline;text-align:left;padding-top:4.2px;padding-bottom:4.2px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(204, 204, 204);border-bottom-color:rgb(204, 204, 204);font-size:14px;">580 мс</td>
</tr>
</tbody></table><div/>
Как вы можете видеть, время работы отличается иногда на порядок. Надо сказать, я отдаю себе отчет в том, что далеко не в каждом окружении будут такие же или похожие результаты. В текущей реализации поток ждет в течение 10 000 итераций цикла перед тем как заблокироваться на семафоре. Я бегло рассматривал возможность использования адаптивного алгоритма, но наилучший способ показался мне неочевидным. Так что я открыт для предложений.<div/>
<div/>
<h4 style="font-size:16.8px;font-weight:400;margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-family:Verdana,sans-serif;"><b style="font-size:16.8px;font-style:normal;">Сравнение семафоров и условных переменных</b></h4><div/>
Семафоры оказались гораздо более полезными примитивами, чем я ожидал. Почему же тогда они отсутствуют в C++11 STL? По той же причине, по которой они отсутствовали в Boost: предпочтение отдали мьютексам и условным переменным. С точки зрения разработчиков библиотеки, применение традиционных семафоров <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2043.html#SemaphoreTypes" style="cursor:pointer;color:rgb(109, 163, 189);text-decoration-color:rgb(109, 163, 189);border-top-color:rgb(109, 163, 189);border-bottom-color:rgb(109, 163, 189);font-size:14px;outline-color:rgb(109, 163, 189);">слишком часто приводит к ошибкам</a>.<div/>
<div/>
Если подумать, то паттерн box office это всего лишь оптимизация обычных условных переменных для случая, когда все операции над условными переменными исполняются в конце критической секции. Рассмотрим класс AutoResetEvent. Я реализовал класс AutoResetEventCondVar с таким же поведением, но при помощи std:condition_variable. Все операции над условной переменной выполняются в конце критической секции.<div/>
<pre style="margin-block-start:;margin-block-end:;margin-top:0px;margin-bottom:0px;font-size:14px;word-break:break-all;overflow-y:hidden;overflow-x:auto;"><code style="font-family:Menlo,Monaco,&quot;Courier New&quot;,monospace;padding-top:1px;padding-bottom:1px;border-top-width:1px;border-bottom-width:1px;border-top-style:solid;border-bottom-style:solid;border-top-color:rgb(225, 225, 232);border-bottom-color:rgb(225, 225, 232);outline-color:rgb(34, 34, 34);background-color:rgb(247, 247, 249);display:block;white-space:pre-wrap;color:rgb(34, 34, 34);border-top-left-radius:3px;border-top-right-radius:3px;border-bottom-right-radius:3px;border-bottom-left-radius:3px;">void <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">AutoResetEventCondVar::</span>signal()
{
    <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">Increment</span> m_status atomically via critical section.
    <span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">std:</span><span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">:unique_lock&lt;std</span><span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">:</span><span style="border-top-color:rgb(150, 142, 91);border-bottom-color:rgb(150, 142, 91);outline-color:rgb(150, 142, 91);color:rgb(150, 142, 91);">:mutex&gt;</span> lock(m_mutex);
    int oldStatus = m_status;
    <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (oldStatus == <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">1</span>)
        <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">return</span>;     <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">Event</span> object is already signaled.
    m_status++;
    <span style="border-top-color:rgb(77, 115, 134);border-bottom-color:rgb(77, 115, 134);outline-color:rgb(77, 115, 134);color:rgb(77, 115, 134);">if</span> (oldStatus &lt; <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">0</span>)
        m_condition.notify_one();   <span style="border-top-color:rgb(47, 152, 255);border-bottom-color:rgb(47, 152, 255);outline-color:rgb(47, 152, 255);color:rgb(47, 152, 255);">//</span> <span style="border-top-color:rgb(34, 34, 34);border-bottom-color:rgb(34, 34, 34);outline-color:rgb(34, 34, 34);">Release</span> one waiting thread.
}
</code></pre><div/>
Мы можем оптимизировать этот метод за два итерации:<div/>
<ol style="margin-block-start:;margin-block-end:;-moz-padding-start:;margin-top:0px;margin-bottom:0px;font-size:14px;">
<li style="font-size:14px;">Вынесем каждую условную переменную из критической секции и преобразуем ее в семафор. Независимость последовательности операций <i style="font-size:14px;">signal</i> — <i style="font-size:14px;">wait</i> над семафором делает такую оптимизацию возможной. После этого шага наша реализация метода уже похожа на реализацию паттерна box office.</li>
<li style="font-size:14px;">Теперь мы можем сделать метод lock-free, заменив все операции на CAS, тем самым резко повысив масштабируемость системы.</li>
</ol><div/>
После этих двух простых оптимизаций мы получим AutoResetEvent.<div/>
<div/>
<div style="font-size:14px;text-align:center;"><en-media hash="4f5cd290ebc86289f6e5b80755424aef" type="image/png" style="font-size:14px;vertical-align:middle;max-width:1000px;"/></div><div/>
<div/>
На моем PC под управлением Windows простая замена AutoResetEventCondVar на AutoResetEvent увеличивает скорость работы алгоритма в 10 раз.<div/>
<div/>
<em style="font-size:14px;">От переводчика: я давно ничего не переводил, так что буду благодарен за исправления и уточнения.</em>
  	<div style="font-size:14px;clear:both;"/>
    </div></div></en-note>
