Здравствуйте, Философ, Вы писали:

Ф>Я таки настаиваю, что название "lock-free" крайне кривое и не отражает сути вещей. Дело не в мьютексах потому что блокировка вполне может быть на spin-wait'е. Посмотри:

Ф>

Ф> private static bool CAS(
Ф>    ref Node<T> location, Node<T> comparand, Node<T> newValue) {
Ф>    return 
Ф>      comparand == Interlocked.CompareExchange<Node<T>>(
Ф>                     ref location, newValue, comparand);
Ф>  }

Ф>  public void Push(T item) {
Ф>    Node<T> node = new Node<T>();
Ф>    node.Item = item;
Ф>    do {
Ф>      node.Next = head.Next;
Ф>    } while (!CAS(ref head.Next, node.Next, node));
Ф>  } 
Ф>

Ф>lock-free stack — классический пример, но тут мы видим модифицированный spin-wait. Цикл в методе Push равнозначен spin-wait'у и может быть им заменён.

Странно рассуждаешь. ))
В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.

И если конкурирующий поток уйдёт в спячку через вытеснение, то очередь не останется надолго заблокированной, как оно было бы при защите обычной очереди мьютексом, если бы перед вытеснением поток завладел бы ресурсом.


Ф>Я в общем-то знал, что поход в ядро — дорогое удовольствие, просто хотел намекнуть, что это необязательно: во многих случаях вполне можно обойтись spin-wait'ом.

Зачастую это плохая практика.
При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.

Тут банально стоит в тестах смотреть, куда и сколько тратиться больше бесполезных тиков — на лишние переключения контекстов или на 10 GOTO 10.
В моих тестах, если данные идут с задержками более ~5 микросекунд (5 миллионных секунды!), то выгодней уходить в спячку, освобождая ресурсы для других задач, чем крутить бесполезный spin-wait.

Например, в твоём цикле указан код писателя.
А что делать читателю в отсутствии данных?

Ну вот покрутил сколько-то spin-wait, дальше что? ))


Ф>Там было вставлено только затем, чтобы в цикл ожидания впихнуть инструкцию PAUSE. В шарпе такой вызов это наиболее простой способ. Это способ экономить электричество: эта инструкция — хинт процессору о том, что тут цикл активного ожидания, она специально для этого создавалась.

Это работает только в многопоточных ядрах, т.к. отдаёт ресурсы ядра процессору другому потоку (гипер-потоку в терминах Интел, например).
Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.


Ф>>>..."lock-free" — это обман.
V>>Никакого обмана. ))
Ф>Я про название.

Я тоже.
См. пример своей очереди выше.

У тебя писатели не блокируют очередь взаимно, и читатели могу читать конкурентно (правда, там за раз можно безопасно забрать только всю накопленную очередь, а не один элемент, но это уже тонкости... зато по этой порции можно уже итерироваться без interlocked-операций)


V>>Просто гонку на CAS выиграет только один из потоков.
Ф>Ужасная терминология.

Сорри, у нас много кальки с английского. ))
В данном случае "a thread that won the race".

В русской терминологии "состязание потоков", конечно.