COMP 3000 Essay 2 2010 Question 7

Paper

Ad Hoc Synchronization Considered Harmful

Weiwei Xiong University of California, San Diego

Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou University of Illinois at Urbana-Champaign

Zhiqiang Ma Intel

Research Problem

As the computer industry continues to shift towards multicore processors, concurrent programming and the use of multithreaded designs has increased to keep up with this growing trend. Multithreaded applications can be found in a variety of popular applications today as they take advantage of the multithreaded approach. However, the concepts behind concurrent programming bring with them a host of potential dangers in the form of race conditions and deadlocks resulting from bad programming design and threads accessing shared memory. Fortunately, there are well known and standard methods for dealing with these problems, i.e synchronization primitives. But in real world situations, due to a variety of reasons, as we shall see, programmers often implement their own "ad hoc" synchronizations that eschew common design standards. Ad hoc synchronizations are not well documented and are not discovered by traditional tools for race conditions that look for standard synchronization primitives.

This paper addresses these concerns in two regards, first it details a thorough study of ad hoc synchronizations. It details their nature, dangers, impact on bug detection tools and prevalence in several major open-source applications. Secondly, it introduces SyncFinder, a program that detects all ad hoc synchronizations and automatically annotates the source code where ad hoc sychnronizations are found. This can see use in conjunction with other data race checkers to improve accuracy and to build custom tools for finding deadlocks and bad programming practices.

With detailed analysis of ad hoc synchronization and study of their occurrences in several applications, the research ultimately concludes that they are harmful and should be removed. At the same time, SyncFinder detects and documents ad hoc synchronizations in the source code enabling programmers for the first time to easily track and remove them.

Contribution

Intro to the study of the major applications and what they found

Findings

1.they are prevalent, all applications had them

2. hard to find

3. error prone

4.effect other bug detection

5. They are diverse. Different forms, multiple exits and dependencies

Reasons behind why people use ad hoc synchronization and possible improvements over them ie Synchronization primitives

SyncFinder

Intro to what it is and what it does

How it works

1. find loops

2. identify sync loops

3. EDV analysis

4. Pruning

5. Annotation of found sync

Uses

1. A tool to detect bad practices

2. Extensions to data race detection

Related Work and similar tools

There has been attempts to remove synchronization issues entirely from concurrent programming, such as transactional memory¹, a lock-free synchronization that does not require mutexes, and avoids having to use lock, unlock operations. Other attempts have been made to remove bugs that would otherwise be safe from data races but are are still at risk of unintended effects from thread interactions, such as Atomizer², a dynamic atomicity checker.

There are tools that detect data races such as CHESS³, a dynamic data race checker that runs through all possible thread execution paths and CTrigger⁴, a tool that checks for atomicity violations. The problem with these programs is that they only look for standard synchronization methods and structures, such as lock() and cond_wait(). They are not looking for ad hoc synchronizations.

A similar tool to SyncFinder exists that can detect simple spinning, also an ad hoc synchronization⁵, but it only detects simple spinning and not the more complicated ad hoc variations.

Several studies on bug characteristics⁶ and concurrency bugs⁷ have been composed. This paper complements these studies to better understand the nature of ad hoc synchronizations and their occurrence in concurrent programs.

Critique

1. Uses static approach, dynamic would be better

• As stated in the paper, dynamic introduces run-time overhead and is not guaranteed to find if not executed in the test cases

2. not entirely accurate, some false positives.

3. In terms of style, lots of unnecessary repetition

References

¹ Author, 2010. Title. [online] Company(optional) Available at: <http://www.cs.brown.edu/~mph/HerlihyM93/herlihy93transactional.pdf> [Accessed 23 November 2010].

² Author, 2010. Title. [online] Company(optional) Available at: <http://www.cs.williams.edu/~freund/papers/atomizer-padtad.pdf> [Accessed 23 November 2010].

³ Author, 2010. Title. [online] Company(optional) Available at: <http://research.microsoft.com/pubs/70509/tr-2007-149.pdf> [Accessed 23 November 2010].

⁴ Author, 2010. Title. [online] Company(optional) Available at: <http://pages.cs.wisc.edu/~shanlu/paper/asplos092-zhou.pdf> [Accessed 23 November 2010].

⁵ LI, T., LEBECK, A. R., AND SORIN, D. J. Spin detection hardware for improved management of multithreaded systems. IEEE Transactions on Parallel and Distributed Systems PDS-17, 6 (June 2006), 508–521.

⁶ Author, 2010. Title. [online] Company(optional) Available at: <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.1203&rep=rep1&type=pdf> [Accessed 23 November 2010].

⁷ Author, 2010. Title. [online] Company(optional) Available at: <[1]> [Accessed 23 November 2010].