Чрезмерное использование Interlocked.exchange?

Question

Я пытаюсь понять правильное использование Interlocked.Exchange, поэтому я реализую простой отсортированный LinkedList с функцией добавления и удаления.

Если бы это был не потокобезопасный список, очевидно, чтобы найти точку вставки, у вас было бы что-то вроде приведенного ниже, чтобы найти правильную точку для вставки нового узла.

    public void Insert(int newValue)
    {
        var prev = _header;
        Node curr = _header.Next;

        while(curr != null && curr.value > newValue )
        {
            prev = curr;
            curr = curr.Next;
        }
        var newNode = new Node(newValue, curr);
        prev.Next = newNode;
    }

Ниже мое мнение о том, как вы должны сделать это для одновременного списка. Слишком много заблокировано. Обмен происходит? Без этого вставка была бы все еще потокобезопасной? Могут ли сотни или тысячи операций с блокировками вызывать плохую производительность?

    public void InsertAsync(int newValue)
    {
        var prev = _header;
        Node curr = new Node(0, null);
        Interlocked.Exchange(ref curr, _header.Next);

        while (curr != null && curr.value > newValue)
        {
            prev = Interlocked.Exchange(ref curr, curr.Next);
        }
        //need some locking around prev.next first, ensure not modified/deleted, etc..
        //not in the scope of this question.
        var newNode = new Node(newValue, prev.Next);
        prev.Next = newNode;
    }

Я понимаю, что, например, curr = curr.next является атомарным чтением, но могу ли я быть уверен, что конкретный поток будет читать самое актуальное значение curr.next, без Interlocked?

Answer 1

Используя Interlocked Метод делает две вещи:

1. Он выполняет ряд операций, которые обычно не являются атомарными, и делает их эффективно атомарными. В случае Exchange вы делаете эквивалент: var temp = first; first=second; return temp; но без риска изменения какой-либо переменной другим потоком, пока вы это делаете.
2. Это вводит барьер памяти. Оптимизация компилятора, среды выполнения и / или оборудования может привести к тому, что разные потоки будут иметь локальную "копию" значения, которое технически находится в разделяемой памяти (обычно в результате кеширования переменных). Это может привести к тому, что одному потоку понадобится много времени, чтобы "увидеть" результаты записи в другом потоке. Барьер памяти по сути синхронизирует все эти разные версии одной и той же переменной.

Итак, конкретно на ваш код. Ваше второе решение не является потокобезопасным. Каждый человек Interlocked операция атомарная, но любое количество звонков на различные Interlocked звонки не атомарны. Учитывая все, что вы делаете методами, ваши критические разделы на самом деле намного больше; вам нужно будет использовать lock или другой аналогичный механизм (например, семафор или монитор) для ограничения доступа к разделам кода только для одного потока. В вашем конкретном случае я думаю, что весь метод является критическим разделом. Если вы действительно, очень осторожны, вы можете иметь несколько меньших критических блоков, но в результате будет очень трудно убедиться, что в результате не будет возможных условий гонки.

Что касается производительности, ну, как это код не работает, и поэтому производительность не имеет значения.

Answer 2

Реализация связанного со свободным замком списка немного сложнее, чем эта. Я настоятельно рекомендую вам не делать этого. Просто используйте вместо этого простые старые мониторы. Если это ради интереса, тогда вам нужно провести исследование алгоритмов без блокировки.

Чтобы более прямо ответить на ваш вопрос, стоимость операции с блокировкой зависит от количества разногласий по поводу переменных. В неконкурентном сценарии (например, однопоточном) стоимость крайне минимальна. По мере увеличения числа одновременных обращений стоимость возрастает. Причина в том, что блокированная операция на самом деле не блокируется. Он просто использует аппаратную блокировку вместо программной. По этой причине алгоритмы без блокировок часто работают не так, как вы ожидаете.

Answer 3

Вы только защищаете задания, но они все равно атомарны. Вы должны проверить, действительно ли Обмен произошел.

Но это все равно не сделает ваш список поточно-ориентированным, параллельный поток может вставлять новое значение, большее, чем ваше newValue, перед точкой вставки. Я думаю, что список может даже оказаться сломанным.