Polymorphic Contention Management

In software transactional memory (STM) systems, a contention manager resolves con- icts among transactions accessing the same memory locations. Whereas atomicity and serializabil- ity of the transactions are guaranteed at all times, the contention manager is of crucial importance for guaranteeing that the system as a whole makes progress. A number of dieren t contention management policies have been proposed and evaluated in the recent literature. An empirical evaluation of these policies leads to the striking result that there seems to be no \universal" contention manager that works best under all reasonable circumstances. Instead, transaction throughput can vary dramatically depending on factors such as transaction length, data access patterns, the length of contended vs. uncontended phases, and so on. This paper proposes polymorphic contention management, a structure that allows contention man- agers to vary not just across workloads, but across concurrent transactions in a single workload, and even across dieren t phases of a single transaction. The ability to mix contention managers or to change them on-the-y provides performance benets, but also poses number of questions concerning how a contention manager of a given class can interact in a useful way with contention managers of dieren t, possibly unknown classes. We address these questions by classifying con- tention managers in a hierarchy, based on the cost associated with each contention manager, and present a general algorithm to handle conict between contention managers from dieren t classes. We describe how our polymorphic contention management structure is smoothly integrated with nested transactions in the SXM library.