IEEE Concurrency Virtual Roundtable

Applying Patterns to Meet the Challenges of Concurrent Software

Invited contribution to the IEEE Concurrency Special Edition on Software Engineering for Parallel and Distributed Systems, Vol. 5, No. 3, Fall 1997.

1. Why Patterns are Important for Concurrent Software

It is expensive and error-prone to develop complex concurrent systems in domains like telecommunications, avionics, and distributed medical imaging. Past challenges centered largely on efficient use of expensive computer and network hardware resources (such as memory, disk, CPUs, and bandwidth). During the last decade, however, advances in VLSI technology and fiber optics have increased computer processing power by 2-3 orders of magnitude and network channel speeds by 5-6 orders of magnitude.

Unfortunately, software quality and programmer productivity have not increased as dramatically as hardware performance. Across the industry, this situation has yielded a ``concurrent software crisis,'' where hardware gets smaller, faster, cheaper, and more reliable, whereas concurrent software gets larger, slower, and more expensive to develop, debug, and maintain. Ironically, much of the effort associated with building concurrent software is spent rediscovering core synchronization concepts (such as active objects) and reinventing common components (such as futures, tasks, and monitors). The problem is that despite significant advances in concurrency algorithms, specification techniques, and low-level multi-threading APIs, most developers lack an intuition for how and when to best apply these techniques and APIs.

Patterns are an important means to alleviate the costly rediscovery and reinvention of proven concurrent software concepts and component solutions. Patterns are useful for documenting recurring micro-architectures, which are abstractions of common object-structures that expert developers apply to solve concurrent software problems (such as deadlock avoidance and wait-free synchronization). By studying and applying patterns, developers can often avoid traps and pitfalls that have traditionally been learned only by prolonged trial and error.

I believe that one of main issues involved in developing high quality parallel and distributed systems is identifying and documenting the key design patterns necessary to solve complex concurrent software problems. In order for concurrent software development to move from an art to an engineering discipline, successful practices and design expertise must be documented systematically and disseminated widely. Without a thorough understanding of successful concurrency patterns, developing complex concurrent systems will remain expensive and error-prone.

Until recently, patterns used to develop complex concurrent systems existed largely in programming folklore. Today, these concurrency patterns are becoming more thoroughly documented and more widely applied by researchers and developers. The remainder of this article explains the types of problems that patterns address and outlines our experiences applying patterns to reusable concurrent object-oriented communication frameworks.

2. How Patterns Address the Challenges of Concurrent Software

One source of concurrent software complexity is largely accidental, arising from limitations with existing development tools and platforms. For instance, the diversity of hardware and software platforms complicates the development of portable concurrent applications and tools that run on multiple OS platforms like POSIX, Win32, and embedded systems. These tool and platform limitations can be addressed by building concurrent object computing middleware (such as CORBA and DCOM) and object-oriented communication frameworks and components (such as ACE) that shield developers from tedious, error-prone, and non-portable programming details.

Core design patterns (like Adapter, Proxy, Facade, and Bridge [GoF]) have been widely used to motivate and document the strategic and tactical architectural designs of middleware, frameworks, and components. However, most of these design patterns were identified by developers of object-oriented user interfaces, which are judged primarily in terms of software quality factors like usability, extensibility, and portability. In contrast, concurrent software has traditionally emphasized high performance and correctness over other quality factors. Therefore, it has become increasingly important to document patterns that guide developers through the solution space for inherently difficult concurrent programming tasks such as the following:

Selecting efficient concurrency architectures that minimize the overhead of context switching, synchronization, and data movement in high-performance concurrent applications (such as video-on-demand servers, Object Request Brokers, and HTTP servers). Patterns such as Thread-per Request, Thread Pool, and Thread-per Session are commonly used as concurrency architectures.
Structuring efficient concurrent systems that contain synchronous and asynchronous components. Patterns like Reactor, Half-Sync/Half-Async, and Active Object are commonly used to decouple synchronous components from asynchronous components in a system in order to simplify concurrent programming effort without degrading execution efficiency.
Eliminating unnecessary threads and locks in concurrent applications without compromising correctness. Patterns such as Thread-Specific Storage and Double-Checked Locking minimize the cost of accessing state shared by multiple methods or threads in concurrent programs.
Selecting the appropriate synchronization primitives to increase performance and reduce maintenance costs of parallel programs running on symmetric shared-memory multi-processors [McKenney].

Solving these inherent complexities requires much more than portable multi-threading APIs or Object Request Brokers -- it requires deep knowledge of successful patterns for developing concurrent protocols, components, frameworks, and system architectures. Much research remains to be done to identify, document, classify, and formalize these types of patterns and pattern languages.

3. Lessons Learned and Future Directions

My research group at Washington University has used design pattern-based reuse strategies for the past three years. These strategies are applied toward prototype and production communication systems we're building as part of the ACE project [Schmidt:94]. Thus far, our experience has been very positive. The following is a synopsis of our lessons learned thus far:

Patterns facilitate reuse of architecture and design artifacts, which reduces the effort required to develop high quality, reusable frameworks and components for concurrent software. We've been able to reuse concurrency patterns in ACE even when reuse of algorithms, implementations, interfaces, or detailed designs was not feasible due to differences in OS platforms [Schmidt:95].
Patterns document ``best practices'' of concurrent software systems, which have traditionally resided in the minds of expert developers or buried within complex system source code. We've found that capturing the most useful strategies and tactics of our communication frameworks in terms of patterns lowered the learning curve for new developers by giving them good role models for evolving our communication frameworks and applications.
Patterns preserve important design information, which is often lost over time, thereby increasing maintenance costs and decreasing software quality. On the ACE project we've significantly reduced our software maintenance effort by documenting the intent, structure, and behavior of ACE's concurrent network programming components in terms of the patterns they reify.
Patterns help to guide design choices for new systems -- Patterns capture experience and insight in a form that can be used to address new design challenges. By understanding the potential traps and pitfalls in their domain, developers can select suitable concurrency architectures, protocols, and platform features without wasting time and effort implementing solutions that are known to be inefficient or error-prone.

Over the next few years, I expect that a wealth of concurrent software design knowledge will be documented in pattern form and implemented in application frameworks. In addition, I believe that we'll see a closer connection between patterns and formalisms for specifying, analyzing, and validating concurrent software systems. However, these patterns will only be successful to the extent that researchers and developers read them, learn them, apply them, and write them. This article just scratches the surface of topics related to patterns for concurrent systems. To find out about books, online papers, electronic mailing lists, and conferences on concurrency patterns please see the Patterns Home Page (st-www.cs.uiuc.edu/users/patterns/patterns.html).

References

[GoF] E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Reading, MA: Addison-Wesley, 1995.

[McKenney] P. McKenney, Selecting Locking Primitives for Parallel Programs , CACM, (Special Issue on Software Patterns, D. Schmidt, Ralph Johnson, and M. Fayad Eds.), 39, 10, October 1996.

[Schmidt:94] D. Schmidt ``ACE: an Object-Oriented Framework for Developing Distributed Applications,'' Proceedings of the 6th USENIX C++ Technical Conference, Cambridge, MA, April, 1994.

[Schmidt:95] D. Schmidt, Using Design Patterns to Develop Reusable Object-Oriented Communication Software, CACM, (Special Issue on Object-Oriented Experiences, M. Fayad and W.T. Tsai Eds.), 38, 10, October 1995.