Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? отлаживать механизмы синхронизации нужно с самого начала работы над проектом, так как внедрить эти механизмы в уже готовый проект гораздо сложнее.
.2 Неблокирующая синхронизация
1.2.1 Общие сведения
Алгоритмы и структуры данных для неблокирующей синхронизации (в дальнейшем неблокирующие алгоритмы и структуры) частично лишены недостатков блокирующих алгоритмов и структур, однако они не являются универсальными. Самое замечательное свойство подобных алгоритмов и структур состоит в том, что они часто не требуют вообще никаких дополнительных техник параллельного программирования, то есть последовательный алгоритм, реализованный с их помощью, во многих случаях превращается в параллельный алгоритм без дополнительных усилий.
В основе лежит взаимодействие с ресурсами при помощи указателей. Учитывая эту особенно, можно создать копию ресурса по указателю, которая заведомо не будет использоваться другими потоками, изменить данные в копии и, подменив указатель, получить изменённый ресурс, а старый освободить. Однако для реализации данного алгоритма необходимо учитывать некоторые особенности, к примеру, если какой-то поток использует ресурс, то мы не можем уничтожить оригинал, а если его используют несколько потоков, то этот ресурс необходимо уничтожить только после того, как все потоки закончат с ним работать.
Эти особенности учитываются в следующих принципах:
-узлы неизменяемого типа;
-подмена указателей;
-атомарные операции;
-специальные методы управления памятью.
В простом виде неблокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.2.
Рис. 1.2 Блок-схема простого неблокирующего алгоритма
.2.2 Принципы неблокирующих алгоритмов
Узлы неизменяемого типа
Как было сказано в самом начале, изменяемость данных автоматически ведет к тому, что в некоторый промежуток времени при их изменении, данные могут быть несогласованными. Блокирующая синхронизация позволяет легко гарантировать, что посторонний процесс не получит доступа к данным во время их изменение. Но неблокирующая синхронизация по определению подразумевает, что доступ к данным любого процесса в любой момент времени должен быть гарантирован!
К счастью, существует парадигма программирования, которая позволяет гарантировать с одной стороны то, что доступ к данным в несогласованном состоянии никогда посторонним процессом получен не будет, и, с другой стороны, данные все же могут быть изменены.
Эта парадигма - использование структур данных неизменяемого (immutable) типа. Неизменяемый тип - это такой тип структуры данных, когда данные, входящие в структуру заносятся в нее (изменяются в ней) только однократно - при ее создании. Изменить данные такой структуры непосредственно нельзя, но можно:
)скопировать структуру;
)в копии задать необходимые новые значения;
)далее вместо исходной структуры использовать копию;
)оригинал уничтожить.
Чтобы выполнение третьего пункта было возможным, необходимо применить следующий принцип - подмену указателей.
До того, как рассмотреть этот принцип, необходимо отметить особенность структур данных неизменяемого типа: их использование может дорого обойтись в вычислительном плане и в плане эффективности использования памяти. Действительно, если всегда происходит изменение не самой структуры, а ее копии, то эту копию ведь еще нужно получить. Операция же копирования является довольно дорогой в вычислительном плане, и, кроме того, при работе с типами и структурами большого размера, вообще говоря, можно столкнуться даже с проблемой нехватки памяти.
Подмена указателей
Итак, после получения копии узла структуры данных, который необходимо изменить, и произведения необходимых согласно алгоритму изменений данных узла, необходимо обеспечить подмену оригинального узла его копией. Это действие производится за счет подмены указателя на оригинальный узел на указатель на копию узла. Фактически, задача изменения произвольной динамической структуры данных (сложная) подменяется на задачу изменения лишь одного указателя на эту структуру (простую). Такая подмена задачи позволяет устранить сам промежуток времени, когда изменяемые данные могут быть не согласованы, - за счет использования атомарных операций, поскольку значение указателя - адрес области памяти - это обычное число, которое можно изменить с помощью единственной процессорной инструкции.
Атомарные операции
Атомарность означает неделимость операции. Это значит, что ни один поток не может увидеть промежуточное состояние операции, она либо выполняется, либо нет. Рассмотрим пример простой операции инкрементирования значения, описанный в работе [8]:
int x = 0;
++x;
Даже такой простой код нужно синхронизировать в многопоточной среде. Если посмотреть ассемблерный код второй строки, то мы увидим, что она состоит из трех операций:
mov eax, dword ptr [x] ; загрузка текущего значения из памяти в регистр eax
add eax, 1 ; инкрементирование значения регистра eax
mov dword ptr [x], eax ; запись значения регистра eax обратно в память
Модификация встроенных C++ типов не является атомарной, то есть если два потока одновременно попытаются модифицировать переменную x, мы вполне можем получить ситуацию, где значение x станет 1 после двух инкрементов. Пример показан в таблице 1.1.
Таблица 1.1 Пример неверной модификации переменной х двумя потоками
Поток 1Поток 2исходно: x = 0прочитат