Simple and fast wait-free snapshots for real-time systems

Abstract. A wait-free algorithm for implementing a snapshot mechanism for real-time systems is presented in this paper. S-napshot mechanisms give the means to real-time task to read a globally consistent set of variable values while other concurren-t tasks are updating them. Such a mechanism can be used to solve a variety of communication and synchronisation problems, including system monitoring and control of real-time application-s. Typically, implementations of such mechanisms are based on interlocking. Interlocking protects the consistency of the shared data by allowing only one process at a time to access the data. In a real-time environment locking typically leads to diÆculties in guaranteeing deadlines of high priority tasks because of the block-ing. Researchers have introduced non-blocking algorithms and data structures that address the above problems. In this paper we present a simple and eÆcient wait-free (non-blocking) snap-shot algorithm by making use of timing information that is avail-able and necessary to the scheduler that schedules the tasks of real-time systems. Experiments on a SUN ENTERPRISE 10000 multiprocessor system show that the algorithm that we propose here, because of its simplicity, outperforms considerably the re-spective wait-free snapshot algorithm that is not using the timing information