Изменения

'''Стек Трайбера''' (англ. ''Treiber Stack'') — масштабируеммый стек без блокировок (англ. ''lock-free'' стек) . Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber<ref>[http://domino.research.ibm.com/library/cyberdig.nsf/0/58319a2ed2b1078985257003004617ef?OpenDocument R. Kent Treiber {{---}} Systems Programming: Coping with Parallelism, 1968]</ref>. Алгоритм использует примитив <tex>CAS</tex> ''(compare and set)''.

Основное отличие Treiber stack стека Трайбера от однопоточного случая заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Чтобы не получилась каша, хотелось бы Необходимо как-то контролировать процесс взаимодействия потоков. Конечно, это можно было бы сделать просто блокируя каждую операцию, производимую на стеке. Но такая блокировка не есть хорошо, ведь тем самым мы уменьшаем параллелизм, а значит, уменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потоком потокам работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.=== Lock-freedom free алгоритмы и CAS ===Свойство неблокируемости (англ. ''Lock-freedom'' ) гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.

'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументовпервым аргументом, и в случае успеха записывающая второй аргумент в память.