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

Как уже отмечалось, после определения интерфейса (в предположении, что состояний гонки в нем нет), обеспечить потокобезопасность можно, заведя единственный мьютекс, который дет захватываться в начале каждой функции-члена для защиты внутренней структуры данных. Однако тем самым мы сведем на нет все возможности распараллеливания, которые могли бы открыться в результате наличия отдельных функций для чтения и модификации структуры данных. Отчасти исправить ситуацию можно было бы, воспользовавшись мьютексом, который разрешает нескольким потокам читать данные, но только одному — изменять их, например, классом boost::shared_mutexиз листинга 3.13. Это, конечно, несколько улучшило бы общую картину, но при таком решении модифицировать структуру данных по-прежнему может только один поток. В идеале хотелось бы добиться большего.

Как и в случае очереди (см. раздел 6.2.3), чтобы ввести мелкогранулярные блокировки, нужно внимательно изучить особенности структуры данных, а не пытаться обернуть уже имеющийся контейнер, например std::map<>. Есть три общепринятых подхода к реализации ассоциативного контейнера, каковым является, в частности, справочная таблица:

• двоичное, например красно-черное, дерево;

• отсортированный массив;

• хеш-таблица.

Двоичное дерево плохо приспособлено для распараллеливания — каждый просмотр или модификация должны начинается с доступа к корневому узлу, который, следовательно, нужно блокировать. Блокировку, конечно, можно освобождать по мере спуска вниз по дереву, но в целом это немногим лучше блокирования всей структуры целиком.

Отсортированный массив еще хуже, потому что заранее невозможно сказать, в каком месте массива может оказаться требуемое значение, поэтому придется заводить одну блокировку на весь массив. Остается только хеш-таблица. В предположении, что число кластеров фиксировано, вопрос о том, в каком кластере находится ключ, является свойством только лишь самого ключа и хеш-функции. А это значит, что мы сможем завести по одной блокировке на каждый кластер. Если еще и использовать мьютекс, который поддерживает несколько читателей и одного писателя, то коэффициент распараллеливания увеличится в N раз, где N — число кластеров. Недостаток в том, что нужна хорошая хеш-функция для ключа. В стандартной библиотеке С++ имеется шаблон std::hash<>, которым можно воспользоваться для этой цели. Он уже специализирован для таких фундаментальных типов, как int, и некоторых библиотечных типов, например std::string, а пользователь может без труда написать специализации и для других типов ключа. Если, следуя примеру стандартных неупорядоченных контейнеров, указать в качестве параметра шаблона тип объекта-функции, которая выполняет хеширование, то пользователь сможет сам решить, специализировать ли ему шаблон std::hash<>для типа своего ключа или предоставить отдельную хеш-функцию.

Теперь обратимся собственно к коду. Как могла бы выглядеть реализация потокобезопасной справочной таблицы? Один из вариантов показан ниже.

Листинг 6.11.Потокобезопасная справочная таблица

template

typename Hash = std::hash >

class threadsafe_lookup_table {

private:

class bucket_type {

private:

typedef std::pair bucket_value;

typedef std::list bucket_data;

typedef typename bucket_data::iterator bucket_iterator;

bucket_data data;

mutable boost::shared_mutex mutex;← (1)

bucket_iterator find_entry_for(Key const& key) const {← (2)

return std::find_if(data.begin(), data.end(),

[&](bucket_value const& item)

{ return item.first == key; });

}

public:

Value value_for(

Key const& key, Value const& default_value) const {

boost::shared_lock lock(mutex);← (3)

bucket_iterator const found_entry = find_entry_for(key);

return (found_entry==data.end()) ?

default_value : found_entry->second;

}

void add_or_update_mapping(

Key const& key, Value const& value) {

std::unique_lock lock(mutex);← (4)

bucket_iterator const found_entry = find_entry_for(key);

if (found_entry == data.end()) {

data.push_back(bucket_value(key, value));

} else {

found_entry->second = value;

}

}

void remove_mapping(Key const& key) {

std::unique_lock lock(mutex);← (5)

bucket_iterator const found_entry = find_entry_for(key);

if (found_entry != data.end()) {

data.erase(found_entry);

}

}

};

std::vector> buckets;← (6)

Hash hasher;