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

Алгоритм чтения

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


Читайте также:
  1. F65.6 Множественные расстройства сексуального предпочтения
  2. F81.0 Специфическое расстройство чтения
  3. Matlab-реализация алгоритма
  4. X МЕЖДУНАРОДНЫЕ ГЕНДЕРНЫЕ ЧТЕНИЯ
  5. XI МЕЖДУНАРОДНЫЕ ГЕНДЕРНЫЕ ЧТЕНИЯ
  6. А) алгоритмічна конструкція, де перевіряється умова (значення логічного виразу), і залежно від її істинності чи хибності виконується та чи інша серія команд.
  7. Аксиомы теории поведения потребителя. Предпочтения. Функция полезности.

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

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

Как и в случае разработки алгоритма записи, вначале необходимо определить входные данные. Для чтения данных никакие данные кроме номера ячейки массива, из которой будет производиться чтение, не потребуется.

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

Рис. 2.5. Блок-схема алгоритма чтения для метода

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


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


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

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