Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Содержание
Введение
Глава 1. Обзор методов и средств многопоточного взаимодействия
.1 Блокирующая синхронизация
.2 Неблокирующая синхронизация
.2.1 Общие сведения
.2.2 Принципы неблокирующих алгоритмов
.2.3 Обзор специальных методов управления памятью
.2.4 Оценка эффективности методов
.2.5 Типы алгоритмов для неблокирующей синхронизации
.3 Выводы
Глава 2. Разработка структуры и алгоритмов взаимодействия
.1 Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации
.2 Обзор существующих неблокирующих структур
.3 Разработка структуры данных
.4 Разработка алгоритмов
.4.1 Алгоритм записи
.4.2 Алгоритм чтения
.4.3 Алгоритм освобождения памяти
.4.4 Алгоритм добавления и удаления опасных указателей
Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия
.1 Особенности программной реализации
.2 Тестирование разработанных алгоритмов
.3 Тестирование разработанной структуры при многопоточном доступе
.4 Сравнение структур по временным характеристикам
Заключение
Список литературы
Введение
Многопоточность - свойство платформы, например, операционной системы, виртуальной машины, или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких исполнительных потоков, выполняющихся параллельно. Она увеличивает производительность процесса за счет распараллеливания вычислительных операций и/или операций ввода/вывода при наличии нескольких задач, которые могут (хотя бы частично) работать одновременно на соответствующей платформе. Код правильно написанного многопоточного приложения выглядит просто, потому что каждый поток выполняет свою конкретную задачу. Однако в многопоточной среде часто возникают проблемы, связанные с использованием параллельно исполняемыми потоками одних и тех же данных или устройств. Для решения подобных проблем используются различные методы синхронизации потоков. Все они имеют свои положительные и отрицательные стороны, основным критерием их оценки является время, затрачиваемое для выполнения операций, обеспечивающих отсутствие конфликтов между потоками, непредсказуемых результатов, а также координированное выполнение взаимозависимого кода для обеспечения правильной последовательности событий, причём это время может варьироваться на разных итерациях. В связи с этим в системах реального времени проблема многопоточного доступа к общим данным стоит наиболее остро, так как данная система либо не должна опаздывать с реакцией на событие (операционной системой мягкого реального времени), либо никогда не опоздает с реакцией на событие (система жёсткого реального времени).
В данной работе будут рассмотрены возможные варианты многопоточного доступа к данным, выбраны и реализованы методы синхронизации, удовлетворяющие поставленной задаче, которые в дальнейшем можно будет использовать в системах реального времени.
Глава 1. Обзор методов и средств многопоточного взаимодействия
Работа с изменяемыми типами и структурами подразумевает выполнение таких операций, как чтение и модификация данных соответствующих объектов. Если используется только операция чтения, то есть, если типы и структуры, с которыми производится работа, имеют постоянные значения, никаких проблем с параллельным доступом к ним не возникает. Доступ к таким данным может производиться из множества потоков без всякой их синхронизации. Однако, другое дело, если работа производится с данными, которые могут изменяться: с момента начала операции модификации и вплоть до ее окончания, структура может находиться в несогласованном состоянии. Если теперь в этом промежутке времени будет произведена операция чтения, то она вернет неверное значение. Существует два решения проблемы: блокирующая и неблокирующая синхронизация.
.1 Блокирующая синхронизация
Традиционные алгоритмы синхронизации в многопоточной среде, как известно, основаны на механизме блокировок. В момент времени до начала операции доступ к структуре для потоков, отличных от потока, получившего монопольный доступ, блокируется, далее - производится необходимое изменение, и, наконец, доступ для других потоков вновь разрешается. Таким образом, гарантируется целостность структуры данных. В простом виде блокирующий алгоритм можно представить в виде блок-схемы, показанной на рис. 1.1.
Рис. 1.1 Блок-схема простого алгоритма с блокировкой
Блокировки являются мощным средством синхронизации действий в многопоточной среде, которое может обеспечить синхронизацию любых сложных структур. Но, как и все мощное, эта это средство таит в себе множество недостатков, например:
-они являются довольно медленными операциями и требуют много ресурсов;
-они являются узким местом программы, поскольку с ресурсом, на котором установлена блокировка, может работать только заблокировавший его процесс, и в связи с этим процесс с низким приоритетом может заблокировать на неопределенное время другой процесс, с более высоким приоритетом;
-они подвержены проблеме взаимных блокировок, отладка же взаимных блокировок бывает чрезвычайно сложна, поскольку возникает при определенных специфических условиях;
-использование блокирующих механизмов синхронизации подразумевает применение особой техники программирования, и внедрять