research-article

Automatic fine-grain locking using shape properties

Authors:

Guy Golan-Gueta,

Nathan Bronson,

Eran YahavAuthors Info & Claims

OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

Pages 225 - 242

https://doi.org/10.1145/2048066.2048086

Published: 22 October 2011 Publication History

Abstract

We present a technique for automatically adding fine-grain locking to an abstract data type that is implemented using a dynamic forest -i.e., the data structures may be mutated, even to the point of violating forestness temporarily during the execution of a method of the ADT. Our automatic technique is based on Domination Locking, a novel locking protocol. Domination locking is designed specifically for software concurrency control, and in particular is designed for object-oriented software with destructive pointer updates. Domination locking is a strict generalization of existing locking protocols for dynamically changing graphs. We show our technique can successfully add fine-grain locking to libraries where manually performing locking is extremely challenging. We show that automatic fine-grain locking is more efficient than coarse-grain locking, and obtains similar performance to hand-crafted fine-grain locking.

References

[1]

Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., and Verkamo, I. Advances in knowledge discovery and data mining. American Association for Artificial Intelligence, Menlo Park, CA, USA, 1996, ch. Fast discovery of association rules, pp. 307--328.

Digital Library

[2]

Aho, A. V., Lam, M. S., Sethi, R., and Ullman, J. D. Compilers: Principles, Techniques, and Tools (2nd Edition). Addison Wesley, 2006.

Digital Library

[3]

Aragon, C., and Seidel, R. Randomized search trees. Foundations of Computer Science, Annual IEEE Symposium on 0 (1989), 540--545.

Digital Library

[4]

Attiya, H., Ramalingam, G., and Rinetzky, N. Sequential verification of serializability. In POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 2010), ACM, pp. 31--42.

Digital Library

[5]

Barnes, J., and Hut, P. A hierarchical O(N log N) force-calculation algorithm. Nature 324 (Dec. 1986), 446--449.

[6]

Bayer, R., and Schkolnick, M. Concurrency of operations on B-Trees. Acta Informatica 9 (1977), 1--21.

Digital Library

[7]

Boyapati, C., Lee, R., and Rinard, M. Ownership types for safe programming: preventing data races and deadlocks. In Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications (New York, NY, USA, 2002), OOPSLA '02, ACM, pp. 211--230.

Digital Library

[8]

Brass, P. Advanced Data Structures. Cambridge University Press, New York, NY, USA, 2008.

Digital Library

[9]

Bronson, N. G., Casper, J., Chafi, H., and Olukotun, K. A practical concurrent binary search tree. In PPOPP (2010), pp. 257--268.

Digital Library

[10]

Chaudhri, V. K., and Hadzilacos, V. Safe locking policies for dynamic databases. In PODS '95: Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (New York, NY, USA, 1995), ACM, pp. 233--244.

Digital Library

[11]

Cherem, S., Chilimbi, T., and Gulwani, S. Inferring locks for atomic sections. In PLDI (2008), pp. 304--315.

Digital Library

[12]

Cunningham, D., Gudka, K., and Eisenbach, S. Keep off the grass: Locking the right path for atomicity. In Compiler Construction, vol. 4959 of Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2008, pp. 276--290.

Digital Library

[13]

Deutsch, L. P., and Bobrow, D. G. An efficient, incremental, automatic garbage collector. Commun. ACM 19, 9 (1976), 522--526.

Digital Library

[14]

Dice, D., Shalev, O., and Shavit, N. Transactional locking ii. In DISC (2006), pp. 194--208.

Digital Library

[15]

Emmi, M., Fischer, J. S., Jhala, R., and Majumdar, R. Lock allocation. In POPL (2007), pp. 291--296.

Digital Library

[16]

Eswaran, K. P., Gray, J. N., Lorie, R. A., and Traiger, I. L. The notions of consistency and predicate locks in a database system. Commun. ACM 19 (November 1976), 624--633.

Digital Library

[17]

Gudka, K., Eisenbach, S., and Harris, T. Lock Inference in the Presence of Large Libraries. Tech. rep., November 2010.

[18]

Guibas, L. J., and Sedgewick, R. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (Washington, DC, USA, 1978), IEEE Computer Society, pp. 8--21.

Digital Library

[19]

Harris, T., Larus, J., and Rajwar, R. Transactional memory, 2nd edition. Synthesis Lectures on Computer Architecture 5, 1 (2010), 1--263.

Digital Library

[20]

Herlihy, M., Lev, Y., Luchangco, V., and Shavit, N. A provably correct scalable concurrent skip list. In OPODIS '06: Proceedings of the 10th International Conference On Principles Of Distributed Systems (December 2006).

[21]

Herlihy, M., Luchangco, V., Moir, M., and III, W. N. S. Software transactional memory for dynamic-sized data structures. In PODC (2003), pp. 92--101.

Digital Library

[22]

Herlihy, M., and Moss, J. E. B. Transactional memory: Architectural support for lock-free data structures. In ISCA (1993), pp. 289--300.

Digital Library

[23]

Herlihy, M. P., and Wing, J. M. Linearizability: a correctness condition for concurrent objects. Proc. of ACM TOPLAS 12, 3 (1990), 463--492.

Digital Library

[24]

Hicks, M., Foster, J. S., and Prattikakis, P. Lock inference for atomic sections. In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (June 2006).

[25]

Kedem, Z. M., and Silberschatz, A. A characterization of database graphs admitting a simple locking protocol. Acta Inf. 16 (1981), 1--13.

Digital Library

[26]

Lanin, V., and Shasha, D. Tree locking on changing trees. Tech. rep., 1990.

Digital Library

[27]

Lev-Ami, T., and Sagiv, M. TVLA: A framework for Kleene based static analysis. In Saskatchewan (2000), vol. 1824 of Lecture Notes in Computer Science, Springer-Verlag, pp. 280--301.

Digital Library

[28]

Levanoni, Y., and Petrank, E. An on-the-fly reference-counting garbage collector for Java. ACM Trans. Program. Lang. Syst. 28, 1 (2006), 1--69.

Digital Library

[29]

McCloskey, B., Zhou, F., Gay, D., and Brewer, E. Autolocker: synchronization inference for atomic sections. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 2006), ACM, pp. 346--358.

Digital Library

[30]

Moss, J. E. B. Open Nested Transactions: Semantics and Support. In Poster at the 4th Workshop on Memory Performance Issues (WMPI-2006). February 2006.

[31]

Narayanan, R., Özis. Ikyilmaz, B., Zambreno, J., Memik, G., and Choudhary, A. Minebench: A benchmark suite for data mining workloads. In 2006 IEEE International Symposium on Workload Characterization (2006), pp. 182--188.

[32]

Nurmi, O., and Soisalon-Soininen, E. Uncoupling updating and rebalancing in chromatic binary search trees. In Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (New York, NY, USA, 1991), PODS '91, ACM, pp. 192--198.

Digital Library

[33]

Papadimitriou, C. H. The serializability of concurrent database updates. J. ACM 26, 4 (1979), 631--653.

Digital Library

[34]

Sagiv, M., Reps, T., and Wilhelm, R. Parametric Shape Analysis via 3-valued Logic. ACM Trans. on Prog. Lang. and Systems (TOPLAS) 24, 3 (2002), 217--298.

Digital Library

[35]

Silberschatz, A., and Kedam, Z. A family of locking protocols for database systems that are modeled by directed graphs. Software Engineering, IEEE Transactions on SE-8, 6 (Nov. 1982), 558 -- 562.

Digital Library

[36]

Sleator, D. D., and Tarjan, R. E. Self adjusting heaps. SIAM J. Comput. 15 (February 1986), 52--69.

Digital Library

[37]

Wang, Y., Lafortune, S., Kelly, T., Kudlur, M., and Mahlke, S. A. The theory of deadlock avoidance via discrete control. In POPL (2009), pp. 252--263.

Digital Library

[38]

Weikum, G., and Vossen, G. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001.

Digital Library

[39]

Welc, A., Saha, B., and Adl-Tabatabai, A.-R. Irrevocable transactions and their applications. In SPAA (2008), pp. 285--296.

Digital Library

[40]

Yang, H., Lee, O., Berdine, J., Calcagno, C., Cook, B., and Distefano, D. Scalable shape analysis for systems code. In In CAV (2008).

Digital Library

Cited By

Ghosh RHsieh CMisailovic SMitra S(2020)Koord: a language for programming and verifying distributed robotics applicationProceedings of the ACM on Programming Languages10.1145/34283004:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428300
He FHan J(2020)Termination analysis for evolving programs: an incremental approach by reusing certified modulesProceedings of the ACM on Programming Languages10.1145/34282674:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428267
Sang BEugster PPetri GRavi SRoman P(2020)Scalable and serializable networked multi-actor programmingProceedings of the ACM on Programming Languages10.1145/34282664:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428266
Show More Cited By

Recommendations

Automatic fine-grain locking using shape properties
OOPSLA '11

We present a technique for automatically adding fine-grain locking to an abstract data type that is implemented using a dynamic forest -i.e., the data structures may be mutated, even to the point of violating forestness temporarily during the execution ...
Sequential verification of serializability
POPL '10

Serializability is a commonly used correctness condition in concurrent programming. When a concurrent module is serializable, certain other properties of the module can be verified by considering only its sequential executions. In many cases, concurrent ...
Altruistic locking

Long-lived transactions (LLTs) hold on to database resources for relatively long periods of time, significantly delaying the completion of shorter and more common transactions. To alleviate this problem we propose an extension to two-phase locking, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

October 2011

1104 pages

ISBN:9781450309400

DOI:10.1145/2048066

General Chair:
Cristina Videira Lopes
University of California, Irvine, USA
,
Program Chair:
Kathleen Fisher
Tufts University, USA

ACM SIGPLAN Notices Volume 46, Issue 10
OOPSLA '11
October 2011
1063 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2076021
Issue’s Table of Contents

Copyright © 2011 ACM.

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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPLASH '11

Sponsor:

SIGPLAN

SPLASH '11: Conference on Systems, Programming, and Applications: Software for Humanity

October 22 - 27, 2011

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
289
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghosh RHsieh CMisailovic SMitra S(2020)Koord: a language for programming and verifying distributed robotics applicationProceedings of the ACM on Programming Languages10.1145/34283004:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428300
He FHan J(2020)Termination analysis for evolving programs: an incremental approach by reusing certified modulesProceedings of the ACM on Programming Languages10.1145/34282674:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428267
Sang BEugster PPetri GRavi SRoman P(2020)Scalable and serializable networked multi-actor programmingProceedings of the ACM on Programming Languages10.1145/34282664:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428266
Madsen Mvan de Pol J(2020)Polymorphic types and effects with Boolean unificationProceedings of the ACM on Programming Languages10.1145/34282224:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428222
Kallas KNiksic FStanford CAlur R(2020)DiffStream: differential output testing for stream processing programsProceedings of the ACM on Programming Languages10.1145/34282214:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428221
Back JHua BHachisuka TMoon B(2020)Deep combiner for independent and correlated pixel estimatesACM Transactions on Graphics10.1145/3414685.341784739:6(1-12)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417847
Chakravarthula PTseng ESrivastava TFuchs HHeide F(2020)Learned hardware-in-the-loop phase retrieval for holographic near-eye displaysACM Transactions on Graphics10.1145/3414685.341784639:6(1-18)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417846
Kalikar SNasre R(2018)NumLockProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225141(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225141
Gilad EBrown TOskin MEtsion Y(2018)Snapshot-Based Synchronization: A Fast Replacement for Hand-over-Hand LockingEuro-Par 2018: Parallel Processing10.1007/978-3-319-96983-1_33(465-479)Online publication date: 1-Aug-2018
https://doi.org/10.1007/978-3-319-96983-1_33
Kalikar SNasre R(2017)DomLockACM Transactions on Parallel Computing10.1145/31275844:2(1-29)Online publication date: 18-Sep-2017
https://dl.acm.org/doi/10.1145/3127584
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents