Abstract

Coarse grained locks are a source of bottlenecks in programs that want to run on machines with large numbers of threads. I will describe new techniques that I have developed to allow lock-based programs to use optimistic concurrency control. This lets multiple threads optimistically acquire the same lock, and run in parallel as long as they do not conflict on the data that they access. A specially constructed software transactional memory (STM) is used to maintain the illusion of mutual exclusion. This approach is toolchain-agnostic; it works on unmodified native x86 binaries, meaning that there are no restrictions on source language, compiler or debugger and software lock elision is applied optionally at runtime. In this talk, I will focus on two key challenges in building such a system. The first is building an STM that can preserve the x86 memory consistency model. The second is achieving efficient instrumentation for x86 machine code. I will show that there is a fundamental tradeoff between safety and the general applicability of the system in terms of programs that can be handled. The talk will present evaluations of improvements in scalability that the system brings to coarse grained locks.