The Concurrent Reading and Writing of Clocks
Leslie Lamport · 2016
As an exercise in synchronization without mutual exclusion, algorithms are developed to implement both a monotonic and a cyclic multiple-word clock that is updated by one process and read by one or more other processes. Capsule Review It is convenient for an operating system to maintain the system clock in shared memory, so it can be read directly by user processes, without a system call. But doing this is tricky if the clock has more than one word of precision, because the system may update the clock while a user process is partway through reading it. This paper presents a simple algorithm for maintaining the clock in shared memory that requires no locking or retries. Theorists will find the algorithm and its correctness proof interesting, while practitioners will find the algorithm useful and easy to implement. Tim Mann v Contents 1 Introduction 1 2 Notation and Theorems 2 3 A Monotonic Clock 3 4 A Cyclic Clock 6 References 7 vi 1 Introduction In an asynchronous multiprocess s...