Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Но и у этого решения есть недостаток (помимо увеличенного расхода памяти): теперь мы должны подсчитывать узлы в списке освобождения, то есть использовать атомарный счетчик, а, кроме того, за доступ к самому списку конкурируют несколько потоков. Если память позволяет, то можно предложить еще более эффективную схему освобождения: каждый поток хранит собственный список освобождения в поточно-локальной памяти. Тогда ни для счетчика, ни для доступа к списку не понадобятся атомарные переменные. Но в обмен придется выделить память для max_hazard_pointers * max_hazard_pointersузлов. Если поток завершается прежде, чем освобождены все его узлы, то оставшиеся можно перенести в глобальный список, как и раньше, а затем добавить в локальный список следующего потока, пожелавшего выполнить процедуру освобождения.

Еще один недостаток указателей опасности состоит в том, что они защищены патент пой заявкой, поданной IBM [13] Maged M. Michael, U.S. Patent and Trademark Office application number 20040107227, «Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation». . Если вы пишете программное обеспечение, которое будет применяться в стране, где эти патенты признаются, то придется получить соответствующую лицензию. Это проблема, общая для многих методов освобождения памяти без блокировок; поскольку в этой области ведутся активные исследования, крупные компании берут патенты всюду, где могут. Возможно, вы задаетесь вопросом, зачем я посвятил так много страниц описанию техники, которой многие не смогут воспользоваться. Что ж, вопрос не праздный. Во-первых, в некоторых случаях ей можно воспользоваться, не платя лицензионных отчислений. Например, если вы разрабатываете бесплатную программу на условиях лицензии GPL [14] GNU General Public License http://www.gnu.org/licenses/gpl.html. , то она может подпадать под заявление IBM об отказе от патентных притязаний [15] IBM Statement of Non-Assertion of Named Patents Against OSS, http://www.ibm.com/ibm/licensing/patents/ . Во-вторых — и это более существенно — объяснение техники помогает высветить вещи, о которых надо помнить при написании кода, свободного от блокировок, например, о плате за атомарные операции.

А существуют ли непатентованные методы освобождения памяти, применимые в программах без блокировок? К счастью, да. Один из них — подсчет ссылок.

В разделе 7.2.2 мы видели, что проблема удаления узлов сводится к задаче нахождения узлов, к которым еще обращаются потоки-читатели. Если бы можно было точно узнать, на какие узлы есть ссылки и когда количество ссылок обращается в нуль, то узлы можно было бы удалить. Указатели опасности решают эту проблему путем хранения списка используемых узлов, а механизм подсчета ссылок — путем хранения числа потоков, обращающихся к каждому узлу.

Выглядит просто и элегантно, но реализовать на практике очень трудно. Сразу приходит в голову мысль, что для такой задачи подошло бы что-то вроде std::shared_ptr<>— ведь это и есть указатель с подсчетом ссылок. Увы, хотя некоторые операции над std::shared_ptr<>атомарны, не гарантируется, что они свободны от блокировок. Сам по себе класс std::shared_ptr<>ничем не хуже прочих с точки зрения операций над атомарными типами, но он рассчитан на применение в самых разных контекстах, и попытка сделать атомарные операции над ним свободными от блокировок, скорее всего, привела бы к увеличению накладных расходов при любом его использовании. Если на вашей платформе функция std::atomic_is_lock_free(&some_shared_ptr)возвращает true, то проблему освобождения памяти можно считать полностью решенной. Достаточно хранить в списке объекты std::shared_ptr, как показано в следующем листинге.

Листинг 7.9.Свободный от блокировок стек на основе свободной от блокировок реализации std::shared_ptr<>

template

class lock_free_stack {

private:

struct node {

std::shared_ptr data;

std::shared_ptr next;

node(T const& data_) :

data(std::make_shared(data_)) {}

};

std::shared_ptr head;

public:

void push(T const& data) {

std::shared_ptr const new_node =

std::make_shared(data);

new_node->next = head.load();

while (!std::atomic_compare_exchange_weak(

&head, &new_node->next, new_node));

}

std::shared_ptr pop() {

std::shared_ptr old_head = std::atomic_load(&head);

while(old_head && !std::atomic_compare_exchange_weak(

&head, &old_head, old_head->next));

return old_head ? old_head->data : std::shared_ptr();

}

};

В том весьма вероятном случае, когда реализация std::shared_ptr<>не свободна от блокировок, управлять подсчетом ссылок придется самостоятельно.