Abstract
Fine-grained locking is often necessary to increase concurrency. Correctly implementing fine-grained locking with today's concurrency primitives can be challenging—race conditions often plague programs with sophisticated locking schemes.
We present views, a new approach to concurrency control. Views ease the task of implementing sophisticated locking schemes and provide static checks to automatically detect many data races. A view of an object declares a partial interface, consisting of fields and methods, to the object that the view protects. A view also contains an incompatibility declaration, which lists views that may not be simultaneously held by other threads. A set of view annotations specify which code regions hold a view of an object. Our view compiler performs simple static checks that identify many data races. We pair the basic approach with an inference algorithm that can infer view incompatibility specifications for many applications.
We have ported four benchmark applications to use views: portions of Vuze, a BitTorrent client; Mailpuccino, a graphical email client; jphonelite, a VoIP softphone implementation; and TupleSoup, a database. Our experience indicates that views are easy to use, make implementing sophisticated locking schemes simple, and can help eliminate concurrency bugs. We have evaluated the performance of a view implementation of a red-black tree and found that views can significantly improve performance over that of the lock-based implementation.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Views: Synthesizing fine-grained concurrency control
- Abadi, M., Flanagan, C., and Freund, S. N. 2006. Types for safe locking: Static race detection for Java. ACM Trans. Program. Lang. Syst. 28, 2, 207--255. Google ScholarDigital Library
- Bacon, D. F., Strom, R. E., and Tarafdar, A. 2000. Guava: A dialect of Java without data races. In Proceedings of the International Conference on Object-Oriented Programming, Systems, Languages, and Applications. Google ScholarDigital Library
- Blanchet, B. 1999. Escape analysis for object-oriented languages: application to Java. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. 20--34. Google ScholarDigital Library
- Boyapati, C., Lee, R., and Rinard, M. 2002. Ownership types for safe programming: Preventing data races and deadlocks. InProceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. Google ScholarDigital Library
- Boyapati, C. and Rinard, M. 2001. A parameterized type system for race-free Java programs. In Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. Google ScholarDigital Library
- Buhr, P. A. and Harji, A. S. 2005. Concurrent urban legends. Concur. Comput. Pract. Exper. 17, 9, 1133--1172. Google ScholarDigital Library
- Cherem, S., Chilimbi, T., and Gulwani, S. 2008. Inferring locks for atomic sections. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 304--315. Google ScholarDigital Library
- Choi, J., Lee, K., Loginov, A., O'Callahan, R., Sarkar, V., and Sridharan, M. 2002. Efficient and precise datarace detection for multithreaded object-oriented programs. In Proceedings of the ACM Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- Demsky, B. and Lam, P. 2010. Views: Object-inspired concurrency control. In Proceedings of the International Conference on Software Engineering. Google ScholarDigital Library
- Emmi, M., Fischery, J. S., Jhala, R., and Majumdar, R. 2007. Lock allocation. In Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Google ScholarDigital Library
- Engler, D. and Ashcraft, K. 2003. RacerX: Effective, static detection of race conditions and deadlocks. In Proceedings of the 19th ACM Symposium on Operating Systems Principles. Google ScholarDigital Library
- Flatt, M., Krishnamurthi, S., and Felleisen, M. 1998. Classes and mixins. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '98). ACM, New York, NY, 171--183. Google ScholarDigital Library
- Greenhouse, A. 2003. A programmer-oriented approach to safe concurrency. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA. Google ScholarDigital Library
- Halpert, R. L., Pickett, C. J., and Verbrugge, C. 2007. Component-based lock allocation. In Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques. Google ScholarDigital Library
- Harris, T., Larus, J., and Rajwar, R. 2010. Transactional Memory, 2 ed. Vol. 5. Morgan and Claypool Publishers. Google ScholarDigital Library
- Hicks, M., Foster, J. S., and Pratikakis, P. 2006. Lock inference for atomic sections. In Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing.Google Scholar
- Korty, J. A. 1989. Sema: A lint-like tool for analyzing semaphore usage in a multithreaded UNIX kernel. In Proceedings of the USENIX Winter Technical Conference.Google Scholar
- Kulkarni, M., Nguyen, D., Prountzos, D., Sui, X., and Pingali, K. 2011. Exploiting the commutativity lattice. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- Lev, Y., Luchangco, V., and Olszewski, M. 2009. Scalable reader-writer locks. In Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures. ACM, New York, NY, 101--110. Google ScholarDigital Library
- Marino, D., Musuvathi, M., and Narayanasamy, S. 2009. LiteRace: Effective sampling for lightweight data-race detection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- Naik, M. 2008. Effective static race detection for Java. Ph.D. thesis, Stanford University. Google ScholarDigital Library
- Naik, M. and Aiken, A. 2007. Conditional must not aliasing for static race detection. In Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 327--338. Google ScholarDigital Library
- Naik, M., Aiken, A., and Whaley, J. 2006. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN conference on Programming Language Design and Implementation. 308--319. Google ScholarDigital Library
- Nystrom, N., Clarkson, M. R., and Myers, A. C. 2003. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction. Google ScholarDigital Library
- Orlin, J. 1977. Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae 80, 5, 406--424.Google ScholarCross Ref
- Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., and Anderson, T. 1997. Eraser: A dynamic data race detector for multi-threaded programs. In Proceedings of the Symposium on Operating Systems Principles. Google ScholarDigital Library
- Sterling, N. 1993. Warlock: A static data race analysis tool. In Proceedings of the USENIX Winter Technical Conference.Google Scholar
- Sutherland, D. F. and Scherlis, W. L. 2010. Composable thread coloring. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '10). 233--244. Google ScholarDigital Library
- Vaziri, M., Tip, F., and Dolby, J. 2006. Associating synchronization constraints with data in an object-oriented language. In Proceedings of the 33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Google ScholarDigital Library
- Vaziri, M., Tip, F., Dolby, J., Hammer, C., and Vitek, J. 2010. A type system for data-centric synchronization. In Proceedings of the 24th European Conference on Object-Oriented Programming. Google ScholarDigital Library
- Von Praun, C. and Gross, T. 2001. Object-race detection. In Proceedings of the International Conference on Object-Oriented Programming, Systems, Languages, and Applications. Google ScholarDigital Library
- Yeung, D. and Agarwal, A. 1993. Experience with fine-grain synchronization in MIMD machines for preconditioned conjugate gradient. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 187--197. Google ScholarDigital Library
- Zhang, Y., Sreedhar, V. C., Zhu, W., Sarkar, V., and Gao, G. R. 2007. Minimum lock assignment: A method for exploiting concurrency among critical sections. InProceedings of the International Workshop on Languages and Compilers for Parallel Computing.Google Scholar
Index Terms
- Views: Synthesizing fine-grained concurrency control
Recommendations
A Transactional Correctness Tool for Abstract Data Types
Transactional memory simplifies multiprocessor programming by providing the guarantee that a sequential block of code in the form of a transaction will exhibit atomicity and isolation. Transactional data structures offer the same guarantee to concurrent ...
Refined transactional lock elision
PPoPP '16Transactional lock elision (TLE) is a well-known technique that exploits hardware transactional memory (HTM) to introduce concurrency into lock-based software. It achieves that by attempting to execute a critical section protected by a lock in an atomic ...
Inferring locks for atomic sections
PLDI '08: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and ImplementationAtomic sections are a recent and popular idiom to support the development of concurrent programs. Updates performed within an atomic section should not be visible to other threads until the atomic section has been executed entirely. Traditionally, ...
Comments