Comments 32
А другие библиотеки, например, https://www.1024cores.net/home/relacy-race-detector смотрели?
Базово он будет работать следующим образом: тестируемая функция превращается в корутину
Я правильно понял, что будет взят ассемблер и автоматически переписан так, чтобы получилась корутина? А что с вызовами функций?
Я правильно понял, что будет взят ассемблер и автоматически переписан так, чтобы получилась корутина?
Работать с ассемблером сложно, поэтому мы работали с 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() же будет считаться атомарной, в ней исполнение прерываться не будет.
Проблема в том, что корутины Golang нас разбаловали
Фигасе проблемы у людей...
Если чего-то нет, значит, надо это написать. Вот мы и написали библиотеку, содержащую:
примитивы синхронизации для корутин;
обычные lock-free структуры данных вроде FAA-очереди;
корутинный сетевой движок;
планировщик корутин;
другие необходимые для работы наших баз данных компоненты.
Никогда не видел, чтобы такой самопал нормально работал и нормально поддерживался.
Наша инфраструктурная команда поддерживает:
Самописные хранилища данных
Самописный консенсусный репликатор
Самописный распределённый компилятор C++ (видео, статья, код)
Самописную систему мониторинга больших распределённых систем (видео, код)
И ещё много всяких интересных и крутых штук. Думаю, что и с библиотекой конкурентных примитивов тоже справимся.
А возможные точки передачи управления устанавливаются вручную и представляют собой потенциальный источник ошибок? Или используете для этого статический анализ ГЗД, и, соответственно, автоматическое нахождение всех потенциально возможных конфликтных мест для установки точек переключения?
Точки переключения мы выставляем автоматически, на этапе преобразования исходного кода при помощи написанного нами 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;
}
}
}
}
Интересная статья. Пара вопросов:
1) С++ компилятор переставляет statements без зависимости по данным? Если да, то как изложенный подход справится с этим?
2) конвертор в модельный Си язык для истинного параллелизма (например Promela в SPIN model checker) не проще было бы (не связываясь с "ассемблером")?
С++ компилятор переставляет 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 мы в курсе, некоторые связанные с ней проекты (например, вот и вот) кажутся нам интересными, идеи из них мы планируем использовать и развивать в дальнейшей работе.
Есть простой пример. Пусть у нас будет код, увеличивающий значение переменной Variable на единицу....
А почему бы эти строки не "окружить", например, мютексом или семафором? Т.е. фактически данную последовательность строк кода преврадить в атомарный код. И тогда не должно быть проблем.от слова совсем.
Что-то не так в этой идее?
С алгоритмами на блокировках есть фундаментальная проблема: пусть у нас есть код вида
struct counter_t {
int value{0};
std::mutex lock;
void inc() {
mutex.lock();
++value;
mutex.unlock();
}
}И пусть есть два потока, пытающиеся исполнить операцию inc . Первый поток захватывает блокировку и в этот момент ОС убирает этот поток с CPU на неопределённое (иногда достаточно большое) время. Всё это время второй поток будет просто ждать получения блокировки и не совершать никакой полезной работы, хотя его с конвейра CPU никто не снимал и он мог бы совершать полезную работу.
Для того, чтобы избежать такой ситуации, мы хотим писать алгоритмы, удовлетворяющие определённым гарантиям прогресса: три самые часто встречающиеся это obstruction-free, lock-free и wait-free.
Obstruction-freedom гарантирует, что если все потоки, кроме одного, приостановить, то единственный не приостановленный завершится за конечное число шагов. Наша реализация этого не гарантирует, так как единственный не приостановленный поток (второй) не завершится пока первый поток (приостановленный ОС) не отпустит блокировку
Lock-freedom гарантирует, что хотя бы один поток завершится за конечное число шагов. Наша реализация этого не гарантирует, так как первый поток приостановлен, а второй поток ожидает пробуждения первого потока, и следовательно, не завершит свою работу пока первый поток не отпустит блокировку.
Wait-freedom гарантирует, что все потоки завершатся за конечное число шагов. Очевидно, в нашей реализации это не так, потому что второй поток ожидает пробуждения первого потока.
Зачастую алгоритмы с блокировками на практике показывают перфоманс хуже, чем lock-free алгоритмы: например, в статье Майкла и Скотта про очереди есть график, показывающий что lock-free реализация обгоняет реализацию с блокировками
Кроме того, даже алгоритмы с блокировками бывают сложными (например, вот такая реализация AVL дерева с fine-grained блокировками), их тоже нужно верифицировать, и наш метод подходит в том числе для верификации алгоритмов с блокировками.
И пусть есть два потока, пытающиеся исполнить операцию
inc. ...
На мой взгляд тут поможет только одно - отказаться от ОС, позволяющей подобное... ОС должна быть предсказуемой и надежной, как ... процессор ;) Есть и другое радикальное решение - не использовать потоки.
И еще. Понятие конкуррентности (параллелизма) применимо к процессам, но по отношению к данным звучит как-то странно?
На мой взгляд тут поможет только одно - отказаться от ОС, позволяющей подобное... ОС должна быть предсказуемой и надежной
Ну в целом существуют детерминированные планировщики и ОС реального времени, которые умеют давать какие-то гарантии на время нахождения процесса в 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]);
}
}
Если честно, не могу найти, где я в статье использовал бы такой термин.
А в самом названии статьи? - "конкурентные структуры данных". Или "структуры данных" и просто "данные" -это разные вещи. Первые - процессы, а второе - нет?
Что касается конкурентности и параллелизма — это в целом разные вещи,
В целом это должно быть и есть на самом деле одно и то же. По крайней мере термины - параллельные системы, параллельные алгоритмы, параллельное програмирование и т.п. появились много-много раньше того, как активно стал использоваться термин "конкурентное програмирование". Последнее - дань некой вдуг откуда ни возьмись (с перепугу?) возникшей моде, которая к смыслу не имеет ни какого отношения.
А параллелизм команд и параллелизм данных - это суть параллельные алгоритмы, различающиеся разными подходами к обработке данных и организации параллельных процессов..
Вот пример. Чем отличается иностранный агент от шпиона? По мне так одно и то же ;). Но нынче они почему-то трактуются по-разному. Так и конкурентное и параллельное програмирование ;)
появились много-много раньше того, как активно стал использоваться
термин "конкурентное програмирование". Последнее - дань некой вдуг
откуда ни возьмись (с перепугу?) возникшей моде
Существует публикация Эдгара Кодда от 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 и всего один тред ОС, на нашу способность писать конкурентный код это никак не влияет. Вот, например, реализация конкурентной многозадачности, не поддерживающей параллелизм.
Уж коли дело дошло до цитирования. Смотрим.
Определения, словари
В.К. Зейденберг и др. Англо-русский словарь по вычислительной технике: Ок. 42 000 терминов / Под редакцией Е.К. Масловского. - М.: Рус. яз., 1990. - 800 с.
concurrency совпадение (во времени); параллелизм...
concurrent 1. одновременный, совпадающий (во времени); параллельный 2. совместный
parallel параллельный...
Толковый словарь по вычислительным системам/Под. ред. В. Иллингоута и др.: Пер. с англ. А.К. Ьелецкого и др.; Под ред. Е.К. Масловского. - М.: Машиностроение, 1991. - 560 с.
C.252 concurrent programming
параллельное программирование
Этот термин почти синонимичен термину параллельная обработка (P.032 parallel processing) Используется для описания как процесса создания программы, содержащей параллельно выполняемые секции, так и ее последующего выполнения.
Словарь иностранных слов. - 13-е изд., стереотип. - М.: Рус. яз., 1986. - 608 с.
КОНКУБИНАТ ...
КОНКУРЕНТ [< лат. concurriens состязающийся < concurrere сталкиваться] -тот, кто конкурирует с кем-л.
КОНКУРЕНЦИЯ [позднелат. concurrentia < concurrere сталкиваться] - 1) соперничество, борьба за достижение лучших результатов на коком-л. поприще; 2) борьба между частными товаропроизводителями за более выгодные условия производства и сбыта товаров; при капитализме - борьба между капиталистами за получение наивысшей прибыли.
КОНКУРИРОВАТЬ - соперничать, участвовать в конкуренции.
КОНКУРС ...
Но еще интереснее. Оглавления двух книг, написанных одним и тем же автором:
Уильямс Э. Параллельное программирование на С++ в действии. -М.:ДМК Пресс, 2012. - 672 с.
Уильямс Э. С++. Практика многопоточного программирования. -СПб: Питер, 2020. - 640 с.
Каша - жуткая. Но можно, ведь совсем кратко, но точно:
Параллельное программирование - это програмирование в рамках параллельной алгоритмической модели.
А дале смотрим, что это за модель. Изучать ее свойства. Сравнивать разные параллельные модели и т.д. и т.п..
Ну и откуда, видимо, "растут ноги"...
Кокурентные структуры данных
Кстати, используют мютексы ;)
Оглавления двух книг, написанных одним и тем же автором
Это два перевода одной и той же книги "C++ Concurrency in Action" (возможно, переводы сделаны по разным изданиям). К слову, в самой книге есть глава "Concurrency vs. parallelism", подсвечивающая некоторые тонкости использования этих понятий. И тут же снова отсылаю к Робу Пайку, "Concurrency is not parallelism".
Кстати, используют мютексы
Не понимаю, что из этого вообще должно следовать. Кто-то использует coarse-grained locking, кто-то использует fine-grained locking, кто-то разрабатывает алгоритмы без блокировок, это выбор реализующего структуру данных программиста.
Кстати, к слову - ну, как хотите. Мой Яндекс Переводчик переводит concurrent programming как параллельное программирование.
Апелляция к переводу на русский не доказывает ничего. Может существовать язык, в котором и термин "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 чтобы дать время на исполнение другому треду (мы предполагаем, что число тредов много больше числа ядер, а планировщик ОС стремится дать каждому из тредов время на исполнение).
Из приведённых примеров, кажется, следует, что конкурентность и параллельность друг к другу не сводимы и мы можем достаточно легко представить одно без другого.
... Это не отменяет того факта, что нам для правильного описания окружающего мира нужно два понятия: и конкурентность, и параллелизм...
А вот это вопрос? ;) Кому нужен? Мне, например, достаточно параллелизма. Но что есть параллелизм? Просто слово? Очевидно, что нет. Так что это?
Есть такой тест Тьюринга фактически на ИИ. Т.е. мы знаем слова ИИ, но не знаем, что такое ИИ. Кто-то создал нечто такое. Как понять, что он создал ИИ? В одну комнату помещаем настоящий интеллект (НИ), в другой - созданный. Если внешний наблюдатель не распознал кто где, то мы создали некий ИИ, который неотличим от НИ. Логично? Логично.
Пойдем этим же путем. В одну комнату поместим настоящий параллельный объект (НПО), в другую - искусственный (ИПО), созданный по технологии конкурентности, параллелизма или чего-то там еще (таких технологий может быть множество, как, кстати и ИИ). .
Осталось выбрать НПО и создать его искусственный аналог. Идея понятна? Если понятно - начнем...
У Вас есть кандидаты на НПО? У меня есть, но хотелось бы услышать предложение от Вас. Ну как?
А уж как назвать - думаю, договоримся? И сколько их будет, сколько будет слов, наверное, тоже ;)
За что минус, неизвестный мне друг? Поясни, будь добр?
За демагогию. Никакой ценности ваш комментарий не несет, только замусоривает тему.
Т.е. Алан Тьюринг - обычный демагог? Интересный взгляд и вывод. А Вы не исключаете, что чего-то не понимаете?
Или Вы легко можете предложить реальный объект, который может послужить основой теста на параллелизм.
Тьюриг, например, такой объект предложил - реальный человек. Улавливаете мысль? Понимаете смысл? Еще раз - "где Ваши доказательства"? :) В смысле НПО, конечно?
Кстати, тот, который Вам поставил плюсик, тоже может/должен поучаствовать в эксперименте. Как минимум два "недемагога", я так понимаю, могут продемонстрировать свою "конкретику". Или как, - слабо?
Жем-с?...
Когда по основному вопросу вам оказалось нечего сказать, вы решили съехать на другую тему. У меня есть коллега, который очень часто любит вспоминать анекдот, про «а вот если бы у нее была шерсть», на мой взгляд это как раз про вас. Ну и в целом ваш комментарий попытка манипулировать, не надо так.
Если вы считаете, что между конкурентностью и параллелизмом нет никакой разницы - напишите статью. Сообщество с удовольствием обсудит.
На этом простите - продолжать обсуждение смысла не вижу.
Про то, что конкурентность не имеет отношение к параллелизму, я написал уже не одну статью. Это про модель параллельных вычислений вообще и модель автоматного програмирования в частности. Почитайте.
Ну, а если вернуться к Тьюрингу. Я вижу Вам предложить конкретно нечего? А потому Вы, так сказать, просто сливаетесь?
Ну, а где тот, кто Вам поставил плюсик? Ау, "товарисчь"?
Или Вы легко можете предложить реальный объект, который может послужить основой теста на параллелизм.
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 допускает такой спецэффект.
Наша тестирующая система такую проблему сейчас не найдёт, поскольку она исполняет операции в рамках одного потока. В целом, проблема решаемая (например с помощью эмулирования семантики модели памяти), мы собираемся это поддержкать.
Как мы написали конкурентные структуры данных на C++ и научились их верифицировать