Concurrent Programming Fundamentals— Thread Safety
thread-safety or thread-safe code in Java refers to code that can safely be utilized or shared in concurrent or multi-threading environment and they will behave as expected.
Thread-safety is one of the risks introduced by using threads in Java and I have seen java programmers and developers struggling to write thread-safe code or just understanding what is thread-safe code and what is not?
How to make Thread-Safe Code in Java
Before you learn how to write a thread-safe code you need to understand what is thread-safety and there is no better way to that than looking at a non-thread-safe code. So, let’s see an example of the potential, not thread-safe code, and learn how to fix that.
Example of Non-Thread-Safe Code in Java
Here is an example of a non-thread-safe code, look at the code, and find out why this code is not thread-safe?
Example 1
The above example is not thread-safe because ++ (the increment operator) is not an atomic operation and can be broken down into reading, update, and write operations.
If multiple thread call getCount() approximately same time each of these three operations may coincide or overlap with each other for example while thread 1 is updating value, thread 2 reads and still gets old value, which eventually let thread 2 override thread 1 increment and one count is lost because multiple threads called it concurrently.
Example 2
What can happen if we use non thread-safe implementation in multi-threaded environment:
In the most general case of multi-threaded environment we shall assume that all methods will be called on random threads at random times. The implementation we used for a single-threaded environment is not safe anymore. It is not hard to imagine a flow when two distinct threads attempt to register new Observers at the same time, and end up leaving our system screwed up. One such flow could be (there are many other flows which could break non-thread-safe implementation):
- Thread A invokes registerObserver(Observer)
- Thread A executes mObservers == null check and proceeds to instantiation of a new set
- before Thread A got a chance to create a new set, OS suspended it and resumed execution of Thread B
- Thread B executes steps 1 and 2 above
- since Thread A hasn’t instantiated the set yet, Thread B instantiates a new set and stores a reference to it in mObservers
- Thread B adds an observer to the newly created set
- at some point OS resumes execution of Thread A (which was suspended right before instantiation of a new set)
- Thread A instantiates a new set and overrides the reference in mObservers
- Thread A adds an observer to the newly created set
Despite the fact that both calls to registerObserver(Observer) completed successfully, the end result is that only one observer will be notified when notifyObservers() called. It is important to understand that any of the observers could end up being “ignored”, or both observers could be registered successfully – the outcome depends on the scheduling of threads by OS which we can’t control. This non-determinism is what makes multi-threading bugs very hard to track and resolve.
How to make Thread-Safe code in Java
There are multiple ways to make this code thread-safe in Java:
1) Use the synchronized keyword in Java and lock the getCount() method so that only one thread can execute it at a time which removes the possibility of coinciding or interleaving.
2) use Atomic Integer, which makes this ++ operation atomic and since atomic operations are thread-safe and saves the cost of external synchronization.
Here is a thread-safe version of NumberCounter class in Java:
Important points about Thread-Safety in Java
Here are some points worth remembering to write thread-safe code in Java, this knowledge also helps you to avoid some serious concurrency issues in Java-like race condition or deadlock in Java:
1) Immutable objects are by default thread-safe because their state can not be modified once created. Since String is immutable in Java, it’s inherently thread-safe.
2) Read-only or final variables in Java are also thread-safe in Java.
3) Locking is one way of achieving thread-safety in Java.
4) Static variables if not synchronized properly become a major cause of thread-safety issues.
5) Example of thread-safe class in Java: Vector, Hashtable, ConcurrentHashMap, String, etc.
6) Atomic operations in Java are thread-safe like reading a 32-bit int from memory because it’s an atomic operation it can’t interleave with other threads.
7) local variables are also thread-safe because each thread has there own copy and using local variables is a good way to write thread-safe code in Java.
8) In order to avoid thread-safety issues minimize the sharing of objects between multiple threads.
9) Volatile keyword in Java can also be used to instruct thread not to cache variables and read from main memory and can also instruct JVM not to reorder or optimize code from threading perspective.
Что Thread-Safe означает в Java или когда мы называем Thread-Safe?
Быть потокобезопасным означает избежать нескольких проблем. Наиболее распространенным и, вероятно, наихудшим называется threadlock. Старая аналогия — история обеденных философов. Они очень вежливы и никогда не протянут свои палочки для еды, когда кто-то другой сделает то же самое. Если они все протянут в одно и то же время, тогда все они остановятся одновременно и ждут. и ничего не происходит, потому что они слишком вежливы, чтобы идти первым.
Как заметил кто-то другой, если ваше приложение никогда не создает дополнительные потоки, а просто запускается из основного метода, то есть только один поток или один «философ столовой», поэтому нить не может произойти. Когда у вас есть несколько потоков, самый простой способ избежать threadlock — использовать «монитор», который является просто объектом, который отложен. Фактически, ваши методы должны получить «блокировку» на этом мониторе перед доступом к потокам, так что конфликтов нет. Тем не менее, вы все равно можете иметь threadlock, потому что могут быть два объекта, пытающихся получить доступ к двум различным потокам, каждый со своим собственным монитором. Объект A должен дождаться, когда объект B отпустит его блокировку на объекте монитора 1; Объект B должен дождаться, когда объект A отпустит свою блокировку на объекте монитора 2. Итак, теперь вы вернулись к потоковому экрану.
Короче говоря, безопасность потоков не очень трудно понять, но для этого требуется время, практика и опыт. В первый раз, когда вы пишете многопоточное приложение, вы столкнетесь с threadlock. Затем вы узнаете, и это скоро станет довольно интуитивным. Самое большое предостережение в том, что вам нужно как можно проще поддерживать многопоточную часть приложения. Если у вас много потоков, с большим количеством мониторов и замков, экспоненциально сложнее обеспечить, чтобы ваши обеденные философы никогда не замерзали.
Учебник по Java очень хорошо разбирается в потоковом режиме; это был единственный ресурс, который мне когда-либо понадобился.
Что такое thread safe?
Что это такое? Я так понимаю, что переменная не меняет значения при изменении потоков? Всегда плавала в этой теме.
И какие есть способы сохранить переменную?
thread-safe ли?
Насколько я понимаю, для х32 процессоров атомарными операциями не являются те, что с double/long.
Vector и thread-safe
Как лучше сделать свой класс типа контейнер шаблонный как вектор который будет ещё и thread-safe.
Секундомер и thread-safe
В моей программе мне нужно отслеживать время по секундам. Я сделал следующее: создал доп. поток, в.
Thread-safe smart pointer
Нужно мне это для реализации COW механизма. В STL, насколько я понимаю, shared_ptr такого не.
Делаем любой объект потокобезопасным
В этих 3-ех статьях я детально расскажу об атомарных операциях, барьерах памяти и о быстром обмене данными между потоками, а так же о «sequence-points» на примере «execute-around-idiom», а заодно постараемся вместе сделать что-нибудь полезное — умный указатель, который делает любой объект потоко-безопасным для любых операций с его членами переменными или функциями. А затем покажем как используя его достичь производительности высоко-оптимизированных lock-free алгоритмов на 8 — 64 ядрах.
Три связанные статьи:
- Делаем любой объект потокобезопасным
В стандартной библиотеке C++ не существует потоко-безопасных контейнеров (array, list, map…), которые можно использовать в нескольких потоках без дополнительных блокировок. Используя стандартные контейнеры для многопоточного обмена есть опасность, что вы забудете защитить один из участков кода mutex-ом или по ошибке защитите его другим mutex-ом.
Очевидно, что разработчик совершит больше ошибок если будет использовать собственное решение, вместо стандартного. А если задача настолько сложная, что решения нет в стандарте, то разработчик решая её утонет в ошибках.
Исходя из принципа «практичность важнее безупречности» («practicality beats purity»), мы постараемся создать не идеальное, но практичное решение этой задачи.
В статье мы реализуем умный указатель, который делает любой объект потоко-безопасным, с производительностью не уступающей оптимизированным lock-free контейнерам.
Упрощенный неоптимизированный пример использования такого указателя:
На каждый шаг нашего алгоритма мы приведем цитаты из стандарта гарантирующие необходимое поведение.
Мы детально рассмотрим модель памяти C++, разные возможные варианты синхронизации и обмена данными между потоками.
Во второй статье мы реализуем оптимизированный «contention-free shared-mutex» и оптимизированный указатель на его основе contfree_safe_ptr<>. А в третей статье покажем примеры оптимального использования contfree_safe_ptr<> и приведем тесты производительности.
Начало
Начнем с разработки шаблона умного указателя safe_ptr<T>, который будет потоко-безопасен для любого типа T и покажет многопоточную производительность на уровне оптимизированных lock-free алгоритмов.
Причем, с возможностью работать атомарно и консистентно сразу над несколькими разными объектами, где даже для lock-free структур данных пришлось бы использовать блокировки и появился бы риск вечных deadlock. Но мы разработаем специальный класс блокировки мьютекса разрешающий ситуации deadlocks. Затем реализуем собственный высокопроизводительный contention-free shared-mutex, который значительно быстрее стандартного std::shared_mutex. И на его основе создадим оптимизированную версию безопасного указателя safe_ptr<T>, названную contfree_safe_ptr<>. В конце проведем тесты производительности сравнивая с lock-free библиотекой CDSlib. Мы увидим близкую производительность к CDSlib (SkipListMap и BronsonAVLTreeMap) на примере contfree_safe_ptr<std::map<>>.
В результате, чтобы сделать любой ваш класс T потоко-безопасным от вас не потребуется времени, просто пишите: contfree_safe_ptr<T> ptr_thread_safe;
А производительность окажется близкой к тому, как если бы вы месяц разрабатывали lock-free алгоритмы в методах вашего класса. К тому же будет возможность атомарно изменять сразу несколько contfree_safe_ptr<>. Так же как и std::shared_ptr<> наш умный указатель будет содержать счетчик ссылок. Он может быть скопирован, а после удаления последней копии динамически выделенная память автоматически будет освобождена.
В конце будет предоставлен 1 файл safe_ptr.h, который достаточно подключить через #include “safe_ptr.h”, чтобы вы смогли использовать данный класс.
Базовые принципы многопоточного обмена данными
Как известно, мы можем читать и изменять один и тот же объект из разных потоков только в следующих 4-х случаях:
1. Lock-based. Объект защищен блокировкой: spin-lock, std (mutex, recursive_mutex, timed_mutex, shared_timed_mutex, shared_mutex…): en.cppreference.com/mwiki/index.php?title=Special%3ASearch&search=mutex
2. Atomic. Объект имеет тип std::atomic<T>, где T – указатель, bool или интегральный тип (std::is_integral<T>::value == true), и только если для типа T существуют атомарные операции на уровне CPU: en.cppreference.com/w/cpp/atomic/atomic
2+1 (Lock-based-Atomic) Иначе, если тип T является trivially copyable type, т.е. удовлетворяют условию std::is_trivially_copyable<T>::value == true, тогда std::atomic<T> работает как Lock-based – внутри него автоматически используется блокировка
3. Transaction-safe. Функции, реализованные для работы с объектом, обеспечивают потоко-безопасную гарантию transaction_safe (Transactional Memory TS (ISO/IEC TS 19841:2015) — Experimental C++): en.cppreference.com/w/cpp/language/transactional_memory
4. Lock-free. Функции для работы с объектом реализованы на основе lock-free алгоритмов, т.е. обеспечивают потоко-безопасную гарантию lock-free
Если вы отлично знаете все 4 способа обеспечения потоко-безопасности, то можете пропустить эту главу.
Рассмотрим в обратном порядке:
(4) Lock-free алгоритмы достаточно сложные, и часто для создания каждого сложного алгоритма требуется несколько научных работ. Примеры lock-free алгоритмов для работы с контейнерами: unordered_map, ordered_map, queue… и ссылки на научные работы можно найти в библиотеке – Concurrent Data Structures (CDS) library: github.com/khizmax/libcds
Это очень быстрые и надежные многопоточные структуры данных, но пока что нет планов включать их в стандартную библиотеку C++17 или C++20 и они не включены в черновик стандартов: www.open-std.org/JTC1/SC22/WG21
(3) Transaction-safe планируется включить в экспериментальную часть стандарта C++ и уже есть черновик стандарта ISO/IEC TS 19841:2015: www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4514.pdf
Но даже не все STL-контейнеры планируется сделать transaction-safe. Например, контейнер std::map даже не планируется делать транзакционно-безопасным, т.к. для него определены как transaction-safe только следующие функции: begin, end, size, max_size, empty. Но не определены как потоко-безопасные функции: find, modify, insert. А реализовать собственный объект с transaction-safe функциями-членами совсем не легко, иначе это бы сделали для std::map.
(2) Atomic. Этот подход уже стандартизован в C++11 и вы можете легко его использовать. Например, достаточно объявить переменную std::atomic shared_val; затем передать ссылку или указатель на неё в несколько потоков и все обращения через функции-члены и операторы std::atomic будут потоко-безопасны: [3] coliru.stacked-crooked.com/a/9d0219a5cfaa3cd5
Member functions, Specialized member functions: en.cppreference.com/w/cpp/atomic/atomic
Важно понимать, что если вы делаете несколько операций над атомарной переменной, неважно в одном выражении или в нескольких, то между ними другой поток может изменить значение это переменной. Поэтому для атомарного выполнения нескольких операций используется Lock-free подход на основе CAS-функции (Compare-And-Swap) compare_exchange_weak() – а именно: считываем значение из атомарной переменной в локальную переменную (old_local_val), делаем множество нужных нам операций и результат записываем в локальную переменную (new_local_val), и в конце CAS-функцией сравниваем текущее значение атомарной переменной с начальным (old_local_val) и если они не равны, то выполняем цикл заново, а если равны – значит за это время другой поток не вносил изменений, тогда меняем значение атомарной переменной на новое значение (new_local_val). Причем сравнение и присвоение делаем одной операцией compare_exchange_weak() – это атомарная функция и пока она полностью не выполнится, никто не может изменить значение переменной: [4] coliru.stacked-crooked.com/a/aa52b45150e5eb0a
Этот подход с циклом известен под названием – оптимистическая блокировка. Пессимистическими блокировками называются: spin-lock, mutex…
А если все операции такого цикла выполняются без пессимистических блокировок, то такой алгоритм называется lock-free.
Часто атомарной CAS-функцией подменяют указатели, а именно: выделяется новая память, в неё копируется изменяемый объект и получается указатель на него, выполняется ряд действий над этой копией, и в конце CAS-функцией заменяется старый указатель на указатель нового объекта, если за это время другой поток не изменил старый указатель. Но если указатель был изменен другим потоком, то все повторяется сначала.
Здесь возможна проблема называемая «ABA». Когда другие потоки успевают дважды изменить указатель, причем второй раз указатель изменяется на исходное значение, но по этому адресу другие потоки уже успевают удалить объект и создать новый. Т.е. тоже значение указателя указывает уже на другой объект, а мы видим, что значение не изменилось и думаем, что объект не заменялся. Есть множество способов решить эту проблему, например: LL/SC, RCU, hazard_pointer, garbage collector…
Atomic — это самый быстрый способ обмена данными между потоками. Кроме того, для всех атомарных операций можно использовать менее строгие и более быстрые барьеры памяти, которые мы очень подробно рассмотрим далее. По умолчанию же используется самый безопасный и строгий барьер переупорядочивания: std::memory_order_seq_cst. Но как мы заметили выше: нужно много усилий, чтобы реализовать сложную логику используя атомарные переменные.
(2) – (1) Atomic & Lock-based.
Но если вам необходимо прочитать или изменить атомарно сразу несколько переменных std::atomic a, b, c; и вы не хотите реализовывать lock-free алгоритм и решать ABA-проблему, то необходимо использовать блокировку. Процессорная атомарная CAS-функция на большинстве CPU может проверить была ли изменена только одна переменная шириной максимум 64-bit, но в это время могла измениться уже другая переменная. Решение: std::atomic<T> позволяет использовать для T – тип структуры любого размера.
В стандарте C++ введена возможность использования любого типа T для std::atomic<T>, если он «trivially copyable type», т.е. удовлетворяет условию std::is_trivially_copyable<T>::value == true
Что говорит стандарт C++ Working Draft, Standard for Programming Language C++ N4606 2016-07-12: www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf
Но если процессорная атомарная CAS-функция может проверить была ли изменена только одна переменная шириной максимум 64-bit, а у нас 3 переменные по 32-bit, то как же сработает CAS-функция в std::atomic<T>? CAS и все остальные функции будут автоматически использовать блокировку (std::mutex или какую-то другую), которая содержится в стандартной реализации std::atomic<T>, для T – trivially copyable types.
Для атомарного изменения нескольких переменных – мы можем использовать структуру из переменных struct T < int price, count, total; >; как тип для шаблона std::atomic<T>.
Пример: [5] coliru.stacked-crooked.com/a/bdfb3dc440eb6e51
В этом примере последнее значение 70 в любой момент времени будет равно произведению первых двух значений 10*7 – т.е. вся структура меняется только атомарно.
Этот код в gcc и clang для x86 необходимо компилировать с флагом -latomic
При этом каждое обращение к std::atomic<T> shared_val; будет вызывать блокировку внутри неё, о чем говорит значение функции shared_val.is_lock_free() == false.
Т.е. глобально мы использовали оптимистическую блокировку (цикл), а локально использовали 2 пессимистические блокировки при обращении к атомарной переменной: получении старого значения и вызове CAS-функции.
(1) Lock-based.
Но мы не сможем использовать std::atomic<T> для любых типов T созданных вами из-за обязательного условия «trivially copyable» для типа T. Из всех STL-контейнеров мы можем использовать только std::array<>. Например, не можем использовать std::atomic<std::map<int, int>>, т.к. тип std::map<> не trivially copyable, для любых аргументов его шаблона. И ваши собственные классы скорее всего тоже не смогут быть использованы в качестве типа T для std::atomic<T>.
В этом случае вам придется самим создавать объекты мьютексов, блокировать их каждый раз перед использованием разделяемых (shared) объектов и разблокировать после. Concept: en.cppreference.com/w/cpp/concept/Mutex.
В C++ имеются следующие мьютексы: std::mutex, std::recursive_mutex, std::timed_mutex, std::recursive_timed_mutex, std::shared_timed_mutex, std::shared_mutex. Подробнее о них написано здесь: en.cppreference.com/w/cpp/thread.
Например, создаем любой разделяемый между потоками объект std::map<int, T> и создаем мьютекс защищающий его, затем передаем ссылки на них в несколько потоков. И в каждом потоке блокируем мьютекс перед использованием разделяемого объекта: [6] coliru.stacked-crooked.com/a/a97e905d54ae1fbb.
Причем блокируем с использованием RAII-идиомы: std::lock_guard<std::mutex> lock(mtx); – при создании этого объекта его конструктор блокирует мьютекс, а в конце жизни объекта деструктор разблокирует мьютекс. Таким образом мы точно не забудем его разблокировать, т.к. деструктор вызовется автоматически.
Но остаются ещё 4 основные проблемы:
- Взаимоблокировки (deadlocks) – если вы напишите код так, что поток-1 заблокирует mtx1, а поток-2 заблокирует mtx2, и удерживая блокировку поток-1 попробуют захватить mtx2, а поток-2 попробует захватить mtx1, то эти потоки будут ждать друг друга вечно. Этой проблемы лишены lock-free алгоритмы, но не любую логику можно реализовать с помощью lock-free – это мы покажем на примере согласованного атомарного изменения нескольких контейнеров.
- Если вы напишите код так, что пока мьютекс заблокирован вы присвоите ссылку на разделяемый объект указателю, жизнь которого дольше, чем у блокировки std::lock_guard, то после снятия блокировки вы сможете по этому указателю обратиться к разделяемому объекту – это приведет к проблеме Data races, т.е. к не консистентному состоянию разделяемого объекта и к неверной работе или к краху программы. Тоже самое будет если итератор полученный от разделяемого объекта будет использоваться после разблокировки мьютекса.
- Вы можете перепутать мьютексы и заблокировать мьютекс, который защищает другой объект – Data races.
- Вы можете просто забыть заблокировать мьютекс в нужном месте – Data races.
Execute Around Pointer Idiom
Помимо RAII-идиомы есть ещё одна интересная идиома – Execute Around Pointer, которая поможет справиться с последними двумя проблемами:
- Мьютекс будет слит с вашим объектом, и вы сможете блокировать не отдельный мьютекс, а сам ваш объект
- Мьютекс будет заблокирован автоматически при обращении к любому члену класса защищаемого объекта – причем будет заблокирован на все время выполнения выражения.
Делаем любой объект потоко-безопасным
Execute Around Pointer Idiom – это давно известная идиома со строго определенным порядком исполнения, применяемая в различных целях от визуализации до логирования: en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Execute-Around_Pointer
Пример: [7] coliru.stacked-crooked.com/a/4f3255b5473c73cc
Сначала будут созданы временные объекты типа proxy, которые заблокируют мьютексы внутри execute_around, затем в функцию будут переданы итераторы возвращенные функциями begin() и end(), затем будет исполнена функция my_accumulate(), и только после её завершения временные объекты с типом proxy будут удалены, а их деструкторы разблокируют мьютексы.
Подробнее можно прочитать в статье: C++ Patterns Executing Around Sequences. Kevlin Henney: hillside.net/europlop/HillsideEurope/Papers/ExecutingAroundSequences.pdf
В C++ есть два определения, которые строго определяют порядок выполнения операций Standard § 1.9 (13): sequenced before и sequenced after. В приведенных ниже цитатах стандарта вы 2 раза увидите «sequenced before».
Принцип и последовательность выполнения всех действий в Execute Around Pointer Idiom строго описаны в стандарте C++ Working Draft, Standard for Programming Language C++ N4606 2016-07-12: www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf
Сначала приведем пять цитат из стандарта, а затем покажем, как каждая из цитат объясняет поведение Execute Around Pointer Idiom.
1. Для всех типов T отличных от raw-pointers: x->m интерпретируется как (x.operator->())->m. Т.е. выражение (x->m) будет многократно разворачиваться ((x.operator->().operator->())->m, пока не получим raw-указатель. Пример с тремя идентичными по смыслу выражениями: [8] coliru.stacked-crooked.com/a/dda2474024b78a0b
Например, у нас есть упрощенный класс execute_around<>
И мы используем наш шаблонный класс execute_around<> следующим образом, пример:[45] coliru.stacked-crooked.com/a/d2e02b61af6459f5
Тогда последнее выражение можно через несколько преобразований привести к следующему виду.
1. Согласно 1-й цитате стандарта, x->m интерпретируется как (x.operator->())->m:
2. Т.к. vecc.operator->() возвращает временный объект T::proxy(), получаем:
3. Далее согласно цитатам 2, 3 и 4 – временные объекты типа proxy будут созданы до того, как функция начнет выполняться, и будут уничтожены после окончания функции (после окончания всего выражения):
4. Согласно снова 1-й цитате:
• tmp1->begin() эквивалентно (tmp1.operator->())->begin()
• tmp1.operator->() возвращает p
В итоге получаем, где p – это shared_ptr-указатель на наш объект типа std::vector:
За 4 шага мы описали строгую последовательность всех действий идиомы. Заметим, что стандарт не гарантирует взаимный порядок создания временных переменных tmp1 и tmp2, т.е. сначала может быть создан tmp2, а затем tmp1, но это не меняет логику нашей программы.
Заметим, что мы не обратились к 5-ой цитате стандарта, т.к. в ней описаны 3 случая, когда время удаления объекта может отличаться от приведенного, и как мы видим ни один из этих случаев не может соответствовать нашему. Первые 2 случая в цитате стандарта – это инициализация или копирование массива, они укорачивают жизнь временного объекта, а 3-й случай – это продление жизни временно объекта за счет наличия на него ссылки.
Потоко-безопасный ассоциативный массив
Согласитесь, было бы удобно иметь такой шаблонный класс safe_ptr<> в который можно передать любой тип, и как результат получить потоко-безопасный результирующий тип?
safe_ptr<std::map<std::string, std::pair<std::string, int> >> safe_map_strings;
Далее с этим объектом можно работать, как с указателем на ассоциативный массив: std::shared_ptr<std::map<std::string, std::pair<std::string, int> >>
Но теперь мы можем безопасно работать с ним из разных потоков, и каждое отельное выражение будет потоко-безопасным:
Приведем полностью рабочий пример потоко-безопасного ассоциативного: std::map<>.[9]
coliru.stacked-crooked.com/a/5def728917274b22
Отсюда 2 вывода:
- Итоговые значения равные 100000 означают, что каждое сложение в каждом из 10 потоков было выполнено потоко-безопасно. Действительно, достаточно изменить наш код, чтобы operator -> возвращал указатель на сам объект вместо типов auto_lock_t и auto_lock_obj_t , как мы увидим, что было бы если бы код НЕ был потоко-безопасным – data-race: [10] coliru.stacked-crooked.com/a/45d47bcb066adf2e
- Промежуточные значения не кратные 10000 говорят о том, что потоки исполнялись параллельно или псевдопараллельно, т.е. прерывались посреди любой из операции и в это время исполнялся другой поток. Т.е. перед каждым инкрементом operator++ блокировался мьютекс, и сразу после инкремента разблокировался, а далее мьютекс мог блокироваться другим потоком, который выполнял инкремент. Мы можем вначале каждого потока сразу заблокировать мьютекс до конца исполнения функции потока используя std::lock_guard<>, и увидим какой-бы был результат, если бы потоки исполнялись последовательно, а не псевдопараллельно: [11] coliru.stacked-crooked.com/a/cc252270fa9f7a78
Потоко-безопасность, атомарность и согласованность нескольких объектов.
Покажем, как атомарно изменять сразу несколько объектов, чтобы сохранялась их согласованность. И покажем, когда это нужно, как это сделать и что бывает если этого не сделать.
Приведем упрощенный пример, допустим у нас есть 2 таблицы:
- user_accounts(INT user_id, STRING user_name, INT money) – таблица с количеством денег для каждого клиента – отсортирована по полю user_id
- cash_flows(INT unique_id, INT src_id, INT dst_id, INT time, INT money) – таблица показывающая движение денег – на каждую запись ссылаются два ассоциативных массива, отсортированные: по полю src_id и по полю dst_id
В терминах СУБД (RDBMS):
- 1-я таблица с индексом по полю user_id – это Index-Organized-Table (Oracle) или Table with Clustered Index (MS SQL).
- 2-я таблица – это таблица с двумя упорядоченными индексами по одному полю src_id и одному полю dst_id соответственно.
Предположим от трех пользователей пришли запросы на выполнение трех задач в трех параллельных потоках:
1. move_money() – поток переводит деньги от одного клиента другому
- a) у одного клиента отнимает деньги
- b) другому клиенту прибавляет эту же сумму денег
- c) в индекс по полю id-source добавляет указатель на денежную проводку
- d) в индекс по полю id-destination добавляет указатель на эту же денежную проводку (в реальных задачах это не обязательно, но для примера мы это сделаем)
- a) В цикле проходим по каждому клиенту и суммируем все деньги
- a) incoming – суммируем все деньги, которые пришли клиенту с момента time и позднее (используя индекс по полю id-source)
- b) outcoming – суммируем все деньги, которые ушли от клиента с момента time и позднее (используя индекс по полю id-destination)
- c) user_money – получим текущие деньги у клиента
- d) user_ user_money — incoming + outcoming – это количество денег клиента на момент времени time
Поэтому мы преднамеренно добавим функции ожидания, которые уложат спать поток на несколько миллисекунд в наиболее критичных местах, чтобы сразу увидеть ошибки.
Мы сделаем потоко-безопасными наши таблицы user_accounts, cash_flows_src_id, cash_flows_dst_id используя safe_ptr<>, но станет ли от этого потоко-безопасной вся программа?
[12] coliru.stacked-crooked.com/a/5bbba59b63384a2b
Посмотрим на «основные строки» в выводе программы, помеченные <<<:
Init table safe_user_accounts:
at time = 0 <<<
1 => John Smith, 100
2 => John Rambo, 150
— start transaction… show_total_amount()
1 => John Smith, 100
2 => John Rambo, 100
Result: all accounts total_amount = 200 <<<
— start transaction… show_user_money_on_time()
1 => John Smith, 150, at time = 0 <<<
Сразу видны две ошибки:
- Изначально в сумме у всех (двух) пользователей было 250 денег, а функция show_total_amount() показала только 200, ещё 50 куда-то пропали
- На момент времени time=0 у пользователя 1 было 100 денег, а функция show_user_money_on_time() показала неверный результат – у пользователя 1 было 150 денег на момент time=0
Добавленные строки выделены желтым.
Правильный пример: [13] coliru.stacked-crooked.com/a/c8bfc7f5372dfd0c
Посмотрим на «основные строки» в выводе программы, помеченные <<<:
Init table safe_user_accounts:
at time = 0 <<<
1 => John Smith, 100
2 => John Rambo, 150
Result: all accounts total_amount = 250 <<<
Теперь все верно, сумма денег всех клиентов 250, а количество денег у клиента 1 была 100 на момент времени 0.
Т.е. мы смогли атомарно выполнить операции не с одним объектом, а сразу с 3-мя объектами, сохраняя согласованность данных для любых операций.
Но здесь возможна другая проблема. Если вы или другой разработчик в какой-то из функций заблокирует мьютексы контейнеров в другом порядке, то возможна ситуация под названием deadlock – когда 2 потока повиснут вечно ожидая друг друга.
В правильном примере выше мы блокировали мьютексы в обоих функциях move_money() и show_user_money_on_time() в одинаковом порядке:
- lock1(safe_user_accounts)
- lock2(safe_cash_flows_src_id)
- lock3(safe_cash_flows_dst_id)
- lock2(safe_cash_flows_src_id)
- lock3(safe_cash_flows_dst_id)
- lock1(safe_user_accounts)
- lock3(safe_cash_flows_dst_id)
- lock2(safe_cash_flows_src_id)
- lock1(safe_user_accounts)
Init table safe_user_accounts:
at time = 0 <<<
1 => John Smith, 100
2 => John Rambo, 150
— start transaction… move_money()
— start transaction… show_total_amount()
1 => John Smith, 100
2 => John Rambo, 150
Т.е. функции move_money() и show_user_money_on_time() не были завершены и остановились навечно в deadlock.
Решения есть 4:
1. Все разработчики во всех функциях всегда блокируют мьютексы в одном и том же порядке и никогда не ошибаются – это очень ненадежное предположение
2. Вы изначально объединяете в одну структуру все объекты, которые будут использоваться атомарно, и используете безопасный указатель с типом этой структуры struct all_t < std::map<int,int>m1; std::multimap<int,int> m2; … >; safe_ptr<all_t> safe_all_obj; – но если вы изначально использовали эти 2 контейнера только отдельно safe_ptr<map<int,int>> m1; safe_ptr<multimap<int,int>> m2; и уже написали много кода, а затем решили их объединить в одну структуру защищенную одним мьютексом, то вам придется переписать все места где их используете, например, вместо m2->at(5); необходимо safe_all_obj->m2.at(5); Переписывать много кода – это не очень удобно.
3. Вы можете один раз объединить safe_ptr<> которые используются совместно, чтобы они использовали один и тот же рекурсивный мьютекс, после чего будет неважно в каком порядке они блокируются, всегда будет сохраняться консистенность этих объектов и никогда не будет deadlock. Для этого необходимо лишь добавить 1 строчку – это очень удобно. Но это может снизить производительность, т.к. теперь блокировка одного из контейнеров всегда приводит к блокировке всех связанных с ним контейнеров. Вы получите консистентность даже тогда, когда она не нужна – ценой снижения производительности. Пример: [15] coliru.stacked-crooked.com/a/2a6f1535e0b95f7b
Все изменения в коде – это всего лишь одна строчка:
static link_safe_ptrs tmp_link(safe_user_accounts, safe_cash_flows_src_id, safe_cash_flows_dst_id);
Вывод – показаны основные строки:
Init table safe_user_accounts:
at time = 0 <<<
1 => John Smith, 100
2 => John Rambo, 150
Result: all accounts total_amount = 250 <<<
4. Вы можете использовать блокировку сразу для нескольких мьютексов разного типа с установкой времени timeout для блокировки каждого мьютекса. А если не удается заблокировать хотя бы один из мьютексов за это время, то все ранее заблокированные мьютексы разблокируются, поток ждет какое-то время и пытается по очереди заблокировать все мьютексы снова. Для этого достаточно добавить по одной строчке перед каждым использованием контейнеров lock_timed_any_infinity lock_all(safe_cash_flows_src_id, safe_cash_flows_dst_id, safe_user_accounts); и не важно в каком порядке вы будете блокировать мьютексы контейнеров. Пример: [16] coliru.stacked-crooked.com/a/93206f216ba81dd6
Т.е. даже если мы блокируем мьютексы в разных последовательностях:
- То при использовании lock_timed_any_infinity не возникает deadlock: [17] coliru.stacked-crooked.com/a/7ac7640918228090
- А в аналогичном примере при использовании lock_guard<> – возникает deadlock: [18] coliru.stacked-crooked.com/a/a281f90299771434
Компонуемость (Composable) и взаимоблокировки (Deadlocks)
Т.к. выше для потоко-безопасности мы использовали блокировки, то наши алгоритмы называются — lock-based.
А действительно ли все хорошо с отсутствием deadlocks у lock-free контейнеров, алгоритмов на основе Transactional Memory, и бывают ли deadlocks в современных СУБД: MSSQL (lock-based IL) и Oracle (multi-version concurrency control).
Алгоритмы lock-free не позволяют изменять атомарно сразу несколько контейнеров. RDBMS (РСУБД) имеют все те же проблемы с deadlock, как в lock-based алгоритмах, и часто решают их так же через таймауты блокировок или графы блокировок. А новый раздел transaction-safe в стандарте C++ не позволяет потко-безопасно использовать сложные алгоритмы такие как std::map<>.
Lock-free алгоритмы не обладают свойством Composable operations – совместного атомарного использования нескольких lock-free алгоритмов. Т.е. не могут быть изменены или прочитаны атомарно сразу несколько lock-free структур данных. Например, вы можете использовать lock-free контейнеры ассоциативных массивов из libCDS, и они по отдельности будут потоко-безопасны. Но если вы захотите атомарно выполнить операции сразу с несколькими lock-free контейнерами и сохранить консистентность, то вы не сможете этого сделать, т.к. их API не предоставляет функции lock-free операций одновременно над несколькими контейнерами. Пока вы меняете или читаете один контейнер, в это время уже будет изменен другой. Чтобы этого избежать – вам придется использовать блокировки, в этом случае это уже будут контейнеры, основанные на блокировках, а значит им станут свойственны все проблемы lock-based алгоритмов, а именно возможность проблемы взаимоблокировок (deadlocks). Кроме того, блокировки иногда используются и при использовании всего одного контейнера:
- Oracle Database Online Documentation 11g Release 1 (11.1) — Deadlocks: docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm#i5337
Блокировки Oracle: docs.oracle.com/cd/B28359_01/server.111/b28318/consist.htm#i5249
Как видно, эксклюзивные несовместимые блокировки используются любыми выражениями: Insert/Update/Delete/Select-For-Update - MSSQL Detecting and Ending Deadlocks: https://technet.microsoft.com/en-us/library/ms178104(v=sql.105).aspx
Блокировки MS SQL: https://technet.microsoft.com/en-us/library/ms186396(v=sql.105).aspx
- Lock-based алгоритмы не компонуются, если такая возможность не заложена при их реализации, но такую возможность можно реализовать, и мы успешно её реализовали в предыдущих разделах.
- Lock-free алгоритмы не компонуются и скомпоновать их без блокировок это сверх сложная задача, а с блокировками такой алгоритм уже не являются lock-free и появляется риск возникновения вечных deadlocks.
- RDBMS: MSSQL(lock-based IL) и Oracle (MVCC) – возможны вечные взаимоблокировки (deadlocks), которые снимаются через графы блокировок или таймауты
- Транзакционная память из экспериментальной части стандарта C++ – пока ограничена использованием только в самых простых алгоритмах и не позволяет использовать алгоритмы такие, как в методах std::map<> или сложнее.
- static link_safe_ptrs tmp_link(safe_user_accounts, safe_cash_flows_src_id, safe_cash_flows_dst_id); — использовать один мьютекс для нескольких контейнеров
- lock_timed_any_infinity lock_all(safe_cash_flows_src_id, safe_cash_flows_dst_id, safe_user_accounts);- использовать таймауты блокировок, а по окончании времени разблокировать всё и пытаться заблокировать заново
Компонуемость (Composable) lock-based алгоритмов
В общем случае считается, что lock-based программы не компонуемы (Composable), т.е. если просто взять 2 lock-based структуры данных и атомарно по очереди их изменить, то не получится консистентное состояние в любой момент времени.
Но выше мы легко скомпоновали три lock-based контейнера, как же нам это удалось? Есть небольшое уточнение на этот счет – выделенное жирным шрифтом:
—Tim Harris et al., «Composable Memory Transactions», Section 2: Background, pg.2[6]
www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf
Дело в том, что lock-based алгоритмы не компонуются, если такая возможность не заложена при их реализации. Т.е. lock-based структуры данных не компонуются автоматически, но их можно компоновать вручную, например, как у нас с помощью класса lock_timed_any_infinity, если снаружи есть доступ к их мьютексу для операций компоновки.
Мы реализовали lock-based шаблонный класс safe_ptr<T> и в нем для любого типа T мы предусмотрели необходимость компоноваться и разрешать (solve) deadlocks с использованием операций компоновки: link_safe_ptrs, lock_timed_any_infinity, lock_timed_any_once.