Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
локирующие структуры основаны на использовании узлов неизменяемого типа и подмене указателей, поэтому ячейки массива должны представляться не непосредственно данными, а указателями на данные. Схематично структура массива изображена на рис. 2.1.
Рис. 2.1 Структура неблокирующего массива
Динамическое выделение памяти под изменяемые данные подразумевает, что в процессе работы программы при создании нового узла происходит выделение под него новой памяти. Раз память выделяется, то значит необходимо предусмотреть её освобождение. Для этого будут использоваться выбранные методы: неблокирующего подсчёта ссылок и опасных указателей. Данные для этих методов будут немного отличаться, так как метод неблокирующего подсчёта ссылок требует включения в структуру динамического узла специального счетчика ссылок, а для метода указателей опасности необходимо иметь разделяемый список опасных указателей. Список инициализируется одним узлом на каждый читающий поток, участвующий во взаимодействии с массивом. Для данного случая достаточно по одному опасному указателю на поток, то есть общее количество опасных указателей равняется числу читающих потоков. Каждый опасный указатель может быть изменён только потоком-владельцем и прочитан любым другим потоком. Схематично структура списка опасных указателей представлена на рис. 2.2.
Рис. 2.2 Структура списка опасных указателей
Кроме этого необходимо отметить, что метод неблокирующего подсчёта ссылок, в отличие от метода опасных указателей, написан для языков программирования со сборкой мусора. В связи с этим оптимально использовать такой же способ освобождения памяти, только опираясь не на опасные указатели, а на счётчик.
В методе опасных указателей для освобождения памяти используется список выбывших узлов, элемент которого содержит в себе указатель на данные, которые уже не являются актуальными, но либо в текущий момент используются, либо ещё могут быть использованными одним или несколькими потоками. Схематично структура списка выбывших узлов представлена на рис. 2.3.
Рис. 2.3 Структура списка выбывших узлов
Количество данных списков совпадает с количеством пишущих потоков, каждый из которых использует только свой список, так как, если использовать общий список для всех пишущих потоков, то может возникнуть серьёзная конкуренция при добавлении данных. Кроме того могут возникать ошибки при удалении данных, если одновременно несколько потоков освобождают память. В условиях поставленной задачи необходимо и достаточного одного списка выбывших узлов.
2.4 Разработка алгоритмов
В любой момент времени данные могут иметь одно из следующих состояний:
-Данные уже существуют, но ещё не добавлены в структуру. Безопасное состояние, так как ещё ни один поток, кроме пишущего, не имеет к ним доступа. Переводится в следующее состояние пишущим потоком после добавления данных в структуру.
-Данные находятся в структуре и являются актуальными. Безопасное состояние, так как доступ к данным могут получать только читающие потоки, которые не изменяют их. Переходят в следующее состояние после устаревания.
-Данные находятся в структуре, но уже не являются актуальными. Опасное состояние, так как читающие потоки всё ещё могут получать доступ к данным, а пишущий поток уже перезаписывает их, при этом новые данные добавляются в структуру, а старые добавляются в список выбывших узлов и переходят в следующее состояние.
-Данные находятся в списке выбывших узлов, и ни один поток не может получить к ним доступ, однако один или несколько читающих потоков всё ещё работают с данными. Опасное состояние, так как при освобождении памяти из-под данных в текущем состоянии возникнут ошибки при чтении. После того как все читающие потоки завершили работу с данными, они переходят в следующее состояние.
-Данные находятся в списке выбывших узлов и не используются в текущий момент, при этом ни один поток не может получить к ним доступ. Безопасное состояние, предшествующее освобождению памяти из-под данных.
Разрабатываемые алгоритмы должны не только обеспечивать предъявленные требования к структуре, но и безопасно переводить данные из одного состояния в другое, а также обеспечивать безопасность каждого состояния.
Прежде чем приступить к разработке алгоритмов, необходимо определить набор выполняемых операций с разрабатываемой структурой. В первую очередь необходимо иметь возможность читать и записывать данные.
При разработке алгоритма чтения необходимо учитывать все принципы неблокирующей синхронизации, чтобы не получить ошибку при доступе к данным, так как отсутствие любого из принципов может привести к ошибке. В то же время при разработке алгоритма записи достаточно учитывать следующие принципы: узлы неизменяемого типа, подмена указателей и атомарные операции, чтобы не произошла ошибка доступа к данным читающими потоками во время их изменения пишущим потоком. Данные принципы полностью обеспечивают это. Принцип специальных методов управления памятью в данном случае не важен, так как пишущий поток всего один.
Кроме этого необходимо предусмотреть операцию освобождения памяти, а для этого, в соответствии с выбранными методами, требуется предусмотреть операцию добавления узла в список выбывших узлов. Её целесообразно объединить с операцией записи, так как данная операция всегда выполняется после изменения элемента масси