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

Алгоритм записи

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


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

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

Для начала необходимо определить данные, поступающие на вход. Так как разрабатываемой структурой является массив, то в первую очередь требуется указать ячейку, в которую необходимо записать данные, а также указатель на сами данные (в соответствии с первыми двумя принципами неблокирующей синхронизации).

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

Рис. 2.4. Блок-схема алгоритма записи


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


<== предыдущая страница | следующая страница ==>
Разработка алгоритмов| Алгоритм чтения

mybiblioteka.su - 2015-2024 год. (0.006 сек.)