Abstract
Concurrent data accesses in high-level languages like Java and C# are typically mediated using mutual-exclusion locks. Threads use locks to guard the operations performed while the lock is held, so that the lock’s guarded operations can never be interleaved with operations of other threads that are guarded by the same lock. This way both atomicity and isolation properties of a thread’s guarded operations are enforced. Recent proposals recognize that these properties can also be enforced by concurrency control protocols that avoid well-known problems associated with locking, by transplanting notions of transactions found in database systems to a programming language context. While higher-level than locks, software transactions incur significant implementation overhead. This overhead cannot be easily masked when there is little contention on the operations being guarded.
We show how mutual-exclusion locks and transactions can be reconciled transparently within Java’s monitor abstraction. We have implemented monitors for Java that execute using locks when contention is low and switch over to transactions when concurrent attempts to enter the monitor are detected. We formally argue the correctness of our solution with respect to Java’s execution semantics and provide a detailed performance evaluation for different workloads and varying levels of contention. We demonstrate that our implementation has low overheads in the uncontended case (7% on average) and that significant performance improvements (up to 3×) can be achieved from running contended monitors transactionally.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adya, A., Gruber, R., Liskov, B., Maheshwari, U.: Efficient optimistic concurrency control using loosely synchronized clocks. ACM SIGMOD Record 24(2), 23–34 (1995)
Agesen, O., Detlefs, D., Garthwaite, A., Knippel, R., Ramakrishna, Y.S., White, D.: An efficient meta-lock for implementing ubiquitous synchronization. In: OOPSLA 1999 [26], pp. 207–222
Aldrich, J., Sirer, E.G., Chambers, C., Eggers, S.J.: Comprehensive synchronization elimination for Java. Science of Computer Programming 47(2-3), 91–120 (2003)
Alpern, B., Attanasio, C.R., Barton, J.J., Cocchi, A., Hummel, S.F., Lieber, D., Ngo, T., Mergen, M., Shepherd, J.C., Smith, S.: Implementing Jalapeño in Java. In: OOPSLA 1999 [26], pp. 314–324
Bacon, D., Konuru, R., Murthy, C., Serrano, M.: Thin locks: Featherweight synchronization for Java. In: Proceedings of the ACM Conference on Programming Language Design and Implementation, Montréal, Canada, ACM SIGPLAN Notices 33(5), 258–268 (1998)
Bacon, D.F., Cheng, P., Rajan, V.T.: A real-time garbage collector with low overhead and consistent utilization. In: Conference Record of the ACM Symposium on Principles of Programming Languages, New Orleans, Lousiana. ACM SIGPLAN Notices 38(1), 285–298 (2003)
Blackburn, S.M., Hosking, A.L.: Barriers: Friend or foe? In: Bacon, D.F., Diwan, A. (eds.) Proceedings of the ACM International Symposium on Memory Management, Vancouver, Canada, October 2004, pp. 143–151. ACM Press, New York (2004)
Boyapati, C., Lee, R., Rinard, M.C.: Ownership types for safe programming: preventing data races and deadlocks. In: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Seattle, Washington. ACM SIGPLAN Notices 37(11), 211–230 (2002)
Carey, M.J., DeWitt, D.J., Kant, C., Naughton, J.F.: A status report on the OO7 OODBMS benchmarking effort. In: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Portland, Oregon. ACM SIGPLAN Notices 29(10), 414–426 (1994)
Carey, M.J., DeWitt, D.J., Naughton, J.F.: The OO7 benchmark. In: Proceedings of the ACM International Conference on Management of Data, Washington, DC. ACM SIGMOD Record 22(2), 12–21 (1993)
Choi, J.-D., Lee, K., Loginov, A., O’Callahan, R., Sarkar, V., Sridharan, M.: Efficient and precise datarace detection for multithreaded object-oriented programs. In: Proceedings of the ACM Conference on Programming Language Design and Implementation, Berlin, Germany. ACM SIGPLAN Notices 37(5), 258–269 (2002)
Clarke, D.G., Potter, J.M., Noble, J.: Ownership types for flexible alias protection. In: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Vancouver, Canada. ACM SIGPLAN Notices 33(10), 48–64 (1998)
Flanagan, C., Freund, S.N.: Type-based race detection for Java. In: PLDI 2000[27], pp. 219–232 (2000)
Flanagan, C., Freund, S.N.: Atomizer: a dynamic atomicity checker for multithreaded programs. In: Conference Record of the ACM Symposium on Principles of Programming Languages, Venice, Italy, January 2004, pp. 256–267 (2004)
Flanagan, C., Qadeer, S.: Types for atomicity. In: Proceedings of the 2003 ACM SIGPLAN International Workshop on Types in Language Design and Implementation, New Orleans, Louisiana, January 2003, pp. 1–12 (2003)
Flatt, M., Krishnamurthi, S., Felleisen, M.: Classes and mixins. In: Conference Record of the ACM Symposium on Principles of Programming Languages, San Diego, California, January 1998, pp. 171–183 (1998)
Harris, T., Fraser, K.: Language support for lightweight transactions. In: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM SIGPLAN Notices 38(11), 388–402 (2003)
Harris, T., Marlow, S., Peyton-Jones, S., Herlihy, M.: Composable memory transactions. In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Chicago, Illinois, June 2005, pp. 48–60 (2005)
Herlihy, M.: Apologizing versus asking permission: Optimistic concurrency control for abstract data types. ACM Trans. Database Syst. 15(1), 96–124 (1990)
Herlihy, M., Luchangco, V., Moir, M., Scherer III, W.N.: Software transactional memory for dynamic-sized data structures. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Boston, Massachusetts, July 2003, pp. 92–101 (2003)
Kung, H.T., Robinson, J.T.: On optimistic methods for concurrency control. ACM Trans. Database Syst. 9(4), 213–226 (1981)
Manson, J., Pugh, W., Adve, S.: The Java memory model. In: Conference Record of the ACM Symposium on Principles of Programming Languages, Long Beach, California, January 2005, pp. 378–391 (2005)
Mellor-Crummey, J.: On-the-fly detection of data races for programs with nested fork-join parallelism. In: Proceedings of the ACM/IEEE Conference on Supercomputing, Albuquerque, New Mexico, November 1991, pp. 24–33 (1991)
Moss, J.E.B.: Nested Transactions: An Approach to Reliable Distributed Computing. MIT Press, Cambridge (1985)
O’Callahan, R., Choi, J.-D.: Hybrid dynamic data race detection. In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, San Diego, California, June 2003, pp. 167–178 (2003)
Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado. ACM SIGPLAN Notices 34(10) (1999)
Proceedings of the ACM Conference on Programming Language Design and Implementation, Vancouver, Canada. ACM SIGPLAN Notices 35(6) (2000)
Ruf, E.: Effective synchronization removal for Java. In: PLDI 2000 [27], pp. 208–218 (2000)
Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15(4), 391–411 (1997)
Smith, L.A., Bull, J.M., Obdrzálek, J.: A parallel Java Grande benchmark suite. In: Proceedings of the ACM/IEEE Conference on Supercomputing, Denver, Colorado, November 2001, p. 8 (2001)
SPEC. SPECjvm98 benchmarks (1998), http://www.spec.org/osg/jvm98
Stonebraker, M., Hellerstein, J. (eds.): Readings in Database Systems, 3rd edn. Morgan Kaufmann, San Francisco (1998)
Ungureanu, C., Jagannathan, S.: Concurrency Analysis for Java. In: Palsberg, J. (ed.) SAS 2000. LNCS, vol. 1824, pp. 413–432. Springer, Heidelberg (2000)
von Praun, C., Gross, T.R.: Object race detection. In: Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM SIGPLAN Notices 36(11), 70–82 (2001)
von Praun, C., Gross, T.R.: Static conflict analysis for multi-threaded object-oriented programs. In: Proceedings of the ACM Conference on Programming Language Design and Implementation, San Diego, California, June 2003, pp. 115–128 (2003)
Welc, A., Jagannathan, S., Hosking, A.L.: Transactional monitors for concurrent objects. In: Odersky, M. (ed.)Proceedings of the European Conference on Object-Oriented Programming. LNCS, vol. 3086, pp. 519–542. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Welc, A., Hosking, A.L., Jagannathan, S. (2006). Transparently Reconciling Transactions with Locking for Java Synchronization. In: Thomas, D. (eds) ECOOP 2006 – Object-Oriented Programming. ECOOP 2006. Lecture Notes in Computer Science, vol 4067. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11785477_8
Download citation
DOI: https://doi.org/10.1007/11785477_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35726-1
Online ISBN: 978-3-540-35727-8
eBook Packages: Computer ScienceComputer Science (R0)