Здравствуйте, remark, Вы писали:

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

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

Два попутных вопроса:
1. А кто автор алгоритма, Вы?
2. Нет ли c# версии? Я его конечно переписал на шарп, но где-то видать накосячил, не взлетело (хотя в одном потоке работает).

Основной вопрос:

Возможна ли следующая ситуация:

Вызвали конструктор, имеем пустую очередь, и инициализированый след. образом seq массив:

enqueue = 0 
dequeue = 0
<0> <1> <2> <3>....

Первый поток начинает добавлять элемент, инкрементировал enqueue, но не успел обновить seq[0] — заснул. Имеем след. картину:

enqueue = 1
dequeue = 0
<0> <1> <2> <3>....

Второй поток добавляет след.элемент, получаем ([2] — скобками показываю что даже данные положили):

enqueue = 2
dequeue = 0
<0> [2] <2> <3>....

Сейчас в очереди имеется один элемент, пытаемся его вытащить, во втором потоке, первый поток все еще спит.

dequeue = 0
seq[0] == 0

а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!

intptr_t dif = (intptr_t)seq - (intptr_t)(pos + 1);