Неблокирующие межпроцессные коммуникации

Александр в данное время работает главным инженером по программному обеспечению в Computer Associates. По вопросам данной статьи с ним можно связаться по адресу lock-free@hotmail.com.

Предисловие

Некоторое время назад я заинтересовался такой задачей: найти способ межпроцессного (или межпотокового) обмена информацией, который предъявлял бы минимальные требования к платформе и не требовал бы наличия у процессора специальных команд. Данная статья описывает способ обмена данными между процессами/потоками безо всяких блокировок, который не требует никаких специальных команд. Единственным условием нормальной работы этих алгоритмов является знание размера машинного слова для данной платформы (processor word length).

Многие "безблокировочные" средства межпроцессных коммуникаций требуют наличия у процессора специальных "атомарных" команд (Прим. перев.: имеются в виду команды, выполняющие в одной неделимой транзакции запись всего блока данных, гарантирующие, что в это время другие задачи, даже выполняющиеся на другом процессоре, не вмешаются). В данной статье я предлагаю способ коммуникации, требующий лишь "атомарной", непрерывной записи одного машинного слова из процессорного кэша в основную память и "атомарное" чтение машинного слова из памяти в кэш или регистр процессора. Насколько мне известно, все платформы удовлетворяют этому требованию, если данные соответствующим образом выровнены - обычно такой границей выравнивания является опять же машинное слово. (Прим. перев.: на самом деле блокировки обычно происходят, но на самом низком аппаратном уровне - на уровне шины данных. Но программисту, конечно же, не стоит об этом задумываться и беспокоиться). Позже мы обсудим проблемы, связанные с кэшем.

На основе этого механизма коммуникаций, я предлагаю реестр, допускающий изменение данных, и в то же время дающий прирост производительности при чтении линейно с увеличением количества процессоров. Будут предложены результаты тестов, проведенных как на однопроцессорных системах, так и многопроцессорных. Эти тесты показывают, что прирост производительности на некоторых платформах составляет в 30 раз и более (>=3000%).

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

Алгоритм первый

Данный алгоритм продемонстрирует саму идею, приведенную в предисловии к статье. Будем рассматривать простейший случай: есть только два процесса (или потока. В данной статье я буду поочередно использовать эти понятия). Назовем их Писатель и Читатель. Писатель передает одно ненулевое машинное слово Читателю и, более того, получает подтверждение прочтения этого слова Читателем. Это осуществляется записью слова в разделенную память, доступную как Писателю, так и Читателю. При этом очень важно, чтобы эта область памяти была выровнена по границе машинного слова - это и обеспечит "атомарность" записи и чтения.

Собственно алгоритм состоит из следующих шагов.

1. Первоначальное состояние машинного слова в разделенной области памяти: оно содержит ноль.
2. Когда Писателю необходимо передать ненулевое значение Читателю, он пишет это значение в разделенную область.
3. Читатель постоянно (в цикле) проверяет значение слова и сравнивает его с нулем. Цикл продолжается, пока значение нулевое. Ненулевое значение является признаком того, что данные в разделенной области появились и доступны для чтения, и, кроме того, это же значение и есть данные.
4. Читатель пишет в эту же область снова нулевое значение. Это - признак того, что информация "дошла" до Читателя.
5. Писатель постоянно проверяет значение слова и сравнивает его с нулем. Значение, равное нулю, говорит о том, что Читатель прочитал данные и разделенная область готова к новой передаче данных.

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

Алгоритм второй (канал "лайт")

Здесь используются также два процесса - те же Писатель и Читатель. Писатель пишет данные в разделенную область (для краткости будем называть ее буфером), а процесс читателя читает последовательные данные из буфера. Буфер также выровнен на машинное слово и первоначально заполнен нулевыми значениями, но содержит (может содержать) не одно слово, а некоторое известное и Писателю, и Читателю целое количество слов. Данные записываются Писателем последовательно, слово за словом, начиная с нулевого слова. Как и в первом алгоритме, данные должны содержать лишь ненулевые значения - ноль является особым значением (позже будет показано, как можно снять это ограничение). Перед тем, как записать очередное слово, Писатель должен проверить значение по очередному адресу на ноль. Если значение нулевое - можно записывать, если же ненулевое - придется ждать, пока там появится нулевое значение. Вот некий псевдокод Писателя:

 
int i = 0;
while( true ) {
    while( SharedMemory[i] != 0 ) {
        DoSomethingUseful();  // Или просто ждать, ничего не делая
    }
    SharedMemory[i] = GetDataToPassToAnotherProcess();
    i = (i+1) mod N;
}

Читатель читает значения из буфера последовательно, слово за словом, начиная с нулевого. Когда очередное значение равно нулю, это означает, что очередных данных нет и нужно ждать их появления, т. е. появления ненулевого значения. После прочтения ненулевого значения Читатель пишет сюда же нулевое значение - признак того, что эти данные прочитаны и Писатель сюда может писать, и двигается к следующему адресу. После прочтения слова номер N-1 (N - размер буфера в машинных словах), процесс переходит снова к нулевому слову (т. е. по сути буфер работает циклически). Вот псевдокод Читателя:

int i = 0;
while( true ) {
    word theWord;
    while( (theWord = SharedMemory[i]) == 0 ) {
        DoSomethingUseful();  // Можно просто ждать, ничего не делая
    }
    SharedMemory[i] = 0;
    ProcessDataReceivedFromTheFirstProcess(theWord);           // Обработаем полученные данные
    i = (i+1) mod N;
}

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

Передача нулевых значений

Вернемся к вопросу о возможности передачи нулевых значений. Решить этот вопрос можно с помощью кодирования. Например, M произвольных слов (т. е. не обязательно ненулевых) кодируются с помощью M+1 ненулевого слова (M Алгоритм третий (канал с кэш-оптимизацией)

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

1. Внутренние данные Писателя и Читателя должны находиться в разных строках кэша. Если имеется несколько уровней кэша, следует брать в учет наибольшую строку кэша.
2. Разделенная область (буфер) должен быть выровнен по размеру строки кэша. При этом следует брать в учет наибольшую строку из всех уровней кэша.
3. Алгоритм Читателя следует модифицировать:

 
int cacheLineLengthInWords = 8;            // Зависит от аппаратной платформы
int i = 0;
while( true ) {
    word theWord;
    while( (theWord = SharedMemory[i]) == 0 ) {
        DoSomethingUseful();  // Или просто ждать
    }
    // Если это последнее слово строки кэша
    if((i +1) mod cacheLineLengthInWords == 0) {
        // Очищаем всю строку кэша
        for(j = 0; j 

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

Алгоритм четвёртый (реестр, оптимизированный для чтения)

Общеизвестна проблема построения "реестра", оптимизированного для чтения и в то же время разрешающего запись. Типичное решение - использовать std::map и ставить блокировки (в случае Windows - критические секции) в моменты записи и чтения. Другое решение, "навеянное" рассмотренными выше алгоритмами, сочетает стандартные средства блокировки (мьютекс - mutex) и описанный выше алгоритм канала. Алгоритм использует основную копию данных реестра (экземпляр класса Registry) и многочисленные копии этих данных, хранящиеся в "видах" реестра (экземпляры класса RegistryView, создаваемые для каждого пользователя).
Собственно канал (см. алгоритм 3) используется для асинхронной передачи изменений, произошедших в основном буфере, пользовательским экземплярам. Любые изменения применяются сначала в основном буфере, затем кодируются и записываются в каналы каждого пользовательского экземпляра.
Каждый пользователь, перед тем как прочесть данные из локальной копии, сначала проверяет, были ли обновления основной копии (путем анализа канала). Если в канале есть данные, они применяются к локальной копии, и уже затем производится чтение необходимых данных. Поскольку обновления данных происходят сравнительно редко, самый распространенный сценарий - когда в канале ничего нет. В этом случае вся проверка сводится к одному-единственному чтению одного слова из канала и сравнению слова с нулем.
Возникают два особых случая.

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

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

Алгоритм 2 сравнивался с алгоритмом 3 и со стандартной версией алгоритма. Тест включал в себя передачу 10 млн. целых (int) от одного потока другому. Стандартный алгоритм выполнял все блокировки при доступе к разделенным ресурсам, причем блокировка выполнялась для каждого целого числа. 

Не следует рассматривать данный тест как некое для обычных приложений - последние обычно не пересылают информацию такими малыми блоками. Однако для некоторых приложений алгоритм 2 или 3 может дать большие преимущества.

Следующий алгоритм сравнивает алгоритм 4 и стандартный алгоритм. Тест включал 8 потоков, каждый из которых производил чтение 1 024 000 раз и вносил изменения 1000 раз.

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

Ссылки:

1. Chandler, Dean. Reduce False Sharing in .NET*, http://www.intel.com/cd/ids/developer/asmo-na/eng/193679.htm?page=1
2. Alexandrescu, Andrei. Lock-free data structures, C/C++ Users Journal, October 2004