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

Это приводит к синхронизации-с (см. раздел 5.3.1) последующим обращением к flag.test_and_set()из функции lock()в другом потоке, потому что в этом обращении задана семантика std::memory_order_acquire. Так как модификация защищенных данных обязательно расположена-перед вызовом unlock(), то эта модификация происходит-раньше вызова unlock()и, следовательно, происходит-раньше последующего обращения к lock()из другого потока (благодаря наличию отношения синхронизируется-с между unlock()и lock()) и происходит-раньше любой операции доступа к данным из второго потока после того, как он захватит блокировку.

В других реализациях мьютексов используются иные внутренние операции, но принцип остается неизменным: lock()— это операция захвата над некоторой внутренней ячейкой памяти, a unlock()— операция освобождения над той же ячейкой памяти.

В этой главе мы рассмотрели низкоуровневые детали модели памяти в C++11 и атомарные операции, лежащие в основе синхронизации потоков. Были также рассмотрены простые атомарные типы, предоставляемые специализациями шаблона класса std::atomic<>, и обобщенный интерфейс в виде основного шаблона std::atomic<>, операции над этими типами и непростые детали, связанные с различными вариантами упорядочения доступа к памяти.

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

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

■ Что понимается под проектированием структур данных, рассчитанных на параллельный доступ?

■ Рекомендации по проектированию таких структур.

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

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

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

При проектировании структуры данных, допускающей параллельный доступ, мы можем использовать основные строительные блоки многопоточных приложений, описанные в предыдущих главах, например мьютексы и условные переменные. На самом деле, вы уже видели примеры структур, в которых сочетание этих блоков гарантирует безопасный доступ из нескольких потоков.

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

Но довольно предисловий — посмотрим, что входит в проектирование структуры данных для параллельного программирования.

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

Но проектирование с учетом параллелизма этим не исчерпывается: задача заключается в том, чтобы предоставить возможность распараллеливания потокам, обращающимся к структуре данных. По природе своей, мьютекс означает взаимное исключение : в каждый момент времени только один поток может захватить мьютекс. Следовательно, мьютекс защищает структуру данных, явным образом предотвращая истинно параллельный доступ к ней.

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

Прежде чем знакомиться с конкретными структурами данных, приведём несколько простых рекомендаций, полезных при проектировании с учетом параллелизма.

Как я уже отмечал, при проектировании структур данных для параллельного доступа нужно учитывать два аспекта: обеспечить безопасность доступа и разрешить истинно параллельный доступ. Как сделать структуру потокобезопасной, я уже рассказывал в главе 3.

• Гарантировать, что ни один поток не может увидеть состояние, в котором инварианты структуры данных нарушены действиями со стороны других потоков.