Алгоритм параллельной очереди. Часть 4. Полностью не блокирующая очередь для нескольких поставщиков и потребителей.

Продолжение перевода статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Начало: Алгоритм параллельной очереди. Часть 1. Множество поставщиков и потребителей. Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками. Алгоритм параллельной очереди. Часть 3. Поставщик и потребитель.

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

В 1996 г. Michael и Scott опубликовали работу (M. Michael and M. Scott. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"), описывющую два варианта реализации очереди с внутренней синхронизацией. Один из вариантов действительно не блокирующий, другой использует блокировку для поставщиков и еще одну для потребителей, подобно примеру в статье. В 2003 Herlihy, Luchango и Moir показали на проблемы масштабируемости в подходе Michael и Scott представили свою собственную реализацию без блокировок (M. Herlihy, V. Luchango and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues As an Example").

Особенностью описанных подходов является необходимость использования операции сравнить-и-обменять двойной ширины (так же известной как "DCAS"), способной обрабатывать указатель и целый счетчик атомарно. Это достаточно проблемтично, потому что не все платформы имеют операцию DCAS, особенно широко распространенные процессоры, которым потребуется к тому же 128 битный CAS (Мы можем заставить это заработать и для 64 бит через героические попытки исхитриться обокрасть 64 битное пространство, допуская, что большинсво операционных систем сегодня на самом деле не используют все 64 бита адреса и возможно удасться ухватить пару-тройку битов не заметно. Тем не менее это крайне хрупкое и непортируемое решение, и нет гарантий что и другим людям, тем же разработчикам вашей ОС, не пришла в голову идея умыкнуть пару бит в этом бешенном 64 битном мире, и гонка за них уж началась. В действительности, провернуть подобный трюк вам удасться только если операционная система это вы, ну или ваш лучший друг). В дополнение, потребуется и корректно работающий инициализатор пустого списка.

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

Алгоритм параллельной очереди. Часть 3. Поставщик и потребитель.

Продолжение перевода статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Начало: Алгоритм параллельной очереди. Часть 1. Множество поставщиков и потребителей. Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками.

Поставщик.

Рассмотрим первый из двух основных методов: Produce. Задача состоит в том, что бы позволить им работать на столько параллельно, на сколько возможно:

void Produce(const T& t) {
 Node* tmp = new Node(new T(t));
  while (producerLock.exchange(true)) { }    // вход в критическую секцию
 last->next = tmp;                          // добавить потребителям
 last = tmp;                                // двигаем указатель
 producerLock = false;                      // выход из критической секции
}

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

Во-вторых, мы "применяем" изменения, получая исключительный доступ к хвосту очереди. В цикле while мы пытаемся поменять prodicerLock в true до тех пор, пока старое значение не было false; полученное старое значение true означает, что кто-то другой уже получил доступ в критическую секцию. Подобный цикл while можно прочесть как "до тех пор, пока я не буду единственным, кто поменял значение prodicerLock из false в true". Потом мы можем обновить last->next и, собственно, сам last; это две различные операции доступа (записи) в память, которые не могут быть выполнены одновременно на большенстве процессоров без какой-либо блокировки. В завершении, мы устанавливаем producerLock в false, освобождая критическую секцию.

Потребитель

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

bool Consume(T& result) {
  while(consumerLock.exchange(true)) { }   // вход в критическую секцию

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

  Node* theFirst = first;
 Node* theNext = first->next;
   if(theNext != nullptr) {            // если очередь не пуста
     T* val = theNext->value;          // взять
     theNext->value = nullptr;         // узел
     first = theNext;                  // подвинуть указатель
     consumerLock = false;             // выйти из исключительной секции

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

  result = *val;                // скопируем его обратно
 delete val;                   // удалим значение
 delete theFirst;              // и временный узел
 return true;                  // сообщим об успешном завершении
}

Иначе, нулевое значение theNext, означает, что список пуст и мы можем немедленно выйти из критической секции и вернуть код завершения.

    consumerLock = false;            // выйдем из критической секции
   return false;                    // сообщим, что очередь пуста
 }
};

Продолжение: Алгоритм параллельной очереди. Часть 4. Полностью не блокирующая очередь для нескольких поставщиков и потребителей.

< offtopic > Active Perl, DBD-Pg < /offtopic >

Запишу сюда, что бы не забыть, только не спрашивайте зачем оно мне понадобилось ;).
При использовании связки Active Perl и DBD-Pg возникают проблемы при установке последнего. Делать следует так:

ppm install http://pgfoundry.org/frs/download.php/1891/DBD-Pg-2.10.0-Perl5.10.ppd

Должно поставиться, если проблемы, смотрите сюда: http://pgfoundry.org/projects/dbdpgppm/ у него там домик, ищите рабочую ссылку соответствующую вашей версии perl'а. Далее. Качаете http://pgfoundry.org/frs/download.php/1851/msvcr80.zip, распаковываете туда где лежит ваш perl.exe

Последний штрих. Все это работать не будет :). Копируете <ваш perl>\site\lib\auto\DBD\Pg\Pg.dll.manifest --> <ваш perl>\bin\perl.exe.manifest (внимание, переименуйте файл!).

Подсмотрел здесь.

Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками.

Продолжение перевода статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Начало: Алгоритм параллельной очереди. Часть 1. Множество поставщиков и потребителей.

Базовой структурой данных для очереди выберем однонаправленный список. Для упрощения кода, поместим пограничный пустой элемент в начале очереди, таким образом, логически, первый элемент будет содержаться в узле фактически следующим за первым. Рис. 1 демонстрирует остояние пустой очереди, рис. 2 демонстрирует очередь из нескольких объектов.

Каждый узел содержит указатель на объект T и поле дополнения.

template <typename T>
struct LowLockQueue {
  private:
    struct Node {
      Node( T* val ) : value(val), next(nullptr) { }
      T* value;
      atomic<Node*> next;
      char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };

Как и любая другая разделяемая переменная, указатель next должен быть защищен мьютексом, или, как здесь, объявлен атомарным (C++0x atomic<>, Java/.NET volatile). Поле дополнения, здесь, добавлено что бы гарантировано предупредить поадание двух узлов на одну линию кэша; на практике, в случае непустой очереди, попадание первого и последнего узла очереди на одну линию кэша отрицательно скажется на производительности, вызывая невидимое соперничество между потребителем и поставщиком. Несмотря на то, что дополнение структуры используется здесь и далее, ошибка в том, что мы перестраховываемся: каждый узел будет выделен в куче, что уже добавит накладные расходы распределителя памяти: выравнивание и служебную информацию, сыграющие роль дополнения. Если так, и если мы узнаем величину накладных расходов, мы сможем уменьшить наше внутреннее дополнение пропорционально, что бы размеры Node соответствовали размерам одной линии кэша.

Рис. 1

Рис. 2

Далее, переменные управления очередью:

char pad0[CACHE_LINE_SIZE];

// для потребителяа
Node* first;

char pad1[CACHE_LINE_SIZE - sizeof(Node*)];

// для синхронизации потребителей
atomic<bool> consumerLock;

char pad2[CACHE_LINE_SIZE - sizeof(atomic<bool>)];

// для поставщика
Node* last;

char pad3[CACHE_LINE_SIZE - sizeof(Node*)];

// для синхронизации поставщиков
atomic<bool> producerLock;

char pad4[CACHE_LINE_SIZE - sizeof(atomic<bool>)];

И опять, мы добавляем дополнение что бы обеспечить раздельное положение данных различных потоков в памяти и кэше. Точнее, мы хотим обеспечить пложение данных поставщика и потребителя в различных линиях кэша, кроме того, даже если один поставщик и один потребитель будут активны, необходимо добиться что бы переменные блокировки находились отдельно, и потребители ожидающие consumerLock не влияли на линию кэша, содержащую first, которую обновляет активный потребитель, а поставщики, ожидающие producerLock, не замедляли активного поставщик, обновляющего last.

Конструктор всего лишь инициализирует начальное пустое состояние, а деструктор (в .NET или Java, это выполнит сборщик мусора), проходит по внутреннему списку и и уничтожает элементы.

public:
LowLockQueue() {
 first = last = new Node( nullptr );
 producerLock = consumerLock = false;
}
~LowLockQueue() {
 while( first != nullptr ) {        
   Node* tmp = first;
   first = tmp->next;
   delete tmp->value;      
   delete tmp;
 }
}

Продолжение: Алгоритм параллельной очереди. Часть 3. Поставщик и потребитель.

Мы в Microsoft всегда считаем, что стандарт можно улучшить.

Цитата, вынесенная в заголовок, уже стала крылатой (вот источник: "Основы COM" Дейл Роджерсон). И правда, могут...

Visual C++ departs from the ANSI Standard in its implementation of exception specifications. The following table summarizes the Visual C++ implementation of exception specifications:
...

throw(type): The function can throw an exception of type type. However, in Visual C++ .., this is interpreted as throw(...). (MSDN)