A Deadlock Holiday

What to do now there's no Moore's Law?


Stob Moore's Law, I need hardly remind a top-notch industry professional like you, states that as the density of silicon circuitry doubles, the probability of you not being able to find some sensibly-priced extra memory to fit your old lappy approaches 1.0.

In recent times it has become generally admitted that, if this well-known observation has not yet quite joined Elvis, it is at the very least fiddling determinedly with the fire exit door. Instead of increasingly quick processors, we are given increasingly cored processors. Whereas it used to take just one running instance of Access 2000 to bring your CPU usage meter to 100%, it now takes two, four or possibly 128.

Once upon a time, all one needed to know about multi-tasking code was how to hang a few lines of badly-written (I speak for myself) assembly language off the timer interrupt. Those were the days, my friend, we thought they'd carry on; yet here I am giving you a whistle-stop tour through the baffling mechanisms designed to help you envisage and write para-multi-threaded applications.

Let us begin with some ancient history.

Co- not Sub-

The great Donald Knuth described the coroutine, a mechanism for writing single-tasked multi-tasking that allowed any programmer to cope with any situation, merely by thinking of everything at once.

Although it has never really taken off as a popular programming construct, it has been very influential, in particular pioneering the important adjective 'lightweight' (subroutines are a lightweight specialisation of coroutines). Nowadays, of course, 'lightweight' is used as a synonym for 'good' throughout comp. sci., yet it still retains a special affinity for the parallel and pseudo-parallel arts.

Threads

A 'thread', abbreviating 'thread of execution', is a lightweight version of the heavier 'process', abbreviating 'process of execution' (as in the phrase 'during the process of execution, the program abruptly died'). Threads save all the tedious mucking about creating state and context demanded by processes, by simply enabling multiple threads to cavort together in the same address space, and with the same resources, like drowning kittens in a bucket of water. Adding cores to the processor improves the threading model by significantly increasing the amount of water available. (Peace: no actual kittens were drowned in the manufacture of that simile.)

In particular, threads suffer badly from 'race conditions'. The race of despised worker threads is made to do boring, low status, 'background' tasks. Meanwhile, the high privilege 'system' threads get to party with the hardware. It's the same the whole world over...

Three old ladies

In order to overcome race conditions, and perhaps to compensate for taking away our beloved 'goto' away from us, top Dutch comp. sci. genius Edsger Dijkstra invented the 'semaphore'. The semaphore is a data structure that allows friendly communication between the threads and tasks of all nations. There are two kinds: the counting semaphore and later, when it has been compiled, the binary semaphore.

The semaphore helped do away with race conditions, and for a while all was sweetness and synchronicity. But it soon became clear that a brand new peril had been introduced: the deadlock.

Today there are at least four well-known kinds of deadlock breeding in the wild:

  • Recursive deadlock, which bloody well happens again and again
  • Deadly mutual embrace deadlock, which is much less fun than it sounds, being a kind of inter-task stalemate
  • Death-of-process deadlock, where the process that claimed the semaphore dies intestate
  • Lady Dedlock, a plaintiff in Jarndyce v. Jarndyce

By way of countering the threat and obtaining a deadlock holiday, it was decided to invent the 'mutex' (or 'mutant' as it is known by posher, system threads).

There is a lot of confusion about the difference between mutexes and semaphores, which frankly I do not see as part of my business to clear up. Instead I will refer you to the conventional explanatory model which is, weirdly, based on the notion of the lockable lavatory (or securable brickhouse, as it is almost known by commoner, worker threads).

The scenario is this: imagine a loo in a restaurant of the dismal kind where you must humiliatingly apply to staff for the key. If there is one lavatory and one key, you have a mutex and a long, fidgety wait. If there are four toilets and four interchangeable keys, you have a counting semaphore. The important thing about a counting semaphore is: it doesn't prevent four threads entering one cubicle together.

This licentious view of synchronisation is disputed by other writers, who say that the difference with mutexes is that, before sitting down, they draw the bolt of ownership across the door.

My own view is: synchronisation primitives will never be understood until somebody goes over their metaphors with gallons of industrial-strength bleach.

Next page: Yet more

Other stories you might like

  • DigitalOcean tries to take sting out of price hike with $4 VM
    Cloud biz says it is reacting to customer mix largely shifting from lone devs to SMEs

    DigitalOcean attempted to lessen the sting of higher prices this week by announcing a cut-rate instance aimed at developers and hobbyists.

    The $4-a-month droplet — what the infrastructure-as-a-service outfit calls its virtual machines — pairs a single virtual CPU with 512 MB of memory, 10 GB of SSD storage, and 500 GB a month in network bandwidth.

    The launch comes as DigitalOcean plans a sweeping price hike across much of its product portfolio, effective July 1. On the low-end, most instances will see pricing increase between $1 and $16 a month, but on the high-end, some products will see increases of as much as $120 in the case of DigitalOceans’ top-tier storage-optimized virtual machines.

    Continue reading
  • GPL legal battle: Vizio told by judge it will have to answer breach-of-contract claims
    Fine-print crucially deemed contractual agreement as well as copyright license in smartTV source-code case

    The Software Freedom Conservancy (SFC) has won a significant legal victory in its ongoing effort to force Vizio to publish the source code of its SmartCast TV software, which is said to contain GPLv2 and LGPLv2.1 copyleft-licensed components.

    SFC sued Vizio, claiming it was in breach of contract by failing to obey the terms of the GPLv2 and LGPLv2.1 licenses that require source code to be made public when certain conditions are met, and sought declaratory relief on behalf of Vizio TV owners. SFC wanted its breach-of-contract arguments to be heard by the Orange County Superior Court in California, though Vizio kicked the matter up to the district court level in central California where it hoped to avoid the contract issue and defend its corner using just federal copyright law.

    On Friday, Federal District Judge Josephine Staton sided with SFC and granted its motion to send its lawsuit back to superior court. To do so, Judge Staton had to decide whether or not the federal Copyright Act preempted the SFC's breach-of-contract allegations; in the end, she decided it didn't.

    Continue reading
  • US brings first-of-its-kind criminal charges of Bitcoin-based sanctions-busting
    Citizen allegedly moved $10m-plus in BTC into banned nation

    US prosecutors have accused an American citizen of illegally funneling more than $10 million in Bitcoin into an economically sanctioned country.

    It's said the resulting criminal charges of sanctions busting through the use of cryptocurrency are the first of their kind to be brought in the US.

    Under the United States' International Emergency Economic Powers Act (IEEA), it is illegal for a citizen or institution within the US to transfer funds, directly or indirectly, to a sanctioned country, such as Iran, Cuba, North Korea, or Russia. If there is evidence the IEEA was willfully violated, a criminal case should follow. If an individual or financial exchange was unwittingly involved in evading sanctions, they may be subject to civil action. 

    Continue reading

Biting the hand that feeds IT © 1998–2022