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.

Background Concepts

Race conditions, deadlocks

Race conditions are an unintended side-effects of programming in concurrent systems, they occur when two or more processes have access to a shared resource and at least one of them have write privilege. This leads to processes modifying the data that all processes share as other may be reading them and results in the reading of stale/incorrect data. They will occur during the execution of the program and often times very difficult to detect or manipulate data in subtle ways.

Deadlock is when two or more processes share a resource and each process is waiting on the other processes to unlock the resource. It becomes a circular chain and no process can continue.

Both these issues occur in concurrent programming and although there are no general solutions for deadlock⁹, there are suitable methods for dealing with them, and in the case of race conditions, using mutual exclusion locks and synchronization primitives can prevent race conditions. But no programmer is infallible and so there is always the issue of race conditions and deadlocks present in production code.

Ad Hoc Synchronization

Ad hoc synchronizations are loops called sync loops that continue until certain conditions are met via outside variables called sync variables. They are designed to control the flow of thread execution much like locking and unlocking of resources. There can be multiple sync variables in a sync loop and they can have multiple exit conditions and dependencies. The diversity of the sync loops, their dependencies and execution paths leads to difficulty in finding them.

Synchronization primitives

Synchronization variables act as barriers to memory that prevent threads from accessing the same shared resource concurrently⁸. They come in many forms such as mutexes and condition variables. Mutexes are mutual exclusive locks that threads employ to lock a resource that they need. No other threads can access them at that point. Once they are finished, they release the lock and the other threads can then lock and access the resource. Condition variables are variables that will block the thread until a certain condition is met. This allows the thread to only execute when it is safe to perform its operation.

Contribution

With concurrent programming commonly used in modern applications, we face many issues that result from having simultaneous execution. In order to maintain a concurrent system, synchronizations are required to ensure that the executing tasks do not interfere with each other, which could be disastrous for the system. However, many programmers do not use proper synchronization techniques to deal with these issues. Rather, they implement synchronizations in an ad hoc fashion. In this study, it is shown that ad hoc synchronizations, though implemented as a solution to concurrency issues, are indeed undesirable in a system. This paper details the characteristics of ad hoc synchronizations and the issues associated with this implementation and introduces the program, SyncFinder, which is used to identify such synchronizations in code.

Findings

In order to identify the characteristics of ad hoc synchronizations, 12 mainstream programs were examined to find instances of ad hoc synchronizations. These programs were either of server, desktop or scientific type, including Apache, MySQL and Mozilla. Through manual inspection of the source code, these characteristics of ad hoc synchronizations were found.

1. In all programs studied, it was found that each had numerous ad hoc synchronizations implemented. The number of synchronizations found ranged from 6-83, with server type programs inhabiting the higher portion of the interval. It is likely that programmers use this type of synchronization for two reasons.

• In order to ensure a certain order of execution in the case of a concurrent system, programmers will use ad hoc synchronization to superimpose this order. With traditional synchronization techniques, this can vary between systems. As the order can vary, it is difficult to create a common interface.
• Some synchronization techniques introduce heavy-weight synchronization primitives. As such, programmers will use ad hoc synchronizations to avoid this and supposedly protect performance.

1. Often, it is very hard to identify an ad hoc loop as a synchronization method. They are hard to distinguish from other computational loops and as the implementations are diverse, it is hard to pinpoint them from the code. This makes the system hard to maintain, as other programmers will not be able to identify ad hoc loops implemented by another and debugging programs cannot recognize them as issues.

1. It was found that ad hoc synchronizations often introduce bugs into the system such as deadlocks or hangs. As these are different than those caused by locks and other synchronizations it is hard for detection tools to recognize them if they were not first identified either manually or automatically.

1. As they are not easily recognizable, it is hard for bug detection tools to fix issues presented by ad hoc synchronizations. In fact, it is often the case that these tools either do not find these issues or report them as false positives as the tool is unaware of the "work arounds" put into affect by using ad hoc synchronization. Since they cannot find these problems, it severely impacts the effectiveness of such tools.

This also impacts analysis of performance. Synchronization is quite costly and if a tool cannot recognize the formm of synchronization, a false report is generated and the programmer will not be aware. This may cause poor decisions on the part of the programmer just from the fact that ad hoc synchronizations are hard to identify.

1. The reason ad hoc synchronizations are hard to identify stems from the fact that there is no single way of implementing it. The ways in which ad hoc synchronizations are done are quite diverse and so it is hard to identify just on a few criteria. Some typical characteristics of an ad hoc synchronization follow.

• These loops can contain one or multiple exit conditions. Some or all of these exit conditions may be satisfied by remote threads while others may be satisfied locally.
• [working on it]

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

¹ M Herlihy and J.E.B. Moss, 2NA0. Transactional Memory: Architectural Support for Lock-Free Data Structures. [online] Available at: <http://www.cs.brown.edu/~mph/HerlihyM93/herlihy93transactional.pdf> [Accessed 23 November 2010].

² C Flanagan and S N Freund, 2NA0. Atomizer: A Dynamic Atomicity Checker For Multithreaded Programs (Summary). [online] Company(optional) Available at: <http://www.cs.williams.edu/~freund/papers/atomizer-padtad.pdf> [Accessed 23 November 2010].

³ T Ball,M Musuvathi and S Qadeer, 2NA0. CHESS: A Systematic Testing Tool for Concurrent. [online] Company(optional) Available at: <http://research.microsoft.com/pubs/70509/tr-2007-149.pdf> [Accessed 23 November 2010].

⁴ Author, 2NA0. 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, 2NA0. 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, 2NA0. Title. [online] Company(optional) Available at: <[1]> [Accessed 23 November 2010].

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

⁹ Author, 2010. Title. [online] Company(optional) Available at: <http://homeostasis.scs.carleton.ca/wiki/index.php/Basic_Synchronization_Principles> [Accessed 23 November 2010].