Алгоритм параллельной очереди. Часть 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. Поставщик и потребитель.