Редактирование: Очередь Майкла и Скотта
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 101: | Строка 101: | ||
'''while''' ('''true'''): <font color=green>//CAS-цикл</font> | '''while''' ('''true'''): <font color=green>//CAS-цикл</font> | ||
tail = T.get() | tail = T.get() | ||
− | + | if ('''CAS'''(tail.next, '''null''', newTail)): | |
− | <font color=green>/* | + | <font color=green> |
− | Если | + | /* |
− | + | Если получилось добавить ещё один элемент в хвост, | |
пробуем передвинуть T. Если не получилось передвинуть T, | пробуем передвинуть T. Если не получилось передвинуть T, | ||
значит, другой поток сделал это за нас, завершаем работу. | значит, другой поток сделал это за нас, завершаем работу. | ||
− | + | если получилось - то мы сами передвинули T, завершаем работу | |
− | */</font> | + | */ |
+ | </font> | ||
'''CAS'''(T, tail, newTail) | '''CAS'''(T, tail, newTail) | ||
'''return''' | '''return''' | ||
− | + | ||
− | + | ||
− | + | ||
− | + | val newTail = Node(x, AtomicReference(null)) | |
− | + | ||
− | + | while (true) { | |
− | + | val tail = T.get() | |
− | + | if (tail.next.compareAndSet(null, newTail)) { | |
+ | /* | ||
+ | Если T - последний добавленный элемент, добавляем ещё один элемент в хвост и | ||
+ | пробуем передвинуть T. Если не получилось передвинуть T, | ||
+ | значит, другой поток сделал это за нас, завершаем работу | ||
+ | */ | ||
+ | T.compareAndSet(tail, newTail) | ||
+ | return | ||
+ | } else { | ||
+ | /* | ||
+ | Если T - не последний элемент, то передвигаем T на последний элемент | ||
+ | Если этого сделать не получилось, значит, это сделал другой поток | ||
+ | В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередь | ||
+ | */ | ||
+ | T.compareAndSet(tail, tail.next.get()) | ||
+ | } | ||
+ | } | ||
== Корректная реализация <tex>pop</tex> == | == Корректная реализация <tex>pop</tex> == |