Bounds on contention management algorithms
We present two new algorithms for contention management in transactional memory, the deterministic algorithm CornmitRounds and the randomized algorithm RandomizedRounds. Our randomized algorithm is efficient: in some notorious problem instances (e.g., dining philosophers) it is exponentially faster than prior work from a worst case perspective. Both algorithms are (i) local and (ii) starvation-free. Our algorithms are local because they do not use global synchronization data structures (e.g., a shared counter), hence they do not introduce additional resource conflicts which eventually might limit scalability. Our algorithms are starvation-free because each transaction is guaranteed to complete. Prior work sometimes features either (i) or (ii), but not both. To analyze our algorithms (from a worst case perspective) we introduce a new measure of complexity that depends on the number of actual conflicts only. In addition, we show that even a non-constant approximation of the length of an optimal (shortest) schedule of a set of transactions is NP-hard - even if all transactions are known in advance and do not alter their resource requirements. Furthermore, in case the needed resources of a transaction varies over time, such that for a transaction the number of conflicting transactions increases by a factor k, the competitive ratio of any contention manager is Omega (k) for k < root m, where m denotes the number of parallel threads. (C) 2010 Elsevier B.V. All rights reserved.
contention management transactions transactional memory scheduling concurrency control