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