Constructing a high-performance garbage collector is hard. Constructing a fully concurrent ‘on-the-fly’ compacting collector is much more so. We describe our experience of implementing the Sapphire algorithm as the first on-the-fly, parallel, replication copying, garbage collector for the Jikes RVM Java virtual machine (JVM). In part, we explain our innovations such as copying with hardware and software transactions, on-the-fly management of Java’s reference types, and simple, yet correct, lock-free management of volatile fields in a replicating collector. We fully evaluate, for the first time, and using realistic benchmarks, Sapphire’s performance and suitability as a low latency collector. An important contribution of this work is a detailed description of our experience of building an on-the-fly copying collector for a complete JVM with some assurance that it is correct. A key aspect of this is model checking of critical components of this complicated and highly concurrent system.

To achieve good multi-core performance, modern microprocessors have weak memory models, rather than enforce sequential consistency. This gives the programmer a wide scope for choosing exactly how to implement various aspects of inter-thread communication through the system's shared memory. However, these choices come with both semantic and performance consequences, often in tension with each other. In this paper, we focus on the performance side, and define techniques for evaluating the impact of various choices in using weak memory models, such as where to put fences, and which fences to use. We make no attempt to judge certain strategies as best or most efficient, and instead provide the techniques that will allow the programmer to understand the performance implications when identifying and resolving any semantic/performance trade-offs. In particular, our technique supports the reasoned selection of macrobenchmarks to use in investigating trade-offs in using weak memory models. We demonstrate our technique on both synthetic benchmarks and real-world applications for the Linux Kernel and OpenJDK Hotspot Virtual Machine on the ARMv8 and POWERv7 architectures.

Intel's latest processor microarchitecture, Haswell, adds support for a restricted form of transactional memory to the x86 programming model. We explore how this can be applied to three garbage collection scenarios in Jikes RVM: parallel copying, concurrent copying and bitmap marking. We demonstrate gains in concurrent copying speed over traditional synchronisation mechanisms of 48-101%. We also show how similar but portable performance gains can be achieved through software transactional memory techniques. We identify the architectural overhead of capturing sufficient work for transactional execution as a major stumbling block to the effective use of transactions in the other scenarios.

Most proposals for on-the-fly garbage collection ignore the question of Java's weak and other reference types. However, we show that reference types are heavily used in DaCapo benchmarks. Of the few collectors that do address this issue, most block mutators, either globally or individually, while processing reference types. We introduce a new framework for processing reference types on-the-fly in Jikes RVM. Our framework supports both insertion and deletion write barriers. We have model checked our algorithm and incorporated it in our new implementation of the Sapphire on-the-fly collector. Using a deletion barrier, we process references while mutators are running in less than three times the time that previous approaches take while mutators are halted; our overall execution times are no worse, and often better.

Abstract Operating systems (OSs) are the core software component of many modern computer systems, ranging from small specialized embedded systems through to large distributed OSs. The demands placed upon these systems are increasingly complex, in particular, the need to handle concurrency in order to exploit increasingly parallel (multi‐core) hardware, to support increasing numbers of user and system processes and to take advantage of increasingly distributed and decentralized systems. The languages and designs that existing OSs employ provide little support for concurrency, leading to unmanageable programming complexities and ultimately errors in the resulting systems, which are hard to detect, hard to remove and hard to prove correct. This article presents the process‐oriented design of a universal serial bus device driver infrastructure for the Raw Metal occam eXperiment (RMoX) OS and its implementation in the occam‐pi multiprocessing language. We show how concurrency can be used for the benefit of such systems, simplifying design and implementation, providing freedom from race‐hazard and aliasing errors and the potential for guarantees of operating system scalability, reliability and efficiency. Copyright © 2007 F.R.M. Barnes & C.G. Ritson. [Correction made here after initial online publication]

Abstract A fine‐grained massively parallel and process‐oriented architecture for the modelling of complex systems is presented. We propose that the concurrency in the model simplifies its design and construction by directly reflecting the processes in the natural world. The architecture is based on CSP, extended with mechanisms for process mobility from the pi‐calculus; implementations are presented using the occam‐pi language. A case study, modelling platelets (possibly artificial) within a blood vessel, is described. The aim for this model is to engineer emergent behaviour: the clotting of platelets in response to a wound in the blood vessel wall and the staunching of blood loss. A three‐dimensional model is constructed, along with mechanisms for visualization and interaction. Its expressiveness and efficiency relies strongly on the dynamic and mobile capabilities of occam‐pi. General principles for the design of large and complex system models are drawn. The described case study runs to millions of processes engaged in ever‐changing communication topologies. It is free from deadlock, livelock, race hazards and starvation by design, employing a small set of synchronization patterns for which we have proven safety theorems. Compiled occam‐π codes automatically and efficiently exploit all cores in a shared‐memory multiprocessor system. They are also straightforward to distribute over standard cluster architectures. Copyright © 2007 CG Ritson & PH Welch.

Process orientation is an approach to concurrency that uses concepts of processes and message-passing communication, with whole systems constructed from layered and dynamically evolving networks of communicating processes. The work described in this paper relates to the automatic model generation and verification of systems developed in process-oriented languages. We discuss some early applications of this technique to our experimental operating system, RMoX, as a means to giving a guarantee of correct system behaviour at a range of levels.