Соображения по поводу программирования без использования блокировок для Xbox 360 и Microsoft Windows

Программирование без блокировки — это способ безопасного обмена данными между несколькими потоками без затрат на получение и освобождение блокировок. Это звучит как панацея, но бессерверное программирование является сложным и тонким, а иногда не дает преимуществ, которые он обещает. Программирование без блокировки особенно сложно на Xbox 360.

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

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

Программирование с помощью блокировок

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

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

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

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

Программирование без блокировки

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

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

Не атомарные операции

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

На всех современных процессорах можно предположить, что операции чтения и записи естественно выровненных собственных типов являются атомарными. Если шина памяти не менее широка, чем тип чтения или записи, ЦП считывает и записывает эти типы в одной транзакции шины, что делает его невозможным для других потоков, чтобы увидеть их в полузаверченном состоянии. В x86 и x64 нет гарантии, что операции чтения и записи размером более восьми байтов являются атомарными. Это означает, что 16-байтовые операции чтения и записи регистров расширения SSE потоковой передачи и строковых операций могут не быть атомарными.

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

Составные операции, такие как последовательность чтения и изменения записи, которая возникает при добавке общей переменной, не являются атомарными. В Xbox 360 эти операции реализуются в виде нескольких инструкций (lwz, addi и stw), а поток может быть переключлен через последовательность. В x86 и x64 существует одна инструкция (inc), которую можно использовать для увеличения переменной в памяти. Если вы используете эту инструкцию, приращение переменной атомарно в однопроцессорных системах, но оно по-прежнему не атомарно в многопроцессорных системах. Для атомарного применения inc в системах с несколькими процессорами на основе x86 и x64 требуется использование префикса блокировки, что позволяет другому процессору выполнять собственную последовательность чтения и изменения записи между чтением и записью инструкции inc.

В коде ниже приведено несколько примеров:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Обеспечение атомарности

Вы можете убедиться, что используете атомарные операции, используя следующие сочетания:

• Естественно атомарные операции
• Блокировки для упаковки составных операций
• Функции операционной системы, реализующие атомарные версии популярных составных операций

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

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

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

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Переупорядочение

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

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

Изменение порядка операций чтения и записи можно сделать как компилятором, так и обработчиком. Компиляторы и процессоры сделали это переупорядочение в течение многих лет, но на однопроцессорных компьютерах это было меньше проблемы. Это связано с тем, что переупорядочение ЦП операций чтения и записи невидимо на компьютерах с одним процессором (для кода драйвера не устройства, который не является частью драйвера устройства), а изменение порядка операций чтения и записи компилятора меньше шансов вызвать проблемы на компьютерах с одним процессором.

Если компилятор или ЦП переупорядочение записей, показанных в следующем коде, другой поток может увидеть, что живой флаг установлен, пока не отображает старые значения для x или y. Аналогичное изменение может произойти при чтении.

В этом коде один поток добавляет новую запись в массив sprite:

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

В следующем блоке кода другой поток считывается из массива sprite:

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Чтобы обеспечить безопасность системы sprite, необходимо предотвратить изменение порядка операций чтения и записи как компилятора, так и ЦП.

Общие сведения о переупорядочении ЦП операций записи

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

Xbox 360

Хотя ЦП Xbox 360 не изменяет порядок инструкций, он изменяет порядок операций записи, которые выполняются после выполнения инструкций. Эта переупорядочение операций записи в частности разрешена моделью памяти PowerPC.

Записи на Xbox 360 не переходят непосредственно в кэш L2. Вместо этого, чтобы улучшить пропускную способность записи кэша L2, они проходят через очереди хранилища, а затем собирают буферы. Буферы хранения позволяют записывать 64-байтовые блоки в кэш L2 в одной операции. Существует восемь буферов сбора хранилища, которые позволяют эффективно записывать в несколько различных областей памяти.

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

Даже если буферы хранилища собираются в кэш L2 в строгом порядке FIFO, это не гарантирует, что отдельные записи записываются в кэш L2 в порядке. Например, представьте, что ЦП записывает данные в расположение 0x1000, а затем в расположение 0x2000, а затем в расположение 0x1004. Первая запись выделяет буфер сбора в хранилище и помещает его перед очередью. Вторая запись выделяет другой буфер сбора в хранилище и помещает его рядом в очередь. Третья запись добавляет свои данные в первый буфер сбора хранилища, который остается в передней части очереди. Таким образом, третья запись заканчивается в кэшЕ L2 перед второй записью.

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

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

x86 и x64

Несмотря на то, что процессоры x86 и x64 выполняют переупорядочение инструкций, они обычно не переупорядочения операций записи относительно других операций записи. Существуют некоторые исключения для объединенной памяти записи. Кроме того, строковые операции (MOVS и STOS) и 16-байтовые записи SSE могут быть внутренне переупорядочены, но в противном случае операции записи не переупорядочены относительно друг друга.

Общие сведения о переупорядочении ЦП для операций чтения

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

Xbox 360

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

x86 и x64

Несмотря на то, что процессоры x86 и x64 выполняют переупорядочение инструкций, они обычно не переупорядочения операций чтения относительно других операций чтения. Строковые операции (MOVS и STOS) и 16-байтовые операции чтения SSE могут быть внутренне переупорядочены, но в противном случае операции чтения не переупорядочены относительно друг друга.

Другое изменение порядка

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

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

Проблема заключается в том, что чтение f1 в P0Acquire может считываться из общего хранилища, прежде чем запись в f0 делает его общим хранилищем. Между тем, чтение f0 в P1Acquire может считываться из общего хранилища, прежде чем запись в f1 делает его общим хранилищем. Чистый эффект заключается в том, что оба потока устанавливают их флаги на TRUE, и оба потока видят флаг другого потока как FALSE, поэтому они оба входят в критически важный регион. Таким образом, в то время как проблемы с переупорядочением систем на основе x86 и x64 менее распространены, чем в Xbox 360, они, безусловно, могут произойти. Алгоритм Dekker не будет работать без аппаратных барьеров памяти на любой из этих платформ.

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

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

Сводка по переупорядочению

Операции переупорядочения ЦП Xbox 360 гораздо более агрессивно, чем процессоры x86 и x64, как показано в следующей таблице. Дополнительные сведения см. в документации по обработчику.

Изменение порядка действий	x86 и x64	Xbox 360
Чтение впереди операций чтения	No	Да
Операции записи впереди операций записи	No	Да
Записи, перемещающиеся впереди операций чтения	No	Да
Чтение впереди операций записи	Да	Да

 

Барьеры для чтения и получения и записи

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

Формальные определения, любезно Херб Саттер, являются следующими:

• Получение чтения выполняется до всех операций чтения и записи в одном потоке, который следует за ним в порядке программы.
• Выпуск записи выполняется после всех операций чтения и записи в одном потоке, который предшествует ему в порядке программы.

Когда код получает владение некоторой памятью, либо путем получения блокировки, либо путем извлечения элемента из общего связанного списка (без блокировки), всегда используется проверка флага или указателя, чтобы узнать, была ли получена ответственность за память. Это чтение может быть частью операции InterlockedXxx, в этом случае она включает как чтение, так и запись, но это чтение, указывающее, была ли получена собственность. После получения владения памятью значения обычно считываются из этой памяти или записываются в нее, и очень важно, чтобы эти операции чтения и записи выполнялись после приобретения владения. Барьер для чтения гарантирует это.

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

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

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

Единственное различие между чтением и выпуском записи — расположение барьера памяти. Функция чтения имеет барьер после операции блокировки, а выпуск записи имеет барьер до. В обоих случаях барьер находится между ссылками на заблокированную память и ссылки на блокировку.

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

Использование правильного барьера для предотвращения переупорядочения компилятора и ЦП для вашей платформы является критически важным.

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

Предотвращение переупорядочения компилятора

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

С помощью Visual C++ можно предотвратить переупорядочение компилятора с помощью встроенного _ReadWriteBarrier компилятора. Когда вы вставляете _ReadWriteBarrier в код, компилятор не перемещает операции чтения и записи по нему.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

В следующем коде другой поток считывается из массива sprite:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Важно понимать, что _ReadWriteBarrier не вставляет никаких дополнительных инструкций, и это не препятствует переупорядочению ЦП операций чтения и записи— это только предотвращает их переупорядочение компилятором. Таким образом, _ReadWriteBarrier достаточно при реализации барьера выпуска записи на x86 и x64 (так как x86 и x64 не переупорядочения записей, а обычное запись достаточно для освобождения блокировки), но в большинстве других случаев также необходимо предотвратить переупорядочение операций чтения и записи ЦП.

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

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

Предотвращение переупорядочения ЦП

Переупорядочение ЦП является более тонким, чем переупорядочение компилятора. Вы никогда не видите, что это происходит напрямую, вы просто видите необъяснимые ошибки. Чтобы предотвратить переупорядочение ЦП операций чтения и записи, необходимо использовать инструкции по барьеру памяти на некоторых процессорах. Имя всех назначений для инструкции по барьеру памяти в Xbox 360 и Windows — MemoryBarrier. Этот макрос реализуется соответствующим образом для каждой платформы.

В Xbox 360 MemoryBarrier определяется как lwsync (упрощенная синхронизация), также доступно через встроенные __lwsync, которые определяются в ppcintrinsics.h. __lwsync также служит барьером памяти компилятора, предотвращая изменение порядка операций чтения и записи компилятором.

Инструкция lwsync — это барьер памяти в Xbox 360, который синхронизирует один процессор с кэшем L2. Это гарантирует, что все записи до lwsync делают его в кэшЕ L2 перед записью, следующей. Он также гарантирует, что любые операции чтения, которые следуют lwsync , не получают старые данные из L2, чем предыдущие операции чтения. Один из типов переупорядочения, который он не предотвращает, является чтение впереди записи на другой адрес. Таким образом, lwsync применяет упорядочение памяти, соответствующее упорядочению памяти по умолчанию для процессоров x86 и x64. Чтобы получить полный порядок памяти, требуется более дорогостоящая инструкция синхронизации (также известная как синхронизация в тяжелом весе), но в большинстве случаев это не требуется. Параметры переупорядочения памяти в Xbox 360 показаны в следующей таблице.

Переупорядочение Xbox 360	Синхронизация не выполняется	lwsync	sync
Чтение впереди операций чтения	Да	No	No
Операции записи впереди операций записи	Да	No	No
Записи, перемещающиеся впереди операций чтения	Да	No	No
Чтение впереди операций записи	Да	Да	Нет

 

PowerPC также содержит инструкции по синхронизации isync и eieio (который используется для управления переупорядочением для кэширования замедленной памяти). Эти инструкции по синхронизации не должны быть необходимы для обычных целей синхронизации.

В Windows MemoryBarrier определен в Winnt.h и предоставляет другую инструкцию барьера памяти в зависимости от того, компилируется ли вы для x86 или x64. Инструкция по барьеру памяти служит полным барьером, предотвращая все переупорядочение операций чтения и записи через барьер. Таким образом, MemoryBarrier в Windows дает более надежную гарантию переупорядочения, чем это делает на Xbox 360.

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

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

Инструкция MemoryBarrier запрещает только изменение порядка операций чтения и записи в кэшируемую память. Если вы выделяете память как PAGE_NOCACHE или PAGE_WRITECOMBINE, распространенный метод для авторов драйверов устройств и для разработчиков игр в Xbox 360, MemoryBarrier не влияет на доступ к этой памяти. Большинству разработчиков не нужна синхронизация не кэшируемой памяти. Это выходит за рамки данной статьи.

Переупорядочение межблокируемых функций и переупорядочения ЦП

Иногда чтение или запись, которая получает или освобождает ресурс, выполняется с помощью одной из функций InterlockedXxx. В Windows это упрощает работу; поскольку в Windows функции InterlockedXxx являются всеми барьерами полной памяти. Они фактически имеют барьер памяти ЦП как до, так и после них, что означает, что они являются полным барьером для чтения или записи- выпуска всех самостоятельно.

В Xbox 360 функции InterlockedXxx не содержат барьеры памяти ЦП. Они препятствуют переупорядочению компилятора операций чтения и записи, но не переупорядочения ЦП. Поэтому в большинстве случаев при использовании функций InterlockedXxx в Xbox 360 следует предшествовать или следовать им с __lwsync, чтобы сделать их барьером для чтения или записи. Для удобства и удобства удобочитаемости существуют версии приобретение и выпуск многих функций InterlockedXxx. Они поставляются со встроенным барьером памяти. Например, InterlockedIncrementAcquire выполняет межблоковый добавочный шаг, за которым следует __lwsync барьер памяти для предоставления полной функции получения чтения.

Рекомендуется использовать версии функций InterlockedXxx (большинство из которых доступны в Windows, без штрафа производительности), чтобы сделать намерение более очевидным и упростить получение инструкций по барьеру памяти в правильном месте. Любое использование InterlockedXx на Xbox 360 без барьера памяти следует тщательно изучить, так как это часто ошибка.

В этом примере показано, как один поток может передавать задачи или другие данные другому потоку с помощью версий "Получение и выпуск" функций InterlockedXxSList. Функции InterlockedXxSList — это семейство функций для поддержания общего связанного списка без блокировки. Обратите внимание, что варианты получения и выпуска этих функций недоступны в Windows, но обычные версии этих функций являются полным барьером памяти в Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Переменные и изменение порядка

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

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

Visual C++ 2005 выходит за рамки стандартного C++ для определения многопоточных семантик для доступа к переменным. Начиная с Visual C++ 2005, операции чтения из изменяемых переменных определяются для получения семантики чтения и записи в переменные, для которых задана семантика выпуска записи. Это означает, что компилятор не переупорядочения операций чтения и записи мимо них, и в Windows он гарантирует, что ЦП не делает этого.

Важно понимать, что эти новые гарантии применяются только к Visual C++ 2005 и будущим версиям Visual C++. Компиляторы из других поставщиков обычно реализуют другую семантику без дополнительных гарантий Visual C++ 2005. Кроме того, в Xbox 360 компилятор не вставляет никаких инструкций, чтобы предотвратить переупорядочение операций чтения и записи ЦП.

Пример канала данных без блокировки

Канал — это конструкция, которая позволяет одному или нескольким потокам записывать данные, которые затем считываются другими потоками. Бессерверная версия канала может быть элегантным и эффективным способом передачи работы из потока в поток. Пакет SDK DirectX предоставляет LockFreePipe, одинарный модуль чтения, бессерверный канал записи, доступный в DXUTLockFreePipe.h. Тот же LockFreePipe доступен в пакете SDK Xbox 360 в AtgLockFreePipe.h.

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

Производительность Xbox 360

Производительность инструкций и функций синхронизации в Xbox 360 зависит от того, какой другой код выполняется. Получение блокировок займет гораздо больше времени, если другой поток в настоящее время владеет блокировкой. Операции interlockedIncrement и критически важных разделов будут занимать гораздо больше времени, если другие потоки записываются в ту же строку кэша. Содержимое очередей хранилища также может повлиять на производительность. Таким образом, все эти числа являются всего лишь приблизиниями, созданными из очень простых тестов:

• lwsync измеряется как прием 33-48 циклов.
• InterlockedIncrement измеряется как прием 225-260 циклов.
• Получение или освобождение критического раздела измеряется как принятие около 345 циклов.
• Получение или освобождение мьютекса было измерено как принятие около 2350 циклов.

Производительность Windows

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

Однако даже некоторые измерения, созданные из очень простых тестов, полезны:

• MemoryBarrier измеряется как прием 20-90 циклов.
• InterlockedIncrement измеряется как прием 36-90 циклов.
• Получение или освобождение критического раздела измеряется как прием 40-100 циклов.
• Получение или освобождение мьютекса было измерено как принятие около 750-2500 циклов.

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

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

Мысли о производительности

Получение или освобождение критического раздела состоит из барьера памяти, операции InterlockedXxx и дополнительной проверки для обработки рекурсии и возврата к мьютексу при необходимости. Вы должны быть осторожны в реализации собственного критического раздела, потому что спиннинг в цикле, ожидая блокировки, чтобы быть свободным, не падая обратно в мьютекс, может тратить значительную производительность. Для критически важных разделов, которые сильно утверждаются, но не удерживаются в течение длительного времени, следует рассмотреть возможность использования InitializeCriticalSectionAndSpinCount , чтобы операционная система выполнялась в течение некоторого времени, ожидая, чтобы критически важный раздел был доступен, а не немедленно откладывать на мьютекс, если критически важный раздел принадлежит при попытке получить его. Чтобы определить критические разделы, которые могут воспользоваться счетчиком спинов, необходимо измерить длину типичного ожидания определенной блокировки.

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

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

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

Сводка по различиям платформ

• Функции InterlockedXxx препятствуют переупорядочению операций чтения и записи ЦП в Windows, но не на Xbox 360.
• Чтение и запись переменных с помощью Visual Studio C++ 2005 предотвращает переупорядочение операций чтения и записи ЦП в Windows, но в Xbox 360 только предотвращает изменение порядка чтения и записи компилятора.
• Записи переупорядочены на Xbox 360, но не на x86 или x64.
• Операции чтения переупорядочены на Xbox 360, но в x86 или x64 они переупорядочены только относительно операций записи, и только если операции чтения и записи предназначены для разных расположений.

Рекомендации

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

Ссылки

• "переменная (C++)". Справочник по языку C++.
• Вэнс Моррисон. "Понимание влияния методов низкой блокировки в многопоточных приложениях". MSDN Magazine, октябрь 2005 г.
• Лионс, Майкл. "Модель хранилища PowerPC и программирование AIX". IBM developerWorks, 16 ноября 2005 г.
• Маккенни, Пол E. "Порядок памяти в современных микропроцессорах, часть II". Журнал Linux, сентябрь 2005 г. [В этой статье приведены некоторые сведения о x86.]
• Корпорация Intel. "Упорядочение памяти архитектуры Intel® 64". Август 2007 года. [Относится к процессорам IA-32 и Intel 64.]
• Niebler, Эрик. "Отчет о поездке: нерегламентированное собрание по потокам в C++". Источник C++ 17 октября 2006 г.
• Харт, Томас Э. 2006. "Быстрое выполнение синхронизации без блокировки: последствия для восстановления памяти". 2006 Международный параллельный и распределенный семинар по обработке (IPDPS 2006), Остров Родос, Греция, апрель 2006 года.