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

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;

bucket_type& get_bucket(Key const& key) const {← (7)

std::size_t const bucket_index = hasher(key)%buckets.size();

return *buckets[bucket_index];

}

public:

typedef Key key_type;

typedef Value mapped_type;

typedef Hash hash_type;

threadsafe_lookup_table(

unsigned num_buckets = 19,

Hash const& hasher_ = Hash()):

buckets(num_buckets), hasher(hasher_) {

for (unsigned i = 0; i < num_buckets; ++i) {

buckets[i].reset(new bucket_type);

}

}

threadsafe_lookup_table(

threadsafe_lookup_table const& other) = delete;

threadsafe_lookup_table& operator=(

threadsafe_lookup_table const& other) = delete;

Value value_for(Key const& key,

Value const& default_value = Value()) const {

return get_bucket(key).value_for(key, default_value);← (8)

}

void add_or_update_mapping(Key const& key,Value const& value) {

get_bucket(key).add_or_update_mapping(key, value);← (9)

}

void remove_mapping(Key const& key) {

get_bucket(key).remove_mapping(key);← (10)

}

};

В этой реализации для хранения кластеров используется вектор std::vector> (6), это позволяет задавать число кластеров в конструкторе. По умолчанию оно равно 19 (произвольно выбранное простое число); оптимальные показатели работы хеш-таблиц достигаются, когда имеется простое число кластеров. Каждый кластер защищен мьютексом типа boost::shared_mutex (1), который позволяет нескольким потокам одновременно читать, но только одному обращаться к любой из функций модификации данного кластера .

Поскольку количество кластеров фиксировано, функцию get_bucket() (7)можно вызывать вообще без блокировки (8), (9), (10), а затем захватить мьютекс кластера для совместного (только для чтения) (3)или монопольного (чтение/запись) (4), (5)владения — в зависимости от вызывающей функции.

Во всех трех функциях используется функция-член кластера find_entry_for() (2), которая определяет, есть ли в данном кластере указанный ключ. Каждый кластер содержит всего лишь список std::list<>пар ключ/значение, поэтому добавлять и удалять элементы легко.

Я уже рассматривал это решение с точки зрения распараллеливания, и мы убедились, что все надежно защищено мьютексами. Но как обстоит дело с безопасностью относительно исключений? Функция value_forничего не изменяет, поэтому с ней проблем нет: если она и возбудит исключение, то на структуру данных это не повлияет.

Функция remove_mappingмодифицирует список, обращаясь к его функции-члену erase, которая гарантированно не возбуждает исключений, так что здесь тоже всё безопасно. Остается функция add_or_update_mapping, которая может возбуждать исключения в обеих ветвях if. Функция push_backбезопасна относительно исключений, то есть в случае исключения оставляет список в исходном состоянии, так что с этой ветвью всё хорошо. Единственная проблема — присваивание в случае замены существующего значения; если оператор присваивания возбуждает исключение, то мы полагаемся на то, что он оставляет исходный объект неизмененным. Однако это не влияет на структуру данных в целом и является свойством пользовательского типа, так что пускай пользователь и решает эту проблему.

В начале этого раздела я упоминал, что было бы хорошо, если бы можно было получить текущее состояние справочной таблицы, например, в виде объекта std::map<>. Чтобы копия состояния была согласована, потребуется заблокировать контейнер целиком, то есть все кластеры сразу. Поскольку для «обычных» операций захватывается мьютекс только одного кластера, то получение копии состояния будет единственной операцией, блокирующей все кластеры. При условии, что мьютексы всегда захватываются в одном и том же порядке, взаимоблокировка не возникнет. Такая реализация приведена в следующем листинге.

Листинг 6.12.Получение содержимого таблицы threadsafe_lookup_tableв виде std::map<>

std::map threadsafe_lookup_table::get_map() const {

std::vector > locks;

for (unsigned i = 0; i < buckets.size(); ++i) {

locks.push_back(

std::unique_lock(buckets[i].mutex));

}

std::map res;

for (unsigned i = 0; i < buckets.size(); ++i) {

for (bucket_iterator it = buckets[i].data.begin();

it != buckets[i].data.end(); ++it) {

res.insert(*it);

}

}

return res;

}

Реализация справочной таблицы, показанная в листинге 6.11, увеличивает уровень параллелизма таблицы в целом за счет того, что каждый кластер блокируется отдельно, и при этом используется boost::shared_mutex, который позволяет нескольким потокам одновременно читать кластер. Но нельзя ли добиться большего уровня параллелизма, еще уменьшив гранулярность блокировок? В следующем разделе мы покажем, как это сделать, воспользовавшись потокобезопасным списковым контейнером с поддержкой итераторов.

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

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