Наименьшее ограничение в памяти для спин-блокировки с двумя атомами

У меня есть рабочие потоки, выполняющие критичную по времени обработку с регулярными интервалами (примерно 1 кГц). В каждом цикле рабочих будят для выполнения работы, каждая из которых должна (в среднем) завершаться до начала следующего цикла. Они работают с одним и тем же объектом, который может иногда изменяться основным потоком.

Чтобы предотвратить скачки, но разрешить модификацию объекта до следующего цикла, я использовал спин-блокировку вместе с атомарным счетчиком, чтобы записать, сколько потоков все еще работают:

class Foo {
public:
    void Modify();
    void DoWork( SomeContext& );
private:
    std::atomic_flag locked = ATOMIC_FLAG_INIT;
    std::atomic<int> workers_busy = 0;
};

void Foo::Modify()
{
    while( locked.test_and_set( std::memory_order_acquire ) ) ;   // spin
    while( workers_busy.load() != 0 ) ;                           // spin

    // Modifications happen here ....

    locked.clear( std::memory_order_release );
}

void Foo::DoWork( SomeContext& )
{
    while( locked.test_and_set( std::memory_order_acquire ) ) ;   // spin
    ++workers_busy;
    locked.clear( std::memory_order_release );
    
    // Processing happens here ....

    --workers_busy;
}

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

Доступ к atomic_flag осуществляется с помощью заказов на получение и освобождение памяти, что, по-видимому, является приемлемым способом реализации спин-блокировок в C ++ 11. Согласно документации на cppreference.com:

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

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

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

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

Все вызовы ++workers_busy, --workers_busy и workers_busy.load() в настоящее время имеют порядок памяти по умолчанию, memory_order_seq_cst. Учитывая, что единственное интересное использование этого атома - это разблокировать Modify() с помощью --workers_busy (который не синхронизируется мьютексом спин-блокировки), можно ли использовать тот же порядок получения-освобождения памяти с этой переменной, используя расслабленное приращение? т.е.

void Foo::Modify()
{
    while( locked.test_and_set( std::memory_order_acquire ) ) ;
    while( workers_busy.load( std::memory_order_acquire ) != 0 ) ;  // <--
    // ....
    locked.clear( std::memory_order_release );
}

void Foo::DoWork( SomeContext& )
{
    while( locked.test_and_set( std::memory_order_acquire ) ) ;
    workers_busy.fetch_add( 1, std::memory_order_relaxed );         // <--
    locked.clear( std::memory_order_release );
    // ....
    workers_busy.fetch_sub( 1, std::memory_order_release );         // <--
}

Это верно? Возможно ли дальнейшее ослабление любого из этих порядков памяти? И какое это имеет значение?


person paddy    schedule 02.02.2016    source источник
comment
Отказ от ответственности: не эксперт по атомной энергии. Разве fetch_sub за пределами блокировки вращения не должно быть не менее memory_order_acq_rel, чтобы гарантировать, что он видит записи других потоков в счетчик, и, чтобы другие потоки видели запись, которую он выполняет? Может, что-то не замечает.   -  person ShadowRanger    schedule 02.02.2016
comment
Какая у вас аппаратная платформа? Имейте в виду, что некоторые из функций упорядочивания памяти C ++ существуют для относительно эзотерических платформ. Возможно, вы много работаете и учитесь без прямой выгоды!   -  person Yakk - Adam Nevraumont    schedule 02.02.2016
comment
@Yakk: То, что некоторые memory_order константы не используют специальных аппаратных функций, не означает, что они ничего не делают. Даже на x86 (который имеет строго упорядоченную семантику памяти) выбор memory_order изменяет ограничения оптимизации / переупорядочения компилятора; две memory_order_relaxed операции подряд могут быть заменены компилятором, поэтому вторая операция выполняется первой. Аналогично, relaxed или release stores обычно несут нулевые накладные расходы, но с memory_order_seq_cst компилятор добавляет явные, дорогостоящие (~ 100 циклов задержки) mfence инструкции.   -  person ShadowRanger    schedule 02.02.2016
comment
на x86 хотя бы указание порядка памяти может избавить от префикса lock в некоторых случаях (при условии, что операция может быть завершена за один цикл), тогда как большинство компиляторов выдадут префикс lock без него, это не большая задержка ~ 100-500 циклов в зависимости от чипа, но все же ... это НАМНОГО дороже, чем обычное приращение.   -  person Mgetz    schedule 18.02.2016
comment
@Mgetz В каком случае можно избежать префикса lock в операции?   -  person curiousguy    schedule 29.11.2019
comment
@ShadowRanger выбор memory_order изменяет ограничения компилятора на оптимизацию / переупорядочение Теоретически: да, это так. На практике: какой компилятор оптимизирует на основе порядка памяти?   -  person curiousguy    schedule 29.11.2019
comment
@ Yakk-AdamNevraumont Какой порядок является эзотерическим?   -  person curiousguy    schedule 29.11.2019
comment
@curious Я не понимаю вопроса. Если вы хотите узнать, какие особенности модели памяти C ++ не имеют значения на каких платформах на практике, вы можете использовать кнопку [задать вопрос]. Обратите внимание, что аппаратные ограничения и предположения оптимизатора могут отличаться.   -  person Yakk - Adam Nevraumont    schedule 29.11.2019
comment
@ Yakk-AdamNevraumont Вы, кажется, предположили, что некоторые значения порядка памяти редко, если даже практически, используются на обычном оборудовании.   -  person curiousguy    schedule 29.11.2019


Ответы (2)


Поскольку вы говорите, что ориентируетесь только на x86,, вам все равно гарантировано строго упорядоченная память ; Избегать memory_order_seq_cst полезно (это может вызвать дорогостоящие и ненужные ограничения памяти), но, помимо этого, большинство других операций не налагают никаких особых накладных расходов, поэтому вы ничего не получите от дополнительного расслабления, кроме разрешения возможного неправильного переупорядочения инструкций компилятора. Это должно быть безопасно и не медленнее, чем любое другое решение с использованием атомики C ++ 11:

void Foo::Modify()
{
    while( locked.test_and_set( std::memory_order_acquire ) ) ;
    while( workers_busy.load( std::memory_order_acquire ) != 0 ) ; // acq to see decrements
    // ....
    locked.clear( std::memory_order_release );
}

void Foo::DoWork( SomeContext& )
{
    while(locked.test_and_set(std::memory_order_acquire)) ;
    workers_busy.fetch_add(1, std::memory_order_relaxed); // Lock provides acq and rel free
    locked.clear(std::memory_order_release);
    // ....
    workers_busy.fetch_sub(1, std::memory_order_acq_rel); // No lock wrapping; acq_rel
}

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

person ShadowRanger    schedule 18.02.2016

Вам следует избегать использования версии теста для C ++ и установки блокировки. Вместо этого вы должны использовать атомарные инструкции, предоставленные компилятором. Это действительно имеет большое значение. Это будет работать с gcc и является проверкой и проверкой и установкой блокировки, которая немного более эффективна, чем стандартная проверка и установка блокировки.

unsigned int volatile lock_var = 0;
#define ACQUIRE_LOCK()   {                                                                           
                    do {                                                                    
                        while(lock_var == 1) {                                              
                            _mm_pause;                                                    
                        }                                                                   
                    } while(__sync_val_compare_and_swap(&lock_var, 0, 1) == 1);              
                }
#define RELEASE_LOCK()   lock_var = 0
//

Intel рекомендует использовать _mm_pause для своих процессоров, поэтому есть время для обновления блокировки.

Ваш поток выйдет из цикла do while только тогда, когда он получит блокировку, а затем войдет в критическую секцию.

Если вы посмотрите документацию для __sync_val_compare_and_swap, вы заметите, что он основан на инструкции xchgcmp и будет иметь слово lock над ним в сгенерированной сборке, чтобы заблокировать шину во время выполнения этой инструкции. Это гарантирует атомарное чтение и запись.

person Careful Now    schedule 18.02.2016
comment
Есть ли у вас отставание в цифрах, имеет большое значение? Указанный вами дизайн может быть несколько быстрее, чем правильное использование атомики с семантикой получения / выпуска, но он также не накладывает никаких ограничений на порядок компилятора; действие RELEASE_LOCK, по крайней мере, может быть переупорядочено (компилятором, хотя на x86, а не процессором благодаря строгим гарантиям упорядочения), чтобы оно произошло до мутаций, которые должны быть защищены блокировкой, поэтому вы не избежите условия гонки, которые вы пытаетесь предотвратить. Он также не переносится на архитектуры, отличные от Intel (возможно, не x86). - person ShadowRanger; 18.02.2016
comment
Да, я знаю о _mm_pause, и уже использую его. Я исключил это из своего вопроса, потому что он не казался актуальным. Насколько мне известно, std::atomic_flag будет преобразовывать точно такую ​​же xchgcmp инструкцию. Однако я не уверен, что простая установка значения на ноль вместо выполнения атомарной очистки в конечном итоге будет атомарной и не будет иметь предсказуемого порядка памяти. - person paddy; 18.02.2016
comment
Да, это часть темы моей магистерской диссертации, и это дает примерно 10% разницу в производительности. Если вы хотите упорядочить, вам нужно взглянуть на что-то вроде блокировки Bakery, которая будет упорядочиваться в зависимости от того, когда поток пытается получить блокировку. Замки Black and White Bakery или MCS также обеспечивают заказ, но не так просты. - person Careful Now; 18.02.2016
comment
В то время как ваш поток имеет блокировку, то, что вы делаете, не обязательно должно быть атомарным, поэтому не имеет значения просто установить для него значение 0. - person Careful Now; 18.02.2016
comment
Что-то я упустил, так это то, что замок должен быть нестабильным. Если блокировка не является изменчивой, она не будет принудительно читать из памяти при проверке переменной, что будет означать, что блокировка не будет работать. - person Careful Now; 18.02.2016
comment
@DanielDowd: Что мешает компилятору переупорядочить код ACQUIRE_LOCK(); ++x; RELEASE_LOCK(); на ACQUIRE_LOCK(); RELEASE_LOCK(); ++x;? Без ограничений порядка, поддерживаемых компилятором, последнее вполне разумно; два потока могут получать и снимать блокировку (только по одному, но с условиями гонки можно предположить, что оба потока одновременно начинают выполнение кода после выхода из блокировки), и теперь у вас есть классическое состояние гонки на приращении. - person ShadowRanger; 18.02.2016
comment
@DanielDowd: Ах, да, это имеет огромное значение. Тем не менее, официально volatile также не требует упорядочивания памяти; он требует, чтобы чтение и запись происходили, но не требует, чтобы это происходило в определенном порядке относительно доступа к другим переменным, поэтому я сомневаюсь, что volatile исправит это даже по стандарту. В компиляторах, которые реализуют volatile таким образом, чтобы он был полезен для многопоточности, они часто навязывают поведение, эквивалентное memory_order_seq_cst, с полным забором памяти; вряд ли принесет большую экономию. - person ShadowRanger; 18.02.2016
comment
Если это имеет значение, я ориентируюсь на архитектуры x86 для Mac OS X и Windows (компиляция с помощью Clang и MSVC ++ соответственно). - person paddy; 18.02.2016
comment
Вы помещаете ACQUIRE_LOCK (); перед критической секцией и RELEASE_LOCK () после критической секции. Это останавливает переупорядочивание компилятора. Это работает и с clang, поскольку clang поддерживает соглашение об именах gcc для атомарных вызовов, которые они определили с ужасным __sync перед ними. - person Careful Now; 18.02.2016
comment
@DanielDowd: RELEASE_LOCK не накладывает таких ограничений, даже если lock_var volatile: ... энергозависимые обращения ... не упорядочивают память (обращения к энергонезависимой памяти могут быть свободно переупорядочены вокруг энергозависимого доступа), поэтому ничто не мешает переупорядочению, которое я описал. Он отмечает, что одним примечательным исключением является Visual Studio, где при настройках по умолчанию каждая изменчивая запись имеет семантику выпуска, а каждое изменчивое чтение имеет семантику, но это специфично для Visual Studio, а не для языковой гарантии. - person ShadowRanger; 18.02.2016
comment
Чтобы использовать volatile в качестве флага, вам часто нужно сделать все ваши общие объекты также изменчивыми. Очень редко бывает то, что вы хотите или даже можете сделать. - person curiousguy; 29.11.2019