Exclusion for composite objects

ABSTRACT

Designing concurrent object-oriented programs is hard. Correct programs must coordinate multiple threads accessing composite objects, using low-level mechanisms such as locks and read-write sets. Efficient programs must balance the complexity and overhead of the coordination mechanisms against the increased performance possible through concurrency. A method-level algebra of exclusion provides a succinct description of the conditions under which a thread must be excluded from a component of a composite object. Using the algebra, programmers can check whether their programs meet their exclusion requirements, can eliminate redundant exclusion controls, and can remove synchronisation overhead by reducing concurrency.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Jonathan Aldrich , Craig Chambers , Emin Gün Sirer , Susan J. Eggers, Static Analyses for Eliminating Unnecessary Synchronization from Java Programs, Proceedings of the 6th International Symposium on Static Analysis, p.19-38, September 22-24, 1999
• 3: P. S. Almeida. Baloon Types: Controlling sharing of state in data types. In ECOOP Proceedings, June 1997.
• 4: Pierre America, Pool-T: a parallel object-oriented language, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 5: C. Atkinson, S. Goldsack, A. D. Maio, and R. Bayan. Object oriented concurrency and distribution in DRAGOON. Journal of Object- Oriented Programming (JOOP), 4(1):11-19, 1991.
• 6: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 7: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 8: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 9: Jan Vitek , Boris Bokowski, Confined types, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.82-96, November 01-05, 1999, Denver, Colorado, United States
• 10: Grady Booch, Software Component with ADA, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1987
• 11: G. Booch. Software Components With Ada: Structures, Tools, and Subsystems. Benjamin/Cummings, 1990.
• 12: Per Brinch Hansen, Operating System Principles, Prentice Hall PTR, Upper Saddle River, NJ, 1973
• 13: Jean-Pierre Briot , Rachid Guerraoui , Klaus-Peter Lohr, Concurrency and distribution in object-oriented programming, ACM Computing Surveys (CSUR), v.30 n.3, p.291-329, Sept. 1998 [doi>10.1145/292469.292470]
• 14: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• 15: Andrew A. Chien , Uday S. Reddy , John Plevyak , Julian Dolby, ICC++-AC++ Dialect for High Performance Parallel Computing, Proceedings of the Second JSSST International Symposium on Object Technologies for Advanced Software, p.76-95, March 11-15, 1996
• 16: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 17: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 18: D. L. Detlefs, K. R. M. Leino, G. Nelson, and J. B. Saxe. Extended static checking. Technical Report 159, COMPAQ Systems Research Center, Dec. 1998.
• 19: Martin Fowler , Kendall Scott, UML distilled: applying the standard object modeling language, Addison-Wesley Longman Ltd., Essex, UK, 1997
• 20: E. Gamma, R. Helm, R. E. Johnson, and J. Vlissides. Design Patterns. Addison-Wesley, 1994.
• 21: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 22: L. Gunaseelan and R. J. LeBlanc. Distributed Eiffel: a language for programming multi-granular distributed objects. In International Conference on Computer Languages Proceedings, 1992.
• 23: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 24: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 25: D. Holmes. Synehronisation Rings: Composable Synehronisation for Object-Oriented Systems. PhD thesis, Macquarie Unviersity, Sydney, 1999.
• 26: David Holmes , James Noble , John Potter, Aspects of Synchronization, Proceedings of the Technology of Object-Oriented Languages and Systems - Tools-25, p.2, November 24-28, 1997
• 27: G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. V. Lopes, J.-M. Loingtier, and J. Irwin. Aspect oriented programming. In ECOOP Proceedings, 1997.
• 28: Douglas Lea, Concurrent Programming in Java(TM): Design Principles and Patterns (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2006
• 29: D. Lea. util.concurrent, a Java package. http://g.oswego, edu/, Apr. 1999.
• 30: Klaus-Peter Löhr, Concurrency annotations for reusable software, Communications of the ACM, v.36 n.9, p.81-89, Sept. 1993 [doi>10.1145/162685.162708]
• 31: C. V. Lopes. D: A Language Framework for Distributed Programming. PhD thesis, Northeastern University, 1997.
• 32: Satoshi Matsuoka , Akinori Yonezawa, Analysis of inheritance anomaly in object-oriented concurrent programming languages, Research directions in concurrent object-oriented programming, MIT Press, Cambridge, MA, 1993
• 33: Bertrand Meyer, Eiffel: the language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 34: Robin Milner , Joachim Parrow , David Walker, A calculus of mobile processes, I, Information and Computation, v.100 n.1, p.1-40, Sept. 1992 [doi>10.1016/0890-5401(92)90008-4]
• 35: S. E. Mitchell. TAO -- A Model for the Integration of Concurrency and Synehronisation in Object Oriented Programming. PhD thesis, University of York, 1995.
• 36: Oscar Nierstrasz, Regular types for active objects, Object-oriented software composition, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 37: James Noble , Jan Vitek , John Potter, Flexible Alias Protection, Proceedings of the 12th European Conference on Object-Oriented Programming, p.158-185, July 20-24, 1998
• 38: D. C. Schmidt. Strategized locking, thead-safe interface, and scoped locking: Patterns and idioms for simplifying multi-threaded C++ components. C++ Report, 11(9), Sept. 1999.
• 39: J. Van Den Bos , C. Laffra, PROCOL: a parallel object language with protocols, Conference proceedings on Object-oriented programming systems, languages and applications, p.95-102, October 02-06, 1989, New Orleans, Louisiana, United States
• 40: Glynn Winskel, An introduction to event structures, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, p.364-397, May 30-June 03, 1988
• 41: Akinori Yonezawa , Jean-Pierre Briot , Etsuya Shibayama, Object-oriented concurrent programming ABCL/1, Conference proceedings on Object-oriented programming systems, languages and applications, p.258-268, September 29-October 02, 1986, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI)

General Terms:
Design, Management, Performance, Theory