Что такое модель памяти? И с чем её едят?

Модель памяти в широком смысле слова определяет очень много вещей. Например такое фундаментальное, но в тоже время и очевидное, свойство как размер указателя (8/16/32/64 бита). Или организация кэшей, их кол-во, размер, ассоциативность и т.д. Так же для некоторых аппаратных платформ у разработчика есть возможность выбирать режим работы/адресации (например TINY, SMALL, LARGE, FLAT) — это тоже определяется моделью памяти.

Однако я опишу модель памяти с точки зрения параллельного исполнения, те свойства, которые наиболее релевантны и интересны в контексте многоядерности/многопроцессорности, и относительно которых сейчас имеется серьёзное недопонимание и/или интерес со стороны разработчиков.

Итак к делу. Модель памяти определяет 3 фундаментальных свойства: атомарность, видимость и упорядочивание.

Атомарность (atomicity). Что такое атомарность в целом, я надеюсь, понятно. Это — "неделимость" операции в контексте многопоточного исполнения. Или, если переформулировать, может ли другой поток видеть промежуточное состояние операции. Атомарность необходимо рассмотреть для 2 типов операций.

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

Второй тип — это так называемые RMW (read-modify-write) операции. Среди них могут быть — exchange, compare_exchange, fetch_add, increment, load_linked/store_conditional и др. Модель памяти (вместе с набором команд процессора) определяет какие RMW операции доступны и являются ли они атомарными. Обычно современные процессоры предоставляют как минимум атомарную операцию compare_exchange (или аналогичную load_linked/store_conditional), и, возможно, какие-то другие команды, например, fetch_add и exchange.

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

Видимость (visibility). Под видимостью понимается то, через какое время другие потоки увидят изменения, сделанные данным потоком, и увидят ли вообще. Многие почему-то считают это свойство очень важным, и порываются что-то предпринимать для его обеспечения. На практике, это — как раз самое неинтересное свойство для программиста и ничего предпринимать для его обеспечения не надо. Ну точнее так, ничего не надо предпринимать на кэш-когерентных архитектурах (коими являются все распространённые архитектуры: x86, Itanium, PPC, SPARC и т.д.). Когерентный кэш обеспечивает автоматическое и немедленное распространение всех изменений всем заинтересованным процессорам/ядрам. Т.е. можно считать, что любая запись в память становится немедленно видимой всем остальным потокам.

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

Упорядочивание (ordering). При однопоточном исполнении аппаратура обеспечивает так называемую sequential self-consistency, т.е. для программы всё выглядит так, как будто все обращения к памяти происходят именно в том порядке, в каком они указаны в программе. На самом деле исполнение может производится в другом порядке, однако, пока речь идёт только об одном потоке, аппаратура маскирует этот факт от программиста. При многопоточном исполнении картина кардинально меняется, и другие потоки могут видеть сохранения в память в порядке отличном от программного.

Упорядочивание — это наиболее важное и сложное свойство. Модель памяти должна определять какие переупорядочивания возможны, а какие — нет. Для обеспечения необходимого упорядочивания аппаратная платформа обычно предоставляет так называемые барьеры памяти (memory fences/barriers), это специальные команды, которые запрещают некоторые типы переупорядочиваний вокруг себя. Барьеры памяти бывают двух типов: двусторонние (store-store, load-load) или связанные с операциями (acquire, release). Двусторонние барьеры памяти запрещают какому-то типу обращений к памяти (сохранениям или загрузкам) перемещаться через барьер "вниз", и одновременно другому (хотя возможно и тому же) типу обращений к памяти перемещаться через барьер "вверх". Барьеры связанные с операциями всегда связаны с какой-то операцией (не удивительно) — сохранением, загрузкой или атомарной RMW операцией, и предотвращают перемещение обращений к памяти вверх или вниз относительно этой операции (или и вверх, и вниз). Относительно барьеров важно понимать один момент: барьеры памяти — это всегда игра двух игроков, т.е. поток, который производит, например, запись, должен выполнить барьер, и поток, который соответственно читает, так же должен выполнить барьер. Достичь какого-либо упорядочивания, если барьер исполняет только один поток, — невозможно.

Более детальную информацию по вопросу можно найти в документации по процессорам.

Например для архитектур IA-32 и Intel-64 это "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 3A: System Programming Guide, Part 1":

http://www.intel.com/design/processor/manuals/253668.pdf

(CHAPTER 7 MULTIPLE-PROCESSOR MANAGEMENT)

Для Itanium это "Intel® Itanium® Architecture Software Developer’s Manual Volume 2: System Architecture":

http://download.intel.com/design/Itanium/manuals/24531805.pdf

(MP Coherence and Synchronization)

Для SPARC это "The SPARC Architecture Manual":

www.sparc.org/standards/SPARCV9.pdf

(8 Memory Models)

Так же хорошее введение в упорядочивание инструкций современными процессорами "Memory Ordering in Modern Microprocessors, Part I & II" (by Paul E. McKenney):

http://www.linuxjournal.com/article/8211

http://www.linuxjournal.com/article/8212