Ошибки параллельного программирования

Давно хотел начать писать что-то, претендующее на смысловую нагрузку, а так как я люблю ||, буду писать про него. Надеюсь этот текст не особенно сложный и не вызовет особых проблем, если вы хоть раз пытались писать многопоточный код на любом языке (но примеры будут на C++).

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

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

Дисклеймер 1: описание дается на пальцах и не претендует на полноту

Дисклеймер 2: до определенного момента текста предполагается исполнение кода в модели SC

1. Data Race & Race Condition

Если вы не знаете ничего, кроме того как создать поток и запустить в нем код, это первое на что вы обязательно напарываетесь. Начнем с того, что Data Race и Race Condition — вещи разные и про разное, так что видимо сначала надо понять почему.

Скажем, что в нашей программе есть Data Race, если в ней есть ячейка памяти, к которой несколько потоков обращаются не синхронизировано* (что именно это значит пока не важно) и при этом хотя бы один из них пишет.

*Для простоты можно считать, что доступ не синхронизирован, если переменная не атомик и не защищена мьютексом.

Окей, тут кажется нет ничего неожиданного — если вы в одном потоке в цикле пишете в переменную, а в другом потоке в цикле читаете, то вы проиграли — в зависимости от криповости языка можно ожидать разного: от прочтения значений, которые никто не писал и до взрыва компьютера.

Решение тоже не очень сложное — синхронизируйте доступ к переменным и все будет окей.

Другая проблема называется Race Condition. Скажем, что в нашей программе есть Race Condition, если какой-либо из вариантов планирования потоков приводит к нарушению инвариантов нашего кода.

Чуть более абстрактно, но все еще примерно понятно — прокрутим разные варианты чередования потоков на ядре процессора и если какой-то из этих вариантов приводит к нарушению инвариантов, которые мы заложили в код, то мы проиграли снова. При этом Race Condition это не Data Race. Например, возникающий в коде дедлок (про который будет дальше) — это явно Race Condition, так как инвариант того, что потоки не блокируются навечно нарушен, однако никакой гонки данных у нас может и не быть.

На самом деле решать обе эти проблемы можно одинаково — с помощью мьютекса.

2. Deadlock

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

Итак, скажем, что в нашей программе есть Deadlock, если какой-то поток (или несколько) блокируется на ожидании ресурса (например, мьютекса) и при этом уже никогда из этого ожидания не выйдет.

Тут начинаются подслучаи, и примеры лучше посмотреть внутри них :

2.1 Перекрестный Deadlock

Это ситуация, когда происходит более менее следующее:

std::thread t1([&] {
    // ...
    mutex1.lock();
    // ...
    mutex2.lock();
    // ...
});

std::thread t2([&] {
    // ...
    mutex2.lock();
    // ...
    mutex1.lock();
    // ...
});

Тут мы запустили 2 потока, и первый из них лочит мутексы в одном порядке, а второй в другом. Что при этом происходит — представим себе исполнение, когда они выполняют строки по очереди — первый поток захватывает mutex1, затем второй поток захватывает mutex2. И теперь первый поток будет ждать mutex2, который сейчас у второго потока, а второй будет ждать mutex1, который сейчас у первого потока, и никто из них никогда не дождется своей очереди на мьютекс. Мы проиграли.

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

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

2.2 Deadlock на нерекурсивном примитиве синхронизации

Ах да, примитивы синхронизации еще делятся на рекурсивные и нерекурсивные. Рекурсивные это такие, которые поток умеет блокировать вложено, то есть:

std::thread t([&] {
    // ...
    mutex1.lock();
    // ...
    mutex1.lock();
    // ...
});

Если mutex1 — рекурсивный п.с, то этот код будет работать (если конечно не забыть дважды его отпустить), а вот если нет, то при попытке второго захвата случится дедлок. Впрочем, стоит отметить, что если вы пишете на джаве, то про это можно не думать — JVM сама решает какой тип п.с вам нужен.

2.3* Deadlock при вызове fork()

*Тут хотелось бы, чтобы вы понимали что делает системный вызов fork()

Предположим нам по каким-то причинам захотелось сделать наш код многопроцессным. Для этого ОС (в этой части допустим, что мы пишем под линукс) предоставляет нам системный вызов fork(), который создает новый процесс процесс путем копирования старого.

Но так как наш код работает в несколько потоков, в нем конечно есть мьютекс. Допустим он захвачен потоком 1

Теперь в потоке 2 мы делаем fork() процесса. После форка в новом процессе останется только один поток (поток 2), который делал форк. Однако форк работает довольно тупо и просто копирует адресное пространство. В том числе он скопирует место, где хранится мьютекс.

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

Чтобы такого не было, перед форком нужно захватить все примитивы. Если вы пишете на pthread'ах, то (во-первых, соболезную, а во вторых) в нем есть функция pthread_atfork, в которую передаются указатели на обработчики форка.

Также универсальный способ защиты от ошибок 1 и 2 — это средства нахождения ошибок. Например, Thread Sanitizer C/C++ или valgrind --tool=helgrind

3. Spurious Wakeups

Теперь мы умеем ловчить и анлочить мьютексы без дедлоков и нам хочется реализовывать более сложную многопоточную логику работы. На этом этапе начинают возникать так называемые conditional variables. С ними все просто -- мы хотим уметь засыпать на методе wait() и просыпаться на notify_one() и notify_all().

Хорошо, напишем какой-то такой код:

std::thread t1([&] {
    mutex.lock();
    cv.wait(mutex);
    // дождались события, мьютекс тут захвачен, можно продолжать
});

std::thread t2([&] {
    // сформировали какие-то данные
    mutex.lock();
    cv.notify_one(mutex);
    // ...
});

И вот проблема -- такой код не будет работать. Дело в том, что t2 мог сделать notify_one перед тем, как t1 дошел до wait'а, и его уже никто не разбудит. Хорошо, обработаем этот случай:

std::thread t1([&] {
    mutex.lock();
    if (!something_happened) {
        cv.wait(mutex);
    }
    something_happened = false;
    // дождались события, мьютекс тут захвачен, можно продолжать
});

std::thread t2([&] {
    // сформировали какие-то данные
    mutex.lock();
    cv.notify_one(mutex);
    something_happened = true;
    // ...
});

Ну теперь-то победа? Вообще говоря нет. Дело в том, что conditional variables обладают следующим свойством -- поток может выпрыгнуть из wait(), хотя никто его не будил (* На самом деле в этом примере все было бы плохо и без этой особенности, однако мне кажется она хорошо подходит как пример). Это называется spurious wakeups. У меня не получилось придумать нормальное теоретическое объяснение почему spurious wakeups есть и почему с ними ничего не делают. Мне кажется лучший способ это понять -- написать свои conditional variables и посмотреть в каких сценариях и почему spurious wakeups случаются

Однако правильный код написать-таки надо:

std::thread t1([&] {
    mutex.lock();
    while (!something_happened) { // if -> while
        cv.wait(mutex);
    }
    something_happened = false;
    // дождались события, мьютекс тут захвачен, можно продолжать
});

std::thread t2([&] {
    // сформировали какие-то данные
    mutex.lock();
    cv.notify_one(mutex);
    something_happened = true;
   // ...
});

В C++ для такого случая есть более удобный синтаксис:

std::thread t1([&] {
    std::unique_lock guard(mutex); // ~ mutex.lock();
    cv.wait(guard, [] {
        return something_happened;
    });
    something_happened = false;
    // дождались события, мьютекс тут захвачен, можно продолжать
});

4*. Sharing & False Sharing

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

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

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

То есть, предположим мы пишем атомарный счетчик. Выглядел бы он как-то так:

class Counter {
public:

    void Increment() {
        count_.fetch_add(1);
    }
    
    uint64_t Get() {
        return count_.load();
    }

private:

 std::atomic<uint64_t> count_{0};

};

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

Хорошо, давайте сделаем умнее — заведем несколько счетчиков и каждый будем считать отдельно. А в Get() будем агрегировать результаты.

class Counter {
public:

    void Increment() {
        counts_[hash_(std::this_thread::get_id()) % 8].fetch_add(1);
    }
    
    uint64_t Get() {
        uint64_t result = 0;
        for (const auto& count : counts_) {
            result += count.load();
        }
        return result;
    }

private:

 std::array<std::atomic<uint64_t>, 8> counts_;
 std::hash<std::thread::id> hash_;

};

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

И это на самом деле имеет смысл, ведь часто реальные программы которые мы пишем обладают свойством пространственной локальности, то есть если мы работаем с какой-то переменной, возможно нам понадобятся и переменные рядом (так как они вместе лежат в какой-то структуре данных, например)

Однако в нашем случае это играет против нас - получается, что несмотря на то что каждый поток работает со своей переменной, по сути они лежат в одной и той же кеш-линии и ядра все равно каждый раз их синхронизируют. Это называется false sharing

Чтобы такого избегать нужно как минимум выравнивать все атомики по кеш-линии. Например, в C++ нужно написать

alignas(64) std::atomic<uint64_t> counter_;

5*. Слабые барьеры атомиков

В некоторых языках для работы с атомиками можно дополнительно указывать так называемые барьеры памяти

counter_.store(228, std::memory_order_relaxed);

Тут на самом деле не будет подробно про это, так как это довольно сложная тема, но раз уж я позволяю себе раздавать советы, то скажу и про это: НИКОГДА не пишите так, если только вы абсолютно и на 100% не понимаете что именно это значит и к чему приведет (и пока не проверите все synchronises with, synchronization order, program order, happens before отношения)