TO-Lock: Removing Lock Overhead Using the Owners' Temporal Locality
Takeshi Ogasawara, Hideaki Komatsu, Toshio Nakatani · 2004
The performance of locking is critical, as programming languages with built-in thread support come into wide use. Many techniques for optimizing Java monitors have been proposed, based on the observation that the locks are rarely contended for in many applications. However, the prob-lem of the performance degradation in SMP environments caused by necessary serializations of the processors ’ exe-cution has not been addressed for shared objects. We propose a new algorithm for this problem. It uses simple instructions to acquire the lock by exploiting the owner locality for objects even if the ownership has mi-grated among the threads. Our algorithm is particularly ef-fective for SMP environments because we can remove the overhead of the serialization caused by complex atomic op-erations for uncontended locks by allowing the lock oper-ation and the code protected by the lock to be executed in parallel. We verified the safety of the algorithm by using a software tool, Spin. The experimental results of our bench-marking on an SMP machine using Intel Xeon processors showed that our algorithm can significantly improve the performance by 83 % on average compared to the case us-ing a complex atomic instruction. 1.