Модели согласованности памяти

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

Definition

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

Scope

Эта тема охватывает спектр моделей согласованности от последовательной согласованности до ослабленных и слабых моделей, отношение «происходит до» (happens-before) и гарантии отсутствия состояний гонки данных, аппаратные порядки памяти (такие как общий порядок записи), а также модели памяти на уровне языков для C++ и Java. В ней рассматривается, почему существуют ослабленные модели, как барьеры памяти (fences) и атомарные операции восстанавливают упорядочивание, и как корректно рассуждать о параллельной памяти.

Core questions

• Какие порядки операций с памятью может законно наблюдать программа?
• Почему существуют ослабленные модели памяти и что они допускают?
• Как гарантия отсутствия состояний гонки данных упрощает рассуждения?
• Как барьеры памяти и атомарные операции обеспечивают упорядочивание?

Key theories

Последовательная согласованность

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

Ослабленная согласованность и гарантия SC-for-DRF

Адве и Гарахорлу объясняют ослабленные модели и принцип, согласно которому программы без состояний гонки данных ведут себя так, как если бы они были последовательно согласованы, примиряя производительность с программируемостью.

Модели памяти на уровне языка

Мэнсон, Пью и Адве формализовали модель памяти Java, используя отношение «происходит до» (happens-before), определяя, какие оптимизации являются законными и какие гарантии получают даже программы с состояниями гонки.

Clinical relevance

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

History

Лампорт формализовал последовательную согласованность в 1979 году. По мере того как аппаратное обеспечение принимало ослабленные порядки для повышения производительности, учебное пособие Адве и Гарахорлу 1996 года систематизировало ландшафт моделей согласованности и концепцию отсутствия состояний гонки данных. Затем разработчики языков встроили модели памяти в спецификации, при этом модель памяти Java (2005) и модель памяти C++11 установили современный подход.

Debates

Семантика программ с состояниями гонки

Сложный вопрос заключается в том, какие гарантии, если таковые имеются, предоставлять программам, содержащим состояния гонки данных; языковые модели должны предотвращать появление «из ниоткуда» значений, при этом допуская агрессивные оптимизации компилятора и аппаратного обеспечения.

Key figures

• Leslie Lamport
• Sarita Adve
• Kourosh Gharachorloo
• William Pugh
• Jeremy Manson

Seminal works

• lamport1979
• adve1996
• manson2005

Frequently asked questions

Почему не все системы просто используют последовательную согласованность?

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

Что такое гарантия отсутствия состояний гонки данных?

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