Implementing Atomic Sequences on Uniprocessors Using Rollforward

This article presents a software-only solution to the synchronization problem for uniprocessors. The idea is to execute atomic sequences without any hardware protection, and in the rare case of pre-emption, to roll the sequence forward to the end, thereby preserving atomicity. One of the proposed implementations protects atomic sequences without any memory-accesses. This is significant as it enables execution at CPU-speeds, rather than memory-speeds. The benefit of this method increases with the frequency at which atomic sequences are executed. It therefore encourages the building of systems with fine-grained synchronization. This has the additional advantage of reducing average latency. Experiments demonstrate that this technique has the potential to outperform even the best hardware mechanisms. The main contribution of this article is to discuss operating-system related issues of rollforward and to demonstrate its practicality, both in terms of flexibility and performance.