Поделиться через

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

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

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

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

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

При написании многопотокового кода часто необходимо совместно использовать данные между потоками. Если несколько потоков одновременно считывают и записывают общие структуры данных, может возникнуть повреждение памяти. Самый простой способ решения этой проблемы — использовать блокировки. Например, если ManipulateSharedData должна выполняться только одним потоком за раз, можно использовать 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-байтовые операции чтения и записи регистров потокового расширения SIMD (SSE) и строковые операции могут быть неатомарными.

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

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

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

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

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

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

Если компилятор или ЦП переупорядочит записи, показанные в следующем коде, другой поток может увидеть, что флаг alive установлен, видя при этом старые значения для 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;

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

// 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 в одной операции. Существует восемь буферов сборки записи, которые позволяют эффективно записывать в несколько различных областей памяти.

Буферы store-gather обычно записываются в кэш 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
Чтения опережают чтения Нет Да
Операции записи впереди операций записи Нет Да
Записи выполняются раньше операций чтения Нет Да
Чтение опережает операции записи Да Да

 

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

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

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

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

Когда ваш код получает владение некоторой памятью, либо путем получения блокировки, либо извлекая элемент из общего связанного списка (без блокировки), всегда происходит чтение — проверка флага или указателя, чтобы убедиться, что владение памятью было получено. Это чтение может быть частью операции 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;
}

Единственное различие между операциями read-acquire и write-release заключается в расположении барьера памяти. Операция чтения-захвата имеет барьер после операции блокировки, а операция записи-освобождения имеет барьер до операции. В обоих случаях барьер находится между ссылками на заблокированную память и ссылки на блокировку.

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

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

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

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

Задание компилятора заключается в агрессивной оптимизации кода для повышения производительности. Это включает в себя переупорядочение инструкций, где это полезно и где это не изменяет поведение. Так как стандарт 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 синхронизация
Чтения опережают чтения Да Нет Нет
Операции записи впереди операций записи Да Нет Нет
Записи выполняются (или обрабатываются) раньше операций чтения Да Нет Нет
Чтение опережает запись Да Да Нет

 

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

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

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

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 барьер памяти для предоставления полной функции получения чтения.

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

В этом примере показано, как один поток может передавать задачи или другие данные другому потоку, используя версии Acquire и Release функций InterlockedXxxSList. Функции 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++ указывает, что считывания volatile переменных не могут быть кэшированы, записи volatile переменных не могут быть отложены, а считывания и записи volatile переменных не могут быть перемещены относительно друг друга. Это достаточно для взаимодействия с аппаратными устройствами, что является целью изменяющегося ключевого слова в C++ Standard.

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

Visual C++ 2005 выходит за рамки стандартного C++, чтобы определить семантику, благоприятную для многопоточного доступа к переменным типа volatile. Начиная с Visual C++ 2005, операции чтения из volatile-переменных имеют семантику захвата при чтении, а записи в volatile-переменные имеют семантику освобождения при записи. Это означает, что компилятор не будет переупорядочивать операции чтения и записи за их пределами, и в 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 они переупорядочены только относительно операций записи, и только если операции чтения и записи направлены на разные адреса.

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

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

Ссылки

 

 

  • Last updated on