Не нужны ли эти строки в очереди без блокировки?

Вот код из очереди без блокировки, использующей CompareAndSet (в Java):

public void enq(T value) {
    Node newNode = new Node(value);
    while(true) {
        Node last = tail.get();
        Node next = last.next.get();

        if(last != tail.get())
            continue;   //???       

        if (next != null) { //improve tail
            tail.compareAndSet(last, next);
            continue;
        }

        if (last.next.compareAndSet(null, newNode)) {   //update last node
            tail.compareAndSet(last, newNode);  //update tail
            return;
        }
    }
}

public T deq() throws EmptyException {
    while(true) {
        Node first = head.get();
        Node last = tail.get();
        Node next = first.next.get();

        if(first != head.get())
            continue;   //???

        if(first == last) {
            if (next == null)
                throw new EmptyException();

            tail.compareAndSet(last, next);
            continue;
        }

        T value = next.value;
        if (head.compareAnsdSet(first, next)) {
            return value;
        }
    }
}

(голова и хвост являются членами очереди)

В обеих функциях deq и enq первая проверка мне не нужна. (Те, кто прокомментировал с "???") Я подозреваю, что это просто для какой-то оптимизации.

Я что-то здесь упускаю? Эти проверки влияют на правильность кода?

(Код взят из «Искусства многопроцессорного программирования», хотя я реорганизовал стиль кода, чтобы иметь меньше вложенных if и elses, сохраняя при этом эквивалентность кода)

7 голосов | спросил Shiroko 23 MarpmWed, 23 Mar 2011 16:11:56 +03002011-03-23T16:11:56+03:0004 2011, 16:11:56

3 ответа


0

Да, в Java, учитывая, что в нем есть сборка мусора, эти if-ы имеют только реальную ценность в качестве оптимизации, и она довольно большая: CAS невероятно дорог по сравнению с простым чтением из памяти, поэтому убедитесь, что значение не имеет Тем временем он изменился и, таким образом, снижает вероятность сбоя в последующем CAS, помогает уменьшить количество повторных попыток CAS, что повышает производительность.

Вы также можете переместить первый == последний & & проверка обновления хвоста внутри головы. CAS, как дальнейшая оптимизация: хвост может отставать только в том случае, если голова была обновлена, поэтому проверка только в случае успеха CAS имеет смысл. Вы также можете переместить tail.get туда, так как он вам больше не нужен. Пример кода ниже. Надеюсь, это поможет!

public T deq() throws EmptyException {
while(true) {
    Node first = head.get();
    Node next = first.next.get();

    if (first != head.get())
        continue;

    if (next == null) {
        throw new EmptyException();
    }

    T value = next.value;

    if (head.compareAndSet(first, next)) {
        Node last = tail.get();

        if (first == last) {
            tail.compareAndSet(last, next);
        }

        return value;
    }
}

}

ответил llongi 23 MarpmWed, 23 Mar 2011 16:43:13 +03002011-03-23T16:43:13+03:0004 2011, 16:43:13
0

Они не являются необходимыми, но используются по соображениям производительности, обратите внимание, что проверка происходит без использования атомарной операции.

Пример стоимости от MSDN

  • MemoryBarrier измерялся как 20-90 циклов.
  • Измерение InterlockedIncrement составило 36-90 циклов.
  • Получение или освобождение критической секции измерялось как принятие 40-100 циклов.
  • Получение или освобождение мьютекса измерялось в 750–2500 циклах.

Справочник по этой конкретной технике:

  

[Rudolph & Сегалл 84] Рудольф Л. и   Сегалл З. Динамический Децентрализованный   Схемы кэширования для MIMD Parallel   Процессоры. Invù roceedingsof   Ежегодный симпозиум   Компьютерная архитектура, страницы   340i ›347, 1984.

ответил Steve-o 23 MarpmWed, 23 Mar 2011 16:38:19 +03002011-03-23T16:38:19+03:0004 2011, 16:38:19
0

это неблокирующий алгоритм связанного списка. Подробное описание приведено в книге JCP (15.4.2. Неблокирующий связанный список)

ответил yetanothercoder 25 MarpmFri, 25 Mar 2011 12:21:43 +03002011-03-25T12:21:43+03:0012 2011, 12:21:43

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132