Другой взгляд на многопоточность19.11.2021 22:01

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

Откуда ноги растут

В начале 2000-х годов наблюдалось замедление скорости роста производительности процессоров. К 2005 году увеличение тактовой частоты процессора практически остановилось. Сейчас мы можем вспомнить 2010 год и выход Intel Core i5-680 с тактовой частотой 3,60 ГГц. Прошло десять лет и сейчас можно приобрести Intel Core i9–10850K с частотой от 3,60 до 5,20 ГГц. Разница, как можно заметить, не велика. Этот пример очень синтетический и примитивный, но он наглядно показывает скорость и направление развития современных процессоров. Конечно, производительность процессора зависит не только от тактовой частоты, а еще и от других параметров — размера и количества кэшей, частоты шины, типа сокета и так далее. И зачастую, особенно на боевых машинах, оказывается, что выгоднее взять процессор с более низкой тактовой частотой.

78860ebb26e83014d70fab0895efbf45.jpeg

Что делать?

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

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

Представим, что мы обладаем общей памятью и ядрами в количестве N штук.

image-loader.svg

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

Поток

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

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

int a = 0 // операция 1, выполнится самая первая
int b = 0 // операция 2, выполнится после операции 1
a = a + b // операция 3, выполнится после операций 1 и 2
b = a + a // операция 4, выполнится после всех операций

Давайте попробуем решить простую задачу. Какие варианты пар (a, b) возможны после завершения исполнения обоих потоков, положитесь на свою интуицию, стоит рассмотреть даже самые, казалось бы, невозможные варианты:

image-loader.svgОтвет

  1. Пусть поток 1 выполнился полностью, а поток 2 еще не стартовал. Тогда в результате будет пара (0, 1)

  2. Аналогично, поток 2 выполнился полностью, а поток 1 еще не стартовал. Тогда в результате будет пара (1, 0).

  3. Во всех остальных случаях (0, 0)

  4. Случая (1, 1) быть не может, так как хотя бы один поток перед своим завершением обнулит какую-то переменную.

В итоге получается [ (0, 1), (1, 0), (0, 0) ]

Как вы могли догадаться, понимание результата работы многопоточного кода сводится к рассмотрению всех вариантов его исполнения. В данном случае формально такая модель исполнения называется моделью последовательной консистентности (sequential consistency, SC).

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

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

image-loader.svgОтвет

Всего существует 6 вариантов исполнения. 1 — 4 варианты дадут результат (1, 1), 5 вариант даст результат (0, 1), 6 вариант даст результат (1, 0).

image-loader.svg

Многопоточность была бы простой если бы все закончилось здесь.

Конец?

К сожалению, или к счастью, это еще не конец. На процессорах самых популярных архитектур — x86, Arm, Power PC и Alpha, исполнение предложенного выше примера может быть другим — возможен результат (0, 0).

Пруфы

#include 

#include 

int x, y, a, b;

void* thread1(void* unused) {
    x = 1;
    a = y;
    return NULL;
}

void* thread2(void* unused) {
    y = 1;
    b = x;
    return NULL;
}

int main() {
    int i = 0;
    while (1) {
        x = 0;
        y = 0;
        a = 0;
        b = 0;

        pthread_t tid1;
        pthread_attr_t attr1;

        pthread_t tid2;
        pthread_attr_t attr2;

        pthread_attr_init(&attr1);
        pthread_attr_init(&attr2);

        pthread_create(&tid1, &attr1, thread1, NULL);
        pthread_create(&tid2, &attr2, thread2, NULL);

        pthread_join(tid1, NULL);
        pthread_join(tid2, NULL);

        i++;
        if(a == 0 && b == 0) {
            break;
        }
    }

    printf("Iterations: %d\n", i);

    return 0;
}

Код на языке C рано или поздно завершается, хотя в модели SC не должен.

Это не вписывается в модель SC (sequential consistency), поскольку не существует такого исполнения, которое бы привело к результату (0, 0). Выше мы допустили, что «операции с памятью выполняются сразу и без каких-либо задержек». Но для современных процессоров это совсем не так.

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

Сейчас мы разберем (в качестве модели) архитектуру x86.

image-loader.svg

Кэш для чтения, буфер записи (англ. Store Buffer) для записи — все просто.

1. Процессор всегда читает из кэша
2. Если в кэше такого адреса не найдено, процессор идет в память и копирует его в кэш и читает из кэша.
3. Процессор всегда пишет в буфер записи.
4. При записи нового значения в буфер запись происходит и в кэш.
5. Записи из буфера попадают в память.

Все хорошо, когда мы живем в мире одного ядра. Но когда ядер несколько начинаются вопросы.

Ядро 1 прочитало переменную f в кэш, ядро 2 изменило переменную f. Как ядро 1 узнает о изменении переменной?

Пока что, в нашей модели, никакой синхронизации между ядрами у нас нет. Так и сломался наш пример, возьмем вариант исполнения 1 (во вкладке ответ): 

x = 1 // запись попала в буфер записи (не в память)
y = 1 // запись попала в буфер записи (не в память)
b = x // в кэше потока 2 значения нет, читаем из памяти 0
a = y // в кэше потока 1 значения нет, читаем из памяти 0

В ответе (0, 0)

Мы хотим вернуть нашему примеру исполнение, чтобы он согласовывался с моделью SC — интуитивно понятной моделью.

Барьеры

Для таких случаев в процессорах x86 и Arm (а также и в других) предусмотрены специальные инструкции.

  1. load memory fence — обновить кэш*, поток не выполняет инструкции дальше, пока не выполнит обновление кэша

  2. store memory fence — записать накопленные в буфере записи данные в память, поток не выполняет инструкции дальше, пока не запишет все данные в память

*Обновление кэша происходит в соответствии с протоколом когеренции кэшей (для x86 это MESI). Но это тема отдельного разговора.

Тогда, чтобы исключить результат (0, 0) в нашем примере, нужно придумать, куда и какие именно барьеры поставить (барьер это инструкция, для простоты можно считать его вызовом функции — например store_memory_barrier (), и добавить до/после какой-либо строки).

image-loader.svgЗамечание-ответ

Простым решением конечно же будет являться такое добавление барьеров. После записи x и y необходимо, чтобы они попали в память. А перед чтением x и y нужно обновить кэш.

image-loader.svg

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

Окончательный ответ

Попробуем раскрутить простое решение

image-loader.svg

1) Можем ли мы убрать store barrier? — не можем, тогда значения x и y навечно (в нашей модели) останутся в буфере записи.

2) Можем ли убрать load barrier? — тут сложнее. Интуитивно понятно, что если убираем load barrier в одном потоке, то убираем и в другом, поскольку модель симметрична. Перебрав все варианты я пришел к выводу, что можно! Поскольку load barrier ничего нам не дает — значения x и y в кэше еще отсутствуют. И если вы ответили так, то в нашей идеальной модели вы правы.

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

Рабочий пример
#include 
#include 

int x, y, a, b;

void* thread1(void* unused) {
    x = 1;
    // store barrier
    __asm__ __volatile__ ("sfence" ::: "memory");
    // load barrier
    __asm__ __volatile__ ("lfence" ::: "memory");
    a = y;
    return NULL;
}

void* thread2(void* unused) {
    y = 1;
    // store barrier
    __asm__ __volatile__ ("sfence" ::: "memory");
    // load barrier
    __asm__ __volatile__ ("lfence" ::: "memory");
    b = x;
    return NULL;
}

int main() {
    int i = 0;
    while (1) {
        x = 0;
        y = 0;
        a = 0;
        b = 0;
        // store barrier - для честности эксперимента
        __asm__ __volatile__ ("sfence" ::: "memory");

        pthread_t tid1;
        pthread_attr_t attr1;

        pthread_t tid2;
        pthread_attr_t attr2;

        pthread_attr_init(&attr1);
        pthread_attr_init(&attr2);

        pthread_create(&tid1, &attr1, thread1, NULL);
        pthread_create(&tid2, &attr2, thread2, NULL);

        pthread_join(tid1, NULL);
        pthread_join(tid2, NULL);

        i++;
        // load barrier - для честности эксперимента
        __asm__ __volatile__ ("lfence" ::: "memory");
        if(a == 0 && b == 0) {
            break;
        }
    }

    printf("Iterations: %d\n", i);

    return 0;
}

Код скомпилирован с ключом -O0 (отключение оптимизаций)

Если Вам удалось понять содержимое статьи, то любые другие элементы многопоточного программирования дадутся Вам намного легче.

Конец

Если Вы сталкиваетесь с многопоточностью впервые, скорее всего с первого и даже с третьего раза Вам будет понятно не всё. Для полного понимания нужна практика.

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

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

© Habrahabr.ru