ABA + Memory Reclamation

Question 1

What is the ABA problem?

Answer 1

Thread 1 reads a value. thread 2 interrupts and changes it. thread 1 writes original value back again (nodes are recycled)

Question 2

ABA problem in the book.

Answer 2

Head ends up pointing to a node that is
not in the queue anymore, but has been
added to the free-list

Question 3

Solution to ABA

Answer 3

Each pointer should have a counter. it is unique over the lifetime of the node.

Question 4

What class should we use for the pointer

Answer 4

AtomicStampedReference class

Question 5

What happens to nodes if we dequeue them

Answer 5

we depend on built-in garbage collection to remove them from memory

Question 6

Solution to no garbage collector:

Answer 6

each thread has own private free-list of unused queue entries

Question 7

how does enqueue and dequeue work for the free-lists

Answer 7

enq = get node from free list
deq = add removed node to free-list

Question 8

What should we do if the free-list is empty

Answer 8

allocate new node through dynamic memory

Question 9

Problem with free list?

Answer 9

when nodes are recycled = ABA problem