Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
тов.
)Предоставлять доступ пишущему потоку для изменения любого элемента структуры.
)Предоставлять доступ читающим потокам для чтения любого элемента структуры.
)Обеспечивать неблокирующий доступ для пишущего потока.
)Обеспечивать неблокирующий доступ к самым последним данным для читающих потоков.
)Гарантировать отсутствие конфликтов.
)Гарантировать отсутствие некорректных данных.
)Выделять области памяти для новых данных.
)Освобождать области памяти из-под неактуальных и неиспользуемых данных.
)Быть разработана на языке программирования C++ в среде Microsoft Visual Studio и функционировать в ОС Windows.
Первое требование позволяет определиться с типом разрабатываемой структуры: статический массив. Следующие два требования не влияют на выбор методов и способов реализации и будут учитываться только при разработке и реализации алгоритмов для взаимодействия со структурой.
Неблокирующая синхронизация на основе алгоритма без препятствий не удовлетворяет четвёртому и пятому требованиям, так как может привести к livelock. В отличие от deadlock это не приведёт к простою системы, однако при возникновении такой ситуации заблокированные потоки не завершатся. В связи с этим в дальнейшем рассматривать данный алгоритм не имеет смысла.
Шестому требованию удовлетворяют оба оставшихся алгоритма, однако алгоритм без ожиданий не удовлетворяет седьмому требованию. Но стоит отметить, что его можно использовать для пишущего потока, так как наличие только одного пишущего потока само по себе позволяет обеспечить отсутствие некорректных данных. Таким образом, алгоритм без блокировок будет использоваться при разработке и реализации доступа к данным на чтение, а алгоритм без ожидания - на запись.
Для обеспечения предпоследних двух требований необходимо использовать специальные методы управления памятью (в языке программирования C++ нет сборщика мусора), однако не все эти методы представляют интерес. К примеру, метод использования агрегатных счетчиков ссылок или поточных временных штампов является блокирующим без специального планировщика, а метод использования специальных тэгов (счетчиков изменений) памяти по сути является аппаратным решением и не позволяет использовать перераспределённую память, изначально выделенную под один тип узлов, другим типом узлов. Таким образом, остаётся всего лишь два доступных метода управления памятью: неблокирующего подсчета ссылок и опасных указателей. Учитывая приведённые тесты на производительность, необходимо отметить, что метод опасных указателей является более быстродействующим, однако данные тесты проводились с заранее известным числом потоков, а если их число заранее неизвестно, то появляется необходимость в разработке алгоритмов для автоматического добавления и удаления указателей, которые могут повлиять на производительность метода опасных указателей. Кроме того данные тесты отображают производительность LIFO стеков, FIFO очередей и хеш-таблиц с параметром загрузки 1 и 5, а наиболее оптимальной реализацией структуры, удовлетворяющей указанным требованиям, является статический массив с динамическим выделением памяти под изменяемые данные. В связи с этим имеет смысл реализовать как метод опасных указателей, так и метод неблокирующего подсчета ссылок.
.2 Обзор существующих неблокирующих структур
Несмотря на то, что неблокирующая синхронизация является альтернативным методом написания потокобезопасного кода, на текущий момент данная техника не способна полностью заменить блокирующую синхронизацию. Это связано с тем, что, во-первых, на сегодняшний день не все структуры имеют неблокирующую реализацию, и, во-вторых, написать неблокирующий код, который работает правильно, достаточно сложно. В связи с этим существует не так много различных реализаций различных структур данных:
-стек с динамическим выделением памяти без специальных методов управления памятью;
-очередь со статическим выделением памяти и методов неблокирующего подсчёта ссылок;
-стек, очередь, список и хеш-таблица со статическим выделением памяти и методом опасных указателей.
Прежде всего необходимо отметить, что среди реализованных структур нет массива, только одна структура использует динамическое выделение памяти, но написано для языков программирования со сборкой мусора. К тому же все эти структуры позволяют получить данные только одному потоку, так как после получения доступа к данным они удаляются из структуры. Такая реализация совершенно не подходит для структур с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени, так как необходимо, чтобы все читающие потоки имели доступ к данным в любой момент.
Проведённый обзор неблокирующих структур показал, что существует достаточное количество различных реализаций различных структур, но, во-первых, не было найдено реализации массива, во-вторых, все структуры либо используют статическое выделение памяти, либо рассчитаны на системы со сборкой мусора и, в-третьих, данные получает только один поток, а остальные ожидают новой порции данных. В связи с этим появляется необходимость в разработке собственной структуры.
.3 Разработка структуры данных
В соответствии с предъявленными требованиями было принято решение разрабатывать статический массив с динамическим выделением памяти под изменяемые данные, использующий неблокирующую синхронизацию. Неб