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

Еще один недостаток указателей опасности состоит в том, что они защищены патент пой заявкой, поданной 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<>не свободна от блокировок, управлять подсчетом ссылок придется самостоятельно.

В одном из возможных способов используется не один, а два счетчика ссылок — внутренний и внешний. Их сумма равна общему количеству ссылок на узел. Внешний счетчик хранится вместе с указателем на узел и увеличивается при каждом чтении этого указателя. Когда читатель закапчивает работу с узлом, он уменьшает его внутренний счетчик. Таким образом, по завершении простой операции чтения указателя внешний счетчик увеличится на единицу, а внутренний уменьшится на единицу.

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

В листинге ниже показала внутренняя структура данных и реализация функции push() — простая и элегантная.

Листинг 7.10.Помещение узла в свободный от блокировок стек с разделённым счётчиком ссылок

template

class lock_free_stack {

private:

struct node;

struct counted_node_ptr {← (1)

int external_count;

node* ptr;

};

struct node {

std::shared_ptr data;← (2)

std::atomic internal_count;

counted_node_ptr next; ← (3)

node(T const& data_) :

data(std::make_shared(data_)), internal_count(0) {}

};

std::atomic head;← (4)

public:

~lock_free_stack() {

while(pop());

}

void push(T const& data) {← (5)

counted_node_ptr new_node;

new_node.ptr = new node(data);

new_node.external_count = 1;

new_node.ptr->next = head.load();

while(

!head.compare_exchange_weak(new_node.ptr->next, new_node));

}

};

Обратите внимание, что внешний счетчик хранится вместе с указателем на узел в структуре counted_node_ptr (1). Эта структура затем используется для представления указателя nextв структуре node (3), где хранится также внешний счетчик (2). Поскольку counted_node_ptrопределена как struct, то ее можно использовать в шаблоне std::atomic<>для представления головы списка head (4).

На платформах, где поддерживается операция сравнения и обмена двойного слова, размер этой структуры достаточно мал для того, чтобы тип данных std::atomicбыл свободен от блокировок. Если вы работаете на другой платформе, то лучше пользоваться вариантом std::shared_ptr<>, приведенным в листинге 7.9, потому что в std::atomic<>для гарантирования атомарности используется мьютекс, когда тип слишком велик и с помощью машинных команд обеспечить атомарность невозможно (а, следовательно, ваш алгоритм, якобы «свободный от блокировок», на самом теле таковым не является). Можно поступить и по-другому — если вы готовы ограничить размер счетчика и знаете, что на данной платформе в указателе есть неиспользуемые биты (например, потому что адресное пространство представлено 48 битами, а под указатель отводится 64 бита), то счетчик можно хранить в незанятых битах указателя, и тогда оба поля поместятся в одно машинное слово. Но для таких трюков нужно хорошо знать особенности платформы, так что в этой книге мы их обсуждать не будем.