Ensuring Code Quality in Multi-threaded Applications

By:

Test and QA Quality Assurance Best Practices
-The Technology Behind Static Code Analysis for Identifying Concurrency Defects

Most developers would agree that consumers of software today continually demand more from their applications. Because of its pace of evolution to date, the world now anticipates a seemingly endless expansion of capabilities from their software, regardless of where that software is applied. For the last 40 years of computing, Moore’s Law has held true, with the number of transistors available in an integrated circuit doubling approximately every two years.

This constant pace of innovation provided software developers with critical hardware resources, enabling them to expand the features and functionalities of their applications without concern for performance. However, while Moore’s Law still is holding steady, single-core processing has reached its performance ceiling. In response, hardware manufacturers have developed new multi-core (or multi-processor) devices to accomplish the speed gains to which the world had grown accustomed.

Today, the world of software development is presented with a new challenge. To fully leverage this new class of multi-core hardware, software developers must change the way they create applications. By turning their focus to multi-threaded applications, developers will be able to take full advantage of multi-core devices and deliver software that meets the demands of the world. But this paradigm of multi-threaded software development adds a new wrinkle of complexity for those who care the utmost about software quality. Concurrency defects such as race conditions and deadlocks are software defect types that are unique to multi-threaded applications. Complex and hard-to-find, these defects can quickly derail a software project. To avoid catastrophic failures in multi- threaded applications, software development organizations must understand how to identify and eliminate these deadly problems early in the application development lifecycle.

Testing software code is notoriously difficult, even for single-threaded applications. One reason this is a challenge, is that properly testing an application requires the simulation of all possible inputs to the program. Many organizations are satisfied when they achieve 95% line coverage in their programs (meaning 95% of all lines of code in their program are executed at least once in their test suite). However, this metric of coverage does not even come close to the total number of possible execution paths through a code base. Each decision point in a program means at least a factor of two in the number of paths though that program.

Multi-threaded applications add a new level of complexity to the program that results in an exponential increase in the number of possible run time scenarios. See Figure 1 below for an example as to how turning a simple single-threaded application into a multi-threaded application increases the complexity tremendously.

To completely test the program in Figure 1 the software developer would simply need to make sure that they fed the program a value that was less than 100 as well as a value that was greater than or equal to 100. Then the two paths through the program would be explored and the program would be tested entirely. (NOTE: This assumes that nothing interesting happens in the input_from_user function—admittedly a bad assumption in software development!). Now imagine that the end-user wanted this program to input two values instead of one with the same logic after the input. This change would increase the complexity of the single-threaded application in such a way that the software developer would need to explore four different paths to fully test the program.

Now imagine that a requirement comes in from the field to make this application multi-threaded to take advantage of a dual-core processor. This change would require that the code in Figure 1 would be executed simultaneously by two different threads to take in the two inputs. Assuming that each statement is made up of three instructions (likely an underestimate), the number of possible interleavings of the instructions in the two threads leads to a mind boggling 194,480 different execution possibilities.

By moving to multi-threaded code in this simplified example, complexity explodes by five orders of magnitude, creating a tremendous challenge for any tester of software. If this type of defect does happen to slip into the field, developers are then faced with a dramatic increase in the number of avenues that require exploration before they can determine the root cause of the problem. Worse, for the first time, developers may not be able to reproduce problems that occur in multi-threaded applications because they are not in control of how their application will be executed when it runs. The operating system and thread scheduler together decide when each thread will be executed as multiple threads execute. Fortunately, by leveraging breakthroughs in technology, static analysis solutions can analyze code prior to run-time enabling developers to identify and eliminate onerous multi-threaded defects including race conditions, thread blocks and deadlocks.

Deadlocks
Deadlocks (situations where a multi-threaded program cannot make any progress) are a particularly difficult concurrency issue to debug. They arise when the order of lock acquisition used by the program is inconsistent. A simple example is lock inversion, which happens when one thread attempts to acquire a lock (a), then holds on to the lock while attempting to acquire lock (b) . If another thread tries to acquire the locks in the opposite order (acquiring b before a), neither thread can make progress, and the program is deadlocked. A sample of this type of software defect can be found in Figure 2. (Note: While the remaining code examples in this paper are in Java, all the defects discussed herein can occur in any programming language.

If two distinct threads call methods lock1 and lock2, an unlucky scheduling might have the first thread acquire lock (a), while the second thread acquires lock (b). In this state, it is impossible for either thread to acquire the lock it needs to continue execution or release the lock it holds. More complicated deadlocks exist that involve the acquisition of multiple locks across multiple threads.

One way that advanced static analysis technology detects deadlocks is to ensure that all locks in the program are acquired and released in a consistent order. More concretely, the static analysis can construct an acyclic lock graph for a program. Nodes in a lock graph represent lock names, and an edge between nodes (a) and (b) denotes that at some point, lock (a) was held while lock (b) was acquired.

If a lock graph contains a cycle, the program may have a lock ordering or lock inversion deadlock. Innovative static analysis is now capable of finding these lock ordering defects inter-procedurally (through method calls), as these are likely to be missed by conventional code review or other defect detection techniques.

Full article...

Other Resource

... to read more articles, visit http://sqa.fyicenter.com/art/