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

Многопоточность - свойство платформы, например, операционной системы, виртуальной машины, или приложения, состоящее в том, что процесс, порожденный в операционной системе, может состоять из нескольких исполнительных потоков, выполняющихся «параллельно». Она увеличивает производительность процесса за счет распараллеливания вычислительных операций и/или операций ввода/вывода при наличии нескольких задач, которые могут (хотя бы частично) работать одновременно на соответствующей платформе.Работа с изменяемыми типами и структурами подразумевает выполнение таких операций, как чтение и модификация данных соответствующих объектов. Если используется только операция чтения, то есть, если типы и структуры, с которыми производится работа, имеют постоянные значения, никаких проблем с параллельным доступом к ним не возникает.Традиционные алгоритмы синхронизации в многопоточной среде, как известно, основаны на механизме блокировок. В момент времени до начала операции доступ к структуре для потоков, отличных от потока, получившего монопольный доступ, блокируется, далее - производится необходимое изменение, и, наконец, доступ для других потоков вновь разрешается. Блокировки являются мощным средством синхронизации действий в многопоточной среде, которое может обеспечить синхронизацию любых сложных структур.Алгоритмы и структуры данных для неблокирующей синхронизации (в дальнейшем неблокирующие алгоритмы и структуры) частично лишены недостатков блокирующих алгоритмов и структур, однако они не являются универсальными. Самое замечательное свойство подобных алгоритмов и структур состоит в том, что они часто не требуют вообще никаких дополнительных техник параллельного программирования, то есть последовательный алгоритм, реализованный с их помощью, во многих случаях превращается в параллельный алгоритм без дополнительных усилий. Учитывая эту особенно, можно создать копию ресурса по указателю, которая заведомо не будет использоваться другими потоками, изменить данные в копии и, подменив указатель, получить измененный ресурс, а старый освободить. Однако для реализации данного алгоритма необходимо учитывать некоторые особенности, к примеру, если какой-то поток использует ресурс, то мы не можем уничтожить оригинал, а если его используют несколько потоков, то этот ресурс необходимо уничтожить только после того, как все потоки закончат с ним работать.Операция же копирования является довольно дорогой в вычислительном плане, и, кроме того, при работе с типами и структурами большого размера, вообще говоря, можно столкнуться даже с проблемой нехватки памяти. Такая подмена задачи позволяет устранить сам промежуток времени, когда изменяемые данные могут быть не согласованы, - за счет использования атомарных операций, поскольку значение указателя - адрес области памяти - это обычное число, которое можно изменить с помощью единственной процессорной инструкции. Суть операции сравнение с обменом заключается в том, что она атомарно сравнивает значение одного объекта с другим и при удачном сравнении заменяет значение объекта.CAS принимает три аргумента: адрес области памяти, ожидаемое значение по этому адресу и вновь записываемое значение. Иными словами, CAS(address, expected, new) атомарно выполняет следующую операцию (в псевдокоде): Суть пары операций загрузка с пометкой/попытка записи аналогична сути операции CAS: LL атомарно сравнивает значение одного объекта с другим и при удачном сравнении SCЗАМЕНЯЕТ значение объекта.LL принимает один аргумент: адрес области памяти и возвращает ее содержимое. Дополнительная инструкция validate (VL) принимает один аргумент: адрес области памяти, и возвращает булево значение, определяющее, происходила ли перезапись области памяти со стороны других потоков с того момента времени, как данный поток выполнил LL.Увеличение значение тега в момент, когда происходит запись значения по соответствующему адресу, позволяет операциям сравнения (например, CAS) определить, было ли произведено изменение с момента последнего чтения значения тем же потоком. Однако его недостаток заключается в том, что для применения к произвольным указателям, как в случае с объектами динамического размера, он требует наличия инструкций двойной разрядности DCAS (Double-CAS, подробнее - в работе [3]), которые выполняют CAS для двух независимых областей памяти, что дает возможность выполнять атомарные операции как с указателем, так и с его ассоциированным тегом. Как и в случае метода специальных тегов (счетчиков изменений), методу неблокирующего подсчета ссылок требуется наличие операции DCAS для атомарного манипулирования одновременно указателями и счетчиками ссылок, которая не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Однако возможна реализация, в которой манипулирование указателями и, одновременно, независимо расположенными счетчиками ссылок одноадресной операцией CAS производится в неатомарном режиме, но в таком случае могут произойти следующие ситуации: 1) Если поток вначале увеличивает счетчик ссылок, а потом п

Содержание

Введение

Глава 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 Сравнение структур по временным характеристикам

Заключение

Список литературы

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

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