Как я создаю незапертую очередь?

Вы, вероятно, могли бы реализовать очередь ограниченного размера с наименьшими трудностями ... Я думал об этом недавно и придумал этот дизайн, но вы, вероятно, можете найти много других интересных идей: (ПРЕДУПРЕЖДЕНИЕ : могут возникнуть проблемы!)

• очередь - это массив указателей на элементы
• , которые вы должны управлять двумя указателями (голова, хвост), которые работают с очередью так же, как кольцевой буфер
• if head == tail , нет элементов
• , если вы хотите поставить в очередь (ptr) , Interlocked-Swap tail с NULL ( prev_tail - значение подкачки)
  • if prev_tail == NULL , попробуйте еще раз
  • if prev_tail + 1 (с переносом) == head , ваша очередь заполнена
  • в противном случае поместите ptr в * prev_tail и назначьте prev_tail + 1 на tail (следите за переносом буфера)
• для dequeue () сделайте копию tmp_head = head и проверьте tmp_head == tail
  • , если это правда, верните, потому что очередь пуста
  • , если это false
    • сохранить * tmp_head как ptr
    • выполнить CAS: сравнить head с tmp_head поменять местами head на head + 1
    • , если CAS не удалось - запустить всю функцию с
    • , если это удалось - вернуть ptr

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

Очереди неограниченного размера «немного» сложнее;) Но вы сможете создать достаточно большую очередь для большинства нужд.