Tervel: A unification of descriptor-based techniques for non-blocking programming

The development of non-blocking code is difficult; developers must ensure the progress of an operation on shared memory despite conflicting operations. Managing this shared memory in a non-blocking fashion is even more problematic. The non-blocking property guarantees that progress is made toward the desired operation in a finite amount of time. We present a framework that implements memory reclamation and progress assurance for code that follows the semantics of our framework. This reduces the effort required to implement non-blocking, and more specifically wait-free, algorithms. We also present a library that demonstrates the ease with which wait-free algorithms can be implemented using our framework.

1. Introduction

Non-blocking synchronization is a problem that programmers of real-time systems have been dealing with for years. Now, this problem is becoming mainstream as companies are being funded based on these technologies [15]. The usual method of synchronization is to use a lock-based approach that might include constructs such as a mutex. We can allow for more concurrency by choosing to use a non-blocking approach which does not employ any software locks.