Викиконспекты - Вклад участника [ru]

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

2018-10-01T16:22:01Z

185.22.181.139: /* Описание проблемы */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При данной реализации мы сталкиваемся со следующей проблемой

== Описание проблемы ==

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>elem</tex> и <tex>elem'</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, и этот алгоритм не lock-free.

== Корректная lock-free реализация ==

=== Основная идея ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T16:21:09Z

185.22.181.139: /* Корректная lock-free реализация */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При данной реализации мы сталкиваемся со следующей проблемой

== Описание проблемы ==

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>6</tex> и <tex>7</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, и этот алгоритм не lock-free.

== Корректная lock-free реализация ==

=== Основная идея ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T16:16:34Z

185.22.181.139:

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При данной реализации мы сталкиваемся со следующей проблемой

== Описание проблемы ==

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>6</tex> и <tex>7</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, и этот алгоритм не lock-free.

== Корректная lock-free реализация ==

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T16:15:46Z

185.22.181.139: /* Описание проблемы */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При этом мы сталкиваемся со следующей проблемой

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T16:15:04Z

185.22.181.139: /* Описание проблемы */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>6</tex> и <tex>7</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, и этот алгоритм не lock-free.

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T16:14:03Z

185.22.181.139: /* Описание проблемы */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>6</tex> и <tex>7</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, мы не получили lock-free алгоритм.

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:04:48Z

185.22.181.139: /* Удаление элемента */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:04:27Z

185.22.181.139: /* Многопоточная реализация */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:03:11Z

185.22.181.139: /* Добавление элемента */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
while (true): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' new EmptyException()
newHead = head.next.get()
if (CAS(H, head, nextHead)):
return newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
while (true): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if (CAS(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
break
while (true): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if (CAS(T, tail, nextTail)):
break

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:02:55Z

185.22.181.139: /* Удаление элемента */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = new Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
while (true): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' new EmptyException()
newHead = head.next.get()
if (CAS(H, head, nextHead)):
return newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
while (true): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if (CAS(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
break
while (true): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if (CAS(T, tail, nextTail)):
break

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:02:32Z

185.22.181.139: /* Структура очереди */

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
return H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = new Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
while (true): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' new EmptyException()
newHead = head.next.get()
if (CAS(H, head, nextHead)):
return newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
while (true): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if (CAS(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
break
while (true): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if (CAS(T, tail, nextTail)):
break

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T15:01:15Z

185.22.181.139:

{{В разработке}}
'''Очередь Майкла и Скотта''' ''(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>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух указателей: на голову <tex>H</tex> и на хвост <tex>T</tex>, которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

'''class''' Queue
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>

==Идея реализации==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
return H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = new Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
while (true): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' new EmptyException()
newHead = head.next.get()
if (CAS(H, head, nextHead)):
return newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
while (true): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if (CAS(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
break
while (true): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if (CAS(T, tail, nextTail)):
break

При этом мы сталкиваемся со следующей проблемой

=== Описание проблемы ===

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

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

2018-10-01T14:48:12Z

185.22.181.139: /* Идея реализации */

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

2018-10-01T14:47:38Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T14:46:42Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T14:45:37Z

185.22.181.139: /* Добавление элемента */

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

2018-10-01T14:39:22Z

185.22.181.139: /* Удаление элемента */

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

2018-10-01T14:38:58Z

185.22.181.139:

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

2018-10-01T14:27:23Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T14:24:28Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T14:20:29Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T10:52:19Z

185.22.181.139: /* Структура очереди */

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

2018-10-01T08:13:44Z

185.22.181.139: