skip to main content
10.1145/1146381.1146428acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

Transactional contention management as a non-clairvoyant scheduling problem

Published: 23 July 2006 Publication History

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(s2) 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 and Xiaotie Deng, Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. J. Scheduling, 6(3): 231--250 (2003).
[2]
R. Guerraoui, M. Herlihy and S. Pochon, Toward a Theory of Transactional Contention Management. PODC 2005: 258--264.
[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 and William N. Scherer III, Software transactional memory for dynamic-sized data structures. PODC 2003: 92--101.
[5]
Sandy Irani and Vitus Leung, Scheduling with Conflicts, and Applications to Traffic Signal Control. SODA 1996: 85--94.
[6]
Bala Kalyanasundaram and Kirk R. Pruhs, Fault-tolerant scheduling. SIAM Journal on Computing, 34(3): 697 -- 719 (2005).
[7]
R. Motwani, S. Phillips and E. Torng, Non-Clairvoyant Scheduling. Theor. Comput. Sci, 130(1): 17--47 1994.
[8]
Daniel J. Rosenkrantz, Richard E. Stearns and Philip M. Lewis II, System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst., 3(2): 178--198 (1978).
[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 and Michael Scott, Advanced Contention Management for Dynamic Software Transactional Memory, PODC 2005: 240--248.
[11]
Abraham Silberschatz and Peter Galvin, Operating Systems Concepts, 5th edition, John Wiley & sons, 1999.
[12]
Gottfried Vossen and Gerhard Weikum, Transactional Information Systems, Morgan Kaufmann, 2001.

Cited By

View all
  • (2025)Fast and fair randomized wait-free locksDistributed Computing10.1007/s00446-024-00474-438:1(51-72)Online publication date: 24-Jan-2025
  • (2023)Separating Mechanism from Policy in STM2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
  • (2022)Fast and Fair Randomized Wait-Free LocksProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538448(187-197)Online publication date: 20-Jul-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
July 2006
230 pages
ISBN:1595933840
DOI:10.1145/1146381
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. concurrency control
  2. contention management
  3. scheduling
  4. software transactional memory
  5. transactions

Qualifiers

  • Article

Conference

PODC06

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Fast and fair randomized wait-free locksDistributed Computing10.1007/s00446-024-00474-438:1(51-72)Online publication date: 24-Jan-2025
  • (2023)Separating Mechanism from Policy in STM2023 32nd International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT58117.2023.00031(279-296)Online publication date: 21-Oct-2023
  • (2022)Fast and Fair Randomized Wait-Free LocksProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538448(187-197)Online publication date: 20-Jul-2022
  • (2017)Analysis, Classification and Comparison of Scheduling Techniques for Software Transactional MemoriesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.274028528:12(3356-3373)Online publication date: 1-Dec-2017
  • (2017)Providing QoS in contention management for software transactional memory2017 13th International Computer Engineering Conference (ICENCO)10.1109/ICENCO.2017.8289793(231-236)Online publication date: Dec-2017
  • (2015)Transactional Read-Modify-Write Without AbortsACM Transactions on Architecture and Code Optimization10.1145/268890411:4(1-24)Online publication date: 9-Jan-2015
  • (2015)On Avoiding Spare Aborts in Transactional MemoryTheory of Computing Systems10.1007/s00224-015-9607-757:1(261-285)Online publication date: 1-Jul-2015
  • (2015)Hybrid Transactional Memory RevisitedProceedings of the 29th International Symposium on Distributed Computing - Volume 936310.1007/978-3-662-48653-5_15(215-231)Online publication date: 7-Oct-2015
  • (2015)Case Study: Using Transactions in MemcachedTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_20(449-467)Online publication date: 2015
  • (2015)Scheduling-Based Contention Management Techniques for Transactional MemoryTransactional Memory. Foundations, Algorithms, Tools, and Applications10.1007/978-3-319-14720-8_10(213-227)Online publication date: 2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media