Очередь Майкла и Скотта

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Очередь Майкла и Скотта (Michael-Scott Queue) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье [1].

Структура очереди

Очередь моделируется с помощью односвязного списка. Каждый элемент списка ([math]Node[/math]) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

data class Node<T>(val data: T, val next: AtomicReference<Node<T>?>)
    

Примечания

Источники информации

  • Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230