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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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