Очередь Майкла и Скотта — различия между версиями
(Новая страница: «{{В разработке}} '''Очередь Майкла и Скотта''' ''(Michael-Scott Queue)'' - алгоритм построения lock-free очер…») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
'''Очередь Майкла и Скотта''' ''(Michael-Scott Queue)'' - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье <ref>[http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf? Simple, Fast, and Practical Non-Blocking and BlockingConcurrent Queue Algorithms]</ref>. | '''Очередь Майкла и Скотта''' ''(Michael-Scott Queue)'' - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье <ref>[http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf? Simple, Fast, and Practical Non-Blocking and BlockingConcurrent Queue Algorithms]</ref>. | ||
| − | == | + | == Структура очереди == |
| + | Очередь моделируется с помощью односвязного списка. Каждый элемент списка (<tex>Node</tex>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно). | ||
| + | |||
| + | '''data class''' Node<T>('''val''' data: T, '''val''' next: AtomicReference<Node<T>?>) | ||
| + | |||
==Примечания== | ==Примечания== | ||
Версия 11:13, 1 октября 2018
Эта статья находится в разработке!
Очередь Майкла и Скотта (Michael-Scott Queue) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье [1].
Структура очереди
Очередь моделируется с помощью односвязного списка. Каждый элемент списка () содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).
data class Node<T>(val data: T, val next: AtomicReference<Node<T>?>)
Примечания
Источники информации
- Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
