В первых двух статьях мы ознакомились с атомарными операциями, базовой техникой lock-free программирования, а также с некоторыми алгоритмами сборки мусора. Мы убедились, что разработка неблокирующих алгоритмов довольно сложна, а разработка эффективных алгоритмов вдвойне сложнee. В этой статье я хочу написать об очень важной составляющей процесса разработки программ – о тестировании и отладке. Отладка многопоточных программ (а тем более неблокирующих) занятие не из простых. Те, кто хоть раз отлаживал сложную систему, знают, как сложно найти ошибку в программе, если ошибка не воспроизводится. Ошибки, возникшие в условиях высокой нагрузки очень сложно воспроизвести в режиме отладки, когда нагрузка отсутствует. Чтобы попадать в подобные ситуации как можно реже, желательно тестировать каждый модуль в отдельности и под высокой нагрузкой с помощью unit-test - ов и в этой статье мы рассмотрим инструмент, предназначенный для тестирования алгоритмов синхронизации, написанных на C++0x.
Relacy Race Detector
Инструмент, автором которого является Dmitriy Vyukov, представляет собой набор заголовочных файлов C++, предоставляющих интерфейс, похожий на интерфейс библиотеки C++ threading library из стандарта C++0x. Он симулирует указанное количество потоков и позволяет выявить race condition, проблемы переупорядочения, попытки обращения к удаленным участкам памяти, и так далее... Рассмотрим несколько нюансов работы с relacy race detector.relacy/relacy_std.hpp – единственный заголовочный файл из библиотеки, который нужно включать в программу.
Для атомарных типов используется шаблонный класс std::atomic<T>.
Например:
std::atomic<node*> head; std::atomic<int> count;Обычные (не атомарные), но shared переменные должны быть обернуты в шаблонный класс rl::var<Т>, эти переменные будут участвовать в проверке на race condition.
Доступы к атомарным переменным типа std::atomic<T> и rl::var<T> должны иметь суффикс ($).
Например:
head($).load(); count($).store(0);Проверки состояния программы совершаются с помощью макроса RL_ASSERT.
Тесты пишутся в классе/структуре, наследуемой от шаблонной структуры rl::test_suite, в которую в виде шаблонных параметров передается тип наследуемого класса (CRTP) и количество потоков для симуляции. Каждый поток запускает функцию thread наследуемой структуры, передавая ему в качестве аргумента свой последовательный идентификатор. Также структура может содержать функции before и after для инициализации и пост-проверок состояние программы.
struct test: rl::test_suite<test, 2> { void before() {} void after() {} void thread(unsigned index) {} };Запуск симуляции происходит в функции main вызовом функции rl::simulate
rl::test_params params;
rl::simulate<test>(params);
rl::test_params params; rl::simulate<test>(params);Параметры можно не передавать, тогда симуляция будет запущена с параметрами по умолчанию.
Ну что же, посмотрим на него в деле. Для начала напишет самый просто тест, тест на инкремент не атомарной переменной из двух потоков – т.е. тест на race condition.
#include "relacy/relacy_std.hpp" struct data_race_test : rl::test_suite<data_race_test, 2> { rl::var<int> x; void before() { x($) = 0; } void thread(unsigned) { x($)++; } }; int main() { rl::simulate<data_race_test>(); }Сначала мы инициализируем переменную x, а потом пытаемся ее модифицировать одновременно из двух потоков. Поскольку переменная x не атомарна, здесь имеет место быть проблематичный race condition.
Теперь исходник надо откомпилировать, передав компилятору путь к директории relacy, и запустить.
5test1 DATA RACE (data race detected) iteration: 1 execution history (10): [0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419) [2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [3] 1: <0x76d8160> store, value=0, in before, main.cpp(9) [4] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419) [5] 1: <0x76d8160> load, value=0, in thread, main.cpp(13) [6] 1: <0x76d8160> store, value=1, in thread, main.cpp(13) [7] 1: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419) [8] 0: <0x76d8160> load, value=0, in thread, main.cpp(13) [9] 0: DATA RACE (data race detected), in thread, main.cpp(13) thread 0: [8] 0: <0x76d8160> load, value=0, in thread, main.cpp(13) [9] 0: DATA RACE (data race detected), in thread, main.cpp(13) thread 1: [0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419) [2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [3] 1: <0x76d8160> store, value=0, in before, main.cpp(9) [4] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419) [5] 1: <0x76d8160> load, value=0, in thread, main.cpp(13) [6] 1: <0x76d8160> store, value=1, in thread, main.cpp(13) [7] 1: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419)Отлично! Мы нашли ошибку в самом начале и сэкономили кому-то (скорее всего самому себе) множество часов кропотливой работы. Исправим код так, чтобы избавиться от этой проблемы и запустим тест заново. Изменим тип переменной x и сделаем ее атомарной.
#include "relacy/relacy_std.hpp" struct data_race_test : rl::test_suite<data_race_test, 2> { std::atomic<int> x; void before() { x($) = 0; } void thread(unsigned) { x($)++; } }; int main() { rl::simulate<data_race_test>(); }Теперь осталось откомпилировать и запустить.
5test1 iterations: 1000 total time: 10 throughput: 100000Все отлично, тест прошел успешно, можно конечно добавить количество итераций и оставить его работать на ночь, но в данном случае в этом нет необходимости. Идем дальше.
Усложним задачу.
Как уже говорилось в первой части статьи, все операции с атомарными переменными по умолчанию являются последовательно-консистентными (sequentially consistent), и хотя широко используемые процессорные архитектуры (x86-64) предоставляют последовательную консистентность без особых потерь, на других процессорах это может значительно повлиять на производительность.
Вспомним статью про барьеры памяти и проверим пример, приведенный там.
void func_on_cpu1() { a = 1; b = 1; } void func_on_cpu2() { while (b == 0); assert(a == 1); }Перепишем его на C++0x и напишем для него unit-test. Разумеется переменные a и b должны быть атомарными, но для воспроизведения проблемы, все операции с ними не должны содержать никаких барьеров и не должны быть последовательно-консистентными. Для этого, вместо memory_order_seq_cst, который передается по умолчанию, мы передаем в функции store и load параметр rl::memory_order_relaxed (std::memory_order_relaxed в C++0x), принуждая тем самым компилятор “расслабить” данную операцию.
#include "relacy/relacy_std.hpp" struct ordering_test : rl::test_suite<ordering_test, 2> { std::atomic<int> a; std::atomic<int> b; void before() { a($).store(0); b($).store(0); } void thread(unsigned index) { if (index == 0) { a.store(1, rl::memory_order_relaxed); b.store(1, rl::memory_order_relaxed); } else { while (b.load(rl::memory_order_relaxed) == 0); RL_ASSERT(a.load(rl::memory_order_relaxed) == 1); } } }; int main() { rl::simulate<ordering_test>(); }Осталось откомпилировать и запустить .
13ordering_test USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1) iteration: 5 execution history (14): [0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419) [2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [3] 1: <0x13610250> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(10) [4] 1: <0x13610278> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(11) [5] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419) [6] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22) [7] 0: <0x13610250> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(18) [8] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22) [9] 0: <0x13610278> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(19) [10] 0: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419) [11] 1: <0x13610278> atomic load, value=1, order=relaxed, in thread, main.cpp(22) [12] 1: <0x13610250> atomic load, value=0 [NOT CURRENT], order=relaxed, in thread, main.cpp(23) [13] 1: USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1), in thread, main.cpp(23) thread 0: [7] 0: <0x13610250> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(18) [9] 0: <0x13610278> atomic store, value=1, (prev value=0), order=relaxed, in thread, main.cpp(19) [10] 0: [THREAD FINISHED], in fiber_proc_impl, relacy/context.hpp(419) thread 1: [0] 1: [CTOR BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [1] 1: [CTOR END], in fiber_proc_impl, relacy/context.hpp(419) [2] 1: [BEFORE BEGIN], in fiber_proc_impl, relacy/context.hpp(419) [3] 1: <0x13610250> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(10) [4] 1: <0x13610278> atomic store, value=0, (prev value=0), order=seq_cst, in before, main.cpp(11) [5] 1: [BEFORE END], in fiber_proc_impl, relacy/context.hpp(419) [6] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22) [8] 1: <0x13610278> atomic load, value=0, order=relaxed, in thread, main.cpp(22) [11] 1: <0x13610278> atomic load, value=1, order=relaxed, in thread, main.cpp(22) [12] 1: <0x13610250> atomic load, value=0 [NOT CURRENT], order=relaxed, in thread, main.cpp(23) [13] 1: USER ASSERT FAILED (assertion: a.load(rl::memory_order_relaxed) == 1), in thread, main.cpp(23)Отлично! Мы опять выявили проблему. Теперь попытаемся ее исправить так, как описано в статье барьеры памяти, т.е. установим барьер записи (release) в первом потоке и барьер чтения (acquire) во втором. Для этого мы заменяем rl::memory_order_relaxed на rl::memory_order_release в первом, и на rl::memory_order_acquire во втором.
void thread(unsigned index) { if (index == 0) { a.store(1, rl::memory_order_relaxed); b.store(1, rl::memory_order_release); } else { while (b.load(rl::memory_order_acquire) == 0); RL_ASSERT(a.load(rl::memory_order_relaxed) == 1); } }Теперь компилируем и запускаем
13ordering_test iterations: 1000 total time: 10 throughput: 100000Вот и все, тест пройден.
Пользуйтесь unit-test – ами как можно чаще. Выявление ошибок синхронизации на этапе написания кода сэкономят много времени и сил. И не забывайте про code-review, ведь самому сложно замечать свои же ошибки.
Скачать инструмент relacy race detector, а также задать вопрос автору и посмотреть примеры использования можно по адресу http://groups.google.com/group/relacy/web.
0 comments:
Отправить комментарий