| Atomic Instructions in Java |
 |
 |
Page 1 of 5
Wait-free data structures and algorithms have been an active area of research in recent years[3, 6, 12, 18], and have spawned a variety of applications[4, 8, 9]. They have the desirable property that when multiple threads access a wait- free data structure, stalled threads cannot prevent other threads from making progress. This avoids a variety of problems encountered with lock-based (block- ing) synchronization, such as priority inversion and formation of convoys. Wait- free synchronization is especially useful when a data structure must be accessed in a context from which blocking is impossible or undesirable. Wait-free data structures generally work by making small changes atom- ically, such that before and after the atomic operation the data structure is in a consistent state. These atomic operations are usually implemented using Page 2 atomic machine instructions, in which one or more memory locations are ac- cessed and updated atomically. For example, many architectures support an atomic compare-and-swap, or ‘CAS’, instruction. CAS atomically compares the contents of a single memory location against an input value, and if they are equal stores a second value in the memory location. Atomic memory operations are easy to express in languages such as C and C++, in which it is possible to determine the address of any variable, array element, or field. (It is necessary to resort to assembly language to implement these operations, but most compilers support some form of inline assembly.) However, type-safe languages such as Java do not permit manipulation of ar- bitrary memory locations, nor do they permit the direct execution of arbitrary machine instructions. The problem of how to express atomic memory operations in such languages in a way that respects the language’s safety guarantees is thus more challenging. In this paper we consider several techniques for supporting atomic memory operations in the Java programming language[7]. We propose idiom recognition as a lightweight technique for expressing atomic instructions in a way that is simple to implement and is fully compatible with the semantics of the language. While much of our discussion is specific to Java, the same basic techniques could also be used in other type-safe virtual machines, such as Microsoft’s CLR (Common Language Runtime). The structure of the paper is as follows. In Sect. 2, we give a general overview of atomic instructions and how they are used in wait-free algorithms. In Sect. 3, we describe several techniques for supporting atomic instructions in the Java virtual machine. In Sect. 4 we discuss several questions of strategy that arise in supporting atomic instructions. In Sect. 5, we describe an algorithm for recogniz- ing instances of idioms which can be translated into atomic machine instructions within the Java virtual machine. In Sect. 6 we show performance results that show that support for atomic instructions allow the implementation of a con- current queue that is more scalable than a comparable queue implemented with blocking synchronization. In Sect. 7 we describe related work. Finally, in Sect. 8 we summarize our findings and describe possibilities for future work. 2 Atomic Instructions Atomic machine instructions atomically access and modify one or more memory locations. They have two primary advantages over using a lock to guarantee atomicity: 1. an atomic instruction is generally faster than equivalent lock-based code, and 2. atomic instructions execute in a finite amount of time, whereas acquiring a lock may block the executing thread for an unbounded period of time For these reasons, atomic instructions are valuable in situations where a small update is made to a shared data structure, especially when the use of a lock Page 3 might significantly reduce potential concurrency. Table 1 lists examples of atomic instructions and common commercial architectures in which they are supported in hardware
|