Nicholas Mc Guire, Lanzhou University, SISE, China

Traditional locking is trying to provide consistency of concurrently accessed data objects, and is sometimes misused for ordering purposes on top of this. Fundamentally though, locking is not a solution but rather a workaround to controlling the non-determinism that we build into code. As we simply don't know - even stronger: can't know - the access patterns of concurrently executing tasks on computers (even more so on modern multicore systems), we need locking to overcome this lack of predictability.

While traditional locking approaches were developed in the context of predominantly single core systems, or at least relatively deterministic hardware, the picture has changed quite significantly with the introduction of super-scalar CPUs that are, by design, partially unpredictable with respect to temporal behavior (i.e. pLRU cache replacement strategies). With the introduction of NUMA systems, the predictability has diminished even further resulting in an ever increasing computational expense of synchronization. The temporal indeterminism paired with the relatively high memory access costs to "remote" CPUs has two interesting consequences on locking:

• traditional locking is becomming increasingly expensive
• the impact of locking on real-time behavior, notably jitter, is quite dramatic

In the past years, a few interesting probabilistic approaches have been making their way into operating systems. Sequence locks have been in the Linux kernel for quite some time, which are temporally non-deterministic, and RCU which exchanges guranteed local consistency against temporary global inconsistency and eliminates many of the possible contention zones rather than serializing them.

The deaper question though is if there is not an alternative to locking that actually can profit from growing system complexity - we believe the answer is yes.

The basic model of locking is to serialize access to the resource by advisory locks (with all the consequences that the advisory nature of these have) so to ensure that the access pattern to the critical region is well defined. But if the access pattern without these locks is not well defined we can utilize just this: a solution is to simply provide a construct that needs a sufficiently complex deterministic access pattern to fail. The construction of probabilisitc locking thus needs to find constructs that result in inconsistent data only if a complex series of activations between the contending partners occures - with the ability to increase the complexity arbitrarily making this activation patter arbitrarily unlikely.

In this paper, we introduce a prototypical implementation of what we call probabilistic write copy select (pWCS) locks, which are strictly speaking not locks at all - but with sleeping spin-locks in the kernel the naming is justfiied. pWCS is a working example that follows the "build on complexity" model and, as we believe, demonstrate the feasibility of the approach.