Оптимальный порядок памяти для алгоритма блокировки без блокировки

Question

Каковы оптимальные настройки для барьеров памяти NQFENCE и DQFENCE в следующем закодированном алгоритме C++ 11 для блокировки свободного пакета?

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

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

Объяснение: операции dequeue начинаются с нуля и заменяют указатель NULL для значения. Если результат не равен NULL, верните его, застряв там NULL. В противном случае мы заменили NULL на NULL, поэтому мы увеличиваем индекс слота и повторяем после сна.

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

Мы не отслеживаем местоположения головы или хвоста, потому что это потребует дополнительных ограничений и вреда в бесконтактных операциях. Когда есть конкуренция, может потребоваться дополнительное время для поиска массива для подходящего слота, однако это может быть желательно!

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

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

#include <atomic> 
#include <stdlib.h> 

#define NQFENCE ::std::memory_order_cst 
#define DQFENCE ::std::memory_order_cst 

struct bag { 
    ::std::atomic <void *> volatile *a; 
    size_t n; 

    bag (size_t n_) : n (n_), 
    a((::std::atomic<void*>*)calloc (n_ , sizeof (void*))) 
    {} 

    void enqueue(void *d) 
    { 
    size_t i = 0; 
    while 
    (
     (d = ::std::atomic_exchange_explicit(a + i, d, 
     NQFENCE)) 
    ) 
    { 
     i = (i + 1) % n; 
     SLEEP; 
    } 
    } 
    void *dequeue() 
    { 
    size_t i = 0; 
    void *d = nullptr; 
    while 
    (
     !(d = ::std::atomic_exchange_explicit(a + i, d, 
     DQFENCE)) 
    ) 
    { 
     i = (i + 1) % n; 
     SLEEP; 
    } 
    return d; 
    } 
}; 

Answer 1

Если value, который хранится в пакете используется «как есть», с помощью внешнего кода (например, printf("Value: %p", value);), то никаких ограничений порядка памяти не требуется; то есть NQFENCE и DQFENCE может быть только ::std::memory_order_relaxed.

В противном случае (например value является указателем на структуру/объект, какие поля имеют Sence), NQFENCE должен быть ::std::memory_order_release для убедитесь, что поля объекта инициализируются перед публикацией объекта. Что касается DQFENCE, это может быть ::std::memory_order_consume в случае простого объекта с полями, поэтому поле каждого значения будет выбрано после самого значения. В общем случае ::std::memory_order_acquire следует использовать для DQFENCE. Таким образом, каждая операция памяти, выполняемая производителем до публикации значения, будет видна потребителю.

Когда говорят о производительности, то достаточно иметь NQFENCE только на первой итерации в enqueue(), другие итерации могут safetly использовать ::std::memory_order_relaxed:

void enqueue(void *d) 
    { 
    size_t i = 0; 
    if(d = ::std::atomic_exchange_explicit(a + i, d, 
     NQFENCE)) 
    { 
     do 
     { 
     i = (i + 1) % n; 
     SLEEP; 
     } while(d = ::std::atomic_exchange_explicit(a + i, d, 
     ::std::memory_order_relaxed)); 
    } 
    } 

Similary, только последней итерации в dequeue() требуется DQFENCE. Поскольку последняя итерация может быть обнаружена только после атомной операции, универсальной оптимизации для этого случая нет. Вы можете использовать дополнительный забор вместо того памяти:

void *dequeue() 
    { 
    size_t i = 0; 
    void *d = nullptr; 
    while 
    (
     !(d = ::std::atomic_exchange_explicit(a + i, d, 
     ::std::memory_order_relaxed)) 
    ) 
    { 
     i = (i + 1) % n; 
     SLEEP; 
    } 

    ::std::atomic_thread_fence(DQFENCE); 
    return d; 
    } 

Это обретут Perfomance в случае, когда atomic_exchange_explicit на самом деле быстрее расслабленном порядка, но потерял Perfomance, если эта операция уже подразумевает последовательное упорядочение (см Антона comment) ,