Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ючается в проходе по списку и проверке данных на использование. Если данные не используются, то из-под них можно освободить память. Однако необходимо учитывать, что пишущий поток имеет доступ к данному списку и может добавлять в начало новые узлы, поэтому целесообразно начинать освобождение памяти со второго узла.
Метод неблокирующего подсчёта ссылок
В данном методе использование данных определяется по счётчику ссылок. На вход алгоритма поступает указатель на второй элемент списка выбывших узлов. После этого создаётся копия указателя, чтобы обеспечивать возможность прохода по списку без потери полученного указателя. Далее происходит обход списка, в котором проверяются значения счётчика по указателю на данные, которые хранится в узле списка выбывших узлов. Если счётчик равен нулю, то данные не используются и из-под них можно безопасно освободить память. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Разработанный алгоритм является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего.
Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок представлена на рис. 2.7.
Рис. 2.7 Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок
Метод опасных указателей
В отличие от метода неблокирующего подсчёта ссылок, данный метод основан на проверке списка опасных указателей. На вход алгоритма поступают указатели на второй элемент списка выбывших узлов и на вершину списка опасных указателей. Далее создаются копии полученных указателей, чтобы обеспечивать возможности прохода по спискам без потери полученных указателей. Далее происходит обход списка выбывших узлов, из каждого узла которого берётся указатель на данные и сравнивается со всеми опасными указателями списка опасных указателей.
Рис. 2.8 Блок-схема алгоритма освобождения памяти для метода опасных указателей
Если указатели совпадают, то совершается переход к следующему узлу списка выбывших узлов. В том случае, если ни один из опасных указателей не совпал с указателем на данные из списка выбывших узлов, то данные не используются ни одним читающим потоком и память из-под них может быть безопасно освобождена. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Данный алгоритм, также как и алгоритм освобождения памяти для метода неблокирующего подсчёта ссылок, является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего. Блок-схема алгоритма освобождения памяти для метода опасных указателей представлена на рис. 2.8.
.4.4 Алгоритм добавления и удаления опасных указателей
Данный алгоритм применим исключительно к методу опасных указателей и служит для предотвращения конфликтов при создании и удалении опасных указателей для каждого читающего потока.
В отличие от работы со списком опасных указателей с заранее известным числом читающих потоков, где можно создать необходимое количество элементов, а затем выдать каждому потоку указатель на свой элемент с опасным указателем, работа со списком опасных указателей с заранее неизвестным числом читающих потоков не позволяет провести аналогичные действия. Поэтому при создании нового читающего потока необходимо создать свой элемент списка опасных указателей, включающий в себя опасный указатель созданного потока, и добавить его в список опасных указателей. Однако необходимо обеспечить отсутствие конфликтов, так как сразу несколько потоков могут пытаться добавить элемент в список. Для этого будет использоваться операция CAS, которая будет добавлять элемент в начало списка только в том случае, если вершина списка не изменилась. После выполнения данного алгоритма поток получает указатель на свой элемент с опасным указателем в списке опасных указателей. Блок-схема алгоритма добавления опасных указателей представлена на рис. 2.9.
Рис. 2.9 Блок-схема алгоритма добавления опасных указателей
При завершении работы поток должен удалить свой элемент из списка опасных указателей. Для этого необходимо найти предшествующий элемент в списке опасных указателей, изменить его указатель на следующий элемент, а затем удалить свой. Однако при завершении нескольких потоков одновременно может произойти следующая ситуация: один из потоков останавливается на элементе, который в этот момент времени удаляется другим потоком. В результате мы получаем ошибку при обращении к несуществующему элементу. В случае небольшого количества читающих потоков можно не освобождать память при завершении, а обнулять указатель и освобождать память из-под всего списка непосредственно перед завершением работы программы, так как решение данной задачи средствами неблокирующего программирования на данный момент не представляется возможным. Это объясняется тем, что во время проверки следующего элемента, может быть удалён текущий, как и любой другой элемент списка. Для решения данной проблемы можно использовать спин-блокировку. В данной ситуации использование простейшей блокирующей синхронизации не приведёт ни к каким отрицательным последствием, так как единственным её предназначением будет обеспечение выполнения алгоритма удаления опасных указателей только одним читающим поток