ABA в алгоритмах без блокировки

Я понимаю проблему ABA. Но вещь, которую я не могу понять: они говорят, что в языках, имеющих автоматическую сборку мусора, это может не показываться. Итак, мои вопросы:

  • Как автоматическая сборка мусора предотвращает возникновение проблемы ABA?
  • Это возможно в Java, и если да, то как?
  • Можно ли предотвратить это?
Источник

4 ответа

Решение

  • Когда включена автоматическая сборка мусора, никакие два объекта не могут быть выделены с одной и той же ссылкой и сосуществовать в одно и то же время, потому что до тех пор, пока количество ссылок превышает 0, сама ссылка не будет освобождена и использована повторно.,

    таким образом, вы не можете "переключить" содержимое ссылки на "точку" для другого объекта, в то время как у кого-то еще есть старая ссылка.

Источник

Задача ABA ортогональна сборке мусора. Например, приложения могут перемещать объекты из связанного списка в свободный список, а затем снова использовать их обратно. Следовательно, объект никогда не освобождается до повторного использования. С учетом сказанного, проблема ABA может произойти следующим образом:

Thread1:
    prevHead = head;

Thread2:
    prevHead = head;
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);

Thread3:
    prevHead = head;
    newHead = getFromFreeList(); // Get the same object 'released' by Thread2
    cas(&head, prevHead, newHead) // succeeds and put back what was removed by Thread2

Thread1:
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);
    // CAS will succeed although it shouldn't since there were
    // a modification on the head done by 'Thread3' in between.
Источник

Как автоматическая сборка мусора предотвращает возникновение проблемы ABA? Смотрите "Искусство многопроцессорного программирования" Херлихи Шавита. Цитата: Это (проблема ABA) часто появляется, особенно в алгоритме динамической памяти.

Так что, конечно, проблема ABA может появиться в Java, но, поскольку в большинстве случаев проблема возникает в алгоритме динамической памяти, и вы не часто реализуете такой алгоритм в Java, вы не увидите эту ошибку в Java очень часто.

Это возможно в Java, и если да, то как? В книге "Искусство многопроцессорного программирования" приведен пример на Java для этой проблемы, связанной с восстановлением памяти для параллельной очереди без блокировки.

Можно ли предотвратить это? Цитата: Избегайте ABA, проверяя, не является ли значение одинаковым в два момента времени, но не меняется ли значение между этими точками. Один из способов сделать это - использовать AtomicStampedReference.

Источник

В книге "Искусство многопроцессорного программирования" авторы обсуждают ситуации, в которых программисты могут захотеть реализовать свой собственный пул ресурсов (например, пул узлов списка) в Java. Затем программисты, непосредственно управляющие пулом, обходят сборку мусора, что повышает производительность. Тем не менее, следует соблюдать осторожность, чтобы избежать проблемы ABA.

Вот ядро ​​Java-кода для управления памятью в Java:

ThreadLocal<Node> freeList = new ThreadLocal<Node>() {
    protected Node initialValue() { return null; };
};

Полный код LockFreeQueueRecycle.java доступен здесь:

http://booksite.elsevier.com/9780123705914/exercises/07~Chapter_10.zip

Смотрите слайды и код для главы 10 на:

http://booksite.elsevier.com/9780123705914/?ISBN=9780123705914

Источник
Другие вопросы по тегам