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

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

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

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

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

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

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

Дата добавления: 2015-11-14