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

А могут ли при таком обилии мьютексов возникнуть взаимоблокировки или состояния гонки? Ответ — твердое нет , при условии, что полученные от пользователя предикаты и функции ведут себя, как положено. Итерирование всегда производится в одном направлении, начиная с узла head, и следующий мьютекс неизменно блокируется до освобождения текущего, поэтому не может случиться так, что в разных потоках порядок захвата мьютексов будет различен. Единственный потенциальный кандидат на возникновение гонки — удаление исключенного из списка узла в функции remove_if() (20), потому что это делается после освобождения мьютекса (уничтожение захваченного мьютекса приводит к неопределённому поведению). Однако, немного поразмыслив, мы придём к выводу, что это безопасно, так как в этот момент все еще удерживается мьютекс предыдущего узла ( current), поэтому ни один другой поток не сможет попытаться захватить мьютекс удаляемого узла.

Что можно сказать по поводу распараллеливания? Вся эта возня с мелкогранулярными блокировками затевалась для того, чтобы увеличить уровень параллелизма по сравнению с единственным мьютексом. Так достигли мы своей цели или нет? Да, безусловно — теперь разные потоки могут одновременно работать с разными узлами списка, выполняя разные функции: for_each()для обработки каждого узла, find_first_if()для поиска или remove_if()для удаления элементов. Но, поскольку мьютексы узлов захватываются по порядку, потоки не могут обгонять друг друга. Если какой-то поток тратит много времени на обработку конкретного узла, то, дойдя до этого узла, остальные потоки вынуждены будут ждать.

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

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

■ Реализация параллельных структур данных без использования блокировок.

■ Техника управления памятью в структурах данных без блокировок.

■ Простые рекомендации по написанию структур данных без блокировок.

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

Мьютексы — это мощный механизм, позволяющий нескольким потокам безопасно обращаться к структуре данных, не нарушая инвариантов и не порождая гонок. Рассуждать о поведении кода, в котором используются мьютексы, сравнительно просто: код либо захватывает защищающий данные мьютекс, либо нет. Но не всё коту масленица — в главе 3 мы видели, что некорректное использование мьютексов может стать причиной взаимоблокировок, а при рассмотрении очереди и справочной таблицы показали, как гранулярность блокировок может влиять на истинно параллельное выполнение программы. Если бы удалось разработать структуры данных, с которыми можно было бы безопасно работать, не прибегая к блокировкам, то эти проблемы вообще не возникали бы. Такие структуры называются структурами данных без блокировок , или свободными от блокировок .

В этой главе мы рассмотрим, как можно использовать свойства упорядочения доступа к памяти, присущие атомарным операциям (см. главу 5), для настроения структур данных без блокировок. При проектировании таких структур надо проявлять крайнюю осторожность, потому что реализовать их правильно трудно, а условия, при которых проявляются ошибки, могут возникать очень редко. Начнем с ответа на вопрос, что понимается под структурой данных без блокировок. Затем остановимся на причинах, но которым такие структуры полезны, и, наконец, проработаем ряд примеров и дадим некоторые общие рекомендации.