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

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

Альтернатива — включить функции итерирования, например for_each, в сам контейнер. Тогда контейнер сможет полностью управлять своим обходом и блокировкой, но зато перестаёт отвечать рекомендациям но предотвращению взаимоблокировок из главы 3. Чтобы функция for_eachделала что-то полезное, она должна вызывать предоставленный пользователем код, удерживая блокировку. Хуже того, она должна передавать ссылку на каждый элемент контейнера пользовательскому коду, чтобы тот мог к этому элементу обратиться. Можно было бы вместо ссылки передавать копию элемента, но это обойдется слишком дорого, если размер элементов велик.

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

Остается решить, какие операции должен поддерживать список. Вернувшись к листингам 6.11 и 6.12, вы увидите, что именно нам требуется:

• добавлять элемент в список;

• удалять элемент из списка, если он удовлетворяет некоторому условию;

• искать в списке элемент, удовлетворяющий некоторому условию;

• изменить элемент, удовлетворяющий некоторому условию;

• скопировать все элементы списка в другой контейнер.

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

Основная идея связанного списка с мелкогранулярными блокировками — завести по одному мьютексу на каждый узел. Если список длинный, то получится целая куча мьютексов! Достоинство заключается в том, что операции над отдельными частями списка полностью распараллеливаются: каждая операция удерживает только блокировки на узлы, которыми манипулирует, и освобождает блокировку при переходе к следующему узлу. В листинге ниже приведена реализация такого списка.

Листинг 6.13.Потокобезопасный список с поддержкой итераторов

template

class threadsafe_list {

struct node { ← (1)

std::mutex m;

std::shared_ptr data;

std::unique_ptr next;

node() : ← (2)

next() {}

node(T const& value) : ← (3)

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

};

node head;

public:

threadsafe_list() {}

~threadsafe_list() {

remove_if([](node const&){return true;});

}

threadsafe_list(threadsafe_list const& other) = delete;

threadsafe_list& operator=(

threadsafe_list const& other) = delete;

void push_front(T const& value) {

std::unique_ptr new_node(new node(value));← (4)

std::lock_guard lk(head.m);

new_node->next = std::move(head.next); ← (5)

head.next = std::move(new_node); ← (6)

}

template

void for_each(Function f) { ← (7)

node* current = &head;

std::unique_lock lk(head.m); ← (8)

while(node* const next = current->next.get()) {← (9)

std::unique_lock next_lk(next->m);← (10)

lk.unlock(); ← (11)

f(*next->data); ← (12)

current = next;

lk = std::move(next_lk);← (13)

}

}

template

std::shared_ptr find_first_if(Predicate p) {← (14)

node* current = &head;

std::unique_lock lk(head.m);

while (node* const next=current->next.get()) {

std::unique_lock next_lk(next->m);