3.2.6 Coping With Concurrency

Space does not permit more than a flavour of the problems posed by concurrent allocators, and how the LeapHeap list algorithm anticipates them.

First, there is a general principle of re-reading. An allocator scans the descriptor list for a suitably sized free block without issuing any locked instructions. Then if, for example, it is performing block-fit, it uses a locked instruction to mark the corresponding descriptor as allocated. Achieving this fixes the addr fields of the descriptor and the following descriptor, by the properties given in the previous section. The thread must re-read these two fields (amongst others) to be sure the block size has not meanwhile been changed by the actions of other threads.

The coalescence of adjacent free blocks by the block-coalesce operation gives rise to the majority of concurrency challenges.

In the diagram, thread-1 is navigating the descriptor list, and holds descA.nxt as pointer to the succeeding list element. Meanwhile an interleaved block-coalesce operation from thread-2 has overwritten descA.nxt, so that thread-1 goes on to examine unused descriptor descB. Thread-1 is said to have gone astray, because it has steered away from the true list, the set of in-use descriptors found by instantaneously navigating from list head to end-marker. In this case, it looks like thread-1 will get back to the true list quickly, as descB.nxt still points to descC. Imagine however a thread being switched out and not scheduled again for several seconds; the descriptor list is likely to have been substantially reorganised by the time the thread resumes.

A stray thread will wander through unused descriptors until one of three things happens.

  1. It may encounter an unaltered in-use descriptor.
  2. It may encounter a reused descriptor.
  3. It may encounter an end-marker, either the true end-marker or some unused descriptor indistinguishable from it.

The first possibility is the simple case illustrated above. In the second, the reused descriptor causes the thread to rejoin the true list at some arbitrary point. The third case is the only one in which the allocator cares that it has gone astray, which it realises from the absence of a penultimate descriptor preceding the end marker; it starts again from the beginning of the list. The second and third cases admit the possibility of starvation, a drawback largely of academic interest given the way the NT scheduler works.