Mr. Lott has been involved in over 70 software development projects in a career that spans 30 years. He has worked in the capacity of internet strategist, software architect, project leader, DBA, programmer. Since 1993 he has been focused on data warehousing and the associated e-business architectures that make the right data available to the right people to support their business decision-making. Steven is a DZone MVB and is not an employee of DZone and has posted 136 posts at DZone. You can read more from them at their website. View Full User Profile

Multithreading -- Fear, Uncertainty and Doubt

06.08.2011
| 5271 views |
  • submit to reddit

Read this: "How to explain why multi-threading is difficult".

We need to talk. This is not that difficult.

Multi-threading is only difficult if you do it badly. There are an almost infinite number of ways to do it badly. Many magazines and bloggers have decided that the multithreading hurdle is the Next Big Thing (NBT™). We need new, fancy, expensive language and library support for this and we need it right now.

Parallel Computing is the secret to following Moore's Law. All those extra cores will go unused if we can't write multithreaded apps. And we can't write multi-threaded apps because—well—there are lots of reasons, split between ignorance and arrogance. All of which can be solved by throwing money after tools. Right?

Arrogance

One thing that makes multi-threaded applications error-prone is simple arrogance. There are lots and lots of race conditions that can arise. And folks aren't trained to think about how simple it is to have a sequence of instructions interrupted at just the wrong spot. Any sequence of "read, work, update" operations will have threads doing reads (in any order), threads doing the work (in any order) and then doing the updates in the worst possible order.

Compound "read, work, update" sequences need locks. And the locations of the locks can be obscure because we rarely think twice about reading a variable. Setting a variable is a little less confusing. Because we don't think much about reads, we fail to see the consequences of moving the read of a variable around as part of an optimization effort.

Ignorance

The best kind of lock is not a mutex or a semaphore. It surely isn't an RDBMS (but God knows, numerous organizations have used an RDBMS as a large, slow, complex and expensive message queue.)

The best kind of lock seems to be a message queue. The various concurrent elements can simply dequeue pieces of data, do their tasks and enqueue the results. It's really elegant. It has many, simple, uncoupled pieces. It can be scaled by increasing the number of threads sharing a queue.

A queue (read with an official "get") means that the reads aren't casually ignored and moved around during optimization. Further, the creation of a complex object can be done by one thread which gets pieces of data from a queue shared by multiple writers. No locking on the complex object.

Using message queues means that there's no weird race condition when getting data to start doing useful work; a get is atomic and guaranteed to have that property. Each thread gets an thread-local, thread-safe object. There's no weird race condition when passing a result on to the next step in a pipeline. It's dropped into the queue, where it's available to another thread.

Dining Philosophers

The Dining Philosophers Code Kata has a queue-based solution that's pretty cool.

A queue of Forks can be shared by the various Philosopher threads. Each Philosopher must get two Fork resources from the queue, eat, philosophize and then enqueue the two Forks again. It's quite short, easy to write and easy to demonstrate that it must work.

Perhaps the hardest thing is designing the Dining Room (also know as the Waiter, Conductor or Footman) that only allows four of the five philosophers to dine concurrently. To do this, a departing Philosopher must enqueue themselves into a "done eating" queue so that the next waiting Philosopher can be seated.

A queue-based solution is delightfully simple. 200 or so lines of code including docstrings comments so that the documentation looked nice, too.

Additional Constraints

The simplest solution uses a single queue of anonymous Forks. A common constraint is to insist that each Philosopher use only the two adjacent forks. Philosopher p can use forks (p+1 mod 5) and (p-1 mod 5).

This is pleasant to implement. The Philosopher simply dequeues a fork, checks the position, and re-enqueues it if it's a wrong fork.

FUD Factor

I think that the publicity around parallel programming and multithreaded applications is designed to create Fear, Uncertainty and Doubt (FUD™).

  1. Too many questions on StackOverflow seem to indicate that a slow program might magically get faster if somehow threads where involved. For programs that involve scanning the entire hard drive or downloading Wikipedia or doing a giant SQL query, the number of threads has little relevance to the real work involved. These programs are I/O bound; since threads must share the I/O resources of the containing process, multi-threading won't help.
  2. Too many questions on StackOverflow seem to have simple message queue solutions. But folks seem to start out using inappropriate technology. Just learn how to use a message queue. Move on.
  3. Too many vendors of tools (or languages) are pandering to (or creating) the FUD factor. If programmers are made suitably fearful, uncertain or doubtful, they'll lobby for spending lots of money for a language or package that "solves" the problem.

Sigh. The answer isn't software tools, it's design. Break the problem down into independent parallel tasks and feed them from message queues. Collect the results in message queues.

Some Code

class Philosopher( threading.Thread ):
"""A Philosopher. When invited to dine, they will
cycle through their standard dining loop.

- Acquire two forks from the fork Queue
- Eat for a random interval
- Release the two forks
- Philosophize for a random interval

When done, they will enqueue themselves with
the "footman" to indicate that they are leaving.
"""
def __init__( self, name, cycles=None ):
"""Create this philosopher.

:param name: the number of this philosopher.
This is used by a subclass to find the correct fork.
:param cycles: the number of cycles they will eat.
If unspecified, it's a random number, u, 4 <= u < 7
"""
super( Philosopher, self ).__init__()
self.name= name
self.cycles= cycles if cycles is not None else random.randrange(4,7)
self.log= logging.getLogger( "{0}.{1}".format(self.__class__.__name__, name) )
self.log.info( "cycles={0:d}".format( self.cycles ) )
self.forks= None
self.leaving= None
def enter( self, forks, leaving ):
"""Enter the dining room. This must be done before the
thread can be started.

:param forks: The queue of available forks
:param leaving: A queue to notify the footman that they are
done.
"""
self.forks= forks
self.leaving= leaving
def dine( self ):
"""The standard dining cycle:
acquire forks, eat, release forks, philosophize.
"""
for cycle in range(self.cycles):
f1= self.acquire_fork()
f2= self.acquire_fork()
self.eat()
self.release_fork( f1 )
self.release_fork( f2 )
self.philosophize()
self.leaving.put( self )
def eat( self ):
"""Eating task."""
self.log.info( "Eating" )
time.sleep( random.random() )
def philosophize( self ):
"""Philosophizing task."""
self.log.info( "Philosophizing" )
time.sleep( random.random() )
def acquire_fork( self ):
"""Acquire a fork.

:returns: The Fork acquired.
"""
fork= self.forks.get()
fork.held_by= self.name
return fork
def release_fork( self, fork ):
"""Acquire a fork.

:param fork: The Fork to release.
"""
fork.held_by= None
self.forks.put( fork )
def run( self ):
"""Interface to Thread. After the Philosopher
has entered the dining room, they may engage
in the main dining cycle.
"""
assert self.forks and self.leaving
self.dine()

 The point is to have the dine method be a direct expression of the Philosopher's dining experience.  We might want to override the acquire_fork method to permit different fork acquisition strategies.

For example, a picky philosopher may only want to use the forks adjacent to their place at the table, rather than reaching across the table for the next available Fork.

 

The Fork, by comparison, is boring.

class Fork( object ):
    """A Fork.  A Philosopher requires two of these to eat."""
    def __init__( self, name ):
        """Create the Fork.
        
        :param name: The number of this fork.  This may 
            be used by a Philosopher looking for the correct Fork.
        """
        self.name= name
        self.holder= None
        self.log= logging.getLogger( "{0}.{1}".format(self.__class__.__name__, name) )
    @property
    def held_by( self ):
        """The Philosopher currently holding this Fork."""
        return self.holder
    @held_by.setter
    def held_by( self, philosopher ):
        if philosopher:
            self.log.info( "Acquired by {0}".format( philosopher ) )
        else:
            self.log.info( "Released by {0}".format( self.holder ) )
        self.holder= philosopher

The Table, however, is interesting.  It includes the special "leaving" queue that's not a proper part of the problem domain, but is a part of this particular solution.

class Table( object ):
    """The dining Table.  This uses a queue of Philosophers
    waiting to dine and a queue of forks.
    
    This sets Philosophers, allows them to dine and then
    cleans up after each one is finished dining.
    
    To prevent deadlock, there's a limit on the number
    of concurrent Philosophers allowed to dine.
    """
    def __init__( self, philosophers, forks, limit=4 ):
        """Create the Table.
        :param philosophers: The queue of Philosophers waiting to dine.
        :param forks: The queue of available Forks.
        :param limit: A limit on the number of concurrently dining Philosophers.
        """
        self.philosophers= philosophers
        self.forks= forks
        self.limit= limit
        self.leaving= Queue.Queue()
        self.log= logging.getLogger( "table" )
    def dinner( self ):
        """The essential dinner cycle:
        admit philosophers (to the stated limit);
        as philosophers finish dining, remove them and admit more;
        when the dining queue is empty, simply clean up.
        """
        self.at_table= self.limit
        while not self.philosophers.empty():
            while self.at_table != 0:
                p= self.philosophers.get()
                self.seat( p )
            # Must do a Queue.get() to wait for a resource
            p= self.leaving.get()
            self.excuse( p )
        assert self.philosophers.empty()
        while self.at_table != self.limit:
            p= self.leaving.get()
            self.excuse( p )
        assert self.at_table == self.limit
    def seat( self, philosopher ):
        """Seat a philosopher.  This increments the count 
        of currently-eating Philosophers.
        
        :param philosopher: The Philosopher to be seated.
        """
        self.log.info( "Seating {0}".format(philosopher.name) )
        philosopher.enter( self.forks, self.leaving)
        philosopher.start()
        self.at_table -= 1 # Consume a seat
    def excuse( self, philosopher ):
        """Excuse a philosopher.  This decrements the count 
        of currently-eating Philosophers.
        
        :param philosopher: The Philosopher to be excused.
        """
        philosopher.join() # Cleanup the thread
        self.log.info( "Excusing {0}".format(philosopher.name) )
        self.at_table += 1 # Release a seat

The dinner method assures that all Philosophers eat until they are finished.  It also assures that four Philosophers sit at the table and when one finishes, another takes their place.  Finally, it also assures that all Philosophers are done eating before the dining room is closed.

From http://slott-softwarearchitect.blogspot.com/2011/06/multithreading-fear-uncertainty-and.html

Published at DZone with permission of Steven Lott, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Oliver Plohmann replied on Wed, 2011/06/08 - 3:11am

The use of queues where each queue is served by one thread is basically the idea behind actors. Since queues are typically used in an asynchronous way (see JMS) you have the problem that messages don't necessarly arrive in the order they were sent by the producer. Hence the consumer needs to have some logic to process messages in the right order.

Typically, hierarchical state machines have been used to handle this. However, if some message doesn't arrive that needs to be processed before some other you also run into a deadlock. You can continue after a timeout by sending messages back and starting anew. But to get the logic right to do this correctly can be demanding, especially because the producers in the meanwhile have continued to send messages to some queues. For instance, you might end up with some very intricated endless-loops over several queues, which you only find out about after wondering why system performance has started to drop significantly. In most cases you simply cannot handle all the possible combinations of what state the system is now in and have to give up. In this respect it is very important not only to have a decoupled class design, but also a decoupled "thread design", where threads don't go through the entire application but only through some small restricted area.

Then you have sometimes the problem that some output is only correct if the input in the meanwhile has remained unchanged. If not, the output has to be re-created. This problem cannot be addressed with the use of queues alone. STM is one solution here, which also comes for some cost. You have to observe how often retries occur due to outdated input data. If it happens too often you might have to think about changing the logic in your application, make transaction boundaries smaller, etc. which is also effortful. Finally, if you find a solution that is simple and deadlock-free, you might still be left with a solution with a high degree of thread contention. So you are still not done...

Had to throw in some issues that struck my mind ;-). Wasn't meant to be negative. I like you article in the way that it tries to look up to the horizon and think about ways to solve difficult problems in simpler ways. This is what part of the fun in software development is about. And I guess multi-threading will be fun and challenging in that way for a long time to come :-).

Regards, Oliver

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.