Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
невозможность доступа к ней других потоков, неблокирующим образом.
Есть несколько способов, которые применяются в различных системах iелью выполнения этой задачи:
-Метод использования специальных тэгов (счетчиков изменений) памяти, основывающийся на ассоциировании специального тега с каждым адресом памяти, который может быть использован в операции;
-Метод неблокирующего подсчета ссылок, основывающийся на включении в структуру динамического узла специального счётчика ссылок;
-Метод использования агрегатных счетчиков ссылок или поточных временных штампов, основывающийся на наличии специального планировщика и являющийся блокирующим без него (именно поэтому в дальнейшем данный метод не рассматривается, ввиду отсутствия такого планировщика), то есть ошибка или задержка хотя бы одного потока в данном методе может воспрепятствовать достижению нуля агрегатным счетчиком ссылок или обновлению временного штампа и, следовательно, воспрепятствовать перераспределению памяти;
-Метод опасных указателей, основывающийся на ассоциировании с каждым потоком, который должен работать со структурами, некоторого числа (обычно один или два) указателей с типом доступа один писатель - много читателей.
Также существует другая связанная с повторным использованием памяти проблема - это так называемая проблема ABA. Ее наличие влияет практически на все неблокирующие алгоритмы. Проблема эта обнаруживается тогда, когда поток читает значение A из некоей разделяемой области памяти, далее другой поток изменяет значение в этой области памяти на B, после чего снова на A. Позднее, когда первый поток проверяет, не изменилось ли значение, например, с помощью CAS, сравнение с сохраненным значением возвращает истину (то есть не изменилось). И поток продолжает выполнение далее, ошибочно считая, что значение не изменялось с момента первого чтения. В результате, поток может повредить структуру данных или вернуть неверный результат, поскольку другой поток мог произвести другие, скрытые изменения, которые первый поток просто не обнаружит.
Проблема ABA является фундаментальной, и должна быть устранена вне зависимости от способа обеспечения повторного использования памяти. Однако методы обеспечения повторного использования памяти (например, сборка мусора или garbage collection (GC)) часто предотвращают возникновение этой проблемы в качестве побочного эффекта, так сказать, без каких бы то ни было дополнительных затрат, но, к сожалению, в некоторых языках нет сборщика мусора.
.2.3 Обзор специальных методов управления памятью
Метод использования специальных тегов
Метод использования специальных тегов (счетчиков изменений) является самым ранним и наиболее простым неблокирующим методом повторного использования памяти узлов. Он требует, чтобы с каждым адресом памяти, который может быть использован в операции сравнения с ожидаемым значением, подверженной ABA-проблеме, был ассоциирован специальный тег. Увеличение значение тега в момент, когда происходит запись значения по соответствующему адресу, позволяет операциям сравнения (например, CAS) определить, было ли произведено изменение с момента последнего чтения значения тем же потоком. Таким образом, проблема ABA устраняется. Данный метод требует, чтобы тег имел достаточную разрядность для того, чтобы полный цикл инкрементации был невозможен за время выполнения любой единичной неблокирующей операции. Этот метод очень эффективен и позволяет немедленное освобождение памяти узлов или их повторное использование.
Однако его недостаток заключается в том, что для применения к произвольным указателям, как в случае с объектами динамического размера, он требует наличия инструкций двойной разрядности DCAS (Double-CAS, подробнее - в работе [3]), которые выполняют CAS для двух независимых областей памяти, что дает возможность выполнять атомарные операции как с указателем, так и с его ассоциированным тегом. Эти инструкции совсем не поддерживаются в 64-разрядных архитектурах и в большинстве 32-разрядных. Кроме того, семантика тегового поля должна сохраняться постоянно. Таким образом, если тег является частью динамической структуры узлов, повторное использование таких узлов затрудняется. Их память не может быть поделена или объединена, поскольку это может привести к изменению семантики теговых полей. Это значит, то коль скоро некая область памяти была использована для определенного типа узлов, она не может уже быть повторно использована для другого типа узлов, которые не сохраняют семантику теговых полей. Таким образом, данный метод является, по сути, аппаратным решением, в связи с чем от его дальнейшего рассмотрения приходится отказаться.
Метод неблокирующего подсчета ссылок
Метод неблокирующего подсчета ссылок, описанный в работе [1], требует включения в структуру динамического узла специального счетчика ссылок, отражающего текущее число ссылок на данный узел структуры и локальных переменных потоков, оперирующих данной структурой. Каждый раз, когда получается, либо удаляется новая ссылка на динамический узел, счетчик ссылок должен быть увеличен, либо уменьшен, используя инструкцию fetch-and-addилиcompare-and-swap. Только в том случае, если счетчик ссылок равен нулю, узел может быть повторно использован.
Как и в случае метода специальных тегов (счетчиков изменений), методу неблокирующего подсчёта ссылок требуется наличие операции DCAS для атомарного манипулирования одновременно указателями и счетчиками ссылок, которая не под