Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Lock-free конструкции данных. Основы: откуда пошли быть барьеры памяти

Anna | 24.06.2014 | нет комментариев
Как только я заинтересовался lock-free алгорифмами, меня стал мучить вопрос – а откуда взялась надобность в барьерах памяти, в «наведении порядка» в коде?
Безусловно, прочитав несколько тысяч страниц начальств по определеннойархитектуре, мы обнаружим результат. Но данный результат будет годен для этой определенной архитектуры. Есть ли всеобщий? В конце концов, мы же хотим, Дабы наш код был портабелен. Да и модель памяти C 11 не заточена под определенный процессор.
Особенно приемлемый всеобщий результат дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он возвел некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и для чего он был введен.
Вообще, Paul McKenney – вестимая фигура. Он является разработчиком и энергичным агитатором спецтехнологии RCU, которая энергично применяется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к неопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C 11.
Статья огромная, я даю перевод только первой половины. Я дозволил себе добавить некоторые комментарии,[которые выделены в тексте так].

Memory Barriers: a Hardware View of Software Hackers

Что подвигло дизайнеров CPU ввести барьеры памяти и тем самым подложить свинью разработчикам? Короткий результат таков: переупорядочение обращений к памяти разрешает достичь лучшей продуктивности, а барьеры памяти необходимы для «наведения порядка» в вещах типа примитивов синхронизации [и lock-free алгорифмов, естественно], где корректность примитива зависит как раз от порядка обращений к памяти.
Подробный результат требует отменного понимания того, как работает кэш CPU, и что требуется для ещё лучшей его работы. Следственно дальше мы:

  • разглядим конструкцию кэша;
  • опишем, как протокол когерентности кэша обеспечивает видимость всякой ячейки памяти для различных процессоров;
  • разглядим, как буферы записи (store buffers) и очереди инвалидаций (invalidate queues) помогают кэшу достичь максимальной продуктивности.

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

Конструкция кэша


Современные CPU гораздо стремительней подсистемы памяти. Процессор примера 2006 года мог исполнять 10 инструкций в наносекунду, но требовалось много десятков наносекунд для извлечения данных из стержневой памяти. Эта диспропорция в скорости (больше чем на два порядка!) привела к многомегабайтным кэшам у современных процессоров. Кэши принадлежат процессорам и, как правило, время доступа к ним — несколько тактов.

Примечание

На самом деле, устоявшейся практикой является присутствие нескольких ярусов кэша. Самый небольшой по объему кэш находится ближе каждого к процессору и доступен за один такт. Кеш второго яруса имеет время доступа порядка 10 тактов. Особенно продуктивные процессоры имеют 3 и даже 4 яруса кэшей

CPU обменивается данными с кэшем блоками, называемыми кэш-линиями (cache line), размер которых обыкновенно является степенью двойки – от 16 до 256 байт (зависит от CPU). Когда к ячейке памяти впервой обращается процессор, ячейка отсутствует в кэше, — эта обстановка именуется промахом (cache miss либо, больше верно, “startup” либо “warmup” cache miss). Промах обозначает, что CPU должен ожидать (stalled) сотни тактов, пока данные не будут извлечены из памяти. Наконец данные будут загружены в кэш, и дальнейшие обращения по данному адресу обнаружат данные в кэше, так что CPU будет трудиться на полной скорости.
через некоторостов эта ручательство является подсознательно внятным требованием, так что hardware-инженеры обязаны были внедрить store forwarding: всякий CPU читает данные не только из своего кэша, но инепременно из store buffer. Другими словами, всякая операция записи может прямо передаваться дальнейшей операции чтения через store buffer, без обращения к кэшу.
С store forwarding, шаг 8 в вышеприведенном примере должен прочитать правильное значение 1 переменной “a” из store buffer. В итоге значение “b” станет 2, что нам и требуется.

Буферы записи и барьеры памяти

Дабы увидеть иную загвоздку, — нарушение глобального порядка памяти (global memory ordering), — разглядим дальнейший пример, в котором переменные “a” и “b” имеют исходное значение 0:

1	void foo()
2	{
3		a = 1;
4		b = 1;
5	}
6
7	void bar()
8	{
9		while ( b == 0 ) continue;
10		assert( a == 1 );
11	}

Пускай CPU 0 исполняет foo(), а CPU 1 — bar(). Представим, что память, содержащая “a”, находится только в кэше CPU 1, а CPU 0 обладает памятью, содержащей “b”. Тогда допустима дальнейшая последовательность действий:

  • 1. CPU 0 исполняет a=1. Кэш-линия для “a” не находится в кэше CPU 0, так что CPU 0 помещает новое значение “a” в свой буфер записи и издает сигнал “read invalidate”.
  • 2. CPU 1 исполняет while (b==0) continue, но “b” нет в его кэше, так что он посылает сообщение “read”
  • 3. CPU 0 исполняет b = 1. Он теснее обладает “b” в своем кэше, то есть соответствующая кэш-линия находится в состоянии “exclusive” либо “modified”, — так что он имеет полное право сберечь новое значение “b” в своем кэше, никому ничего не информируя
  • 4. CPU 0 получает сообщение “read” и передает в результате кэш-линию со свежайшим значением “b”, заодно переводя эту линию в состояние “shared” у себя в кэше
  • 5. CPU 1 получает кэш-линию с “b” и помещает её в свой кэш
  • 6. CPU 1 сейчас может закончить выполнение while (b == 0) continue, так как он видит, что b == 1, и приступить к выполнению дальнейшей инструкции
  • 7. CPU 1 исполняет assert(a == 1). Так как CPU 1 работает со ветхим значением “a”, условие не выполняется
  • 8. CPU 1 получает сообщение “read invalidate” и передает кэш-линию с “a” CPU 0, заодно инвалидируя эту линию в своем кэше. Но слишком поздно
  • 9. CPU 0 получает кэш-линию с “a” и исполняет запись из буфера (сбрасывает store buffer в свой кэш)

Вопрос-результат

Отчего CPU 0 в шаге 1 вынужден слать сообщение “read invalidate”, а не легко “invalidate”?
Потому что кэш-линия содержит не только значение переменной “a”. Размер кэш-линии достаточно огромный.

Hardware-инженеры не могут ничем подмогнуть в этом случае, так как процессоры ничего не знают про связь переменных в программе. Следственно инженеры ввели инструкции барьеров памяти, с поддержкой которых программисты могут выразить в программе сходственные связи данных. Фрагмент программы должен быть изменен так:

1	void foo()
2	{
3		a = 1;
4		smp_mb();
5		b =1;
6	}
7
8	void bar()
9	{
10		while ( b == 0 ) continue;
11		assert( a == 1 );
12	}

Барьер памяти smp_mb() [это настоящая функция из ядра Linux] говорит процессору сбросить store buffer перед выполнением дальнейшей записи в кэш. CPU может либо легко остановиться, ждя, пока его store buffer не станет пустым, либо может применять store buffer для последующих записей, пока все записи, теснее находящиеся в store buffer, не будут исполнены [тем самым в store buffer наводится определенный FIFO-порядок].

Последовательность выполнения программы с барьером памяти

  • 1. CPU 0 исполняет a=1. Кеш-линия для “a” не находится в кэше CPU 0, так что CPU 0 помещает новое значение “a” в свой буфер записи и издает сигнал “read invalidate”.
  • 2. CPU 1 исполняет while (b==0) continue, но “b” нет в его кэше, так что он посылает сообщение “read”
  • 3. CPU 0 исполняет smp_mb() и помду соответствующими операциями, для которых она является барьером:
    • Load1; membar #LoadLoad; Load2
    • Load; membar #LoadStore; Store
    • Store; membar #StoreLoad; Load
    • Store1; membar #StoreStore; Store2

    Скажем, полный барьер памяти в Sparc будет выглядеть на ассемблере так:

    membar    #LoadLoad|#LoadStore|#StoreStore|#StoreLoad
    

    В тезисе, все флаги и их комбинации представляют достаточно легкие барьеры, помимо одного —#StoreLoad. И это не специфика архитектуры Sparc, а реально качество всех современных weakly-ordered процессоров.

Дальше

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

Вытесняющий планировщик и барьеры памяти

Стоит подметить, что барьеры памяти — это именно отдельные ассемблерные инструкции фактически у всех современных архитектур (особняком стоит, вероятно, только Intel Itanium – в нем барьер может являться частью load/store/RMW-инструкции). Правильная расстановка барьеров скептически главна в lock-free алгорифмах. Но современные операционные системы в подавляющем большинстве реализуют вытесняющую модель управления процессами/потоками. То есть потоку отводится квант времени, по истечении которого он вытесняется иным потоком. Вытеснение (переключение контекста) может случиться и непринужденно перед инструкцией барьера памяти. Получается, что все наши старания насмарку – мы исполнили скептическую атомарную операцию, а барьера позже неё нет?
На самом деле барьер есть. Код переключения контекста имеет одной из своих первых инструкций как разполный барьер памяти либо что-то сходственное, нередко больше массивное, чем нам необходимо. Следственно наш lock-free алгорифм будет трудиться верно, если, безусловно же, мы сами где-то не накосячим.

Рассмотренный подход к расстановке барьеров памяти я бы назвал read/wrire-подходом. В ходе разработки эталона C 11 read/write-подход к задачам упорядочения доступа к памяти был признан слишком привязанным к архитектуре и была разработана acquire/release семантика, легшая в основу эталона. Как не раз было сказано в статье, барьеры памяти прямо влияют только на процессор, исполняющий барьер, и только опосредованно (через протокол MESI) — на другие процессоры. Модель acquire/release поступает по-иному, — в ней постулируется, как обязаны взаимодействовать различные параллельные потоки (то есть процессоры/ядра), и фактически ничего не говорится, как этого достичь. На самом деле, реализация этой модели — это использование тех либо иных барьеров памяти.
О модели памяти C 11 я собираюсь побеседовать в дальнейшей статье Основ.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB