Thursday, October 13, 2011

Deadlocking the Virtual Machine

As mentioned in an earlier posting, ParaSail has its own virtual machine which directly supports the notion of picothreads, very light-weight threads which are served by heavier-weight server processes (see  We are now compiling and executing various interesting ParaSail examples, and we recently began to see some apparent deadlocks in the virtual machine implementation. 

The actual ParaSail program (N Queens -- see does not have any inherent deadlock itself.  In fact, it only has one concurrent object, a vector of solutions, and the only locking operation used is to add another solution on to the end of the vector.  Nevertheless, we are seeing with a true multi-threaded virtual machine implementation, a deadlock in the virtual machine, such that all forward progress stops.  Like many situations in concurrent programs (at least pre-ParaSail...), these kinds of problems are timing dependent.  In some cases we can get the N-Queens solver for 8 queens to finish, sometimes not.  The version using a single-kernel-thread virtual machine, which merely simulates multi-threading, never has a problem.

So what could be causing the deadlock?  After lots of debugging, a hypothesis has emerged.  We are now in the process of acting on this hypothesis, so we don't know whether it is correct, or whether making a corresponding fix will solve the entire problem.  So here is the hypothesis:

As explained in the posting about the virtual machine (actually, in a comment on that posting), we serve the queue of picothreads associated with a particular server process in a LIFO manner.  But when a server steals threads from another server, it picks up the oldest picothread, i.e. uses FIFO.  This is essentially identical to the approach used in the Cilk thread scheduler (see  Our hypothesis is that it is the stealing of picothreads which is creating the deadlock.

So how could the stealing of threads create a deadlock?  The hypothesized mechanism begins with a server executing a pictothread that gets a lock on an object.  This happens when there is a call on an operation with a locked or queued parameter, or when an individual concurrent object (such as the Solutions vector in N-Queens) is passed to an operation where it is not known to be concurrent (such as the "|=" operation in the Vectors module). 

In the virtual machine implementation, getting a lock means acquiring a mutex or equivalent.  This mutex is automatically released when the operation completes.  However, suppose the operation has internal parallelism.  In ParaSail, parallelism is everywhere, and any operation of any complexity is likely to have some internal parallelism.  The "|=" operation is relatively complex, particularly if the underlying array needs to be expanded before adding on another element to the vector.  So there is plenty of opportunity for some internal parallelism.  That is manifested in the virtual machine by one or more additional picothreads being created and queued on the same server's thread, and then eventually, the server waits for the parallel picothreads to complete.

As soon as new picothreads show up on the server's queue, other servers may start stealing them.  As mentioned above, stealing works FIFO, i.e. oldest first, but if the original server's queue is essentially empty at the moment when a picothread from the locked operation is queued, then it will be the oldest thread on the queue, and so is a candidate for stealing.   So let's presume that this new sub-picothread gets stolen.  And perhaps that was the only picothread spawned by the original server.  When it gets around to waiting for it to complete, it finds it is not yet done, and in fact its own queue is now empty, so it steals from a third server.  So now we have our original server thread which is executing a picothread which is waiting for a subthread, going off and stealing work from some random third server's queue.  Now let's suppose that the thread on that third server's queue wants to get the original lock.  So the original server is now waiting on the lock that it already holds on behalf of some other picothread.  A classic tail-chasing deadlock.  Pretty soon all of the other servers stack up behind this same lock and everything grinds to a halt.

So how do we avoid this problem?  Fundamentally we don't want a server that is holding a lock, to go off and start executing a thread which is not a sub-thread of the original thread which acquired the lock.  If each server and each picothread keeps track of the innermost lock it holds, and locks are chained together so that an inner lock points to the next outer lock, if any, held, then we should be able to avoid the problem.  Whenever a server goes looking for a thread, if it holds a lock, then the thread it chooses must also hold that same lock.  It might also have some additional lock, but it must, somewhere on the chain of locks starting at the innermost one, have the same lock as that held by the server.  This argues for having at least two queues per server, one of picothreads holding no locks, and one of picothreads holding at least one lock.  Then when a queue is served by a server holding a lock, either FIFO or LIFO, it will only look at the queue of picothreads holding at least one lock, and it will ignore those on that queue that don't have the server's lock somewhere in their chain of locks.

Deadlocks are fun -- no doubt about it...

1 comment:

  1. I am happy to report that the fix described above resolved the problem with the N-Queens solver. We now keep all of the server processes busy, and no virtual machine deadlock. So the hypothesis seems to have been correct. Of course there might be other dragons lurking...