Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Используя такую операцию можно гарантировать, что счетчик ссылок никогда не будет иметь значение, меньшее реального числа ссылок. Однако возможна реализация, в которой манипулирование указателями и, одновременно, независимо расположенными счетчиками ссылок одноадресной операцией CAS производится в неатомарном режиме, но в таком случае могут произойти следующие ситуации:
)Если поток вначале увеличивает счётчик ссылок, а потом получает указатель, то может получиться, что в промежуток между этими двумя операциями другой поток уже изменил указатель. В результате первый поток получает уже другой указатель, а в памяти остается структура, которая не будет удалена, так как счётчик ссылок будет равен минимум единице.
)Если поток вначале получает указатель, а потом увеличивает счётчик, то может получиться, что в промежуток времени между этими двумя операциями другой поток уже удалил структуру, указатель на которую получил первый поток. В результате первый поток получит ошибку при попытке увеличить указатель или увеличит какие-то неизвестные данные, что приведёт либо к ошибке, либо к тому, что потоки будут работать с некорректными данными.
В связи с этим необходимы дополнительные проверки корректности счётчиков и указателей.
Метод опасных указателей
Метод опасных указателей, описанный в работах [4,5], является относительно новым подходом к решению данной задачи. В отличие от остальных специальных методов управления памятью он не требует никаких дополнительных методов, например, сборки мусори (garbage collection), а также его можно использовать в качестве решения проблемы повторного использования памяти в неблокирующих алгоритмах, которые написаны для систем со сборкой мусора, в системах без сборки мусора.
Основная идея этого метода заключается в том, чтобы ассоциировать с каждым потоком, который должен работать с неблокирующими структурами, некоторое число (обычно один или два) указателей с диiиплиной доступа один пишет - много читают, так же называемых опасными указателями или hazard pointers. Указатель опасности либо равен нулю, либо указывает на узел, доступ к которому позднее может потребоваться без дополнительного подтверждения того, что ссылка на узел еще допустима. Каждый опасный указатель может быть переписан только его потоком-владельцем, но прочитан может быть любым потоком.
Метод опасных указателей гарантирует, что никакой поток не получит доступ к динамическому узлу в то время, как он может быть удален из структуры, если ни один из ассоциированных с потоками опасных указателей не указывал на него начиная с того момента времени, когда достижимость узла из корня структуры была гарантирована. Кроме того данный метод предотвращает освобождение памяти любого выбывшего узла, на который указывал хотя бы один указатель опасности одного или нескольких потоков, начиная с момента времени, предшествовавшего его удалению.
Стоит отметить, что даже малого числа указателей опасности ассоциированных с каждым потоком хватает для поддержки произвольного числа структур данных или объектов, если этого числа достаточно для работы с каждой структурой или объектом в отдельности. Например, в программе, где каждый поток может произвольно оперировать сотнями разделяемых объектов, каждому из которых требует не более двух указателей опасности на поток (например, хэш-таблицы, FIFO очереди, LIFO стеки, связные списки), программе всего требуется лишь два указателя опасности на поток.
.2.4 Оценка эффективности методов
В работе [4] приводятся данные, отражающие относительную эффективность методологии указателей опасности по сравнению с другими методологиями управления освобождением и повторным использованием памяти в неблокирующих алгоритмах, а так же их общую эффективность, по сравнению с блокирующими алгоритмами.
Эти данные приводятся ниже. Из них можно увидеть, что производительность метода опасных указателей во всех тестах практически идентична производительности метода счетчиков изменений (специальных тегов), при том, что последний, по существу, является аппаратным решением. Так же видно, что чем больший вычислительный параллелизм возможен в системе, тем лучше себя показывает метод указателей опасности, в сравнении с остальными методами. На рис. 1.3 представлена производительность FIFO очередей при различных методах управления освобождением памяти и повторным использованием узлов.
Рис. 1.3 Производительность FIFO очередей
На рис. 1.4 представлена производительность LIFO стеков.
Рис. 1.4 Производительность LIFO стеков
На рис. 1.5 и 1.6 представлены производительности различных методов при реализации хеш-таблиц методом цепочек. На них отображены данные для коэффициентов загрузки 1 и 5 соответственно.
Рис. 1.5 Производительность хеш-таблиц с параметром загрузки 1
Рис. 1.6 Производительность хеш-таблиц с параметром загрузки 5
.2.5 Типы алгоритмов для неблокирующей синхронизации
В работах [2,10] приводятся описания трёх типов алгоритмов для неблокирующей синхронизации.
Wait-free
Wait-free алгоритмом или алгоритмом без ожидания называется такой алгоритм, который гарантирует, что каждая операция, выполняемая потоком согласно этому алгоритму, будет выполнена за определенное известное число шагов, не зависимо от других потоков.
Каждый поток продвигается вперед не зависимо от в