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

Ф>>Без блокировок совсем не выходит, название "lock-free" — это обман.

V>Всё-таки, взаимных блокировок не происходит, и это важно...
V>Вот там мьютексы были паиньками...

Я таки настаиваю, что название "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'у и может быть им заменён.

Ф>>Проблема в переключении контекстов, в том что они долгие/медленные?
V>Да. Переключение контекстов заставляет перепрошивать внутренние таблицы виртуальной памяти, т.е. подтягивать эти таблицы, считай, в кеш 0-го уровня.
V>Помимо этого, переключение потока дорогое еще для потока, который вытесняют, потому что его ставят в очередь потоков, а это приоритетная очередь, операции в которой относительно затратны. А если поток вытесняется из-за блокирующего ожидания на примитиве синхронизации, то еще поток ставят в очередь к примитиву синхронизации.

Я в общем-то знал, что поход в ядро — дорогое удовольствие, просто хотел намекнуть, что это необязательно: во многих случаях вполне можно обойтись spin-wait'ом. Притом многие это понимают, и я юзал такие интерфейсы, вот пример:
https://github.com/scumware/RTSS_time_reader/blob/87d6308bec5c5e0a6e8c1b89392f1c21b899906c/RTSS_interop/OSD.cs#L415

 Thread.SpinWait(100);

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

Однако о виндовом шедуллере всерьёз не задумывался. Мне всегда хватало твёрдого знания того, что поход в ядро — дорого.

Ф>>..."lock-free" — это обман.
V>Никакого обмана. ))

Я про название.

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

Ужасная терминология.