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