Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Алгоритм освобождения памяти

ГЛАВА 1. Обзор методов и средств многопоточного взаимодействия | Атомарные операции | Специальные методы управления памятью | Оценка эффективности методов | Типы алгоритмов для неблокирующей синхронизации | Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации | Разработка структуры данных | Разработка алгоритмов | Алгоритм записи | Особенности программной реализации |


Читайте также:
  1. Matlab-реализация алгоритма
  2. А) алгоритмічна конструкція, де перевіряється умова (значення логічного виразу), і залежно від її істинності чи хибності виконується та чи інша серія команд.
  3. Алгоритм 2.1. Разбор цепочек символов по ДС с действиями
  4. Алгоритм 2.14. Сортировка таблиц, управляемая пользователем
  5. Алгоритм 2.15. Форматирование единиц времени календарной диаграммы
  6. Алгоритм 2.25. Форматирование графика ресурсов
  7. Алгоритм 2.33. Создание нового фильтра

Алгоритм освобождения памяти является наиболее важным, так как именно от него зависит правильность освобождения память. Если память будет освобождаться неправильно, то это может привести к утечке памяти или к освобождению памяти из-под используемых данных, что в свою очередь приведёт к ошибкам при чтении данных.

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

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

Метод неблокирующего подсчёта ссылок

В данном методе использование данных определяется по счётчику ссылок. На вход алгоритма поступает указатель на второй элемент списка выбывших узлов. После этого создаётся копия указателя, чтобы обеспечивать возможность прохода по списку без потери полученного указателя. Далее происходит обход списка, в котором проверяются значения счётчика по указателю на данные, которые хранится в узле списка выбывших узлов. Если счётчик равен нулю, то данные не используются и из-под них можно безопасно освободить память. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Разработанный алгоритм является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего.

Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок представлена на рис. 2.7.

Рис. 2.7. Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок

Дата добавления: 2015-11-14; просмотров: 77 | Нарушение авторских прав

<== предыдущая страница | следующая страница ==>
Алгоритм чтения| Алгоритм добавления и удаления опасных указателей
mybiblioteka.su - 2015-2024 год. (0.006 сек.)