Nicholas Mc Guire, OpenTech EDV Research GmbH
Peter Okech, Department of Physics University of Nairobi Nairobi

Sequence locks are a concurrency primitive that allows multiple readers to coexist anonymously as well as new readers to enter any time. The single writer may enter the critical section at any point in time resulting in a read-side detectable data inconsistency and following this detection a retry of the read operation. If readers and writers were non-preemptible, then this would be a well-bounded operation on both sides - unfortunately this cannot be assured, and under rare circumstances a writer may delay multiple - spinning - readers more or less arbitrarily long. Due to the reader anonymity, boosting (PI) is not doable.

In this paper, we introduce a slight modification of sequence locks that employs a replication strategy, allowing to switch between buffers and so ensuring that at any given time a non-preempted reader will be able to retrieve a consistent copy of data without unbounded delays. Different strategies of buffer selection (sequential vs. random) as well as different numbers of buffers and execution conditions are compared.

Buffer swapping sequence locks not only may be an improvement for general purpose operating systems but particularly are of interest to real-time operating systems as they can give bounds guarantees for readers that sequence locks can not give.

Further, we briefly introduced the use of inherent non-determinism to extract random bits on demand for low-level algorithms in complex hardware software systems, allowing to implement symmetry-breaking in the theoretically unbounded nature of retries in deterministic sequence lock algorithms.

Preliminary results for a simplified user-space proof-of-concept are presented as well as the current state of experimental kernel level work.