Page Comparison

...

• wait until there is need for eviction
• lock head lock
  
  • go through list until the required eviction size is reached
  • change head to new first element
• unlock head lock
• subtract evicted size from total buffer size
• we assume here that eviction will never empty the buffer, so it does not need to acquire the tail lock

Correctness

Checking for possible inconsistent states for the "completely lock-free" approach, by analyzing what happens when two operations are executed in parallel:

1. Dequeue and Evict
   
   • both CAS head first:
     
     • if dequeue succeeds, no eviction is done (first element is different => CAS in eviction fails)
     • if evict succeeds, dequeue fails this time and succeeds next time it tries => the evicted elements are not dequeued
2. several enqueues
   
   • CAS tail is always the first operation, therefore only one thread can succeed in doing the operation
   • the next thread will change tail and link the element after the last element added
   • if buffer is empty i.e. (last == dummy) => head is changed only if CAS tail succeeds
3. enqueue and dequeue
   
   • if buffer is empy, no dequeue is done (head == dummy)
   • dequeue: CAS head to dummy; if this succeeds, set tail to dummy
   • if an enqueue is done before CAS head => OK, because enqueue only changes tail (if buffer is empty, enqueue can change head, but no dequeue in that case)
   • if an enqueue is done after CAS head, but before set tail, then the element added will be dequeued as well, because it will be added at the end of the buffer.
   • when dequeue finally sets tail to dummy, we have an empty buffer
   • if an enqueue is done after head and tail are set in dequeue, we have an empty buffer and everything is OK
     
     
   • after enqueue CAS tail to new node, it links the old tail to the new node: this should be OK and it should happen before the dequeuer reaches to that node (because it has to first set the tail, and then go through the list)
   • for a while after dequeue, the size might be greater than the real size (because the size is changed after setting the head, tail, going through the list and calculating the size of the dequeued elements) -> but evict check is head is dummy
   • what if eviction happens after dequeue has canged head, tail, but not size, and some enqueues were already done?
     
     • shouldEvict checks if size>capacity, which will be true, but the real size is much smaller! then the eviction will be performed, even though it was not needed, thus we lose some valid new elements!

Testing

Issues that need to be checked:

...