Читайте также:
|
В связи с тем, что при разработке алгоритма записи не важны специальные методы управления памятью, его не имеет смысл разрабатывать отдельно для каждого метода.
Для начала необходимо определить данные, поступающие на вход. Так как разрабатываемой структурой является массив, то в первую очередь требуется указать ячейку, в которую необходимо записать данные, а также указатель на сами данные (в соответствии с первыми двумя принципами неблокирующей синхронизации).
После определения входных данных можно перейти непосредственно к алгоритму. В первую очередь необходимо создать новый узел для списка выбывших узлов, затем записать в него указатель на данные из ячейки массива. Это необходимо, чтобы при подмене указателя в ячейке массива не потерять старые данные. Далее происходит атомарная подмена указателя из ячейки массива на указатель новых данных. Данная операция должна выполняться атомарно, чтобы не возникли ошибки при чтении. Операцию CAS можно не использовать, так как пишущий поток всего один ни один другой поток не изменит указатели. После обновления данных необходимо добавить созданный узел с указателем на старые данные в список выбывших узлов и сместить его вершину на добавленный узел. Данные операции можно совершать не атомарно, так как непосредственно со списком выбывших узлов работает только читающий поток. Далее происходит увеличение счётчика, показывающего текущее количество выбывших узлов. Стоит отметить, что счётчик узлов не является обязательным, однако его наличие позволяет задать частоту освобождения памяти, а также уменьшает вероятность ложного вызова освобождения памяти. После увеличение счётчика остается проверить, что его значение больше заданного, при котором происходит вызов операции освобождения памяти. Если данное условие выполнено, то происходит сброс счётчика выбывших узлов и вызов функции освобождения памяти. Разработанный алгоритм является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего. Блок-схема алгоритма записи представлена на рис. 2.4.
Рис. 2.4. Блок-схема алгоритма записи
Дата добавления: 2015-11-14; просмотров: 55 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Разработка алгоритмов | | | Алгоритм чтения |