previousupnext

3.2.7 Concurrency Example

The diagram below shows the sort of complex situation that might arise (if rarely) around the end of the LeapHeap big-block descriptor list.


At the very end of the list there is straightforward contention between thread-4 and thread-5 performing block-append. Both have constructed end-markers based on the addr field of descD. The penult field of descC holds three; it started as one when descD was appended to it, then thread-4 and thread-5 each reinforced it once. The winning thread will subtract two from it (as described in section 3.2.3 Block Append) and the losing thread will subtract one as it resiles.

Earlier in the list there is unfinished business. Low-priority thread-1 prepared an end-marker to chain onto descB, but was beaten to it some time ago by thread-2. As it happens, thread-2 has still to subtract two from the penultimate count of descA. All the same, as soon as thread-2 appended descC, high-priority thread-3 was able to navigate to it and append descD. In fact thread-3 has had time to complete its allocation, process the memory block corresponding to descC and free it.

The compare and exchange instruction that thread-1 has lined up at descB is doomed to fail, since the nxt pointer of descB is no longer nil. As long as thread-1 is stuck in the block-append operation, the penult field of descA cannot drop to zero. This prevents the blocks corresponding to descA and descB being coalesced, which might in turn result in descB being prepared as an end-marker and lead to the compare and exchange instruction succeeding when it shouldn't.