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

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

Попытаться полностью объяснить модель в этой книге довольно безнадежно. Она описывается в терминах графов безумных зависимостей, для объяснения которых понадобится отдельная книга. Если хотите изучить все эти штучки-дрючки, смотрите в спецификацию Си (Секция 7.17). Итак, мы попытаемся объяснить основы и некоторые проблемы, с которыми столкнулись разработчики Rust.

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

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

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

x = 1;
y = 3;
x = 2;

Компилятор может решить, что лучше бы ваша программа делала так

x = 2;
y = 3;

Порядок событий поменялся, и одно из них просто удалилось. С точки зрения одного потока, это не играет роли: после выполнения все окажется в том же состоянии. Но если наша программа многопоточна, мы рассчитываем, что x присвоится 1 до присвоения y. Мы бы хотели, чтобы компилятор мог выполнять оптимизации для ускорения производительности. С другой стороны мы бы также хотели, чтобы наша программа делала то, что мы написали.

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

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

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

Например, заставим компилятор имитировать следующую логику:

initial state: x = 0, y = 1

THREAD 1        THREAD2
y = 3;          if x == 1 {
x = 1;              y *= 2;
                }

В идеале, у этой программы 2 вероятных конечных состояния:

  • y = 3: (поток 2 выполнил проверки перед тем, как завершился поток 1)
  • y = 6: (поток 2 выполнил проверки после того, как завершился поток 1)

Однако потенциально у этой программы есть третье состояние, возможное благодаря железу:

  • y = 2: (поток 2 видит x = 1, но не y = 3, и затем переписывает y = 3)

Стоит отметить, что разные типы CPU предоставляют разные гарантии. Обычно разделяют железо на две категории: со строгим и нестрогим порядком выполнения. Надо заметить, что x86/64 гарантируют строгий порядок, а ARM, наоборот, нестрогий. Из этого можно сделать два вывода для параллельного программирования:

  • Запрос гарантий строгого порядка у железа со строгим порядком может стоить очень дешево, или даже не стоить ничего, потому что они и так предоставляют такие гарантии безусловно. Гарантии нестрого порядка могут дать выигрыш в производительности только на железе с нестрогим порядком выполнения.

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

Обращения к данным

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

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

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

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

  • Последовательный порядок (SeqCst)
  • Освобождение (Release)
  • Получение (Acquire)
  • Расслабленный порядок (Relaxed)

(Заметьте: Мы явно не выделяем потребляющий порядок C11)

TODO: плюсы и минусы? TODO: "не забыть синхронизацию"

Последовательный порядок

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

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

На практике, последовательный порядок редко необходим для правильности программ. Однако он будет точно правильным выбором, если вы не осведомлены о других порядках обращения к памяти. Чуть более медленная программа - это гораздо лучше, чем неправильная программа! Также в будущем легко будет перейти к более слабым ограничениям атомарных операций. Просто измените SeqCst на Relaxed и все! Конечно, это еще большой вопрос, будет ли это изменение правильно работать.

Получение-Освобождение

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

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

Когда поток A освобождает место в памяти, и после этого поток B последовательно получает то же место в памяти, устанавливается причинно-следственная связь. Каждая запись, происходящая до освобождения блокировки A, будет замечена B после освобождения блокировки. Однако никакая другая причинно-следственная связь не устанавливается с другими потоками. Аналогично, она не устанавливается между A и B, если они обращаются к разным местам в памяти.

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

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;

fn main() {
    let lock = Arc::new(AtomicBool::new(false)); // значение отвечает на вопрос "Я занят?"

    // ... распределяем блокировку по потокам каким-то образом ...

    // Пытаемся получить блокировку, устанавливая ее в true
    while lock.compare_and_swap(false, true, Ordering::Acquire) { }
    // выход из цикла говорит, что мы успешно получили блокировку!

    // ... ужасные обращения к данным ...

    // Ок, закончили, освобождаем блокировку
    lock.store(false, Ordering::Release);
}

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

Расслабленный порядок

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

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