Memory model

Очень часто при обсуждении многопоточности на платформе .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.

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

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

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

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

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

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

SpinWait

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

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

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

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

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

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

1. Выполняется Interlocked-операция: каждый объект в .NET имеет хедер, который говорит, на каком потоке он находится и для чего он заблокирован.

   
   

2. Идёт SpinWait, если операция завершится неудачей.

   
   

3. CRL создает 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. На сайте начинают появляться первые доклады, со временем список будет пополняться.

Это расшифровка-перевод доклада Саши Гольдштейна, признанного лучшим на конференции DotNext 2016 Piter. С годами этот доклад стал лишь актуальнее прежнего: появление Mac на ARM-процессорах еще один пример, почему разработчикам сегодня нужно думать не только о x86-аерхитектуре.

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

То, что подходит процессорам Intel на архитектурах x86 и x86-64, может не подойти другой архитектуре. Как только вы перенесете свой код на другой процессор, например, на ARM для iPhone и Android, есть вероятность, что он перестанет работать как надо. Проблемы могут быть как очевидными (воспроизводиться с первого-второго раза), так и не очень (возникать только раз в миллион итераций). Вполне вероятно, что такие баги могут добраться до продакшна. Сегодня .NET и, конечно, C++ можно использовать не только на Windows и Intel, но и на других платформах, так что доклад будет полезен многим разработчикам.

Дисклеймер: данная статья предназначена для продвинутых читателей. Смотрите на свой страх и риск. За частое упоминание барьеров памяти и изменения порядка исполнения инструкций она получила возрастное ограничение 18+.

Вступление (My assumptions)

• Вы C++ или C#-разработчик.
• Вы пишете многопоточный код (а кто не пишет?).
• Вы следите за корректностью кода и хотите, чтобы он правильно работал на различных платформах.
• Возможно, вы привыкли к заботливой x86-архитектуре, но теперь хотите убедиться, что ваш код остался корректным в суровых и опасных условиях ARM-архитектуры.

Agenda

• Атомарность, эксклюзивность и изменение порядка
• Примеры переупорядочивания памяти
• Что такое модель памяти
• Volatile и атомарные переменные
• Примеры сломанного кода и решения, как его починить

Атомарность

Итак, начнем с трех фундаментальных концепций атомарность, эксклюзивность и изменение порядка. Когда мы говорим, что операция атомарна, мы имеем в виду, что она не может быть прервана. Это означает, что во время выполнения операции не может произойти переключение потока, операция не может частично завершиться. На оборудовании с 64-битными процессорами Intel можно быть уверенными, что операции чтения и записи значений меньше 64 бит являются атомарными. Эти операции не могут быть прерваны и не могут частично завершиться. Проблема в том, что большинство на первый взгляд простых операций, которые мы пишем на языках высокого уровня, на самом деле не являются атомарными. Очевидный пример, с которым многие из вас наверняка знакомы увеличение значения на единицу. На C++, компилятор сгенерирует код наподобие такого:

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

Эксклюзивный доступ к памяти

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

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

Раньше префикс полностью блокировал шину памяти. То есть пока выполняется инструкция, помеченная данным префиксом, другие ядра (CPU) в принципе не могли получить доступ к памяти. Довольно высокая плата за эксклюзивность. На современных системах (начиная с Pentium 4, возможно, даже более старых) префикс больше не блокирует шину памяти полностью. Теперь блокируется только часть памяти достаточно убедиться, что линия кэша, где находится наше значение, не находится в кэше других ядер. Иначе говоря, если я обновляю значение на своем ядре, другие ядра временно не имеют доступ к этому значению. Это работает, но опять-таки, это довольно дорого, и, чем больше ядер, тем дороже обойдется операция. Резюмируя, эксклюзивность это возможность ядра получить монопольный доступ к памяти. Это вторая концепция, о которой я хотел поговорить.

Изменение порядка

Третья концепция изменение порядка. И под этим определением подразумевается, что некоторые части системы могут взять операции, выполняемые вашим приложением, и переставить их. То есть они могут взять операцию записи и выполнить ее после чтения, хотя изначальный порядок был другим, могут взять две операции записи разных переменных и также изменить порядок выполнения. Например: одно ядро считает, что значение переменной равно 7, а другое ядро еще не заметило изменение значения и считает, что оно все еще равно 6. Такое различие информации, хранящейся в ядрах, может привести к проблемам. Далее в статье мы поговорим о нескольких примерах, которые, я надеюсь, лучше прояснят ситуацию.

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

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

Примеры

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

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

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

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

И мы не против подобных оптимизациях и не очень хотим о них знать, пока они не приводят к ошибкам. Это весьма лицемерный подход: нельзя просто предположить, что компьютер понимает, сломают ли оптимизации код или нет, потому что компьютер не знает о наших намерениях. Например, вы реализуете очередь на C, C++ или C#. У вас есть функция enqueue(x new_element), которая кладет новое значение в очередь и обновляет переменную locked присваивает ей значение 0.

Компьютер может переставить эти операции местами: сначала обновить locked, потом положить новый элемент в очередь. Вы можете сказать: Это неправильная оптимизация, это сломает мой код, и вообще, у компьютера не должно быть возможности так делать! Но эта оптимизация такая же, как и в предыдущих примерах. Процессор или компилятор могут изменить порядок выполнения связанных чтений и записей, потому что решат, что это ускорит некоторые части вашего кода. Как показано в предыдущем примере, это может полностью нарушить ваши планы, но это только из-за того, что вы не сообщили о них компьютеру.

Зачем нужны оптимизации?

Зачем компьютеры (компиляторы или процессоры) выполняют подобные оптимизации? Процессоры переставляют местами некоторые операции из-за конвейерной обработки.

Эта простая иллюстрация показывает, что инструкция внутри процессора проходит через несколько стадий. Так происходит у процессоров с MIPS-архитектурой сорокалетней давности. На современных процессорах Intel может быть 20 подобных фаз. Одна инструкция перемещается между фазами, пока другая инструкция находится в первой фазе, еще одна инструкция во второй и так далее. То есть множество инструкций находятся в разных фазах в одно и то же время. И результатом может быть изменение порядка: первая инструкция, записывающая значение в память, выполнится после третьей инструкции, считывающей значение из памяти, хотя изначальный порядок был другим. Наличие нескольких стадий в выполнении инструкций может привести к изменению порядка этих инструкций, если только вы не скажете компьютеру, что не допускаете подобные перестановки и хотите, чтобы инструкции выполнялись в изначальном порядке.

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

В современных процессорах Intel, например, у каждого ядра есть свой буфер небольшая очередь, которая хранит последние операции записи. Этот буфер сбрасывается в память в фоновом режиме. То есть, если процессору пришла инструкция Запиши Х в память и он ответил Сделано, на самом деле это может быть не так, и значение Х может находиться в буфере, который не видят другие ядра процессора. Буфер сбрасывается в память асинхронно. Даже после выгрузки буфера значение должно пройти несколько этапов кэширования, что также происходит довольно медленно.

Как понять, какие перестановки инструкций допустимы и что именно процессор будет считать верной оптимизацией? Есть одно правило, которое гласит, что необходимо соблюдать зависимости данных. Например, если в одном потоке сначала переменной Х присваивается значение 1, затем происходит считывание Х, последняя операция должна вернуть 1. Или если в потоке сначала какое-то значение присваивается переменной Х, затем какое-то значение присваивается переменной Y, и после этого происходит вычисление суммы Х и Y. Нет гарантий, какое присвоение произойдет раньше, но обе операции должны произойти до того, как X и Y будут считаны из памяти снова.

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

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

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

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

Счетчик g_shared _counter лежит в общей памяти. Есть два потока, каждый из которых 20 миллионов раз ограничивает доступ к счетчику (g_protector.lock()), увеличивает его на единицу и освобождает доступ (g_protector.unlock()). К реализации lock() мы вернемся немного позже. Предположим, что кто-то, кому вы доверяете, предоставил вам реализацию.

Я запустил этот код на iPhone-симуляторе и в конце вывел значение счетчика на экран. Результат выполнения оказался верным на экране через некоторое время отобразилось сорок миллионов. Ура! Но я запускал iOS-симулятор на своем маке, внутри которого процессор Intel. А если вместо симулятора протестировать код на реальном iPhone? Результат 39999999. Близко, но не сорок миллионов. Итак, блокировка счетчика сломалась, причем только на ARM и только один раз из сорока миллионов.

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

Операции в коде выглядят атомарными, и чтение из памяти, и запись в память происходит только один раз. Казалось бы, здесь нет многократных изменений, которые могут помешать друг другу, поэтому код должен работать. Однако, на ARM, например, он работать не будет, так как конструктор во втором потоке также производит запись в память (инициализирует объект). Эта операция записи может произойти после записи значения в глобальную переменную. Тогда первый поток увидит частично инициализированную переменную, то есть переменную, создание которой еще не закончено. При этом код выглядит довольно чисто. На Intel данный код будет работать, потому что там, в отличие от ARM, не разрешены перестановки операций записи.

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

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

Финальный пример, который на этот раз я запущу на Windows алгоритм синхронизации Петерсона. Возможно, вы слышали о нем на курсе по операционным системам. Ниже упрощенная версия этого алгоритма.

Если коротко, два потока хотят получить доступ к критической секции. Также есть два флага, по одному на каждый поток. Если flag1 равен единице, значит, поток 1 хочет получить доступ к критической секции. То же самое для второго потока. Каждый поток кладет единицу в свой флаг, затем проверяет чужой флаг. Если другой флаг также равен единице, значит, оба потока хотят получить доступ к критической секции одновременно. Это неразрешимый спор, попробуем заново. Мы присвоим флагу значение 0 и повторим все сначала (часть с goto). Эти действия будут повторяться до тех пор, пока один из флагов во время проверки не будет равен нулю. Такая ситуация означает, что один из потоков не хочет получить доступ к критической секции. Кажется, что алгоритм должен работать, пусть и не очень эффективно, ведь раз за разом повторяется одно и то же. Это как вежливый обмен мнениями: Ты хочешь получить доступ к критической секции, я тоже хочу получить доступ, давай договоримся и найдем компромисс. Но, оказывается, на x86-архитектуре алгоритм не будет работать, так как операции чтения и записи в каждом потоке могут быть переставлены. Может получиться так, что один поток проверит флаг другого потока до того, как установит свой собственный флаг. Тогда возможна ситуация, в которой каждый поток будет думать, что другой поток не хочет получить доступ к критической секции, хотя на самом деле это не так.

Проблема в том, что подобную ситуацию не так-то просто зафиксировать, ведь такое происходит довольно редко (14 раз за 26551 повторение). Вы можете подумать, что ваш алгоритм синхронизации работает правильно, ведь вы проверили его сотни раз. Возможно, у вас есть автотесты, которые проверили его тысячи раз и не обнаружили этот редкий баг. Его сложно обнаружить, а если получилось, удачи воспроизвести его еще раз будет непросто. Что будет, если подобный алгоритм с таким небольшим, казалось бы, незначительным шансом на поломку будет внедрен в большую программу? Будет очень неприятно :(

Что такое модель памяти?

Несколько слов о модели памяти перед тем, как мы перейдем к части о защите от подобных феноменов. Термин последовательная согласованность (sequential consistency) появился давно, и мы могли бы посвятить ему весь доклад целиком, но это будет довольно скучно. Главная идея результат выполнения многопоточного кода должен быть таким же, как если бы код выполнялся в порядке, определенным программой. То есть система не должна разрешать как-либо изменять порядок выполнения операций чтения и записи. Но, как мы говорили ранее, перестановки операций не происходят из-за того, что система желает нам зла, это просто оптимизации. И последовательная согласованность препятствует этому.

Следующее определение последовательная согласованность для программ без состояний гонки (sequential consistency for data-race-free programs или SC-DRF). На сегодняшний день эту модель использует большинство языков. Детали, опять-таки, довольно скучны, но в целом, состояние гонки это именно то, что вы думаете. Состояние гонки происходит, когда у вас есть несколько потоков, каждый из которых обращается к определенной переменной, то есть к определенной области в памяти, и хотя бы один из потоков производит запись в память. Если ваш код не предотвращает это, у вас произойдет состояние гонки. SC-DRF означает, что если в коде нет состояний гонки, система обеспечивает последовательную согласованность. Все будет выглядеть так же, как при выполнении в порядке, предусмотренном программой. И это, в большей степени, то, что вы можете получить от оборудования сегодня, то, что, например, ARM может предложить. Если вы предпримете необходимые шаги, чтобы гарантировать отсутствие гонок, система предоставит вам последовательную согласованность между несколькими ядрами.

Все это довольно скучно и теоретично, но это определяет модель памяти. Например, для C++11 модель памяти это SC-DRF. То есть C++, язык и библиотеки, предоставляют инструменты для избавления от состояний гонки. И если состояний гонки действительно нет в вашем коде, компилятор C++ гарантирует последовательную согласованность. И мы получаем нечто похожее от модели CLR, из официальной спецификации ECMA (the European Association of computer manufacturers). Если вы позаботитесь о состояниях гонки, то получите последовательную согласованность и отсутствие багов. Тем не менее, текущая реализация .NET, CLR, предлагает немного больше она избавляется от некоторых перестановок, не предусмотренных ECMA-спецификацией. По сути, реализация от Microsoft более дружелюбна к разработчикам, чем ECMA-спецификация. Но, даже со всем вышесказанным, пример с алгоритмом Петерсона все еще не будет работать.

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

Good fences make good neighbours (крепкие заборы дружные соседи)

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

Поэтому если вернуться к примеру с алгоритмом Петерсона и добавить volatile к каждому флагу, баг с перестановками все еще будет проявлять себя. Что ж, если говорить о предотвращении состояний гонки, volatile в C++ довольно бесполезен. Вы можете проверить это сами, посмотрев на сгенерированный код. В C# volatile предотвращает перестановки не только компилятора, но и процессора, создавая однонаправленные барьеры (далее я объясню, что это такое). Однако, volatile не гарантирует отсутствие состояния гонки и перестановок.

Примеры сломанного кода и решения, как его починить

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

Добавление барьера во второй поток предотвратит перестановку операции записи и создания объекта. Это обеспечит безопасность, которой мы добивались. MemoryBarrier() это реальная функция, которую вы можете использовать в C++ на Windows и Visual Studio. Аналог этой функции в .NET называется Thread.MemoryBarrier() это статический метод класса Thread, который предотвращает перемещение операций через барьер.

Если посмотреть на реализацию, там используется специальная инструкция, благодаря которой CPU понимает, что нужно запретить перестановки через эту точку. Конкретно на Intel единственное, о чем стоит беспокоиться такому барьеру, это операции чтения после записи. Поэтому барьеры на Intel обходятся не так дорого, как барьеры на ARM. Если на ARM вы разбросаете барьеры случайным образом по всему коду, последствия могут оказаться плачевными. В нашем случае добавление барьера в алгоритм Петерсона поможет избежать ранее описанного бага с перестановками.

Типы барьеров

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

Функции Monitor.Enter и Monitor.Exit гарантируют, что в одном из направлений операция точно не будет переставлена. Операции между двумя функциями не разрешено пересекать барьеры. Иными словами, операции не могут сбежать из под лока. В .NET чтение и запись переменной, помеченной ключевым словом volatile, создает однонаправленные барьеры, такие же, как на примере с Monitor. В C++11 появился довольно полезный класс, называемый std::atomic. Такая атомарная переменная дает вам полный контроль над тем, какой барьер вы в итоге получите.

Вернемся к примеру с счетчиком, лежащим в общей памяти, и посмотрим на реализацию spinlock. Она базируется на флаге, который принимает значения 0 или 1.

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

В первой версии, которая используется сейчас, обе инструкции используют memory_order_relaxed. Иначе говоря, какие-либо барьеры отсутствуют.

А это значит, что если в функции lock нет барьеров, и в функции unlock нет барьеров, операции записи, производимые внутри lock, могут быть выполнены до или после метода. Значит, блокировка не очень хорошая, она не выполняет свою основную функцию.

Сейчас возьмем вторую версию, в которой методы lock и unlock используют однонаправленный барьер.

Теперь при запуске кода на iPhone скорость выполнения уменьшилась это цена за добавление барьеров памяти, но результат оказывается верным.

Мы можем использовать std::atomic, барьеры памяти для избавления от состояний гонки. Иногда при смешивании однонаправленных барьеров результат выполнения может отличаться от ожидаемого. Например, если в алгоритме Петерсона пометить флаги ключевым словом volatile в C#, или сделать их атомарными в C++, мы получим однонаправленные барьеры для операций чтения и записи.

К сожалению, наличие этих барьеров не мешает двум инструкциям поменяться местами. То есть ни volatile, ни std::atomic не решат проблему с перестановками, здесь поможет только полный барьер. Довольно сложно продумать такие моменты даже с двумя переменными, а если их больше, все становится еще более запутанно.

В финале хотелось бы рассказать о потокобезопасной реализации синглтона. Задача реализовать синглтон в C++ и сделать его потокобезопасным. Начнем с очень простой и очевидно нерабочей и определенно не потокобезопасной реализации, в которой несколько потоков могут инициализировать синглтон одновременно.

Прекрасно. Добавим в реализацию блокировку lock.

Это все еще не будет работать, так как два потока могут одновременно попасть внутрь блокировки и инициализировать синглтон.

Реализуем блокировку с двойной проверкой, которая выглядит следующим образом.

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

Хорошо, обработаем исключения.

Но этот код также не будет работать по причине, которую мы рассматривали ранее. Операции записи, производимые конструктором, могут произойти после операции присвоения значения переменной instance. Если это произойдет, другой поток может подумать, что синглтон уже инициализирован, хотя это не так. Вы можете сказать: Хорошо, давайте добавим volatile к переменной instance.

Однако, опять-таки, volatile в C++ не оказывает никакого влияния на оптимизации процессора. Единственное, что действительно поможет, это std::atomic.

Есть еще более простой способ создания потокобезопасного синглтона.

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

Аналогичный раздел о синглтонах на C# есть в книге C# In Depth

Вывод

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

Это был доклад с DotNext. А в апреле состоится новый DotNext, и какие доклады будут там, зависит в том числе от вас: приём заявок ещё открыт.