company_banner

Многопоточность на низком уровне

    Очень часто при обсуждении многопоточности на платформе .NET говорят о таких вещах, как детали реализации механизма async/await, Task Asynchronous Pattern, deadlock, а также разбирают System.Threading. Все эти вещи можно назвать высокоуровневыми (относительно темы хабрапоста). Но что же происходит на уровне железа и ядра системы (в нашем случае — Windows Kernel)?


    На конференции DotNext 2016 Moscow Гаэл Фретёр, основатель и главный инженер компании PostSharp, рассказал о том, как в .NET реализована многопоточность на уровне железа и взаимодействия с ядром операционной системы. Несмотря на то, что прошло уже пять лет, мы считаем, что никогда не поздно поделиться хардкорным докладом. Гаэл представил нам хорошую базу по работе процессора и атомным примитивам.



    Вот репозиторий с примерами из доклада. А под катом — перевод доклада и видео. Далее повествование будет от лица спикера.



    Сегодня я хотел бы поговорить о многопоточности на самом низком уровне. В докладе не будет ничего принципиально нового, всё это уже было в версии .NET 1.0. Однако, я потратил несколько недель на то, чтобы изучить спецификацию AMD64 и структурировать информацию.


    У этого доклада две цели:


    • дать точное понимание того, как происходят многопоточные вычисления на низком уровне
    • научить создавать высокопроизводительный многопоточный код.

    Сначала мы разберем, что происходит на уровне железа: CPU и уровни памяти, всё, что с ними происходит. Далее перейдем к ядру Windows. А после этого обсудим на первый взгляд простые вещи, такие как lock. Скорее всего, вы и сами знаете, зачем нужно это ключевое слово. Я же собираюсь объяснить, как оно реализовано.


    Микроархитектура


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



    Это что-то вроде Intel Core i7 своего времени. Как вы видите, за 70 лет была проделана большая работа.


    К чему это все? Обычно предполагают, что байт памяти представлен где-нибудь в ячейке оперативной памяти. Но на самом деле всё иначе: он может быть представлен в нескольких местах одновременно. Например, в шести ядрах, может быть в кэшах L1 и L2, в кэше L3, наконец, может быть в оперативной памяти. Важно упомянуть: в этой архитектуре процессора есть общий кэш L3, и между ними есть Uncore. Этот компонент отвечает за координацию ядер. Также есть QPI, который отвечает за разницу между CPU. Это относится только к мультипроцессорным системам.



    Почему нас беспокоит архитектура процессора? По той же причине, по которой нам нужны несколько разных уровней кэшей. У каждого уровня своя задержка. Обращаю внимание на то, что цикл CPU на этой спецификации занимает 0,3 наносекунды и сравнивается с задержкой кэшей L1, L2, L3 и DRAM. Важно заметить, что извлечение конструкции из DRAM требует около 70 циклов процессора. Если вы хотите рассчитать эти значения для своего процессора, то могу посоветовать хороший бенчмарк SiSoft Sandra.



    Теперь давайте посмотрим на это более подробно. Для простоты предположим, что здесь у меня есть двухпроцессорная система. У каждого из процессоров есть четыре ядра и L2-кэш, а L1-кэш отсутствует. Также есть L3-кэш и общая оперативная память.



    Хорошая аналогия для понимания многопоточных систем — распределенные системы.


    Если вы знаете, что такое очередь сообщений (message queue) или шина данных (message bus), вам будет легче понять многопоточность: похожие вещи есть внутри вашего процессора. Там есть очередь сообщений, шина сообщений, буферы — из-за всего этого у нас возникают проблемы с синхронизацией. При взаимодействии ядер информация распределена между L2 и L3-кэшами и памятью. Поскольку шины сообщений асинхронны, порядок обработки данных не гарантирован. Кроме кэширования процессор буферизует данные и может решить оптимизировать операции и отправлять сообщения на шину в другом порядке.


    Переупорядочивание памяти


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



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



    Итак, давайте рассмотрим одну архитектуру. Пусть это будет x86 или AMD64, здесь не так много Y. Это означает, что она дает нам много гарантий в разных вопросах. На самом деле, x86 изначально не разрабатывался под многоядерные процессоры, поэтому когда Intel начали добавлять новые ядра, они решили сохранить ту же семантику, что раньше.


    По таблице видим, что процессор с этой архитектурой может переупорядочить операции «сохранить» (store), после операций «загрузить» (load). Когда вы хотите сохранить значение, достаточно отправить сообщение. Ждать ответа не обязательно. А когда вы «загружаете» данные, вам нужно отправить запрос и ждать ответа. Для этой операции процессор может применить различные оптимизации.


    Теперь посмотрим на колонку ARM. Как видите, эта архитектура дает нам меньше гарантий. Причина очень проста: ARM не нацелена на совместимость с x86. Их целевые платформы были совершенно разные. А еще ARM использует слабую модель памяти, чтобы повысить производительность.


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


    На Intel x86 вы можете быть уверены, что переменные A и B идут строго последовательно, то есть если удалось загрузить B, то переменная A точно инициализирована. А если всё это выполняется на ARM, то у нас нет никаких гарантий, в каком порядке все это будет выполняться и как процессор проведет оптимизацию.



    Барьеры памяти



    Помимо оптимизации процессора, существует ещё оптимизация компилятора и среды выполнения. В контексте данной статьи под компилятором и средой я буду понимать JIT и CLR. Среда может кэшировать значения в регистрах процессора, переупорядочить операции и объединять операции записи (coalesce writes).


    Например, для цикла for CLR может решить заранее рассчитать значение и вынести локальную переменную за пределы цикла. Во избежание этого, конечно же, можно использовать ключевое слово volatile, но бывают и более сложные случаи.


    Иногда бывает нужно, чтобы весь код был точно выполнен до какой-либо определенной инструкции, и для этого используются барьеры памяти. Барьер памяти — это инструкция, которая реализуется процессором. В .NET она доступна с помощью вызова Thread.MemoryBarrier(). И что же он делает? Вызов этого метода гарантирует, что все операции перед этим методом точно завершились.


    Давайте снова вернемся к программе с двумя переменными. Предположим, что эти процессоры выполняют команды «сохранить» A и «загрузить» B. Если между этими двумя командами находится барьер памяти, то процессор сначала отправит запрос «сохранить» B, подождет, пока она не выполнится. Барьеры памяти дают возможность поставить что-то вроде чекпоинта или коммита, как в базе данных.



    Есть еще одна причина использовать барьеры памяти. Если вы пишете код на 32-битной машине с использованием long, DateTime или struct, то атомарность выполнения операций может нарушаться. Это значит, что даже когда в коде записана одна инструкция, на самом деле могут произойти две операции вместо одной, причем они могут выполняться в разное время.



    Атомарные операции


    Возникает вопрос: что же делать со всем этим беспорядком и неопределенностью? Как синхронизировать ядра? На помощь приходит System.Threading.Interlocked, и это единственный механизм в .NET, предоставляющий доступ к атомарным операциям и на аппаратном уровне.


    Когда мы говорим, что операция атомарна, мы имеем в виду, что она не может быть прервана. Это означает, что во время выполнения операции не может произойти переключение потока, операция не может частично завершиться. О разнице между атомарностью, эксклюзивностью и изменением порядка выполнения вы можете узнать из доклада Саши Гольдштейшна «Модели памяти C++ и CLR». Более подробно об атомарности рассказывал Карлен szKarlen Симонян в докладе «Атомарные операции и примитивы в .NET».

    Interlocked содержит такие операции, как инкрементирование (Increment), обмен (Exchange) и обмен через сравнение (CompareExchange).


    Я собираюсь разобрать не очень часто используемую операцию — CompareExchange, также известную как CAS. Она изменяет значение поля на новое только в том случае, если текущее поле равно какому-либо определенному значению. Эта операция необходима для всех параллельных структур.


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



    Не стоит забывать про стоимость выполнения Interlocked-операций. Стоимость инкрементирования в кэше L1 примерно равна удвоенной задержке кэша L1. Вполне быстро! Но стоимость использования Interlocked-инкремента составляет уже целых 5,5 наносекунд, даже если это происходит в единственном потоке. Этот показатель близок к показателю задержки кэша L3. А если у вас два потока обращаются к одной кэш-линии, то стоимость удваивается: ядрам приходится ждать друг друга.



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



    Многозадачность


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

    На уровне процессора нет таких понятий, как поток и процесс: всё, что мы называем многопоточностью, предоставляет операционная система. А Wait(), на самом деле, не может заставить процессор ждать. Эта команда переводит его в режим пониженного энергопотребления (lower energy state).


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


    Для процессора существует только понятие задачи (Task). Вместо потоков есть сегмент состояния задачи, который позволяет сменить таск. Состояние процессора означает состояние доступа к регистрам и маппинга памяти.



    Можно использовать compareExchange на примере очень простой реализации ConcurrentStack.


    Весь код (финальная версия):


    internal sealed class MyConcurrentStack<T>
    {
       private volatile Node head;
    
       public void Push(T value)
       {
           SpinWait wait = new SpinWait();
    
           Node node = new Node {Value = value};
    
           for ( ;; )
           {
               Node localHead = this.head;
               node.Next = localHead;
    
               if (Interlocked.CompareExchange(ref this.head, node, localHead) 
                   == localHead)
                   return;
    
               wait.SpinOnce();
           }
       }
    
       public bool TryPop(out T value)
       {
           SpinWait wait = new SpinWait();
    
           for ( ;; )
           {
               Node localHead = this.head;
    
               if (localHead == null)
               {
                   value = default(T);
                   return false;
               }
    
               if (Interlocked.CompareExchange(ref this.head,
                   localHead.Next, localHead) == localHead)
               {
                   value = localHead.Value;
                   return true;
               }
    
               wait.SpinOnce();
    
           }
       }
    
       #region Nested type: Node
    
       private sealed class Node
       {
           public Node Next;
           public T Value;
       }
    
       #endregion
    }

    Класс Node (внутри класса MyConcurrentStack<T>) хранит значение и содержит ссылку на следующий элемент.


    Давайте сначала посмотрим на неблокирующую реализацию стека:


    private sealed class Node
    {
       public Node Next;
       public T Value;
    }

    Посмотрим на неблокирующую реализацию стека, здесь мы не используем ключевое слово lock и wait-операции:


    private volatile Node head;
    
    public void Push(T value)
    {
    // первым делом создаем элемент стека, тут все просто
       Node node = new Node {Value = value};
    
       for ( ;; )
       {
    // записываем ссылку на текущую верхушку стека в локальную
    //переменную
           Node localHead = this.head;
    
    // для нового элемента указываем ссылку на следующий элемент,
    // которым будет являться текущая вершина стека
           node.Next = localHead;
    
    // меняем верхушку стека (this.head) на новый элемент (node),
    // если верхушка стека уже не была изменена
           if (Interlocked.CompareExchange(
               ref this.head, node, localHead) == localHead)
               return;
       }
    }

    Зачем здесь нужен условный оператор? Может случиться так, что два потока пытаются запушить новое значение в стек. Эти два потока видят одно и то же поле head. Первый поток начал вставлять новое значение до того, как это начал делать второй поток. После того как первый поток вставил значение, актуальная ссылка на headесть только у этого потока. У второго потока будет ссылка на элемент, который теперь считается следующим после head, то есть head.Next. Такая ситуация показывает, насколько важно бывает иметь такие атомарные операции, как CompareExchange.


    Этот способ решения задачи основан на неблокирующей структуре данных. В методе TryPop() мы используем тот же прием:


    public bool TryPop(out T value)
       {
           for ( ;; )
           {
               Node localHead = this.head;
    
               if (localHead == null)
               {
                   value = default(T);
                   return false;
               }
    
               if (Interlocked.CompareExchange(ref this.head, localHead.Next, 
                  localHead) == localHead)
               {
                   value = localHead.Value;
                   return true;
               }
           }
       }
    

    Берем head и заменяем её следующим узлом, если, конечно, она уже не была изменена.


    В время теста MyConcurentStack участвовало два ядра. Одно ядро выполняло операцию Push(), другое — операцию Pop(), ожидание отсутствовало в течение 6 миллионов операций по обмену сообщениями между двумя ядрами.


    У этой структуры данных есть два недостатка:


    1. необходимость очистки
    2. необходимость выделения памяти для элементов коллекции

    Другая структура данных лишена этих недостатков. Эта структура данных называется «кольцевой буфер». В кольцевом буфере вам не нужно каждый раз выделять память. Есть один большой участок памяти, который перезаписывается при необходимости.


    В результате все работает гораздо быстрее: 9 миллионов транзакций в секунду.


    public class TestMyConcurrentStack : TestCollectionBase
    {
       private readonly MyConcurrentStack<int> stack = 
           new MyConcurrentStack<int>();
    
       protected override void AddItems(int count)
       {
           for (int i = 0; i < count; i++)
           {
               this.stack.Push(i);
           }
       }
    
       protected override void ConsumeItems(int count)
       {
           SpinWait spinWait = new SpinWait();
           int value;
    
           for (int i = 0; i < count;)
           {
               if (this.stack.TryPop(out value))
               {
                   i++;
                   spinWait.Reset();
               }
               else
               {
                   spinWait.SpinOnce();
               }
           }
       }
    }
    


    Операционная система (ядро Windows)



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



    Здесь я хотел бы сделать одно замечание. Наверное, у многих сложилось впечатление, что поток делает какую-либо работу и выполняет задачи, но это не так. Основное предназначение потока — это ожидание.


    Давайте докажу это. На этом компьютере у меня четыре ядра с гипертредингом, то есть восемь логических процессоров. Всего в системе 2384 потока.Так как логических процессоров всего 8, то получается, что все 2376 потоков в данный момент ожидают, пока до них дойдет очередь выполнения. В 99,9% случаев основное занятие потоков — это ожидание.



    Одна из функций ядра Windows состоит в том, чтобы заставлять потоки ждать. У внутреннего ядра Windows есть граф зависимостей между потоками и объектами-диспетчерами (dispatcher objects) Среди этих объектов могут быть таймеры, объекты, семафоры и события.


    В какой-то момент некоторые зависимости исчезают, и соответствующие потоки переходят из состояния ожидания (wait) в состояние готовности (ready). Потоки в состоянии готовности отправляются в очередь ожидания, а после этого они уходят на разные ядра и начинают выполняться.


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


    Затем после ядра поток уходит обратно в очередь ожидания. Причина состоит в том, что закончилось время выполнения потока или была вызвана операция ожидания. Возвращение в очередь ожидания называется «вытесняющей многопоточностью».


    Когда вы запускаете поток ожидания, фактически создается зависимость между потоком и объектом диспетчера.



    Довольно интересный рассказ о реверс-инжиниринге планировщика Windows можно прочитать в статье «Планировщик Windows? Это очень просто».

    Стоимость диспетчеризации уровня ядра


    Сами объекты-диспетчеры, а это события, мьютексы, таймеры и семафоры — это объекты ядра. Они разделимы между процессами, и по этой причине считаются дорогими объектами.



    Посмотрите на график, посмотрите на стоимость инкрементирования или доступа к кэшу L1, а затем — на стоимость присваивания объекта диспетчера ядра. Две наносекунды и 295 наносекунд — огромная разница! А создание объекта диспетчера вообще занимает 2093 наносекунды.


    При разработке важно писать код, который не будут создавать объекты диспетчера лишний раз, иначе можно ожидать большую потерю производительности. На уровне .NET у нас есть Thread.Sleep, который использует внутренний таймер. Thread.Yield возвращает выполняющийся поток обратно в очередь ожидания потоков. Thread.Join блокирует вызывающий поток. Но сейчас я хочу более подробно рассказать про Thread.SpinWait.



    Структура SpinWait


    Первоначальная расшифровка этого блока была неточной. Спасибо DistortNeo и mvv-rus, указавшим на это в комментариях. Здесь речь идет о методе SpinWait.SpinOnce, а не Thread.SpinWait, как могло показаться до редактуры.

    Представьте, что у вас есть у вас есть два процессора, и на нулевом вы выполняете присваивание A = 1, потом устанавливаете барьер памяти, а затем снова выполняете присваивание B = 1.


    На первом процессоре вы получаете А, равное 1, а затем вы ждете, пока B не присвоят значение 1. Казалось бы, такие операции должны быстро выполниться и в кэше L1, и даже в кэше L3. Здесь загвоздка в том, что выполнение нулевым процессором может прерваться из-за вытесняющего прерывания, и между операциями из строк 1 и 3 может пройти несколько миллисекунд. SpinWait способен решать такие проблемы.



    Под капотом SpinOnce работает следующим образом:


    public void SpinOnce()
    {
        if (NextSpinWillYield)
        {
            CdsSyncEtwBCLProvider.Log.SpinWait_NextSpinWillYield();
            int num = (m_count >= 10) ? (m_count - 10) : m_count;
            if (num % 20 == 19)
            {
                Thread.Sleep(1);
            }
            else if (num % 5 == 4)
            {
                Thread.Sleep(0);
            }
            else
            {
                Thread.Yield();
            }
        }
        else
        {
            Thread.SpinWait(4 << m_count);
        }
        m_count = ((m_count == 2147483647) ? 10 : (m_count + 1));
    }

    1. Сначала происходит вызов Thread.SpinWait() (не происходит переключение контекста потока). Этот шаг будет пропущен для одноядерных процессоров:
      public bool NextSpinWillYield
      {
        get => m_count > YIELD_THRESHOLD || PlatformHelper.IsSingleProcessor;
      }
    2. Затем будет вызван Thread.Sleep(0) (может быть прерван потоками такого же приоритета)
    3. Затем, — Thread.Yield() (может быть прерван потоками любого приоритета)
    4. Если операция все еще не завершена, то будет вызван Thread.Sleep(1) (поток засыпает на 1мс)

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


    Монитор и ключевое слово lock


    Теперь давайте вернемся к ключевому слову lock. Скорее всего, вы знаете, что это просто синтаксический сахар для try/catch Monitor.Enter/Monitor.Exit. Чего вы можете не знать — это как устроены эти методы.


    [System.Security.SecuritySafeCritical]
    [MethodImplAttribute(MethodImplOptions.InternalCall)]
    public static extern void Enter(Object obj);
    
    [System.Security.SecuritySafeCritical]
    [MethodImplAttribute(MethodImplOptions.InternalCall)]
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
    public static extern void Exit(Object obj);

    Атрибут [MethodImplAttribute(MethodImplOptions.InternalCall)] означает, что методы реализованы в самом CLR. Алгоритм получения эксклюзивного доступа следующий:


    1. Выполняется Interlocked-операция: каждый объект в .NET имеет хедер, который говорит, на каком потоке он находится и для чего он заблокирован.
    2. Идёт SpinWait, если операция завершится неудачей.
    3. CLR создает kernel event, если выполнение SpinWait не дало ожидаемого результата. После нескольких миллисекунд ожидания создается еще один kernel event, но только в другом потоке.

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


    Структуры данных из пространства имен System.Collections.Concurrent


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


    Concurrent Stack


    В ConcurrentStack вводится понятие производителей и потребителей, которые конкурируют за то, чтобы получить верхушку стека.



    Concurrent Queue


    В другой структуре данных ConcurrentQueue потребители конкурируют за разные узлы. Это увеличивает пропускную способность в два раза: производители и потребители конкурируют между собой только в своей группе.



    Concurrent Bag


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



    Заключение


    1. На аппаратном уровне есть только операции Interlocked и барьеры памяти.
    2. На уровне ядра Windows вводится такая абстракция, как поток. Основное предназначение потока — это ожидание и хранение набора зависимостей.
    3. Также мы рассмотрели некоторые коллекции из стандартной библиотеки.

    Если доклад показался вам достаточно хардкорным, загляните на сайт конференции Dotnext 2021 Piter, которая пройдёт с 20 по 23 апреля. Основными темами станут настоящее и будущее платформы .NET, оптимизация производительности, внутреннее устройство платформ, архитектура и паттерны проектирования, нетривиальные задачи и best practices. На сайте начинают появляться первые доклады, со временем список будет пополняться.
    JUG Ru Group
    Конференции для программистов и сочувствующих. 18+

    Комментарии 16

      +4

      Про SpinWait вообще какая-то ересь написана.


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


      На самом деле:


      SpinWait — это самый обычный busy wait. Логической разницы между


      while (!condition()) {}

      и


      while (!condition()) { Thread.SpinWait(); }

      нет.


      Разница заключается только в том, что проверка условия может быть дорогой, поэтому, чтобы не насиловать шину атомарными операциями, имеет смысл между проверками вставлять задержку, но не настолько длинную, как при Thread.Sleep(0) и Yield.


      Ну а чтобы проц нагружать по-минимуму, под капотом Thread.SpinWait используется инструкция PAUSE. Это просто небольшая задержка, при которой проц отдыхает, что при HT/SMT бывает полезно.

        +2
        Крайне скучный метод:
        public void SpinOnce()
        {
        	if (NextSpinWillYield)
        	{
        		CdsSyncEtwBCLProvider.Log.SpinWait_NextSpinWillYield();
        		int num = (m_count >= 10) ? (m_count - 10) : m_count;
        		if (num % 20 == 19)
        		{
        			Thread.Sleep(1);
        		}
        		else if (num % 5 == 4)
        		{
        			Thread.Sleep(0);
        		}
        		else
        		{
        			Thread.Yield();
        		}
        	}
        	else
        	{
        		Thread.SpinWait(4 << m_count);
        	}
        	m_count = ((m_count == 2147483647) ? 10 : (m_count + 1));
        }
        
          +3

          Вы привели метод SpinWait.SpinOnce(), тогда как в статье речь идёт о Thread.SpinWait(). С автором решили проблему — статья будет немного дополнена и поправлена.

        +5
        С вашего позволения немного позанудствую.
        При использовании Thread.SpinWait() не происходит переключение контекста потока, текущий поток не передает управление планировщику задач Windows. Вместо этого запускается холостой цикл, который при каждой итерации возвращает поток обратно в очередь ожидания (прямо как Thread.Yield()), передавая управление потоку с таким же приоритетом, но не фоновому потоку.

        Что-то странное тут написано: «который при каждой итерации возвращает поток обратно в очередь ожидания» — это про Thread.Sleep(0), а не про SpinWait, который, судя по документации, просто крутит холостой цикл на указанное число итераций, безо всяких вызовов ядра в этом цикле. (UPD: пока писал, про это уже выше написали)
        Без SpinWait цикл может выполняться бесконечно, потому что если нулевой процессор запустится как фоновый поток, то первый процессор заблокирует этот фоновый поток, до тех пор пока поток на первом процессоре не будет прерван.

        Это — не про Windows, точнее — не про потоки обычных пользовательских программ, которые работают с приоритетами в диапазоне динамических приоритетов (1-15). Для этого диапазона планировщик в Windows, если видит, что какой-то поток вообще не получает управление, динамически повышает его приоритет на один или несколько квантов, чтобы поток имел шанс выполниться (как раз вот для подобных случаев).
        Тут, кстати, на Хабре была не так давно статья (может, помните), где автор как раз модифицировал планировщик в WinXP, чтобы избежать этого динамического повышения приоритетов — оно у него работу программы для real-time нарушало.
          +1

          Спасибо, поправил. Там действительно было написано неудачно.


          Тут, кстати, на Хабре была не так давно статья (может, помните), где автор как раз модифицировал планировщик в WinXP, чтобы избежать этого динамического повышения приоритетов — оно у него работу программы для real-time нарушало.

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

            +3
            Не видел, но если вдруг найдется ссылка, будет интересно почитать.

            Планировщик Windows? Это очень просто
            Там об этом мельком.
            А вообще информация об этом в книге «Windows Internals» уже давно есть, из изданиия в издание кочует — не помню, была ли она в первом, которое писала Хелен Кастер, но в тех издания, которые Руссинович делал, кажется, была уже сразу.
          +2

          В дополнение к статье: есть ещё один механизм межпотоковой синхронизации — WaitOnAddress, появившийся в Windows 8.1, и аналогичный ему функционал futex в Linux. Работа с ним оставила у меня положительные впечатления. Для использования из .NET, правда, нужно использовать pinvoke.

            0

            Судя по всему, речь шла о классе SpinWait который как раз использует стратегию отката к Sleep и Yield. А дальше не совсем верный пересказ о том, что busy-wait может очень сильно замедлить общий прогресс всех потоков (thread starvation), особенно если процессор с одним ядром.

              0

              Да, о нем. Я подредактирую статью, чтобы не путать читателей.

              +5
              Вот не пойму в подобных статьях, что такое реордеринг. Как будто есть какой-то порядок-ордеринг в многопроцессорной системе и он может не соблюдаться. То есть его нет, на самом то деле. Я еще понимаю натуральный порядок операций более менее в рамках одного потока и то о каком реордеринге идет речь, если операции исполняются в конвеерах параллельно и имеют предиктивное исполнение, то есть понятие начала и конца операции крайне размыто. Когда заканчивается операция записи в память? По идее когда в с-щей ячейке памяти появляется с-щее значение, или когда из процессора уходит команда на изменение?

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

              А в многопоточной системе? Гарантирует ли запрет на реордеринг 2х записей в ячейке А и Б, а потом 2х чтений оттуда же, что мы увидим при чтении тот же порядок (не увидим запись в Б и отсутствие записи А), что был при записи? Или это какое-то другое требование. Запрет на реордеринг только записей или только чтений вообще не имеет по идее никакого проверяемого эффекта. Как я понимаю, на той же альфе мы можем увидеть запись через гонку вообще в любой момент времени, а потом увидеть честную запись, а потом опять увидеть запись через гонку. В процессоре вообще кмк понятие времени сильно размазано.

              Все статья по многопоточке используют эту терминологию так, будто она всем широко известна. И есть какая-то за этим великая наука, которую все знают. А я вот сижу дурак дураком и до сих пор до конца это не понимаю. А я прилично конкаренси лет 10 уже занимаюсь минимум. Может кто посоветует по этим базам какие-то ссылки или лекции?
                +2
                Вот не пойму в подобных статьях, что такое реордеринг

                Иногда это Out-of-order execution, а иногда Memory ordering. Без контекста действительно не всегда ясно о чем именно речь. Вы какой абзац имеете в виду?


                Может кто посоветует по этим базам какие-то ссылки или лекции?

                Мне кажется, что в докладе Гольдштейшна о моделях памяти простым языком хорошо эти понятия определены.


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

                Вы имеете в виду SC for DRF?

                  0
                  >> Вы какой абзац имеете в виду?
                  Там где про гарантии железа.

                  >>Мне кажется, что в докладе Гольдштейшна о моделях памяти простым языком хорошо эти понятия определены.

                  Легче не стало.) Там тоже неявно вводится порядок и этот неявный порядок нарушается. Как будто операции это некие сущности, на которых еще и введен полный порядок, что очевидно не так. Все те же самые вопросы встают с неменьшей силой. Ну может просто я не соображаю, а остальным эти все концепции понятны. Хоть Java Memory Model мне понятна, там никаких реордерингов нет и логика строится на выстраивании отношений частичного порядка. Мне непонятно, какие именно гарантии я получаю от того, что операциям запрещен реордеринг. Особенно когда мой код проходит цепочку компилятор-jit-scheduller-cpu и они все могут вносить свои искажения в то, как он исполняется. Вот см. пример выше, если и чтения и записи идут с запретом реордеринга, я могу иметь гарантии, что не увижу их в другом порядке? А если только записи? Только чтения? Какие гарантии я получаю? Ну итд выше по списку, о каком вообще порядке может идти речь, если у меня в общем случае не линеаризуемый код.

                  >>Вы имеете в виду SC for DRF?
                  Видимо, я далек от языков низкого уровня и процессоров типа Альфы, где видимо это не всегда так. Поэтому боюсь, что термин мне незнаком. Но судя по вики очень похоже.
                    0

                    Про «гарантии железа» — это про модели памяти. Грубо говоря, в контексте архитектуры процессора это спецификации, определяющая какую дичь CPU может творить в плане перестановок операций. Например, вот параграф из описания модели памяти ARM:


                    The ARMv8-A architecture employs a weakly ordered model of memory. This means that the order of memory accesses is not necessarily required to be the same as the program order for load and store operations.

                    «Слабость» модели памяти ARM отражена на схеме: ARM позволяет себе гораздо больше вольностей, чем X86, поэтому, код, прекрасно работающий на x86, может быть подвержен race conditions на ARM просто потому что ARM подходит к выполнению инструкций «более творчески» (привет, новые макбуки:).


                    Добавим сюда еще:


                    • For example, in Java, this guarantee is directly specified
                    • By contrast, a draft C++ specification does not directly require an SC for DRF property, but merely observes that there exists a theorem providing it...Note that the C++ draft specification admits the possibility of programs that are valid but use synchronization operations with a memory_order other than memory_order_seq_cst, in which case the result may be a program which is correct but for which no guarantee of sequentially consistency is provided. In other words, in C++, some correct programs are not sequentially consistent. This approach is thought to give C++ programmers the freedom to choose faster program execution at the cost of giving up ease of reasoning about their program...

                    В общем, в C# я стараюсь всего это избегать и где только можно использовать статические инициализаторы, чтобы CLR сам за меня отдувался. Не думаю, что стоит сильно переживать, что вы «недостаточно умны». Вот Эрик Липперт тоже «не достаточно умен» :))


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

                      +2
                      В общем, в C# я стараюсь всего это избегать и где только можно использовать статические инициализаторы, чтобы CLR сам за меня отдувался. Не думаю, что стоит сильно переживать, что вы «недостаточно умны». Вот Эрик Липперт тоже «не достаточно умен» :))

                      Я бы написал так: если вам в проекте вдруг понадобилось работать с многопоточностью на низком уровне, значит, вы что-то делаете не так. Например, писать собственные lock-free коллекции — хорошая разминка для мозгов, но вот видеть это в проде я бы не хотел.

                        +1

                        Ага, если баг воспроизвелся, значит он есть. А если не воспроизвелся… ну ничего это не значит в общем-то, удачи с отладкой.

                +1

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

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое