Deadlock: frog vs. snake
Photo: David Maitland / National Geographic

Continuing the discussion about the embedded community moving to muticore/hetrogeneous hardware from watch out here comes multicore, embedded software development teams have historically been shielded from mulitcore issues. This is due to the specialized functionality of many embedded application classes and the inherent serialized nature of the C language.^[1]

Muticore is an ambiguous term for software developers and one they don’t really use; software developers think in terms of threads/processes and concurrency, not how many cores or processors are available on the target. Concurrency is not a new topic either as Mark Smotherman captured in a history of multithreading, it has been a subject in computer science since its early beginnings in the 1950s.

What has changed is the rapidly increasing use of multicore technologies for embedded devices. One of the prominent software challenges that moving to multicore execution exposes is latent deadlocking bugs as true parallel execution comes into play, instead of a single core’s task scheduling/context switching techniques.

As an example, consider the following code snippet, which has been paraphrased from a deadlock discovered in a real-world open source multithreaded project.

Can you spot the deadlock?

lock_t lock1, lock2;
int refCount = 0;

void enter() {
   reserve_lock(lock1);
      if( refCount == 0 )
         reserve_lock(lock2);
       release_lock(lock1);
   refCount++;
}

void leave() {
   reserve_lock(lock1);
   refCount--;
   if( refCount == 0 )
      release_lock(lock2);
   release_lock(lock1);
}

To see the answer and understand the conditions that lead to the deadlock, download Klocwork’s whitepaper on Developing software for multicore.

A little about the picture in this post.  I found it when searching for pictures of deadlocks.  The photographer, David Maitland, titled his image “Deadlock” and describes it as a continuing struggle between a Morelet’s tree frog and cat-eyed snake. After three hours in the high-stakes cage match, Maitland said there was no clear winner.

VDC Research, “Next Generation Embedded Hardware Architectures: Driving Onset of Project Delays, Costs Overruns, and Software Development Challenges”, September 2010.

Processing Architecture for embedded devices in the current projects and expected in next two years

Although multicore and multiprocessor technologies have started to proliferate in the embedded market, smartphone manufacturers are in the midst of a rapid shift to multicores due the market transistion from business users to consumers. It’s becoming evident that in order for handset manufactures to differentiated their products, a feature war has commenced: wireless connectivity, video/flash/audio playback and even video creation/editing/conferencing have become are market drivers.

CPU designers have already responded to this need, just last week ARM announced its next generation of Cortex^™-A15 MPCore^™ design and Intel entered the smartphone cpu market earlier this year with the new Atom Z6 core.

For perspective, in a short few years mobile handset industry has had to move from relatively simple devices supporting cellular communication and user-interface tasks to multicore/multi-chip designs in order to grow features and thus market share. Until the arrival of power-aware multicore and heterogeneous chipsets, cellular devices have been limited by computational horsepower, power envelopes and time-to-market issues.

In any market with tremendous competition, time-to-market is crucial and one of the fastest methods to add features within the tight power budget is to add additional task-specialized silicon either as heterogeneous cores or chips from third-party suppliers that can be put to sleep or turned off entirely when not required.

Feature growth has in turn placed new burdens on mobile software development teams. Leaving the comfortable environment of a single core means addressing potential threading/concurrency problems and endian ordering issues when integer data is transmitted off-core.

Klocwork commissioned VDC Research to quantify the business impact of moving to multicore/multiprocessor environments and the results of this growing complexity is stark: multicore and multiprocessor software projects are

• 4.5X more expensive,
• have 25% longer schedules,
• and require almost 3x as many software engineers.^[1]

Embedded and especially smartphone development teams need to be gearing up for the feature arms race to come and should be looking at methods to mitigate theses impacts by implementing productivity tools like static analysis and automated code reviews sooner than later.

[1] VDC Research, “Next Generation Embedded Hardware Architectures: Driving Onset of Project Delays, Costs Overruns, and Software Development Challenges”, September 2010.

Interesting article on static analysis tools to help find concurrency issues.  These so called “Parallel Lint” tools are specific to finding these types of issues.  Overall there are some great discussions on certain tools, and it is always nice when Klocwork gets mentioned.  But my problem is with the categorization of these tools.  It always makes me feel sick every time someone puts Klocwork in the same category of “powerful static analysis” with JLint, C++Test, FXCop and my favorite PC-Lint.

This is a point I feel keeps getting lost with modern static analysis tools today.  Forget the Lint of the past or these other tools, their focus is on file by file analysis.  These old tools are doing simple grep type analysis.  Sometimes where you’re lucky you get a little bit of control flow with a dash of data flow analysis.  But plainly they are missing the deep inter-procedural analysis and techniques that are used with modern static analysis tools today.  I’m hoping the message is getting out there that static source code analysis is far far beyond Lint and is providing the context you never had before.