Или Вы легко можете предложить реальный объект, который может послужить основой теста на параллелизм.
void sqrt_vectorized(float* const data,
const size_t size) {
#pragma omp parallel
#pragma omp for
for (size_t i = 0; i < size; ++i) {
data[i] = std::sqrt(data[i]);
}
}
В том, что функция работает параллельно, можно легко убедиться, написав простейший бенчмарк:
std::random_device rd;
std::mt19937 engine(rd());
std::uniform_real_distribution<float> dist(1.0, 1e9);
constexpr size_t SIZE = 1'000'000'000;
std::vector<float> v(SIZE);
for (size_t i = 0; i < SIZE; ++i) {
v[i] = dist(engine);
}
const auto begin = std::chrono::steady_clock::now();
sqrt_vectorized(v.data(), v.size());
const auto end = std::chrono::steady_clock::now();
const auto elaped = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin);
std::cout << elapsed.count() << "ms elapsed" << std::endl;
Собираем с -fopenmp, при запуске варьируем OMP_NUM_THREADS. Наблюдая изменение времени работы функции видим, что функция и правда работает параллельно.
Вы тестируете конкурентные структуры в однопоточной среде, имеется в виду один физический поток ОС. При этом, используя модель чередования выполнения инструкций, на которую можно полагаться, только при условии, что весь код корректно синхронизирован с учетом модели памяти конкретного рантайма и железа.
Но в продакшн условиях, как я понимаю у вас многопоточная среда выполнения со своим планировщиком, работающим более чем с одним физическим потоком ОС
К сожалению да, если у нас есть некорректный код, работающий со слабыми модулями памяти, например:
struct two_numbers_t {
std::atomic<int> x{0};
std::array<int, 100> unused; // x and y should be in diffrerent cache lines
std::atomic<int> y{0};
void thread_1_body() {
x.store(1, std::memory_order_relaxed);
x.store(1, std::memory_order_relaxed);
}
void thread_2_body() {
const int local_x_value = x.load(std::memory_order_relaxed);
const int local_y_value = y.load(std::memory_order_relaxed);
assert(!(local_x_value == 0 && local_y_value == 1) &&
"This must not happen!");
}
}
то на реальном многоядерном исполнении мы можем поймать во втором (читающем) потоке ошибку, потому что запись единицы в y дойдёт до оперативной памяти, в то время как запись единицы в x останется в кеше CPU, std::memory_order_relaxed допускает такой спецэффект.
Наша тестирующая система такую проблему сейчас не найдёт, поскольку она исполняет операции в рамках одного потока. В целом, проблема решаемая (например с помощью эмулирования семантики модели памяти), мы собираемся это поддержкать.
Апелляция к переводу на русский не доказывает ничего. Может существовать язык, в котором и термин "Concurrent Programming", и термин "Parallel Programming" переводятся одним и тем же словом. Это не отменяет того факта, что нам для правильного описания окружающего мира нужно два понятия: и конкурентность, и параллелизм. Доказать это очень просто: вот тут, например, приведены примеры четырёх исполнений:
Не конкурентное и не параллельное исполнение: обычный последовательный код вида
int a = 42;
if (a != 24) ++a;
for (int i = 0; i < 1000; ++i) a += i;
Конкурентное, но не параллельное исполнение. Для этого нужно, например, запустить два треда в python:
import threading
import random
def thread_body():
s = 0
for i in range(1_000_000):
s += random.randint(0, 1_000)
if s % 2 == 0:
print('heads')
else:
print('tails')
t1 = threading.Thread(target=thread_body, args=[])
t2 = threading.Thread(target=thread_body, args=[])
t1.start()
t2.start()
t1.join()
t2.join()
В этом случае GIL не даст нам исполнять эти два треда параллельно. Зато время от времени текущий исполняемый тред будет прерываться, уступая возможность исполняться другому треду. Это и будет являться конкурентной работой.
Параллельное, но не конкурентное исполнение. Для этого необходимо чтобы два CPU исполняли параллельно каждый свою задачу, не прерываясь на другие задачи (переключение на другую задачу до завершения текущей задачи обычно и называют конкурентностью).
На современных ОС этого добиться непросто, поскольку время от времени современная многозадачная ОС будет снимать любой пользовательский процесс с CPU. Впрочем, мы всё ещё можем представить себе ОС с кооперативной многозадачностью, которая бы не снимала пользовательский процесс с конвейра CPU пока сам процесс явно не попросит её об этом с помощью особого системного вызова.
Параллельное и конкурентное исполнение. Представим себе код вида
std::vector<std::thread> threads;
for (int i = 0; i < 1'000; ++i) {
threads.emplace_back([]{
int s = 0;
for (int j = 0; j < 1'000'000; ++j) j += rand();
if (s % 2 == 0) printf("heads");
else printf("tails");
});
}
for (std::thread& t: threads) {
t.join();
}
при исполнении которого система честно будет исполнять треды параллельно (если мы, конечно, запустим этот код на многоядерной машине), и при этом время от времени будет снимать текущий тред с конвейра CPU чтобы дать время на исполнение другому треду (мы предполагаем, что число тредов много больше числа ядер, а планировщик ОС стремится дать каждому из тредов время на исполнение).
Из приведённых примеров, кажется, следует, что конкурентность и параллельность друг к другу не сводимы и мы можем достаточно легко представить одно без другого.
Оглавления двух книг, написанных одним и тем же автором
Это два перевода одной и той же книги "C++ Concurrency in Action" (возможно, переводы сделаны по разным изданиям). К слову, в самой книге есть глава "Concurrency vs. parallelism", подсвечивающая некоторые тонкости использования этих понятий. И тут же снова отсылаю к Робу Пайку, "Concurrency is not parallelism".
появились много-много раньше того, как активно стал использоваться термин "конкурентное програмирование". Последнее - дань некой вдуг откуда ни возьмись (с перепугу?) возникшей моде
Существует публикация Эдгара Кодда от 1962 года, буквально начинающаяся с главы "Concurrency". Учитывая, что начинается эта глава со слов "The basic concern of multiprogramming is concurrency of operations within computer systems. Many different types of concurrency are incorporated in the computers in use today" можно предположить, что в 1962 году термин "конкурентность" уже достаточно широко использовался, не нуждался в дополнительных пояснениях и поддерживался современными автору вычислительными системами.
Ну или вот работа 1977 года, в которой термин "Concurrency" используется в абсолютно том же смысле, что и в современных статьях.
В целом это должно быть и есть на самом деле одно и то же.
Нет, это не так. Конкурентность предполагает, что мы можем прервать исполнение некоторой операции A и начать исполнять операцию B (не завершив исполнение операции A до конца), а потом снова вернуться к исполнению операции A и продолжить исполнять её с того места, на котором остановились. При этом никакого параллелизма в нашей системе может и не быть: в нашей системе может быть буквально всего один одноядерный CPU и всего один тред ОС, на нашу способность писать конкурентный код это никак не влияет. Вот, например, реализация конкурентной многозадачности, не поддерживающей параллелизм.
На мой взгляд тут поможет только одно - отказаться от ОС, позволяющей подобное... ОС должна быть предсказуемой и надежной
Ну в целом существуют детерминированные планировщики и ОС реального времени, которые умеют давать какие-то гарантии на время нахождения процесса в idle статусе. Отказ же от ОС целиком не кажется нам сейчас возможным: например, наш сетевой движок активно использует мултиплексирование IO из Linux.
Понятие конкуррентности (параллелизма) применимо к процессам, но по отношению к данным звучит как-то странно?
Если честно, не могу найти, где я в статье использовал бы такой термин. Что касается конкурентности и параллелизма — это в целом разные вещи, есть известный доклад Роба Пайка об этом.
Конкурентность по отношению к данным мне и правда сложно представить, но при этом параллелизм данных это достаточно известная тема, традиционно противопоставляемая параллелизму команд. Параллелизм команд позволяет каждому исполнителю (например ядру CPU) исполнять собственную независимую от остальных исполнителей последовательность инструкций
`std::thread t1([]{
if (rand() % 2 == 0) printf("heads"); else printf("tails");
}); // First CPU executes its own sequence of operations
std::thread t2([]{
int sum = 0;
for (int i = 0; i < 1000; ++i) sum += rand();
printf("sum is %d", sum);
}); // Second CPU executes another sequence of operations
t1.join();
t2.join();
При параллелизме команд же мы параллельно применяем одну и ту же последовательность команд f к разным наборам входных данных A, B, C, D, ... , таким образом параллельно считая f(A), f(B), f(C), f(D), ... . Типичным представителем параллелизма данных являются векторные инструкции CPU, например инструкция SQRTPS параллельно применяет один и то же алгоритм подсчёта квадратного корня сразу к нескольким числам с плавающей точкой, то есть делает что-то вроде
constexpr int SIZE = 8;
std::array<float, SIZE> src{/* ... */};
std::array<float, SIZE> dst;
#pragma omp parallel
{
for (int i = 0; i < SIZE; ++i) {
dst[i] = std::sqrt(src[i]);
}
}
И пусть есть два потока, пытающиеся исполнить операцию inc . Первый поток захватывает блокировку и в этот момент ОС убирает этот поток с CPU на неопределённое (иногда достаточно большое) время. Всё это время второй поток будет просто ждать получения блокировки и не совершать никакой полезной работы, хотя его с конвейра CPU никто не снимал и он мог бы совершать полезную работу.
Для того, чтобы избежать такой ситуации, мы хотим писать алгоритмы, удовлетворяющие определённым гарантиям прогресса: три самые часто встречающиеся это obstruction-free, lock-free и wait-free.
Obstruction-freedom гарантирует, что если все потоки, кроме одного, приостановить, то единственный не приостановленный завершится за конечное число шагов. Наша реализация этого не гарантирует, так как единственный не приостановленный поток (второй) не завершится пока первый поток (приостановленный ОС) не отпустит блокировку
Lock-freedom гарантирует, что хотя бы один поток завершится за конечное число шагов. Наша реализация этого не гарантирует, так как первый поток приостановлен, а второй поток ожидает пробуждения первого потока, и следовательно, не завершит свою работу пока первый поток не отпустит блокировку.
Wait-freedom гарантирует, что все потоки завершатся за конечное число шагов. Очевидно, в нашей реализации это не так, потому что второй поток ожидает пробуждения первого потока.
Зачастую алгоритмы с блокировками на практике показывают перфоманс хуже, чем lock-free алгоритмы: например, в статье Майкла и Скотта про очереди есть график, показывающий что lock-free реализация обгоняет реализацию с блокировками
Кроме того, даже алгоритмы с блокировками бывают сложными (например, вот такая реализация AVL дерева с fine-grained блокировками), их тоже нужно верифицировать, и наш метод подходит в том числе для верификации алгоритмов с блокировками.
С++ компилятор переставляет statements без зависимости по данным? Если да, то как изложенный подход справится с этим?
В этом смысле особенных проблем не будет. Ну вот пусть есть у нас код
func f() {
x := ATOMIC_READ(&V1)
ATOMIC_WRITE(&V1, x + 1)
y := ATOMIC_READ(&V2)
ATOMIC_WRITE(&V2, y - 1)
}
При некоторых условиях компилятор волен будет переставить местами инструкции, получив, например
func f() {
x := ATOMIC_READ(&V1)
y := ATOMIC_READ(&V2)
ATOMIC_WRITE(&V1, x + 1)
ATOMIC_WRITE(&V2, y - 1)
}
Для этого кода мы вызовем наш LLVM pass, получив в итоге корутину вида
func f() {
x := ATOMIC_READ(&V1)
co_yield
y := ATOMIC_READ(&V2)
co_yield
ATOMIC_WRITE(&V1, x + 1)
co_yield
ATOMIC_WRITE(&V2, y - 1)
}
То есть тестировать с помощью эмуляции переключения потоков мы в итоге будем непосредственно тот код, который нам сгенерировал компилятор.
Проблема, с которой мы пока справляемся плохо, заключена в другом: пусть у нас есть код вида
struct two_numbers_t {
int* x = new int(0);
int* y = new int(0);
void thread_1_body() {
*x = 1;
*y = 1;
}
void thread_2_body() {
const int local_x_value = *x;
const int local_y_value = *y;
assert(!(local_x_value == 0 && local_y_value == 1) &&
"This must not happen!");
}
}
Из-за того, как работает реальное железо (в частности, кеши CPU) мы можем получить исполнение, при котором второй поток увидит x равным 0 (то есть x ещё не был инициализирован), а y равным 1 (то есть y уже был инициализирован), хотя в первом потоке инициализация x происходит перед инициализацией y .
В нашем же тестовом фреймворке мы не сможем воспроизвести такую ситуацию, потому что всё чтения и записи происходят в пределах одного треда ОС, что убирает влияние кешей CPU на порядок видимости записей. В дальнейшем мы планируем научиться ловить и такие проблемы, есть уже пара идей, как такое можно делать.
конвертор в модельный Си язык для истинного параллелизма (например Promela в SPIN model checker) не проще было бы (не связываясь с "ассемблером")?
В нашем случае нам показалось, что расставить прерывания в коде было проще, чем учиться превращать наш код C++ в код на Promela. Что интересно, в проекте по верификации распределённых алгоритмов мы пользовались специальными языками, предназначенными для верификации, только это была не связка Promela/SPIN, а связка TLA+/TLC. С помощью TLC мы генерировали все возможные исполнения нашей системы, а потом превращали их в набор тестовых сценариев на Golang и проверяли, что код нашей системы при всех исполнениях ведёт себя так же, как TLA+-модель. Вот тут можно узнать подробнее, как это работает, если интересно.
Про саму связку Promela/SPIN мы в курсе, некоторые связанные с ней проекты (например, вот и вот) кажутся нам интересными, идеи из них мы планируем использовать и развивать в дальнейшей работе.
Точки переключения мы выставляем автоматически, на этапе преобразования исходного кода при помощи написанного нами LLVM pass. Никакого сложного анализа мы не делали, а использовали набор достаточно простых эвристик: ставили точку переключения после каждого обращения к разделяемой переменной, то есть к переменной-члену тестируемой структуры или к глобальной переменной. После обращения к локальным переменным точки переключения мы не ставили, поскольку такие обращения никак не меняют разделяемое состояние (так как локальные переменные одного потока недоступны другим потокам). Таким образом, код
struct counter {
int value;
void inrement(int delta) {
while (true) {
const int cur_value = ATOMIC_READ(&this->value); // acess to shared variable
const int new_value = cur_value + delta; // access to local variable
if (COMPARE_AND_SWAP(&this->value, cur_value, new_value)) { // acess to shared variable
return;
}
}
}
}
превратится в
struct counter {
int value;
void inrement(int delta) {
while (true) {
const int cur_value = ATOMIC_READ(&this->value);
co_yield;
const int new_value = cur_value + delta;
// no co_yield here, because no shared state has been modified since the last co_yield
const bool cas_res = COMPARE_AND_SWAP(&this->value, cur_value, new_value);
co_yield;
if (cas_res) {
return;
}
}
}
}
Я правильно понял, что будет взят ассемблер и автоматически переписан так, чтобы получилась корутина?
Работать с ассемблером сложно, поэтому мы работали с LLVM intermediate representation (для работы с ним существует удобное API, называемое LLVM passes).
А что с вызовами функций?
У нас есть два варианта работы с вызовами функций. В первом с каждой вызываемой функцией мы поступаем так же, как с исходной функцией: ставим оператор прерывания корутины co_yield после каждой интересующей нас инструкции. Например, код
fun g() {
y := READ_ATOMIC(V2)
WRITE_ATOMIC(V2, y - 1)
}
fun f() {
x := READ_ATOMIC(V1)
g()
WRITE_ATOMIC(V1, x + 1)
}
превратится в
fun g() {
y := READ_ATOMIC(V2)
co_yield
WRITE_ATOMIC(V2, y - 1)
}
fun f() {
x := READ_ATOMIC(V1)
co_yield
g()
co_yield
WRITE_ATOMIC(V1, x + 1)
}
Таким образом, функция f() , будучи вызванной, четыре раза вернёт упаравление вызывающему коду:
После инструкции x := READ_ATOMIC(V1)
После инструкции y := READ_ATOMIC(V2)
После инструкции WRITE_ATOMIC(V2, y - 1) , то есть после выхода из функции g()
После инструкции WRITE_ATOMIC(V1, x + 1) , когда исполнение функции f() будет завершено
Второй вариант работы с вызовами функций состоит в том, что вызываемые функции мы считаем атомарными и не добавляем в их код операторы прерывания. Таким образом, код
fun g() {
y := READ_ATOMIC(V2)
WRITE_ATOMIC(V2, y - 1)
}
fun f() {
x := READ_ATOMIC(V1)
g()
WRITE_ATOMIC(V1, x + 1)
}
превращается в
fun g() {
y := READ_ATOMIC(V2)
WRITE_ATOMIC(V2, y - 1)
}
fun f() {
x := READ_ATOMIC(V1)
co_yield
g()
co_yield
WRITE_ATOMIC(V1, x + 1)
}
Таким образом, функция f() , будучи вызванной, три раза вернёт упаравление вызывающему коду:
После инструкции x := READ_ATOMIC(V1)
После инструкции WRITE_ATOMIC(V2, y - 1) , то есть после выхода из функции g()
После инструкции WRITE_ATOMIC(V1, x + 1) , когда исполнение функции f() будет завершено
Функция g() же будет считаться атомарной, в ней исполнение прерываться не будет.
Это race detector, он не умеет проверять на линеаризуемость, да и на другие критерии корректности тоже: последовательную согласованность (sequential consistency), согласованность при покое (quiescent consistency), etc.
В том, что функция работает параллельно, можно легко убедиться, написав простейший бенчмарк:
Собираем с
-fopenmp, при запуске варьируемOMP_NUM_THREADS. Наблюдая изменение времени работы функции видим, что функция и правда работает параллельно.К сожалению да, если у нас есть некорректный код, работающий со слабыми модулями памяти, например:
то на реальном многоядерном исполнении мы можем поймать во втором (читающем) потоке ошибку, потому что запись единицы в
yдойдёт до оперативной памяти, в то время как запись единицы вxостанется в кеше CPU,std::memory_order_relaxedдопускает такой спецэффект.Наша тестирующая система такую проблему сейчас не найдёт, поскольку она исполняет операции в рамках одного потока. В целом, проблема решаемая (например с помощью эмулирования семантики модели памяти), мы собираемся это поддержкать.
Апелляция к переводу на русский не доказывает ничего. Может существовать язык, в котором и термин "Concurrent Programming", и термин "Parallel Programming" переводятся одним и тем же словом. Это не отменяет того факта, что нам для правильного описания окружающего мира нужно два понятия: и конкурентность, и параллелизм. Доказать это очень просто: вот тут, например, приведены примеры четырёх исполнений:
Не конкурентное и не параллельное исполнение: обычный последовательный код вида
Конкурентное, но не параллельное исполнение. Для этого нужно, например, запустить два треда в python:
В этом случае GIL не даст нам исполнять эти два треда параллельно. Зато время от времени текущий исполняемый тред будет прерываться, уступая возможность исполняться другому треду. Это и будет являться конкурентной работой.
Параллельное, но не конкурентное исполнение. Для этого необходимо чтобы два CPU исполняли параллельно каждый свою задачу, не прерываясь на другие задачи (переключение на другую задачу до завершения текущей задачи обычно и называют конкурентностью).
На современных ОС этого добиться непросто, поскольку время от времени современная многозадачная ОС будет снимать любой пользовательский процесс с CPU. Впрочем, мы всё ещё можем представить себе ОС с кооперативной многозадачностью, которая бы не снимала пользовательский процесс с конвейра CPU пока сам процесс явно не попросит её об этом с помощью особого системного вызова.
Параллельное и конкурентное исполнение. Представим себе код вида
при исполнении которого система честно будет исполнять треды параллельно (если мы, конечно, запустим этот код на многоядерной машине), и при этом время от времени будет снимать текущий тред с конвейра CPU чтобы дать время на исполнение другому треду (мы предполагаем, что число тредов много больше числа ядер, а планировщик ОС стремится дать каждому из тредов время на исполнение).
Из приведённых примеров, кажется, следует, что конкурентность и параллельность друг к другу не сводимы и мы можем достаточно легко представить одно без другого.
Это два перевода одной и той же книги "C++ Concurrency in Action" (возможно, переводы сделаны по разным изданиям). К слову, в самой книге есть глава "Concurrency vs. parallelism", подсвечивающая некоторые тонкости использования этих понятий. И тут же снова отсылаю к Робу Пайку, "Concurrency is not parallelism".
Не понимаю, что из этого вообще должно следовать. Кто-то использует coarse-grained locking, кто-то использует fine-grained locking, кто-то разрабатывает алгоритмы без блокировок, это выбор реализующего структуру данных программиста.
Существует публикация Эдгара Кодда от 1962 года, буквально начинающаяся с главы "Concurrency". Учитывая, что начинается эта глава со слов "The basic concern of multiprogramming is concurrency of operations within computer systems. Many different types of concurrency are incorporated in the computers in use today" можно предположить, что в 1962 году термин "конкурентность" уже достаточно широко использовался, не нуждался в дополнительных пояснениях и поддерживался современными автору вычислительными системами.
Ну или вот работа 1977 года, в которой термин "Concurrency" используется в абсолютно том же смысле, что и в современных статьях.
Нет, это не так. Конкурентность предполагает, что мы можем прервать исполнение некоторой операции A и начать исполнять операцию B (не завершив исполнение операции A до конца), а потом снова вернуться к исполнению операции A и продолжить исполнять её с того места, на котором остановились. При этом никакого параллелизма в нашей системе может и не быть: в нашей системе может быть буквально всего один одноядерный CPU и всего один тред ОС, на нашу способность писать конкурентный код это никак не влияет. Вот, например, реализация конкурентной многозадачности, не поддерживающей параллелизм.
Ну в целом существуют детерминированные планировщики и ОС реального времени, которые умеют давать какие-то гарантии на время нахождения процесса в idle статусе. Отказ же от ОС целиком не кажется нам сейчас возможным: например, наш сетевой движок активно использует мултиплексирование IO из Linux.
Если честно, не могу найти, где я в статье использовал бы такой термин. Что касается конкурентности и параллелизма — это в целом разные вещи, есть известный доклад Роба Пайка об этом.
Конкурентность по отношению к данным мне и правда сложно представить, но при этом параллелизм данных это достаточно известная тема, традиционно противопоставляемая параллелизму команд. Параллелизм команд позволяет каждому исполнителю (например ядру CPU) исполнять собственную независимую от остальных исполнителей последовательность инструкций
При параллелизме команд же мы параллельно применяем одну и ту же последовательность команд
fк разным наборам входных данныхA, B, C, D, ..., таким образом параллельно считаяf(A), f(B), f(C), f(D), .... Типичным представителем параллелизма данных являются векторные инструкции CPU, например инструкцияSQRTPSпараллельно применяет один и то же алгоритм подсчёта квадратного корня сразу к нескольким числам с плавающей точкой, то есть делает что-то вродеС алгоритмами на блокировках есть фундаментальная проблема: пусть у нас есть код вида
И пусть есть два потока, пытающиеся исполнить операцию
inc. Первый поток захватывает блокировку и в этот момент ОС убирает этот поток с CPU на неопределённое (иногда достаточно большое) время. Всё это время второй поток будет просто ждать получения блокировки и не совершать никакой полезной работы, хотя его с конвейра CPU никто не снимал и он мог бы совершать полезную работу.Для того, чтобы избежать такой ситуации, мы хотим писать алгоритмы, удовлетворяющие определённым гарантиям прогресса: три самые часто встречающиеся это obstruction-free, lock-free и wait-free.
Obstruction-freedom гарантирует, что если все потоки, кроме одного, приостановить, то единственный не приостановленный завершится за конечное число шагов. Наша реализация этого не гарантирует, так как единственный не приостановленный поток (второй) не завершится пока первый поток (приостановленный ОС) не отпустит блокировку
Lock-freedom гарантирует, что хотя бы один поток завершится за конечное число шагов. Наша реализация этого не гарантирует, так как первый поток приостановлен, а второй поток ожидает пробуждения первого потока, и следовательно, не завершит свою работу пока первый поток не отпустит блокировку.
Wait-freedom гарантирует, что все потоки завершатся за конечное число шагов. Очевидно, в нашей реализации это не так, потому что второй поток ожидает пробуждения первого потока.
Зачастую алгоритмы с блокировками на практике показывают перфоманс хуже, чем lock-free алгоритмы: например, в статье Майкла и Скотта про очереди есть график, показывающий что lock-free реализация обгоняет реализацию с блокировками
Кроме того, даже алгоритмы с блокировками бывают сложными (например, вот такая реализация AVL дерева с fine-grained блокировками), их тоже нужно верифицировать, и наш метод подходит в том числе для верификации алгоритмов с блокировками.
В этом смысле особенных проблем не будет. Ну вот пусть есть у нас код
При некоторых условиях компилятор волен будет переставить местами инструкции, получив, например
Для этого кода мы вызовем наш LLVM pass, получив в итоге корутину вида
То есть тестировать с помощью эмуляции переключения потоков мы в итоге будем непосредственно тот код, который нам сгенерировал компилятор.
Проблема, с которой мы пока справляемся плохо, заключена в другом: пусть у нас есть код вида
Из-за того, как работает реальное железо (в частности, кеши CPU) мы можем получить исполнение, при котором второй поток увидит
xравным0(то естьxещё не был инициализирован), аyравным1(то естьyуже был инициализирован), хотя в первом потоке инициализацияxпроисходит перед инициализациейy.В нашем же тестовом фреймворке мы не сможем воспроизвести такую ситуацию, потому что всё чтения и записи происходят в пределах одного треда ОС, что убирает влияние кешей CPU на порядок видимости записей. В дальнейшем мы планируем научиться ловить и такие проблемы, есть уже пара идей, как такое можно делать.
В нашем случае нам показалось, что расставить прерывания в коде было проще, чем учиться превращать наш код C++ в код на Promela. Что интересно, в проекте по верификации распределённых алгоритмов мы пользовались специальными языками, предназначенными для верификации, только это была не связка Promela/SPIN, а связка TLA+/TLC. С помощью TLC мы генерировали все возможные исполнения нашей системы, а потом превращали их в набор тестовых сценариев на Golang и проверяли, что код нашей системы при всех исполнениях ведёт себя так же, как TLA+-модель. Вот тут можно узнать подробнее, как это работает, если интересно.
Про саму связку Promela/SPIN мы в курсе, некоторые связанные с ней проекты (например, вот и вот) кажутся нам интересными, идеи из них мы планируем использовать и развивать в дальнейшей работе.
Наша инфраструктурная команда поддерживает:
Самописные хранилища данных
Самописный консенсусный репликатор
Самописный компилятор и рантайм PHP (видео, код)
Самописный распределённый компилятор C++ (видео, статья, код)
Самописную систему мониторинга больших распределённых систем (видео, код)
И ещё много всяких интересных и крутых штук. Думаю, что и с библиотекой конкурентных примитивов тоже справимся.
Точки переключения мы выставляем автоматически, на этапе преобразования исходного кода при помощи написанного нами LLVM pass. Никакого сложного анализа мы не делали, а использовали набор достаточно простых эвристик: ставили точку переключения после каждого обращения к разделяемой переменной, то есть к переменной-члену тестируемой структуры или к глобальной переменной. После обращения к локальным переменным точки переключения мы не ставили, поскольку такие обращения никак не меняют разделяемое состояние (так как локальные переменные одного потока недоступны другим потокам). Таким образом, код
превратится в
Работать с ассемблером сложно, поэтому мы работали с LLVM intermediate representation (для работы с ним существует удобное API, называемое LLVM passes).
У нас есть два варианта работы с вызовами функций. В первом с каждой вызываемой функцией мы поступаем так же, как с исходной функцией: ставим оператор прерывания корутины
co_yieldпосле каждой интересующей нас инструкции. Например, кодпревратится в
Таким образом, функция
f(), будучи вызванной, четыре раза вернёт упаравление вызывающему коду:После инструкции
x := READ_ATOMIC(V1)После инструкции
y := READ_ATOMIC(V2)После инструкции
WRITE_ATOMIC(V2, y - 1), то есть после выхода из функцииg()После инструкции
WRITE_ATOMIC(V1, x + 1), когда исполнение функцииf()будет завершеноВторой вариант работы с вызовами функций состоит в том, что вызываемые функции мы считаем атомарными и не добавляем в их код операторы прерывания. Таким образом, код
превращается в
Таким образом, функция
f(), будучи вызванной, три раза вернёт упаравление вызывающему коду:После инструкции
x := READ_ATOMIC(V1)После инструкции
WRITE_ATOMIC(V2, y - 1), то есть после выхода из функцииg()После инструкции
WRITE_ATOMIC(V1, x + 1), когда исполнение функцииf()будет завершеноФункция
g()же будет считаться атомарной, в ней исполнение прерываться не будет.Это race detector, он не умеет проверять на линеаризуемость, да и на другие критерии корректности тоже: последовательную согласованность (sequential consistency), согласованность при покое (quiescent consistency), etc.