Pitfalls in teaching development and testing of concurrent programs and how to overcome them

Abstract

This lecture captures industrial and academic experience in teaching concurrent programming for several years. While the statement of a concurrent protocol is typically small taking only a few pages to complete, the statement implicitly introduces an exponential or possibly infinite space of possible interleavings. The novice is not aware of this, and as a result sometimes does not understand the lecture. To overcome this pitfall, exploration of the protocol interleaving is practiced from day one. A classical example being how many results does 100 threads executing i++ have? Separation of concerns is used to minimize the interleaving space at design time. Specifically, abstract primitives, such as atomic block and a conditional atomic block are introduced as a design tool. They are typically not to be found in practical programming languages. This reduces the space of interleavings to be considered at design time and facilitate verification and review of the protocol. On the other hand, the approach introduces pitfalls encountered in the translation/implementation stage. Once the abstract design is verified and/or tested, it needs to be translated to a commercial language where the synchronization primitives, for performance reasons, are weaker. For example, an atomic block is implemented using a lock unlock pair. But now atomicity needs to be ensured by the protocol implementer - a typical pitfall being the confusion of a lock/unlock code segment with an atomic block. Locations in the code that access the protected shared resources should be identified and access needs to follow the lock/unlock protocol. Exceptions and signals needs to be handled appropriately and adhere to the lock/unlock protocol. To avoid translation pitfalls, bug patterns are taught and precise understanding of the synchronization primitives is emphasized. Testing of the implemented protocol is taught. Testing should be aggressive, at unit test, and attempt to cover the interleaving space instead of common practice of testing concurrency at system test in a round about way through stress. Tools like ConTest or CHESS can be applied to this end. Copyright 2008 ACM.