16
правок
Изменения
→Lock-freedom алгоритмы и CAS: дизайн
#При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
=== Lock-freedom алгоритмы и CAS ===
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Важное Другое важное свойство - — неблокируемость. Свойство ''Lock-freedom '' гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.
{{Определение
|definition=
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память.
}}
Ниже представлен псевдокод операции <tex>CAS</tex>.
fun cas(p, old, new): bool {
if *p ≠ old {
return true
}
<tex>CAS операция </tex> используется для реализации таких примитивов синхронизации, как ''mutex '' и ''semaphore''. Это своебразный своеобразный базовый "кирпичик " для ''Lock-freedom '' алгоритмов, ведь если <tex>CAS </tex> привел к неудачи, то кто-то другой изменил старое значение. Таким образом, прогресс в системе есть. <tex>CAS </tex> реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и C.
== Алгоритм ==
=== Структура стека ===
