Очередь Майкла и Скотта — различия между версиями
(→Структура очереди) |
(→Структура очереди) |
||
| Строка 6: | Строка 6: | ||
'''case class''' Node<T>('''val''' data: T, '''val''' next: AtomicReference<Node<T>>) | '''case class''' Node<T>('''val''' data: T, '''val''' next: AtomicReference<Node<T>>) | ||
| + | |||
| + | Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста. | ||
| + | |||
| + | Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>. | ||
==Примечания== | ==Примечания== | ||
Версия 17:20, 1 октября 2018
Эта статья находится в разработке!
Очередь Майкла и Скотта (Michael-Scott Queue) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье [1].
Структура очереди
Очередь моделируется с помощью односвязного списка. Каждый элемент списка () содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).
case class Node<T>(val data: T, val next: AtomicReference<Node<T>>)
Сама очередь состоит из двух указателей: на голову и на хвост , которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.
Узел списка, на который указывает , является фиктивным (dummy). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного dummy-элемента, на который указывают и .
Примечания
Источники информации
- Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
