Transactional contention management as a non-clairvoyant scheduling problem

ABSTRACT

The transactional approach to contention management guarantees atomicity by making sure that whenever two transactions have a conflict on a resource, only one of them proceeds. A major challenge in implementing this approach lies in guaranteeing progress, since transactions are often restarted.Inspired by the paradigm of non-clairvoyant job scheduling, we analyze the performance of a contention manager by comparison with an optimal, clairvoyant contention manager that knows the list of resource accesses that will be performed by each transaction, as well as its release time and duration. The realistic, non-clairvoyant contention manager is evaluated by the competitive ratio between the last completion time (makespan) it provides and the makespan provided by an optimal contention manager.Assuming that the amount of exclusive accesses to the resources is non-negligible, we present a simple proof that every work conserving contention manager guaranteeing the pending commit property achieves an O(s) competitive ratio, where s is the number of resources. This bound holds for the GREEDY contention manager studied by Guerraoui et al. [2] and is a significant improvement over the O(s²) bound they prove for the competitive ratio of GREEDY. We show that this bound is tight for any deterministic contention manager, and under certain assumptions about the transactions, also for randomized contention managers.When transactions may fail, we show that a simple adaptation of GREEDY has a competitive ratio of at most O(ks), assuming that a transaction may fail at most k times. If a transaction can modify its resource requirements when re-invoked, then any deterministic algorithm has a competitive ratio Ω(ks). For the case of unit length jobs, we give (almost) matching lower and upper bounds.

REFERENCES

• 1: Jeff Edmonds , Donald D. Chinn , Tim Brecht , Xiaotie Deng, Non-clair voy ant multiprocessor scheduling of jobs with changing execution characteristics, Journal of Scheduling, v.6 n.3, p.231-250, May/June 2003 [doi>10.1023/A:1022952324290]
• 2: Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, Toward a theory of transactional contention managers, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073863]
• 3: R. Guerraoui, M. Herlihy, M. Kapalka and S. Pochon, Robust Contention Management in software transactional memory. Synchronization and Concurrency in Object-Oriented Languages (SCOOL) workshop, in conjunction with OOPSLA 2005. http://urresearch.rochester.edu/handle/1802/2103.
• 4: Maurice Herlihy , Victor Luchangco , Mark Moir , William N. Scherer, III, Software transactional memory for dynamic-sized data structures, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.92-101, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872048]
• 5: Sandy Irani , Vitus Leung, Scheduling with conflicts, and applications to traffic signal control, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.85-94, January 28-30, 1996, Atlanta, Georgia, United States
• 6: Bala Kalyanasundaram , Kirk R. Pruhs, Fault-Tolerant Scheduling, SIAM Journal on Computing, v.34 n.3, p.697-719, 2005 [doi>10.1137/S0097539794261799]
• 7: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1 ]
• 8: Daniel J. Rosenkrantz , Richard E. Stearns , Philip M. Lewis, II, System level concurrency control for distributed database systems, ACM Transactions on Database Systems (TODS), v.3 n.2, p.178-198, June 1978 [doi>10.1145/320251.320260]
• 9: William N. Scherer III and Michael Scott, Contention Management in Dynamic Software Transactional Memory. PODC Workshop on Concurrency and Synchronization in Java Programs, 2004: 70--79.
• 10: William N. Scherer, III , Michael L. Scott, Advanced contention management for dynamic software transactional memory, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073861]
• 11: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 1999
• 12: Gottfried Vossen and Gerhard Weikum, Transactional Information Systems, Morgan Kaufmann, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms

Keywords:
concurrency control, contention management, scheduling, software transactional memory, transactions