23 Dec 2002 lukeg   » (Master)

Threads and state machines

So it looks like threads make an interesting topic! pphaneuf's comments and references make a good case that shared-everything threads are hard to use. It's a pity that MichaelCrawford brought up SMP though ;-)

Since consensus is no fun, let me suggest that both threads and state machines have advantages and disadvantages, and that there are other solutions that take the best of both worlds and more. So, bold-assertion-mode-on, and please forgive me my blunders :-)

The state of play, pros and cons

To put things in context, here's what I think are the main good and bad points of shared-memory threads and state machines.

The upside to state machines is that they can be implemented efficiently in languages like C using structs for states and select()-style scheduling, and they avoid micro-level synchronization problems by performing multiple concurrent tasks with a single thread of execution. The main downside is that they are more cumbersome to code because they have to explicitly represent states that would otherwise be implicit in the stack. I'll wave my arms a bit about this below.

The upside to threads is that they easily support blocking operations (like I/O and IPC), which makes a lot of things simpler, and they are easily implemented to take advantage of SMP. The downside of typical implementations is that they are heavy-weight (e.g. because they pre-allocate large private stacks), and that preemption in shared-memory environments makes every line of code susceptible to race conditions. This area is already very well covered by pphaneuf's last post so I'll leave it alone.

Both models still leave you to find a good way for your threads or state-machines to communicate, if they need to.

The good thing is that it's possible to implement light-weight threads with much the same efficiency (and even implementation strategy) as state machines, while still supporting blocking operations and being free of fine-grained race conditions. There are also some elegant and practical high-level models of concurrency and communication (IPC) which make it much easier to write concurrent programs, and which can even take advantage of SMP without the problems of shared-memory threads. These approaches are used in practice to write very nice programs. To avoid lengthiness, I'll do another post later about some types of concurrency and IPC that I really like (unless someone beats me to it), and say why I reckon Erlang is a masterpiece. For now I just want to make an unoriginal observation.

State machines and Continuations

I think that state machine programming has a lot in common with Continuation Passing Style, and that the concept of continuations would be very interesting for people writing event-based programs. The best description of CPS that I know of is in Essentials of Programming Languages by Friedman, Wand, and Haynes. I have the first edition, which I'm told is better than the second.

Continuations are interesting if we think about how to convert an imaginary C program that runs as a thread and uses blocking I/O into an event-driven state machine that only uses non-blocking I/O. (Let's suppose it doesn't interact with other threads, for the moment.) The basic algorithm is that each blocking call in the original program becomes a state in the state machine. Each time the new program reaches its next state, it makes a non-blocking call for I/O and then saves "where I'm up to" in a state structure to pass on for the next event. What goes into the state structure is some explicit representation of the current execution context (continuation) - i.e. the information that the original program has in the stack and program counter, saying where the program is up to and what it has to do next.

After we've done that for each blocking operation, the new program is an asynchronous state machine. Unfortunately, the new program takes more coding because of the explicit representation our execution state. This, I think, is the fundamental downside to C-style state machine programming. For some programs I think explicit state machines are nice and clear, but most of the time I think it's awkward.

The interesting thing is that the above conversion from blocking to non-blocking is really a case of continuation-passing-style conversion (or "CPS-conversion") - maintaining the execution state explicitly and passing it around instead of using the stack. They've figured out a lot of useful things about continuations, like how compilers can do CPS-conversion automatically, and how to represent "first-class" continuations (which let you capture the execution state automatically) efficiently. This is great stuff for concurrent programming.

Fancy languages that support first class continuations, like Scheme and Ruby, don't need to put their state in a struct, they can just use call-with-current-continuation to capture the whole execution context automatically. In fact, in those languages the read() and write() functions could do this themselves and invoke the scheduler (or select()-loop) to convert the whole program from blocking to non-blocking automagically.

Running away, eh?

I'll put my money where my mouth is with some of the things that I think are really great when the festive season allows :-)

New email address:

luke@member.fsf.org

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!