Effective Concurrency: Use Lock Hierarchies to Avoid Deadlock

The latest Effective Concurrency column, "Use Lock Hierarchies to Avoid Deadlock", just went live on DDJ’s site, and will also appear in the print magazine. From the article:

… The only way to eliminate such a potential deadlock is to make sure that all mutexes ever held at the same time are acquired in a consistent order. But how can we ensure this in a way that will be both usable and correct? For example, we could try to figure out which groups of mutexes might ever be held at the same time, and then try to define pairwise ordering rules that cover each possible combination. But that approach by itself is prone to accidentally missing unexpected combinations of locks; and even if we did it perfectly, the result would still be at best "DAG spaghetti"—a directed acyclic graph (DAG) that nobody could comprehend as a whole. And every time we want to add a new mutex to the system, we would have to find a way fit it into the DAG without creating any cycles.

We can do better by directly exploiting the knowledge we already have about the structure of the program to regularize the mess and make it understandable. …

I hope you enjoy it.
Finally, here are links to previous Effective Concurrency columns (based on the dates they hit the web, not the magazine print issue dates):
July 2007 The Pillars of Concurrency
August 2007 How Much Scalability Do You Have or Need?
September 2007 Use Critical Sections (Preferably Locks) to Eliminate Races
October 2007 Apply Critical Sections Consistently
November 2007 Avoid Calling Unknown Code While Inside a Critical Section

Let’s Be Thoughtful Out There

I knew Hanlon’s Razor: "Never attribute to malice that which can be adequately explained by stupidity." And the variants attributed to Heinlein, described on the same page as adding "… but don’t rule out malice." or "… but keep your eyes open."

But I only just now came across Grey’s Law, which follows the flavor of Clarke’s Third Law: "Any sufficiently advanced incompetence is indistinguishable from malice."

One example that irritates me too is focus-stealing popups. Grr, no, I didn’t mean that enter key to select "Reboot", I was just finishing a paragraph or writing a space. Please, Mr. Callous Software Developer, just leave me alone! I don’t care how important you think your application is — it’s never important enough to pop up on top without warning. No. Bad developer. Down. I said down. Stay.

As a counterexample, I really like how Windows handles the "are you sure you want to run this application?" dialog. Not only does it not steal focus… even better, it ignores the first mouse click when it gets focus. That’s right, if the window is visible but not active, and you click on the "Run" button, it doesn’t also push Run — it merely makes the window active. Then if you hit Run again, it runs. Yes! Good developer!

To paraphrase Hill Street Blues: Let’s be thoughtful out there.

TR1 in (Free) VC++ Express

A few weeks ago I blogged about the VC++ update we plan to ship in the first half of next year, which includes extensive additions to MFC as well as TR1. TR1 is the first set of library extensions published by the C++ committee, nearly all of which have also been adopted into the next C++ standard, C++0x. The update will be available to users of Visual Studio 2008 Standard and above in the first half of 2008… but it will not be immediately available to users of our free C++ compiler, Visual C++ Express.

In response to that announcement, an anonymous commenter asked:

Is there planned support later on for TR1 in the Express edition?

Answer: Yes.

The current goal is to include the MFC Update & TR1 bits in the first service pack to Visual Studio 2008, including the Express Edition, but the final decision on this packaging and the timing of SP1 haven’t been firmed up yet. When they are, I’ll mention it here.

Parallel Computing Releases at Microsoft

For those of you who may be interested in concurrency for Microsoft platforms, and .NET in particular, I’m happy to report some fresh announcements:

PFX is for .NET concurrency development, but of course we are (and personally I am) working on native development tools, including for C++ specifically, that are at least as exciting. Stay tuned here for future news. In the meantime, enjoy these bits and the resources and discussion on the Parallel Computing developer center and forums.

The Concurrency Land Rush: 2007-20??

Every time that we experience a "wave" in which the industry takes a programming paradigm that’s been growing in a niche, and brings it to the mainstream, we go through similar phases:

  • A land rush phase during which vendors try to stake out their turf. The market sees an explosive proliferation of products trying to enable mainstream developers to work in the new paradigm and at the same time to differentiate themselves from each other. This phase always takes multiple years, and multiple major releases of many products, consumed at first mainly by early adopters and then, as products mature, broadly across the marketplace.
  • A shakeout phase as, eventually, the market sifts through the products, selects major winners, and realigns itself around them.

We (the software industry) have done it all before for technologies like OO and GUIs, and now we’re going to do it for concurrency.

Starting in 2005, companies started to talk concurrency and to launch internal efforts. But only this year, in 2007, has our industry formally entered the concurrency wave’s land rush phase by starting to field real products and preview releases. We’re starting to see initial steps toward candidate mainstream-accessible products in releases like Intel’s Threading Building Blocks and Software Transactional Memory prototype compiler, and Microsoft’s just-announced and downloadable .NET Parallel Extensions (PFX) including CTP-level support for Parallel LINQ (PLINQ) and the Task Parallel Library.

True, the concurrency landscape has lots of existing tools. So did OO (e.g., Simula) and GUIs (e.g., the Win16 C API) long before they became widely accessible to developers in general. Concurrency’s "Simulas and Win16s" include Thread classes and OpenMPI for doing work asynchronously, to OpenMP for fast parallel computation, to some pre-fab lock-free container classes, to limited race detectors and very basic thread profilers. But today’s tools are still what you’d expect to see in a niche market: Good enough for highly-trained experts to deliver real products, but not easy enough and not integrated enough across the software stack and tool chains to be broadly adopted by mainstream developers.

Just as the OO mainstream land rush was fueled by new and updated tools like Smalltalk and Objective-C and C++ and Java offerings, and the GUI land rush was fueled by MFC and OWL and Cocoa and Visual Basic and Delphi, we’re starting to see new and existing companies bringing lots of new and updated offerings across the entire software stack and ecosystem. Expect to see lots of new and updated/extended offerings of:

  • Languages and frameworks
  • Runtimes and operating systems
  • Debuggers and profilers and program analysis tools
  • Component wizards and IDE integration
  • Books and courses and conferences

These are the just beginning. Much more will come, from those same companies and others. Expect at least dozens of major product announcements and releases across the industry, before the toolset expansion phase is fully underway and approaching some maturity. We the industry have undertaken to bring concurrency to the mainstream, and as with OO and GUIs it will take multiple years, and multiple major releases, across the industry on all platforms.

As I write this, Seattle’s first snowfall of the season is gently descending outside my window. It readily puts one in mind of Frost: We have promises to keep, and miles to go before we sleep.