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

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

Рис. 2.1. Структура неблокирующего массива

Динамическое выделение памяти под изменяемые данные подразумевает, что в процессе работы программы при создании нового узла происходит выделение под него новой памяти. Раз память выделяется, то значит необходимо предусмотреть её освобождение. Для этого будут использоваться выбранные методы: неблокирующего подсчёта ссылок и опасных указателей. Данные для этих методов будут немного отличаться, так как метод неблокирующего подсчёта ссылок требует включения в структуру динамического узла специального счетчика ссылок, а для метода указателей опасности необходимо иметь разделяемый список опасных указателей. Список инициализируется одним узлом на каждый читающий поток, участвующий во взаимодействии с массивом. Для данного случая достаточно по одному опасному указателю на поток, то есть общее количество опасных указателей равняется числу читающих потоков. Каждый опасный указатель может быть изменён только потоком-владельцем и прочитан любым другим потоком. Схематично структура списка опасных указателей представлена
на рис. 2.2.

Рис. 2.2. Структура списка опасных указателей

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

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

Рис. 2.3. Структура списка выбывших узлов

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

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