Ищете критику моей потоковой безопасной реализации без блокировки

Question

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

Вот заголовок:

template <class T> 
class LockFreeQueue 
{ 
public: 
    LockFreeQueue(uint buffersize) : buffer(NULL), ifront1(0), ifront2(0), iback1(0), iback2(0), size(buffersize) { buffer = new atomic <T>[buffersize]; } 
    ~LockFreeQueue(void) { if (buffer) delete[] buffer; } 

    bool pop(T* output); 
    bool push(T input); 

private: 
    uint incr(const uint val) 
     {return (val + 1) % size;} 

    atomic <T>* buffer; 
    atomic <uint> ifront1, ifront2, iback1, iback2; 
    uint size; 
}; 

А вот реализация:

template <class T> 
bool LockFreeQueue<T>::pop(T* output) 
{ 
    while (true) 
    { 
     /* Fetch ifront and store it in i. */ 
     uint i = ifront1; 

     /* If ifront == iback, the queue is empty. */ 
     if (i == iback2) 
      return false; 

     /* If i still equals ifront, increment ifront, */ 
     /* Incrememnting ifront1 notifies pop() that it can read the next element. */ 
     if (ifront1.compare_exchange_weak(i, incr(i))) 
     { 
      /* then fetch the output. */ 
      *output = buffer[i]; 
      /* Incrememnting ifront2 notifies push() that it's safe to write. */ 
      ++ifront2; 
      return true; 
     } 

     /* If i no longer equals ifront, we loop around and try again. */ 
    } 
} 

template <class T> 
bool LockFreeQueue<T>::push(T input) 
{ 
    while (true) 
    { 
     /* Fetch iback and store it in i. */ 
     uint i = iback1; 

     /* If ifront == (iback +1), the queue is full. */ 
     if (ifront2 == incr(i)) 
      return false; 

     /* If i still equals iback, increment iback, */ 
     /* Incrememnting iback1 notifies push() that it can write a new element. */ 
     if (iback1.compare_exchange_weak(i, incr(i))) 
     { 
      /* then store the input. */ 
      buffer[i] = input; 
      /* Incrementing iback2 notifies pop() that it's safe to read. */ 
      ++iback2; 
      return true; 
     } 

     /* If i no longer equals iback, we loop around and try again. */ 
    } 
} 

EDIT: Я сделал некоторые важные изменения в коде, основываясь на комментариях (Спасибо KillianDS и н.м.!). Самое главное, ifront и iback теперь являются ifront1, ifront2, iback1 и iback2. push() теперь увеличит iback1, уведомив другие толки, которые они могут безопасно записать в следующий элемент (пока он не заполнен), напишите элемент, а затем увеличьте iback2. iback2 - это все, что проверяется pop(). pop() делает то же самое, но с индексами ifrontn.

Теперь я снова попадаю в ловушку «Это СЛЕДУЕТ работать ...», но я ничего не знаю о формальных доказательствах или что-то в этом роде. По крайней мере, на этот раз я не могу представить себе потенциальный способ, которым он может потерпеть неудачу. Любые советы приветствуются, за исключением того, что «перестаньте писать код без блокировки».

Answer 1

Нет, это не поточно - рассмотрим следующую последовательность событий: если

1. Первый поток завершает if (ifront.compare_exchange_weak(i, incr(i))) в pop и засыпает планировщиком.
2. Вторые вызовы потоков push size раз (достаточно, чтобы сделать ifront равным значению i в первом потоке).
3. Первая нить просыпается.

В этом случае pop buffer[i] будет содержать последнее нажатое значение, что неверно.

Answer 2

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

Рассмотрим это:

ifront = iback = 0

Нажмите вызывается и CAS увеличивает значение iback 0 -> 1. Однако нить теперь получить заглох перед тем-х буфера [0] присваивается.

ifront = 0, iback = 1

Pop теперь называется. CAS увеличивается ifront 1 -> 1, а буфер [0] считывается до его назначения.

Выдается устаревшее или недопустимое значение.

PS. Поэтому некоторые исследователи попросили DCAS или TCAS (Di и Tri CAS).

Answer 3

Правильный способ приблизиться к структуре данных без блокировки - написать полуформальное доказательство того, что ваш проект работает в псевдокоде. Вы не должны спрашивать «это безопасный безопасный поток кода», а скорее «подтверждает ли мое доказательство, что этот бесплатный код без потолка имеет какие-либо ошибки?"

Только после того, как у вас есть формальное доказательство того, что псевдо-код проектных работ вы пытаетесь реализовать. Часто это приводит к свету такие вопросы, как сбор мусора, которые должны быть тщательно обработаны.

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

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

Непосредственно ta король и попытка проверить, что он заблокирован, непрактичен. Доказательство - важная вещь в правильном проектировании такого рода вещей, фактический код является вторичным, поскольку доказательство является трудной частью.

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

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

Определение того, что куча кода «потокобезопасна» ставит всю нагрузку на других людей. У вас должен быть аргумент, почему ваш код «является потокобезопасным», устроенный таким образом, чтобы было как можно проще найти другие дыры в нем. Если ваш аргумент, почему ваш код «является потокобезопасным», устроен таким образом, что затрудняет поиск дыр, ваш код не может считаться потокобезопасным, даже если никто не может обнаружить дыру в вашем коде.

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