Очередь Майкла и Скотта — различия между версиями
(→Структура очереди) |
(→Структура очереди) |
||
| Строка 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>node</tex> является последним в списке, то его <tex>net</tex> указывает на null. | ||
Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста. | Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста. | ||
Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>. | Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>. | ||
| + | |||
| + | '''class''' Queue<T>: | ||
| + | dummy = new Node(null, new AtomicReference<Node>(null)) | ||
| + | head = new AtomicReference<Node>(dummy) | ||
| + | tail = new AtomicReference<Node>(dummy) | ||
==Примечания== | ==Примечания== | ||
Версия 17:24, 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>>)
Если узел является последним в списке, то его указывает на null.
Сама очередь состоит из двух указателей: на голову и на хвост , которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.
Узел списка, на который указывает , является фиктивным (dummy). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного dummy-элемента, на который указывают и .
class Queue<T>:
dummy = new Node(null, new AtomicReference<Node>(null)) head = new AtomicReference<Node>(dummy) tail = new AtomicReference<Node>(dummy)
Примечания
Источники информации
- Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
