«Жуки, жуки, жуки» — всхрапывая, приговаривал во сне Пумба, и они ему снились!

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

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

Рассмотрим простой пример — мы запускаем два потока, один из которых миллион раз увеличивает значение переменной, а второй миллион раз значение той же переменной уменьшает. Чему будет равно значение переменной после завершения работы обоих процессов, если перед запуском она было равна нулю? Разумеется не нулю, «иначе армянское радио об этом не спрашивало бы». Правильный ответ — любое число в диапазоне от миллиона до — миллиона включительно, если мы не приняли специальных мер предосторожности — об этом позже. Чтобы не быть голословным, приведу пример программы и ее результаты за 2 прогона.

#include <iostream>
#include <thread>
#define NUMBER 1000000
using namespace std;
static int counter=0; // этой директивой мы исключили возможность размещения в регистре
int f1(void) {
    for (int i=0; i<NUMBER; i++) {
            counter++; // ldi r1,#counter; ld r0,@r1; inc r0; st r0,@r1
    };
};
int f2(void) {
    for (int i=0; i<NUMBER; i++) {
            counter--;
        };
};
int main()
{
    thread t1(f1);  
    thread t2(f2); // запускаем два потока
    t1.join();
    t2.join(); // дожидаемся завершения обоих
    cout << counter << endl;
}
340865
-557870

Несколько неожиданно для неподготовленного пользователя? Те, кто имели дело в потоками в МК могли бы ожидать число в диапазоне десятка, но сотни тысяч? В этом и есть прелесть интенсификации неопределенных состояний, что проблема встает в полный рост. Для начала, почему мы не получим в результате ноль (мы, конечно, можем его получить, но вероятность этого события весьма невелика)? Все дело в том, что на большинстве RISС архитектур невозможны прямые операции с данными в оперативной памяти, поэтому команда увеличения счетчика превратится в последоватеьность команд ассемблера, данную в комментарии. Теперь рассмотрим пример с переключением — в counter лежит 2, первый поток выполнил ассемблерные команды 1 и 2, в регистре r0 лежит 2, в этот момент выполнение первого потока прерывается, второй поток начинает работу, в counter все еще лежит 2, второй поток тысячу раз вычитает из него 1, получает числа от 1 до 998, выполняет последнюю команду записи в память, в counter лежит -998, здесь второй поток прерывают и на выполнение ставится первый поток, который выполняет команды 3 и 4 и в counter помещается 3. В итоге, результаты тысячи вычитаний исчезли. Конечно, для того, чтобы произошло именно так, первый поток нужно прервать после выполнения команды 2 и до выполнения команды 4 и это будет происходить не слишком часто, поскольку кроме приведенного фрагмента даже в нашей простенькой программе есть команды, связанные с организацией цикла, но вероятность попасть именно туда, куда надо для получения сбоя, совсем не нулевая.

Если бы в нашем МК была бы команда, которая могла увеличить либо уменьшить число в памяти, а не в регистре, то такой неприятности не произошло бы, но только в случае вытесняющей многозадачности. Если же мы работаем в режиме параллельной обработки потоков, то даже наличие такой команды не спасает нас от более тонкого, но идентичного момента, связанного с работой шины данных. Дело в том, что даже команда модификации содержимого ячейки памяти не может быть выполнена непосредственно на памяти (может быть такие системы есть, но лично мне они неизвестны) — на уровне шины все равно будет чтение из памяти в АЛУ, собственно выполнение модификации и запись полученного результата в память по тому-же адресу, то есть опять-таки есть момент, вторгнувшись в который, одиной поток может исказить результаты другого потока. Определить, какой именно вид конкурентности мы наблюдаем, возможно (оставим это в качестве задачи для пытливого читателя), но на результатах это никак не отразится — мы получили результат заведомо неверный, более того, искаженный случайным образом.
Различие между режимом исполнения на двух ядрах и в режиме переключения будет заключаться в следующем. В первом случае конфликты происходят буквально в каждом цикле (можно сказать, что переключение происходит очень часто), но искажения результата не превосходят 1. Поэтому мы будем получать совершенно случайный числа с относительно равномерным распределением. Во втором случае искажения будут происходить намного реже (только в момент переключения, да и то не всегда) но зато искажения будут составлять все операции, произведенные во время очередного исполнения потока. Поэтомц мы будем получать изменяющееся скачками значение, причем полученные данные будут групироваться вокруг дискретных ступеней. Более того, при определенных условиях мы можем даже получить правильные результаты, что приведет к тому, что мы не заметим данную проблему при отладке. Вот почему я настоятельно рекомендую прогонять программы на множестве ядер с целью интенсификации процесса проявления ошибки.

Эти грабли широко известны, стоят они в прекрасно освещенном месте, что не мешает время от времени на них наступать, я всего лишь показал как превратить их деятельность из редкой и ошеломляющей в условиях вытесняющей многозадачности, в более частую, не менее разрушительную, но значительно более наблюдаемую при параллельном вычислении. Теперь, когда мы подробно грабли разглядели и научились на них наступать с требуемой для целей отладки частотой, поговорим немного о способах обхода данных грабель и длине обходного пути.
У нас имеются средства обеспечить именно тот результат, который мы ожидали, а именно ноль, путем модификации нашей программы для учеты конкурентности вычислений. Прежде всего, это объекты, известные как мьютексы, то есть флаги на разрешение доступа к совместному ресурсу, в нашем случае области памяти с именем counter. Смотрим на код — все прекрасно, понятно и правильно, есть лишь 1 маленький недостаток — время выполнения программы с ожиданием завершения потоков увеличилось в 20+ раз — то есть мы обходим грабли по довольно-таки длинной дуге.

#include <mutex>
using namespace std;
static mutex m;
int f1(void) {
    for (int i=0; i<NUMBER; i++) {
        m.lock();
        counter++;
        m.unlock();
    };
};

Понятно, почему это произошло — вместо простой операции модификации мы дополнительно захватываем мьютекс, при этом второй поток при попытке его захвата приостанавливается, производим операцию и мьютекс отпускаем, что тоже требует времени. Тем не менее, главное преимущество данного варианат, помимо его правильности, в ом что он будет работать везде, где есть пакет thread и mutex. Главный же недостаток данного метода в том что дополнительные операции мы должны проыодить всегда, независимо от наличия в данный момент конкуренции за ресурс.
Есть несколько более вычурный, но зато значительно менее длинный, путь обхода, который связан с операцией CompareAndSwap.

using namespace std;
int f1(void) {
    int j;
    for (int i=0; i<NUMBER; i++) {
            do {
                j=counter;
            } while (__sync_val_compare_and_swap(&counter,j,j+1) != j );
        };
};

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

int f1(void) {
    for (int i=0; i<NUMBER; i++) {
        __sync_add_and_fetch(&counter,1);
    };
};

Все абсолютно правильно, почти понятно с первого взгляда, а если прочитать материалы об атомарных операциях, то абсолютно понятно, компактно и достаточно быстро — у меня время исполнения увеличилось всего лишь в 2+ раза (у вас может получться иначе), но минус — аппаратные атомарные операции редкий зверь, как и C&S, а если вы начинаете применять их программные аналоги, то мгновенно скатываетесь на уровень быстродействия мьютексов.
Подведем итог — если у вас есть атомарные операции, то их применение для элементарного доступа к разделяемому ресурсу дает наиболее быстрый и компактный код, причем вид параллельности абсолютно неважен — будет работать всегда. Команда C&S представляет собой хорошую альтернативу, хотя накладные расходы могут оказаться выше в случае жесткой конкуренции за ресурс. И применение мьютексов — наиболее накладный вариант, если ничего другого нет. Кстати, небольшое рассуждение по поводу мьютексов — а как их вообще делают? Если для варианта с переключением контекста все понятно — мы можем запретить переключение путем либо запрета прерываний, либо путем запрета работы шедулера (последний вариант предпочтительнее, поскольку легко решить проблемы с восстановлением состояния), то для вариатна с множеством ядер ответ не столь очевиден. Скорее всего, без использования длинной блокировки шины либо применения команды C&S не обойтись. Есть еще очень интересный вариант, когда аналог команды C&S реализуется при помощи команды XCH регистра и памяти, но и в этом случае команда должна исполняться в атомарном режиме. Если кто знает другие варианты, поделитесь информацией либо ссылками.

Параллельные вычисления — немного грабель