Разработка структур данных с дисциплиной доступа один пишет — много читают для многопоточного взаимодействия в системах реального времени

Глава 1. Обзор методов и средств многопоточного взаимодействия

1.1 Блокирующая синхронизация

1.2 Неблокирующая синхронизация

1.2.1 Общие сведения

1.2.2 Принципы неблокирующих алгоритмов

1.2.3 Обзор специальных методов управления памятью

1.2.4 Оценка эффективности методов

1.2.5 Типы алгоритмов для неблокирующей синхронизации

1.3 Выводы

Глава 2. Разработка структуры и алгоритмов взаимодействия

2.1 Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации

2.2 Обзор существующих неблокирующих структур

2.3 Разработка структуры данных

2.4 Разработка алгоритмов

2.4.1 Алгоритм записи

2.4.2 Алгоритм чтения

2.4.3 Алгоритм освобождения памяти

2.4.4 Алгоритм добавления и удаления опасных указателей

Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия

3.1 Особенности программной реализации

3.2 Тестирование разработанных алгоритмов

3.3 Тестирование разработанной структуры при многопоточном доступе

3.4 Сравнение структур по временным характеристикам

Заключение

Многопоточность — свойство платформы, например, операционной системы, виртуальной машины, или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких исполнительных потоков, выполняющихся «параллельно». Она увеличивает производительность процесса за счет распараллеливания вычислительных операций и/или операций ввода/вывода при наличии нескольких задач, которые могут (хотя бы частично) работать одновременно на соответствующей платформе. Код правильно написанного многопоточного приложения выглядит просто, потому что каждый поток выполняет свою конкретную задачу. Однако в многопоточной среде часто возникают проблемы, связанные с использованием параллельно исполняемыми потоками одних и тех же данных или устройств. Для решения подобных проблем используются различные методы синхронизации потоков. Все они имеют свои положительные и отрицательные стороны, основным критерием их оценки является время, затрачиваемое для выполнения операций, обеспечивающих отсутствие конфликтов между потоками, непредсказуемых результатов, а также координированное выполнение взаимозависимого кода для обеспечения правильной последовательности событий, причём это время может варьироваться на разных итерациях. В связи с этим в системах реального времени проблема многопоточного доступа к общим данным стоит наиболее остро, так как данная система либо не должна опаздывать с реакцией на событие (операционной системой мягкого реального времени), либо никогда не опоздает с реакцией на событие (система жёсткого реального времени).

В данной работе будут рассмотрены возможные варианты многопоточного доступа к данным, выбраны и реализованы методы синхронизации, удовлетворяющие поставленной задаче, которые в дальнейшем можно будет использовать в системах реального времени.

Глава 1. Обзор методов и средств многопоточного взаимодействия

Работа с изменяемыми типами и структурами подразумевает выполнение таких операций, как чтение и модификация данных соответствующих объектов. Если используется только операция чтения, то есть, если типы и структуры, с которыми производится работа, имеют постоянные значения, никаких проблем с параллельным доступом к ним не возникает. Доступ к таким данным может производиться из множества потоков без всякой их синхронизации. Однако, другое дело, если работа производится с данными, которые могут изменяться: с момента начала операции модификации и вплоть до ее окончания, структура может находиться в несогласованном состоянии. Если теперь в этом промежутке времени будет произведена операция чтения, то она вернет неверное значение. Существует два решения проблемы: блокирующая и неблокирующая синхронизация.

1.1 Блокирующая синхронизация

Традиционные алгоритмы синхронизации в многопоточной среде, как известно, основаны на механизме блокировок. В момент времени до начала операции доступ к структуре для потоков, отличных от потока, получившего монопольный доступ, блокируется, далее — производится необходимое изменение, и, наконец, доступ для других потоков вновь разрешается. Таким образом, гарантируется целостность структуры данных. В простом виде блокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.1.

Рис. 1.1 Блок-схема простого алгоритма с блокировкой

Блокировки являются мощным средством синхронизации действий в многопоточной среде, которое может обеспечить синхронизацию любых сложных структур. Но, как и все мощное, эта это средство таит в себе множество недостатков, например:

— они являются довольно медленными операциями и требуют много ресурсов;

— они являются узким местом программы, поскольку с ресурсом, на котором установлена блокировка, может работать только заблокировавший его процесс, и в связи с этим процесс с низким приоритетом может заблокировать на неопределенное время другой процесс, с более высоким приоритетом;

— они подвержены проблеме взаимных блокировок, отладка же взаимных блокировок бывает чрезвычайно сложна, поскольку возникает при определенных специфических условиях;

— использование блокирующих механизмов синхронизации подразумевает применение особой техники программирования, и внедрять и отлаживать механизмы синхронизации нужно с самого начала работы над проектом, так как внедрить эти механизмы в уже готовый проект гораздо сложнее.

1.2 Неблокирующая синхронизация

1.2.1 Общие сведения

Алгоритмы и структуры данных для неблокирующей синхронизации (в дальнейшем неблокирующие алгоритмы и структуры) частично лишены недостатков блокирующих алгоритмов и структур, однако они не являются универсальными. Самое замечательное свойство подобных алгоритмов и структур состоит в том, что они часто не требуют вообще никаких дополнительных техник параллельного программирования, то есть последовательный алгоритм, реализованный с их помощью, во многих случаях превращается в параллельный алгоритм без дополнительных усилий.

В основе лежит взаимодействие с ресурсами при помощи указателей. Учитывая эту особенно, можно создать копию ресурса по указателю, которая заведомо не будет использоваться другими потоками, изменить данные в копии и, подменив указатель, получить изменённый ресурс, а старый освободить. Однако для реализации данного алгоритма необходимо учитывать некоторые особенности, к примеру, если какой-то поток использует ресурс, то мы не можем уничтожить оригинал, а если его используют несколько потоков, то этот ресурс необходимо уничтожить только после того, как все потоки закончат с ним работать.

Эти особенности учитываются в следующих принципах:

— узлы неизменяемого типа;

— подмена указателей;

— атомарные операции;

— специальные методы управления памятью.

В простом виде неблокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.2.

Рис. 1.2 Блок-схема простого неблокирующего алгоритма

1.2.2 Принципы неблокирующих алгоритмов

Узлы неизменяемого типа

Как было сказано в самом начале, изменяемость данных автоматически ведет к тому, что в некоторый промежуток времени при их изменении, данные могут быть несогласованными. Блокирующая синхронизация позволяет легко гарантировать, что посторонний процесс не получит доступа к данным во время их изменение. Но неблокирующая синхронизация по определению подразумевает, что доступ к данным любого процесса в любой момент времени должен быть гарантирован!

К счастью, существует парадигма программирования, которая позволяет гарантировать с одной стороны то, что доступ к данным в несогласованном состоянии никогда посторонним процессом получен не будет, и, с другой стороны, данные все же могут быть изменены.

Эта парадигма — использование структур данных неизменяемого (immutable) типа. Неизменяемый тип — это такой тип структуры данных, когда данные, входящие в структуру заносятся в нее (изменяются в ней) только однократно — при ее создании. Изменить данные такой структуры непосредственно нельзя, но можно:

1) скопировать структуру;

2) в копии задать необходимые новые значения;

3) далее вместо исходной структуры использовать копию;

4) оригинал уничтожить.

Чтобы выполнение третьего пункта было возможным, необходимо применить следующий принцип — подмену указателей.

До того, как рассмотреть этот принцип, необходимо отметить особенность структур данных неизменяемого типа: их использование может дорого обойтись в вычислительном плане и в плане эффективности использования памяти. Действительно, если всегда происходит изменение не самой структуры, а ее копии, то эту копию ведь еще нужно получить. Операция же копирования является довольно дорогой в вычислительном плане, и, кроме того, при работе с типами и структурами большого размера, вообще говоря, можно столкнуться даже с проблемой нехватки памяти.

Подмена указателей

Итак, после получения копии узла структуры данных, который необходимо изменить, и произведения необходимых согласно алгоритму изменений данных узла, необходимо обеспечить подмену оригинального узла его копией. Это действие производится за счет подмены указателя на оригинальный узел на указатель на копию узла. Фактически, задача изменения произвольной динамической структуры данных (сложная) подменяется на задачу изменения лишь одного указателя на эту структуру (простую). Такая подмена задачи позволяет устранить сам промежуток времени, когда изменяемые данные могут быть не согласованы, — за счет использования атомарных операций, поскольку значение указателя — адрес области памяти — это обычное число, которое можно изменить с помощью единственной процессорной инструкции.

Атомарные операции

Атомарность означает неделимость операции. Это значит, что ни один поток не может увидеть промежуточное состояние операции, она либо выполняется, либо нет. Рассмотрим пример простой операции инкрементирования значения, описанный в работе [8]:

1 int x = 0;

2 ++x;

Даже такой простой код нужно синхронизировать в многопоточной среде. Если посмотреть ассемблерный код второй строки, то мы увидим, что она состоит из трех операций:

1 mov eax, dword ptr [x]; загрузка текущего значения из памяти в регистр eax

2 add eax, 1; инкрементирование значения регистра eax

3 mov dword ptr [x], eax; запись значения регистра eax обратно в память

Модификация встроенных C++ типов не является атомарной, то есть если два потока одновременно попытаются модифицировать переменную x, мы вполне можем получить ситуацию, где значение x станет 1 после двух инкрементов. Пример показан в таблице 1.1.

Таблица 1.1 Пример неверной модификации переменной х двумя потоками

Ситуации подобные этой, в которых финальный результат зависит от очередности выполнения, называется data race. Можно исправить этот код и сделать его потокобезопасным добавив блокировку перед инкрементом и разблокировку после него, тем самым обеспечивая атомарность операции инкрементирования, но существует другой способ.

Некоторые операции, в том числе и операции чтения и записи, являются достаточно простыми и могут быть выполнены процессором атомарно, то есть он может реализовать их в виде специальных инструкций на аппаратном уровне. Поэтому, для того чтобы подменить оригинал узла на его измененную копию, применяется операция подмены указателя, в простейшем случае, используя обычную атомарную операцию записи. Однако неблокирующие алгоритмы более-менее сложных структур требуют наличия и более сложных атомарных операций.

В связи с этим, кроме атомарных операций чтения и записи, в число атомарных примитивов также должна входить такая операция, как сравнение с обменом или compare-and-swap (CAS), также известная, как compare exchange, или пара операций загрузка с пометкой/попытка записи или load linked/store conditional (LL/SC). Суть операции сравнение с обменом заключается в том, что она атомарно сравнивает значение одного объекта с другим и при удачном сравнении заменяет значение объекта. CAS принимает три аргумента: адрес области памяти, ожидаемое значение по этому адресу и вновь записываемое значение. Если и только если область памяти содержит ожидаемое значение, по этому адресу записывается новое значение. Операцией возвращается булево значение, определяющее произошла ли перезапись значения или нет. Иными словами, CAS (address, expected, new) атомарно выполняет следующую операцию (в псевдокоде):

Суть пары операций загрузка с пометкой/попытка записи аналогична сути операции CAS: LL атомарно сравнивает значение одного объекта с другим и при удачном сравнении SCзаменяет значение объекта. LL принимает один аргумент: адрес области памяти и возвращает ее содержимое. SC принимает два аргумента: адрес области памяти и новое значение. Если ни один другой поток не перезаписывал область памяти по адресу после того, как данный поток считал ее значение с помощью LL, только тогда по этому адресу записывается новое значение. Операция возвращает булево значение, определяющее произошла ли перезапись значения. Дополнительная инструкция validate (VL) принимает один аргумент: адрес области памяти, и возвращает булево значение, определяющее, происходила ли перезапись области памяти со стороны других потоков с того момента времени, как данный поток выполнил LL.

Большинство современных широко распространенных процессорных архитектур поддерживает либо CAS, либо пару LL/SC на выровненных однословных операндах. В некоторых 32-разрядных системах эти операции доступны и для двухсловных операндов (то есть доступна поддержка 64-разрядных инструкций), но на 64-битных архитектурах поддержки операций над двухсловными операндами нет (то есть 128-битные инструкции не поддерживаются). Пара LL/SC обычно используется в RISC-архитектурах (DEC Alpha, MIPS, PowerPC, ARM), тогда как на архитектурах x86 используется CAS в различных ее вариациях.

CAS легко выразить через пару LL/SC следующим образом:

Более подробное описание операций можно найти в работах [2,4].

Специальные методы управления памятью

Помимо проблемы образования несогласованных данных, которая решается вышеописанными принципами неблокирующего программирования, при разработке неблокирующих алгоритмов для работы с динамическими структурами возникает более сложная проблема: проблема управления освобождением памяти узлов или их повторного использования.

Главную заботу при работе с неблокирующими структурами представляет проблема освобождения памяти, занимаемой удаляемыми узлами. В случае работы со структурой, основанной на блокировках, легко гарантировать, что когда некий поток удаляет узел из динамической структуры, никакой другой поток впоследствии не обратится к памяти этого узла, до тех пор, пока она не будет заново перераспределена. В результате, для удаляющего потока обычно является вполне безопасным освобождение памяти, занимаемой узлом (например, с помощью delete) для последующего произвольного ее выделения в другом потоке (например, с помощью new).

В случае работы с типичной неблокирующей динамической структурой в многопоточной среде без поддержки автоматического сбора мусора это не так. Ведь для того, чтобы гарантировать прогресс выполнения операции, каждый поток должен иметь неограниченную возможность оперировать объектом в любой момент времени. Когда некий поток удаляет узел, является вполне возможным, что некий другой соперничающий поток уже ранее уже получил ссылку на этот узел и готовится получить доступ к его содержимому. Если удаляющий поток освободит память удаляемого узла для дальнейшего ее перераспределения, соперничающий поток в дальнейшем может либо повредить содержимое некоей другой структуры, которая займет место удаленного узла, либо вернуть неверный результат, либо пострадать от ошибки доступа к памяти. Более того, если перераспределенная память возвращена операционной системе, доступ к ней может повлечь еще более тяжкие последствия. Проще говоря, задача освобождения памяти в данном случае состоит в том, чтобы иметь возможность освобождать память удаляемых узлов (для дальнейшего перераспределения или возврата ОС), гарантируя невозможность доступа к ней других потоков, неблокирующим образом.

Есть несколько способов, которые применяются в различных системах с целью выполнения этой задачи:

— Метод использования специальных тэгов (счетчиков изменений) памяти, основывающийся на ассоциировании специального тега с каждым адресом памяти, который может быть использован в операции;

— Метод неблокирующего подсчета ссылок, основывающийся на включении в структуру динамического узла специального счётчика ссылок;

— Метод использования агрегатных счетчиков ссылок или поточных временных штампов, основывающийся на наличии специального планировщика и являющийся блокирующим без него (именно поэтому в дальнейшем данный метод не рассматривается, ввиду отсутствия такого планировщика), то есть ошибка или задержка хотя бы одного потока в данном методе может воспрепятствовать достижению нуля агрегатным счетчиком ссылок или обновлению временного штампа и, следовательно, воспрепятствовать перераспределению памяти;

— Метод опасных указателей, основывающийся на ассоциировании с каждым потоком, который должен работать со структурами, некоторого числа (обычно один или два) указателей с типом доступа один писатель — много читателей.

Также существует другая связанная с повторным использованием памяти проблема — это так называемая проблема ABA. Ее наличие влияет практически на все неблокирующие алгоритмы. Проблема эта обнаруживается тогда, когда поток читает значение A из некоей разделяемой области памяти, далее другой поток изменяет значение в этой области памяти на B, после чего снова на A. Позднее, когда первый поток проверяет, не изменилось ли значение, например, с помощью CAS, сравнение с сохраненным значением возвращает истину (то есть не изменилось). И поток продолжает выполнение далее, ошибочно считая, что значение не изменялось с момента первого чтения. В результате, поток может повредить структуру данных или вернуть неверный результат, поскольку другой поток мог произвести другие, скрытые изменения, которые первый поток просто не обнаружит.

Проблема ABA является фундаментальной, и должна быть устранена вне зависимости от способа обеспечения повторного использования памяти. Однако методы обеспечения повторного использования памяти (например, сборка мусора или garbage collection (GC)) часто предотвращают возникновение этой проблемы в качестве побочного эффекта, так сказать, без каких бы то ни было дополнительных затрат, но, к сожалению, в некоторых языках нет сборщика мусора.

1.2.3 Обзор специальных методов управления памятью

Метод использования специальных тегов

Метод использования специальных тегов (счетчиков изменений) является самым ранним и наиболее простым неблокирующим методом повторного использования памяти узлов. Он требует, чтобы с каждым адресом памяти, который может быть использован в операции сравнения с ожидаемым значением, подверженной ABA-проблеме, был ассоциирован специальный тег. Увеличение значение тега в момент, когда происходит запись значения по соответствующему адресу, позволяет операциям сравнения (например, CAS) определить, было ли произведено изменение с момента последнего чтения значения тем же потоком. Таким образом, проблема ABA устраняется. Данный метод требует, чтобы тег имел достаточную разрядность для того, чтобы полный цикл инкрементации был невозможен за время выполнения любой единичной неблокирующей операции. Этот метод очень эффективен и позволяет немедленное освобождение памяти узлов или их повторное использование.

Однако его недостаток заключается в том, что для применения к произвольным указателям, как в случае с объектами динамического размера, он требует наличия инструкций двойной разрядности DCAS (Double-CAS, подробнее — в работе [3]), которые выполняют CAS для двух независимых областей памяти, что дает возможность выполнять атомарные операции как с указателем, так и с его ассоциированным тегом. Эти инструкции совсем не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Кроме того, семантика тегового поля должна сохраняться постоянно. Таким образом, если тег является частью динамической структуры узлов, повторное использование таких узлов затрудняется. Их память не может быть поделена или объединена, поскольку это может привести к изменению семантики теговых полей. Это значит, то коль скоро некая область памяти была использована для определенного типа узлов, она не может уже быть повторно использована для другого типа узлов, которые не сохраняют семантику теговых полей. Таким образом, данный метод является, по сути, аппаратным решением, в связи с чем от его дальнейшего рассмотрения приходится отказаться.

Метод неблокирующего подсчета ссылок

Метод неблокирующего подсчета ссылок, описанный в работе [1], требует включения в структуру динамического узла специального счетчика ссылок, отражающего текущее число ссылок на данный узел структуры и локальных переменных потоков, оперирующих данной структурой. Каждый раз, когда получается, либо удаляется новая ссылка на динамический узел, счетчик ссылок должен быть увеличен, либо уменьшен, используя инструкцию fetch-and-addилиcompare-and-swap. Только в том случае, если счетчик ссылок равен нулю, узел может быть повторно использован.

Как и в случае метода специальных тегов (счетчиков изменений), методу неблокирующего подсчёта ссылок требуется наличие операции DCAS для атомарного манипулирования одновременно указателями и счетчиками ссылок, которая не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Используя такую операцию можно гарантировать, что счетчик ссылок никогда не будет иметь значение, меньшее реального числа ссылок. Однако возможна реализация, в которой манипулирование указателями и, одновременно, независимо расположенными счетчиками ссылок одноадресной операцией CAS производится в неатомарном режиме, но в таком случае могут произойти следующие ситуации:

1) Если поток вначале увеличивает счётчик ссылок, а потом получает указатель, то может получиться, что в промежуток между этими двумя операциями другой поток уже изменил указатель. В результате первый поток получает уже другой указатель, а в памяти остается структура, которая не будет удалена, так как счётчик ссылок будет равен минимум единице.

2) Если поток вначале получает указатель, а потом увеличивает счётчик, то может получиться, что в промежуток времени между этими двумя операциями другой поток уже удалил структуру, указатель на которую получил первый поток. В результате первый поток получит ошибку при попытке увеличить указатель или увеличит какие-то неизвестные данные, что приведёт либо к ошибке, либо к тому, что потоки будут работать с некорректными данными.

В связи с этим необходимы дополнительные проверки корректности счётчиков и указателей.

Метод опасных указателей

Метод опасных указателей, описанный в работах [4,5], является относительно новым подходом к решению данной задачи. В отличие от остальных специальных методов управления памятью он не требует никаких дополнительных методов, например, сборки мусори (garbage collection), а также его можно использовать в качестве решения проблемы повторного использования памяти в неблокирующих алгоритмах, которые написаны для систем со сборкой мусора, в системах без сборки мусора.

Основная идея этого метода заключается в том, чтобы ассоциировать с каждым потоком, который должен работать с неблокирующими структурами, некоторое число (обычно один или два) указателей с дисциплиной доступа один пишет — много читают, так же называемых опасными указателями или hazard pointers. Указатель опасности либо равен нулю, либо указывает на узел, доступ к которому позднее может потребоваться без дополнительного подтверждения того, что ссылка на узел еще допустима. Каждый опасный указатель может быть переписан только его потоком-владельцем, но прочитан может быть любым потоком.

Метод опасных указателей гарантирует, что никакой поток не получит доступ к динамическому узлу в то время, как он может быть удален из структуры, если ни один из ассоциированных с потоками опасных указателей не указывал на него начиная с того момента времени, когда достижимость узла из корня структуры была гарантирована. Кроме того данный метод предотвращает освобождение памяти любого выбывшего узла, на который указывал хотя бы один указатель опасности одного или нескольких потоков, начиная с момента времени, предшествовавшего его удалению.

Стоит отметить, что даже малого числа указателей опасности ассоциированных с каждым потоком хватает для поддержки произвольного числа структур данных или объектов, если этого числа достаточно для работы с каждой структурой или объектом в отдельности. Например, в программе, где каждый поток может произвольно оперировать сотнями разделяемых объектов, каждому из которых требует не более двух указателей опасности на поток (например, хэш-таблицы, FIFO очереди, LIFO стеки, связные списки), программе всего требуется лишь два указателя опасности на поток.

1.2.4 Оценка эффективности методов

В работе приводятся данные, отражающие относительную эффективность методологии указателей опасности по сравнению с другими методологиями управления освобождением и повторным использованием памяти в неблокирующих алгоритмах, а так же их общую эффективность, по сравнению с блокирующими алгоритмами.

Эти данные приводятся ниже. Из них можно увидеть, что производительность метода опасных указателей во всех тестах практически идентична производительности метода счетчиков изменений (специальных тегов), при том, что последний, по существу, является аппаратным решением. Так же видно, что чем больший вычислительный параллелизм возможен в системе, тем лучше себя показывает метод указателей опасности, в сравнении с остальными методами. На рис. 1.3 представлена производительность FIFO очередей при различных методах управления освобождением памяти и повторным использованием узлов.

Рис. 1.3 Производительность FIFO очередей

На рис. 1.4 представлена производительность LIFO стеков.

Рис. 1.4 Производительность LIFO стеков

На рис. 1.5 и 1.6 представлены производительности различных методов при реализации хеш-таблиц методом цепочек. На них отображены данные для коэффициентов загрузки 1 и 5 соответственно.

Рис. 1.5 Производительность хеш-таблиц с параметром загрузки 1

Рис. 1.6 Производительность хеш-таблиц с параметром загрузки 5

1.2.5 Типы алгоритмов для неблокирующей синхронизации

В работах [2,10] приводятся описания трёх типов алгоритмов для неблокирующей синхронизации.

Wait-free

Wait-free алгоритмом или алгоритмом без ожидания называется такой алгоритм, который гарантирует, что каждая операция, выполняемая потоком согласно этому алгоритму, будет выполнена за определенное известное число шагов, не зависимо от других потоков.

Каждый поток продвигается вперед не зависимо от внешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы, как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. Такие примитивы, как atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, так как с ним обычно связан цикл вида «выполнять atomic_compare_exchange, пока он не будет выполнен успешно».

Пример wait-free алгоритма:

void increment_reference_counter (rc_base* obj)

{

atomic_increment (obj->rc);

}

void decrement_reference_counter (rc_base* obj)

{

if (0 == atomic_decrement (obj->rc))

delete obj;

}

Как видно, любой поток может выполнить эти функции за конечное число шагов, не зависимо ни от чего, однако нет никаких гарантий, что результатом выполнения данного алгоритма будут ожидаемые данные, так как используемые примитивы гарантируют отсутствие конфликтов между двумя вызовами, но не предотвращают возникновение некорректных данных.

Lock-free

Lock-free алгоритмом или алгоритмом без блокировок называется такой алгоритм, который гарантирует, что в течении времени, за которое некий программный поток выполнит некое известное ограниченное число шагов в операции над таким объектом или структурой, некий, возможно, другой поток обязательно завершит операцию над этим объектом или структурой.

Иными словами данный алгоритм гарантирует прогресс как минимум для одного потока. Другие потоки могут ждать, но один поток минимум должен прогрессировать. Система в целом продвигается вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).

Пример lock-free алгоритма:

void stack_push (stack* s, node* n)

{

node* head;

do

{

head = s->head;

n->next = head;

}

while (!atomic_compare_exchange (s->head, head, n));

}

Как видно, любой поток может крутиться в этом цикле теоретически бесконечно. Но любой повтор этого цикла означает, что какой-то другой поток успешно выполнил свою операцию. И никакой заблокированный/прерванный поток не может препятствовать продвижению других потоков. Отсюда следует, что система в целом продвигается вперед не зависимо ни от чего. В отличие от wait-free алгоритмов, lock-free алгоритмы благодаря использованию примитивов в цикле не только гарантируют отсутствие конфликтов между вызовами, но и предотвращают возникновение некорректных данных.

Obstruction-free

Obstruction-free алгоритмом или алгоритмом без препятствий называется такой алгоритм, который гарантирует, что каждая операция, выполняемая согласно этому алгоритму, будет выполнена за определенное известное число шагов в том случае, если выполнение все конкурирующие потоков приостановлено.

Поток продвигается вперед, только если не встречает конкуренции со стороны других потоков. В частности это означает, что при сильной конкуренции возможно никакой поток не будет совершать продвижения. То есть система будет находиться в так называемом livelock. Это самая слабая гарантия. Этот класс алгоритмов может показаться немного странным, поэтому стоит заметить, что заблокированные/прерванные потоки не могут препятствовать прогрессу других потоков, и obstruction-free алгоритмы могут быть более быстрые, чем lock-free.

1.3 Выводы

На основе проведённого обзора можно сделать следующие выводы:

1) В связи с тем, что одним из наиболее ограниченных ресурсов вычислительной системы является процессорное время, для решения поставленной задачи предпочтительнее использовать неблокирующую синхронизацию, так как в отличие от блокирующей синхронизации она гарантирует доступ к данным любому потоку в любой момент времени и отсутствие deadlock, что особенно важно для систем реального времени.

2) В соответствии с четвёртым принципом неблокирующей синхронизации были рассмотрены специальные методы управления памятью, после чего было принято решения реализовать методы неблокирующего подсчёта ссылок и опасных указателей. Это обусловлено тем, что метод использования агрегатных счетчиков ссылок или поточных временных штампов является блокирующим без использования специального планировщика, а метод использования специальных тегов (счетчиков изменений) затрудняет повторное использование памяти.

3) В разрабатываемой структуре для читающих потоков необходимо использовать алгоритмы без блокировок, так как необходимо следить не только за отсутствием конфликтов, но и предотвращать возникновение некорректных данных, а для пишущего потока достаточно алгоритма без ожидания, так как наличие только одного пишущего потока позволяет обеспечить отсутствие некорректных данных.

Глава 2. Разработка структуры и алгоритмов взаимодействия

2.1 Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации

Задачей данного дипломного проекта является разработка структуры данных с дисциплиной доступа один пишет — много читают для многопоточного взаимодействия в системах реального времени. Последнее условие накладывает существенные ограничения на время доступа к данным и выполнения операций, в связи с чем реализация на основе блокирующих алгоритмов не является оптимальной.

При разработке структуры данных с дисциплиной доступа один пишет — много читают для многопоточного взаимодействия в системах реального времени с использованием неблокирующей синхронизации необходимо учитывать, что структура данных должна:

1) Состоять из задаваемого и постоянного в пределах одной программы числа элементов.

2) Предоставлять доступ пишущему потоку для изменения любого элемента структуры.

3) Предоставлять доступ читающим потокам для чтения любого элемента структуры.

4) Обеспечивать неблокирующий доступ для пишущего потока.

5) Обеспечивать неблокирующий доступ к самым последним данным для читающих потоков.

6) Гарантировать отсутствие конфликтов.

7) Гарантировать отсутствие некорректных данных.

8) Выделять области памяти для новых данных.

9) Освобождать области памяти из-под неактуальных и неиспользуемых данных.

10) Быть разработана на языке программирования C++ в среде Microsoft Visual Studio и функционировать в ОС Windows.

Первое требование позволяет определиться с типом разрабатываемой структуры: статический массив. Следующие два требования не влияют на выбор методов и способов реализации и будут учитываться только при разработке и реализации алгоритмов для взаимодействия со структурой.

Неблокирующая синхронизация на основе алгоритма без препятствий не удовлетворяет четвёртому и пятому требованиям, так как может привести к livelock. В отличие от deadlock это не приведёт к простою системы, однако при возникновении такой ситуации заблокированные потоки не завершатся. В связи с этим в дальнейшем рассматривать данный алгоритм не имеет смысла.

Шестому требованию удовлетворяют оба оставшихся алгоритма, однако алгоритм без ожиданий не удовлетворяет седьмому требованию. Но стоит отметить, что его можно использовать для пишущего потока, так как наличие только одного пишущего потока само по себе позволяет обеспечить отсутствие некорректных данных. Таким образом, алгоритм без блокировок будет использоваться при разработке и реализации доступа к данным на чтение, а алгоритм без ожидания — на запись.

Для обеспечения предпоследних двух требований необходимо использовать специальные методы управления памятью (в языке программирования C++ нет сборщика мусора), однако не все эти методы представляют интерес. К примеру, метод использования агрегатных счетчиков ссылок или поточных временных штампов является блокирующим без специального планировщика, а метод использования специальных тэгов (счетчиков изменений) памяти по сути является аппаратным решением и не позволяет использовать перераспределённую память, изначально выделенную под один тип узлов, другим типом узлов. Таким образом, остаётся всего лишь два доступных метода управления памятью: неблокирующего подсчета ссылок и опасных указателей. Учитывая приведённые тесты на производительность, необходимо отметить, что метод опасных указателей является более быстродействующим, однако данные тесты проводились с заранее известным числом потоков, а если их число заранее неизвестно, то появляется необходимость в разработке алгоритмов для автоматического добавления и удаления указателей, которые могут повлиять на производительность метода опасных указателей. Кроме того данные тесты отображают производительность LIFO стеков, FIFO очередей и хеш-таблиц с параметром загрузки 1 и 5, а наиболее оптимальной реализацией структуры, удовлетворяющей указанным требованиям, является статический массив с динамическим выделением памяти под изменяемые данные. В связи с этим имеет смысл реализовать как метод опасных указателей, так и метод неблокирующего подсчета ссылок.

2.2 Обзор существующих неблокирующих структур

Несмотря на то, что неблокирующая синхронизация является альтернативным методом написания потокобезопасного кода, на текущий момент данная техника не способна полностью заменить блокирующую синхронизацию. Это связано с тем, что, во-первых, на сегодняшний день не все структуры имеют неблокирующую реализацию, и, во-вторых, написать неблокирующий код, который работает правильно, достаточно сложно. В связи с этим существует не так много различных реализаций различных структур данных:

— стек с динамическим выделением памяти без специальных методов управления памятью;

— очередь со статическим выделением памяти и методов неблокирующего подсчёта ссылок;

— стек, очередь, список и хеш-таблица со статическим выделением памяти и методом опасных указателей.

Прежде всего необходимо отметить, что среди реализованных структур нет массива, только одна структура использует динамическое выделение памяти, но написано для языков программирования со сборкой мусора. К тому же все эти структуры позволяют получить данные только одному потоку, так как после получения доступа к данным они удаляются из структуры. Такая реализация совершенно не подходит для структур с дисциплиной доступа один пишет — много читают для многопоточного взаимодействия в системах реального времени, так как необходимо, чтобы все читающие потоки имели доступ к данным в любой момент.

Проведённый обзор неблокирующих структур показал, что существует достаточное количество различных реализаций различных структур, но, во-первых, не было найдено реализации массива, во-вторых, все структуры либо используют статическое выделение памяти, либо рассчитаны на системы со сборкой мусора и, в-третьих, данные получает только один поток, а остальные ожидают новой порции данных. В связи с этим появляется необходимость в разработке собственной структуры.

2.3 Разработка структуры данных

В соответствии с предъявленными требованиями было принято решение разрабатывать статический массив с динамическим выделением памяти под изменяемые данные, использующий неблокирующую синхронизацию. Неблокирующие структуры основаны на использовании узлов неизменяемого типа и подмене указателей, поэтому ячейки массива должны представляться не непосредственно данными, а указателями на данные. Схематично структура массива изображена на рис. 2.1.

Рис. 2.1 Структура неблокирующего массива

Динамическое выделение памяти под изменяемые данные подразумевает, что в процессе работы программы при создании нового узла происходит выделение под него новой памяти. Раз память выделяется, то значит необходимо предусмотреть её освобождение. Для этого будут использоваться выбранные методы: неблокирующего подсчёта ссылок и опасных указателей. Данные для этих методов будут немного отличаться, так как метод неблокирующего подсчёта ссылок требует включения в структуру динамического узла специального счетчика ссылок, а для метода указателей опасности необходимо иметь разделяемый список опасных указателей. Список инициализируется одним узлом на каждый читающий поток, участвующий во взаимодействии с массивом. Для данного случая достаточно по одному опасному указателю на поток, то есть общее количество опасных указателей равняется числу читающих потоков. Каждый опасный указатель может быть изменён только потоком-владельцем и прочитан любым другим потоком. Схематично структура списка опасных указателей представлена на рис. 2.2.

Рис. 2.2 Структура списка опасных указателей

Кроме этого необходимо отметить, что метод неблокирующего подсчёта ссылок, в отличие от метода опасных указателей, написан для языков программирования со сборкой мусора. В связи с этим оптимально использовать такой же способ освобождения памяти, только опираясь не на опасные указатели, а на счётчик.

В методе опасных указателей для освобождения памяти используется список выбывших узлов, элемент которого содержит в себе указатель на данные, которые уже не являются актуальными, но либо в текущий момент используются, либо ещё могут быть использованными одним или несколькими потоками. Схематично структура списка выбывших узлов представлена на рис. 2.3.

Рис. 2.3 Структура списка выбывших узлов

Количество данных списков совпадает с количеством пишущих потоков, каждый из которых использует только свой список, так как, если использовать общий список для всех пишущих потоков, то может возникнуть серьёзная конкуренция при добавлении данных. Кроме того могут возникать ошибки при удалении данных, если одновременно несколько потоков освобождают память. В условиях поставленной задачи необходимо и достаточного одного списка выбывших узлов.

2.4 Разработка алгоритмов

В любой момент времени данные могут иметь одно из следующих состояний:

— Данные уже существуют, но ещё не добавлены в структуру. Безопасное состояние, так как ещё ни один поток, кроме пишущего, не имеет к ним доступа. Переводится в следующее состояние пишущим потоком после добавления данных в структуру.

— Данные находятся в структуре и являются актуальными. Безопасное состояние, так как доступ к данным могут получать только читающие потоки, которые не изменяют их. Переходят в следующее состояние после устаревания.

— Данные находятся в структуре, но уже не являются актуальными. Опасное состояние, так как читающие потоки всё ещё могут получать доступ к данным, а пишущий поток уже перезаписывает их, при этом новые данные добавляются в структуру, а старые добавляются в список выбывших узлов и переходят в следующее состояние.

— Данные находятся в списке выбывших узлов, и ни один поток не может получить к ним доступ, однако один или несколько читающих потоков всё ещё работают с данными. Опасное состояние, так как при освобождении памяти из-под данных в текущем состоянии возникнут ошибки при чтении. После того как все читающие потоки завершили работу с данными, они переходят в следующее состояние.

— Данные находятся в списке выбывших узлов и не используются в текущий момент, при этом ни один поток не может получить к ним доступ. Безопасное состояние, предшествующее освобождению памяти из-под данных.

Разрабатываемые алгоритмы должны не только обеспечивать предъявленные требования к структуре, но и безопасно переводить данные из одного состояния в другое, а также обеспечивать безопасность каждого состояния.

Прежде чем приступить к разработке алгоритмов, необходимо определить набор выполняемых операций с разрабатываемой структурой. В первую очередь необходимо иметь возможность читать и записывать данные.

При разработке алгоритма чтения необходимо учитывать все принципы неблокирующей синхронизации, чтобы не получить ошибку при доступе к данным, так как отсутствие любого из принципов может привести к ошибке. В то же время при разработке алгоритма записи достаточно учитывать следующие принципы: узлы неизменяемого типа, подмена указателей и атомарные операции, чтобы не произошла ошибка доступа к данным читающими потоками во время их изменения пишущим потоком. Данные принципы полностью обеспечивают это. Принцип специальных методов управления памятью в данном случае не важен, так как пишущий поток всего один.

Кроме этого необходимо предусмотреть операцию освобождения памяти, а для этого, в соответствии с выбранными методами, требуется предусмотреть операцию добавления узла в список выбывших узлов. Её целесообразно объединить с операцией записи, так как данная операция всегда выполняется после изменения элемента массива.

Далее важно определиться с потоком, в котором будет вызываться операция освобождения памяти. Существует несколько возможных вариантов:

1) Вызов операции освобождения памяти в пишущем потоке.

2) Вызов операции освобождения памяти в читающем потоке.

3) Вызов операции освобождения памяти и в пишущем, и в читающем потоке.

Каждый из вариантов имеет свои достоинства и свои недостатки. Вызов операции освобождения памяти в пишущем потоке позволяет упростить освобождение памяти, так как данный поток всего один и не надо отслеживать какие-либо изменения со стороны других потоков. С другой стороны, если читающие потоки в данный момент используют все старые данные, то будет осуществлён вызов, в котором память не освободится. Вызов операции освобождения памяти в читающем потоке позволяет ускорить освобождение памяти, но усложняет взаимодействия между потоками, что может привести как к ошибкам, так и к общему уменьшению быстродействия. Третий вариант обеспечивает максимально быстрое освобождение памяти, но приводит к ещё большим проблемам, чем второй. Даже если использовать для выполнения новый поток, который всегда будет один (то есть поток, прежде чем вызвать операцию освобождение памяти, проверяет, не выполняется ли он уже), то всё равно будут потери в быстродействии. А учитывая то, что разрабатываемые алгоритмы должны иметь максимальное быстродействие, наиболее предпочтительным является первым вариант.

Однако и для первого варианта есть возможность выполнения освобождения памяти в новом потоке. В том случае, если выполнение происходит в пишущем потоке, освобождение памяти упрощается, так как не надо отслеживать изменения со стороны других потоков, но это может привести к тому, что новые данные уже поступили и поток должен бы уже писать их, а он занят освобождением памяти, в связи с чем читающие потоки могут либо работать с неактуальными данными, либо ожидать новые данные. В случае же выполнения освобождения памяти в новом происходит ускорение за счёт параллельного выполнения, однако это не избавляет нас от той ситуации, когда читающий или пишущий поток приостанавливается. К тому же может произойти следующая ситуация: вершина списка выбывших узлов не используется, и мы перед освобождением памяти из-под данного узла изменяем вершину с текущего узла на следующий, а в это время читающий поток уже добавил новый узел и изменил вершину. В результате получается, что добавленный пишущим потоком узел не находится в списке выбывших узлов и поэтому освободить из-под него память не представляется возможным в данных условиях. В связи с этим необходимо либо отслеживать изменения со стороны пишущего потока, либо всегда начинать освобождение узла со следующего после вершины, а память из-под неё освобождать перед завершением программы, так как в этом в любом случае может появиться необходимость, если пишущий поток завершился раньше читающих. Кроме этого необходимо отслеживать ситуацию, при которой произойдёт вызов второго потока, когда первый не завершил свою работу. Данная ситуация может привести к проблемам и ошибкам при освобождении, однако её легко отследить, но несмотря на это всё равно будут дополнительные задержки при выполнении. К тому же при наличии всего лишь одного пишущего потока и нескольких читающих, удобнее выполнять освобождение памяти в пишущем потоке, а не в отдельном, особенно в условиях системы с процессором с небольшим количеством ядер. Поэтому было принято решение выполнять освобождение памяти в пишущем потоке.

Также необходимо разработать алгоритмы добавления опасных указателей в список опасных указателей и удаления их оттуда при заранее неизвестном количестве читающих потоков.

После того, как все особенности учтены, можно переходить непосредственно к разработке алгоритмов в зависимости от специального метода управления памятью.

многопоточный синхронизация алгоритм чтение

2.4.1 Алгоритм записи

В связи с тем, что при разработке алгоритма записи не важны специальные методы управления памятью, его не имеет смысл разрабатывать отдельно для каждого метода.

Для начала необходимо определить данные, поступающие на вход. Так как разрабатываемой структурой является массив, то в первую очередь требуется указать ячейку, в которую необходимо записать данные, а также указатель на сами данные (в соответствии с первыми двумя принципами неблокирующей синхронизации).

После определения входных данных можно перейти непосредственно к алгоритму. В первую очередь необходимо создать новый узел для списка выбывших узлов, затем записать в него указатель на данные из ячейки массива. Это необходимо, чтобы при подмене указателя в ячейке массива не потерять старые данные. Далее происходит атомарная подмена указателя из ячейки массива на указатель новых данных. Данная операция должна выполняться атомарно, чтобы не возникли ошибки при чтении. Операцию CAS можно не использовать, так как пишущий поток всего один ни один другой поток не изменит указатели. После обновления данных необходимо добавить созданный узел с указателем на старые данные в список выбывших узлов и сместить его вершину на добавленный узел. Данные операции можно совершать не атомарно, так как непосредственно со списком выбывших узлов работает только читающий поток. Далее происходит увеличение счётчика, показывающего текущее количество выбывших узлов. Стоит отметить, что счётчик узлов не является обязательным, однако его наличие позволяет задать частоту освобождения памяти, а также уменьшает вероятность ложного вызова освобождения памяти. После увеличение счётчика остается проверить, что его значение больше заданного, при котором происходит вызов операции освобождения памяти. Если данное условие выполнено, то происходит сброс счётчика выбывших узлов и вызов функции освобождения памяти. Разработанный алгоритм является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего. Блок-схема алгоритма записи представлена на рис. 2.4.

Рис. 2.4 Блок-схема алгоритма записи

2.4.2 Алгоритм чтения

В отличие от алгоритма записи, в алгоритме чтения важны специальные методы управления памятью, так как благодаря им не удаляются нужные данные. Поэтому алгоритмы для метода неблокирующего подсчёта ссылок и метода опасных указателей имеет смысл разрабатывать по отдельности.

Метод неблокирующего подсчёта ссылок

Как и в случае разработки алгоритма записи, вначале необходимо определить входные данные. Для чтения данных никакие данные кроме номера ячейки массива, из которой будет производиться чтение, не потребуется.