Очень часто при обсуждении многопоточности на платформе .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 миллионов операций по обмену сообщениями между двумя ядрами.
У этой структуры данных есть два недостатка:
- необходимость очистки
- необходимость выделения памяти для элементов коллекции
Другая структура данных лишена этих недостатков. Эта структура данных называется «кольцевой буфер». В кольцевом буфере вам не нужно каждый раз выделять память. Есть один большой участок памяти, который перезаписывается при необходимости.
В результате все работает гораздо быстрее: 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));
}- Сначала происходит вызов
Thread.SpinWait()(не происходит переключение контекста потока). Этот шаг будет пропущен для одноядерных процессоров:
public bool NextSpinWillYield { get => m_count > YIELD_THRESHOLD || PlatformHelper.IsSingleProcessor; } - Затем будет вызван
Thread.Sleep(0)(может быть прерван потоками такого же приоритета) - Затем, —
Thread.Yield()(может быть прерван потоками любого приоритета) - Если операция все еще не завершена, то будет вызван
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. Алгоритм получения эксклюзивного доступа следующий:
- Выполняется Interlocked-операция: каждый объект в .NET имеет хедер, который говорит, на каком потоке он находится и для чего он заблокирован.
- Идёт SpinWait, если операция завершится неудачей.
- CLR создает kernel event, если выполнение
SpinWaitне дало ожидаемого результата. После нескольких миллисекунд ожидания создается еще один kernel event, но только в другом потоке.
Все эти вещи делает за нас .NET. Думаю, это хороший пример того, что должен делать программный фреймворк.
Структуры данных из пространства имен System.Collections.Concurrent
Напоследок хочу немного рассказать о структурах данных, которые используются для обмена информацией между потоками.
Concurrent Stack
В ConcurrentStack вводится понятие производителей и потребителей, которые конкурируют за то, чтобы получить верхушку стека.
Concurrent Queue
В другой структуре данных ConcurrentQueue потребители конкурируют за разные узлы. Это увеличивает пропускную способность в два раза: производители и потребители конкурируют между собой только в своей группе.
Concurrent Bag
Если вы ищете структуру данных, где нет конкуренции между производителями и потребителями, то такая структура данных называется ConcurrentBag. Она оптимизирована для низкой конкуренции. В зависимости от геометрии вашей коллекции, в каждом отдельном случае у вас будут разные виды гарантий и разная производительность. Стоит упомянуть, что такая структура данных не дает никаких гарантий в плане порядка вычислений, но она дает вам список конкурирующих потоков, где каждый поток будет работать над своей задачей.
Заключение
- На аппаратном уровне есть только операции Interlocked и барьеры памяти.
- На уровне ядра Windows вводится такая абстракция, как поток. Основное предназначение потока — это ожидание и хранение набора зависимостей.
- Также мы рассмотрели некоторые коллекции из стандартной библиотеки.
Если доклад показался вам достаточно хардкорным, загляните на сайт конференции Dotnext 2021 Piter, которая пройдёт с 20 по 23 апреля. Основными темами станут настоящее и будущее платформы .NET, оптимизация производительности, внутреннее устройство платформ, архитектура и паттерны проектирования, нетривиальные задачи и best practices. На сайте начинают появляться первые доклады, со временем список будет пополняться.
