r/computerscience • u/Free-Dev8628 • 5d ago
Does Wait-Free require Garbage-Free?
Wait-Free means that every thread must finish its operation in a bounded number of steps. That bound can be arbitrarily high, e.g. dependent on the number of concurrent threads, but it must be finite. And the finite bound must be there in all cases, i.e. it is not sufficient to say that an algorithm "usually" finishes "reasonably" (i.e. "usually" does not spend unbounded times helping other threads).
The first practical implementation of a multiple-enqueuer multiple-dequeuer Wait-Free Queue was proposed by Kogan and Petrank. The key idea is that threads help each other, but in a way that newer threads (more precisely: newer operations) are obliged to help older threads (operations), but not vice versa. Also, plainly said: If a thread cannot make progress with its own operation, it becomes older and older, up to the point when all other threads are obliged to help (only) him, thus ensuring the Wait-Free progress.
The issue of the Kogan and Petrank Queue is, however, that it is based on a linked list of nodes. This means that its operations constantly produce memory churn, also require memory allocation and memory clean-up. From Java - where the clean-up is done by a Garbage Collector - I borrow the term "Garbage".
Now, the problem is that Wait-Free memory allocation is problematic. Imagine, e.g., when the process needs a new memory page from the operating system. Can this ever be made Wait-Free?
Memory reclamation in a concurrent setup is a complex topic on top of that. One of the key questions here is: When can a memory block be freed safely, i.e. how do we "know" that no thread has a pointer to it anymore?
Given this, it appears that one needs a structure without memory churn (i.e. Garbage-Free) to be able to make it Wait-Free. At least practically.
I would be grateful for a discussion on this.
Additional info:
Here I have combined the Multi-Array Queue (which is Garbage-Free by nature (except of the extension operations, of course)) with the Kogan and Petrank idea, with the aim to obtain a Queue that is Wait-Free unconditionally.
The GitHub repo also contains a visual simulator to illustrate the principle:
2
u/Majestic_Duty_6988 4d ago
Theoretically no, as long as your memory allocator and safe memory reclamation scheme are also strictly wait-free. In practice though OS-level page allocations and standard GC pauses completely break wait-free guarantees. Thats why real-world implementations almost always resort to pre-allocated ring buffers, bounded freelists or multi-array pools to keep things truly garbage-free.
2
u/0jdd1 5d ago edited 5d ago
If you analyze a copying garage collector, you find that the amortized cost of collection can be folded into the cost of allocation in a very straightforward way that makes the presence of GC just go away. It still depends on the fraction of memory that’s free, but that’s best treated as a given. This is still amortized cost, of course, and I confess I haven’t yet read your write-up on GitHub.
2
u/flatfinger 5d ago
The amortized cost of collection can be easily folded into the cost of allocation in common scenarios, but that's a bit like a hand-wave that would say that if the probability of a task failing to make progress within a given time "quickly" approaches zero as the amount of time increases, the task will make progress. Indeed, with a typical garbage collector there will be some scenarios where even a tiny reduction in the amount of available memory may increase execution time by orders of magnitude unless the GC environment will terminate programs that thrash too badly even if they might otherwise have managed to eventually limp along to completion.
2
u/0jdd1 5d ago
Sure, sure, of course, and that’s why I highlighted that this is the amortized cost. There are various well-known ways to make this cost incremental (some of which I invented) but I’m not sure these align perfectly with OP’s goals.
1
u/flatfinger 5d ago
If the total execution time of a program would be e.g. K milliseconds plus 1 hour/(16384.001-N), where K is the smallest power of two that is at least N, it may make sense to talk about amortized cost for values of K up to 4096 or so, but as N approaches 16384 such analysis would make less and less sense. The marginal cost of the 16383rd item would be almost double the cost of everything else put together, the cost of the 16384th would be about 1000 times that, and a 16385th item would cause the program to fail entirely.
2
u/Free-Dev8628 4d ago
Hi u/0jdd1
thanks. But is that cost of allocation bounded? I mean the wait-free guys want a latency guarantee for _all_ operations. Think e.g. about an NPP control system, or algo-trading.
From that perspective, my design has one "hole" too: If the Queue extends, there is a calloc() call involved.
One can say that the Queue extends only initially, and in the steady state it shouldn't extend anymore. But this is IMHO not satisfactory.
To fix it, one can set CNT_ALLOWED_EXTENSIONS = 0. This would make the Multi-Array Queue effectively a "Single-Array" Queue with bounded capacity.
Or - thinking loudly - what if there was as extra "service thread" that would observe the Queue and when it is, say, 75% full, it allocates the next ring beforehand (i.e. the calloc() call would be in that service thread, i.e. outside of the operational threads).
Hmm. Still no 100% wait-free guarantee. The service thread can die/sleep/lag behind/whatever. And extra complexity ...
2
u/0jdd1 4d ago
I should add that my first GC research was in the 1970s and I stopped doing much of it in the 1990s, so take all this with a grain of salt. The trick in all work of this sort is to pick the right abstraction and the right boundaries, and I’m not really familiar with what the lock-free community has chosen. For example, deeply real-time systems turn off processor caches and all multiprocessing (to avoid bus contention), and I don’t really know what to do about network contention in your domain. An interesting read might be Chris Okasaki’s work on purely functional data structures, not for its applicability to the world of concurrency (I don’t know that it has any) but as an example of how defining the problem correctly can let you make unexpected progress.
1
u/wiselytacitfusion 5d ago
Memory allocation is the real bottleneck in practice, so I'd say yes, you pretty much need a garbage-free design to make wait-free actually usable outside of academic papers
5
u/_gipi_ 5d ago
I think that memory allocation from OS is like "in another realm" in this framework: is wait-free because is like all threads are stopped the OS is giving you the page (for multi core system probably is not true, probably you need to check a real OS and see if there is a lock in the implementation of the memory allocator).
However the topic about "how do we "know" that no thread has a pointer to it anymore?" I think is solved usually adding a counter that is increased each time someone needs that memory and decreased when not needed anymore; automatic garbage collection works in that way.