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

Пояснительная записка к дипломному проекту

на тему:

«Разработка структур данных с дисциплиной доступа

один пишет – много читают для многопоточного взаимодействия

в системах реального времени»

Студент-дипломник: _______________________ / Н.И. Савин /

Руководитель проекта: _______________________ / А.И. Шаповал /

Рецензент: _______________________ / М.Н. Ёхин /

Заведующий кафедрой №12: _______________________ / М.А. Иванов /

Москва 2012

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Wait-free. 24

Lock-free. 25

Obstruction-free. 27

1.3. Выводы.. 27

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ. 70

СПИСОК ЛИТЕРАТУРЫ.. 72

ВВЕДЕНИЕ

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

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

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

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

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

Дата добавления: 2015-11-14