Isolator: Dynamically Ensuring Isolation in Concurrent Programs - Rajamani, Sriram; Ramalingam, G.; Ranganath, Venkatesh-Prasad; Vaswani, Kapil (2008)
In this paper, we focus on programs that rely on locks for achieving isolation of data accessed by critical sections of code. We present Isolator, an algorithm that guarantees isolation in well-behaved threads of a program that obey the locking discipline even in the presence of ill-behaved threads that disobey the locking discipline. Isolator uses code instrumentation, data replication, and virtual memory protection to detect any possible violation of isolation. Whenever such a violation is detected, Isolator delays the ill-behaved thread until all well-behaved threads have released locks on the data. We present three general desiderata - safety, isolation, and permissiveness - for any scheme that attempts to ensure isolation, and formally prove that Isolator satisfies all of these desiderata. We evaluate Isolator on several benchmark programs and find that Isolator can ensure isolation with reasonable runtime overheads.