Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Alan Cox once said "A Computer is a state machine. Threads are for people who can't program state machines".
Since asking Alan directly is not an option for humble me, I'd rather ask here: how does one achieve multi-threading functionality in high-level language, such as Java, using only one thread and state machine? For example, what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block?
Is using "state-machine only" way viable alternative to multi-threading in high-level languages?

share|improve this question
3  
A computer is also a Turing machine. Nonetheless, it is not necessarily useful to program it like a Turing machine. The stack in imperative languages is a hugely useful thing, and multithreaded programs allow to keep multiple stacks in memory at the same time. Doing the same in a state machine is surely possible, but all the more messy. –  thiton Sep 23 '11 at 12:21
8  
Alan was an OS kernel developer; this was his domian. So his quote should be taken in that context. He would have been programming 'against the metal' where it makes more sense to use such a model. Once the OS abstracts away the hardware, and its intrinsic poperties (that "a computer is a state machine...") you have the opportunity and benefit to be able to use other models that make more sense in your domain. Nearly every game makes heavy use of state machines. –  Steve Evers Sep 23 '11 at 13:26
2  
Threading is simply a feature of the OS to automatically manage some of your state machine switches, if you will. Obviously you can create a huge state machine that'll manage everything by its own, but that's more complicated. The same can be said about processes. You can say that processes are for people who can't program state machines either. But the abstraction provides you with a much simpler and less error-prone interface. In my opinion this is just another "cool quote" that should be heard, contemplated, and then ignored in reality. –  Yam Marcovic Sep 23 '11 at 13:55
1  
"But the [thread] abstraction provides you with a much simpler and less error-prone interface." That seems to be false. The number of people who get thread-safety wrong indicates that it appears to cause errors. –  S.Lott Sep 23 '11 at 14:34
1  
A lot of the comments and answers here interpret the quote as being anti-multitasking in general; I believe Alan Cox is merely anti-threads and would advocate using multiple processes to achieve a lot of the goals that people use threads for. Keep in mind he's a Unix hacker: fork FTW. I haven't found any comments from him directly on the quote, but here's one from Larry McVoy from the Linux kernel mailing list that goes in this direction: lkml.indiana.edu/hypermail/linux/kernel/0106.2/0405.html –  Martin B Sep 24 '11 at 16:26

10 Answers 10

All a thread does is interleave operations so that parts of the process appear to overlap in time. A single-core machine with multiple threads merely jumps around: it executes small bits of code from one thread, then switches to another thread. A simple scheduler decides which thread is highest priority and is actually executed in the core.

On a single-core computer, nothing actually happens "at the same time". It's all just interleaved execution.

There are many, many ways to achieve interleaving. Many.

Let's say you have a simple two-threaded process that uses a simple lock so that both threads can write to a common variable. You have six blocks of code.

  • T1-before lock
  • T1-with lock
  • T1-after lock
  • T2-before lock
  • T2-with lock
  • T2-after lock

[This can be in a loop or have more locks or whatever. All it does is get longer, not more complex.]

The steps of T1 must run in order (T1-before, T1-with, T1-after) and the steps of T2 must run in order (T2-before, T2-with, T2-after).

Other than the "in-order" constraint, these can be interleaved in any way. Any way. They could be run as listed above. Another valid ordering is (T1-before, T2-before, T2-lock, T1-lock, T2-after, T1-after). There are a lot of valid orderings.

Wait.

This is just a state machine with six states.

It's a non-deterministic finite state automata. The ordering of T1-xxx states with T2-xxx states is indeterminate, and doesn't matter. So there are places where the "next state" is a coin toss.

For example, when the FSM starts, T1-before or T2-before are both legitimate first states. Toss a coin.

Let's say it came up T1-before. Do that. When that's done, there is a choice between T1-with and T2-before. Toss a coin.

At each step in the FSM there will be two choices (two threads -- two choices) and a coin toss can determine which specific state is followed.

share|improve this answer
    
Thank you, nice explanation. And what about multi-core machine? I guess, there's no explicit way to exploit cores in Java state machine? One needs to rely on OS for that, right? –  Victor Sorokin Sep 23 '11 at 11:22
4  
A multi-core machine makes the scheduling slightly more complex. However, all cores write to a single common memory, so the Memory Write Ordering between the two cores means that -- essentially -- we're back to interleaved execution of memory writes. The OS exploits cores and the JVM leverages this. No need to think twice about it. –  S.Lott Sep 23 '11 at 13:38

Writing blocking functions is for people who can't create state machines ;)

Threads are useful if you can't get around blocking. No fundamental computer activity is truly blocking, it's just that lots of them are implemented that way for ease of use. Instead of returning a character or "read failed", a read function blocks until the whole buffer is read. Instead of checking for return message in a queue, and returning if none is found, a connect function waits for reply.

You can't use blocking functions in a state machine (at least one that can't be allowed to "freeze").

And yes, using state machine is a viable alternative. In Real Time systems, this is the only option, the system providing a framework for the machine. Using threads and blocking functions is just "the easy way out", because usually one call to a blocking function replaces about 3-4 states in the state machine.

share|improve this answer
    
A code page fault in a single-context-of-execution program is fundamentally truly blocking. By definition, code that has a single context of execution cannot make forward progress until the next chunk of code in the flow is available. –  David Schwartz Sep 23 '11 at 11:51
    
@David Schwartz: true, it's fundamentally blocking; but it's not an 'operation' since it's not something that the blocked code does, it's something that happens to it. –  Javier Sep 23 '11 at 12:45
    
To be more precise, the operation is any operation whatsoever where the code is not resident in memory. If that isn't an 'operation', then nothing is an operation. A file read, for example, may or may not block depending on whether the file data is in memory. My point is that any line of code is like a file read -- it may block if the code is not in memory. –  David Schwartz Sep 23 '11 at 12:53
    
File read is not fundamentally blocking - it can always be split into requesting readout of given location and acquiring the data from buffers after the request was fulfilled. And a page fault is a workaround for haphazard/heuristic swap usage. It will occur if given state was entered before all data necessary for its execution was made available - a lack of foresight, something against the concept of state machine. If swap-out and swap-in operations are a part of the state machine, then a page fault won't occur. –  SF. Sep 23 '11 at 14:48
1  
@David Schwartz: Definition of "blocking" behaviour is always subject to "real-time" requirements. For example: Code page fault is considered non-blocking for application that needs responsiveness in order of hundreds of milliseconds. On the other hand if application has strict realtime requirements, it wouldn't use virtual memory at all. –  MaR Sep 23 '11 at 14:53

How does one achieve multi-threading functionality in high-level language, such as Java, using only one thread and state machine? For example, what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block?

What you're describing is called cooperative multitasking, where tasks are given the CPU and expected to relinquish it voluntarily after some self-determined amount of time or activity. A task that doesn't cooperate by continuing to use the CPU or by blocking gums up the entire works and short of having a hardware watchdog timer, there's nothing the code supervising the tasks can do about it.

What you see in modern systems is called preemptive multitasking, which is where tasks don't have to relinquish the CPU because the supervisor does it for them when a hardware-generated interrupt arrives. The interrupt service routine in the supervisor saves the state of the CPU and restores it next time the task is deemed deserving of a time slice, then restores the state from whatever task is to be run next and jumps back into it as if nothing had happened. This action is called a context switch and can be expensive.

Is using "state-machine only" way viable alternative to multi-threading in high-level languages?

Viable? Sure. Sane? Sometimes. Whether you use threads or some form of home-brewed cooperative multitasking (e.g., state machines) depends on the tradeoffs you're willing to make.

Threads simplify task design to the point where you can treat each one as its own program that happens to share data space with others. This gives you the freedom to focus on the job at hand and not all of the management and housekeeping required to make it work an iteration at a time. But since no good deed goes unpunished, you pay for all of this convenience in context switches. Having many threads that yield the CPU after doing minimal work (voluntarily or by doing something that would block, like I/O) can eat up a lot of processor time doing context switching. This is especially true if your blocking operations rarely block for very long.

There are some situations where the cooperative route makes more sense. I once had to write some userland software for a piece of hardware that streamed many channels of data through a memory-mapped interface that required polling. Every channel was an object built in such a way that I could either let it run as a thread or repeatedly execute a single poll cycle.

The multithreaded version's performance wasn't good at all for exactly the reason I outlined above: each thread was doing minimal work and then yielding the CPU so the other channels could have some time, causing lots of context switches. Letting the threads run free until preempted helped with throughput but resulted in some channels not getting serviced before the hardware experienced a buffer overrun because they didn't get a time slice soon enough.

The single-threaded version, which did even iterations of each channel, ran like a scalded ape and the load on the system dropped like a rock. The penalty I paid for the additional performance was having to juggle the tasks myself. In this case, the code to do it was simple enough that the cost of developing and maintaining it was well worth the performance improvement. I guess that's really the bottom line. Had my threads been ones that sat around waiting for some system call to return, the exercise would probably not have been worth it.

That gets me to Cox's comment: threads aren't exclusively for people who can't write state machines. Some folks are quite capable of doing that but choose to use a canned state machine (i.e., a thread) in the interest of getting the job done sooner or with less complexity.

share|improve this answer
  • In theory, this true. In real life, threads are just an efficient abstraction used to program such a state machine. They are so efficient that they can be used to program Statecharts and Petri nets as well (i.e., parallel behaviours, where state machines are basically sequential).

  • The problem with state machines is combinatorial explosion. The number of states of a computer with 4G RAM is 2^(2^32) states (not counting 2T disk drive).

  • To a man whose only tool is a hammer, every problem looks like a nail.

share|improve this answer

what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block?

Well I honestly can not imagine how to handle blocking I/O without threads. It's called blocking afterall just because code that invokes it has to wait.

Per my reading of original Cox' email (below) he points out though that threading doesn't scale well. I mean, what if there are 100 I/O requests? 1000? 10000? Cox is pointing out that having large number of threads may lead to severe problems:

From: Alan Cox (alan@lxorguk.ukuu.org.uk)
Date: Fri Jan 21 2000 - 13:33:52 EST

the IBM paper), that if your application depends on huge numbers of threads, you're always going to keep bumping up against the scheduler? a lot of people throw lots of threads at a problem and it can really be bad design.

That is the least of your worry. 1000 threads is 8Mb of kernel stacks, and enough switching of tasks to be sure you might as well turn most of your cache off. A computer is a state machine. Threads are for people who cant program state machines.

There are plenty of cases Linux is most definitely not helping the situation notably asynchronous block I/O.

Alan

source: Re: Interesting analysis of linux kernel threading by IBM (linux-kernel mailing list archives)

share|improve this answer

Threads are the only option in two cases:

  • to use multiple cores without memory separation.
  • to cope with external code that blocks.

The second one is why most people think that threads are unavoidable for doing IO or network programming, but this is usually because they don't know their OS has a more advanced API (or don't want to fight with using it).

As for ease to use and readability, there are always event loops (like libev or EventMachine) which make programming a state machine almost as simple as doing it with threads, yet giving enough control to forget about sync problems.

share|improve this answer
    
The best of both worlds: Small, blocking state machines in threads makes for very simple application code. And threads split up nicely to cores if you've got them. If everything doesn't have at least two cores, it will soon. i.e. quad core arm based phones coming 2012. –  Tim Williscroft Sep 26 '11 at 5:02

A good way to grok the way state machines and multithreading interact is to look at GUI event handlers. Many GUI applications/framework utilize a single GUI thread that will poll the possible sources of input and call a function for each received input; essentially, this could be written as a huge switch:

while (true) {
    switch (event) {
        case ButtonPressed:
        ...
        case MachineIsBurning:
        ....
    }
}

Now, it becomes clear quite quickly that level of high-level control in this construct can't be high: The handler for ButtonPressed must finish without user interaction and return to the main loop, because if it doesn't, no further user events can be processed. If it has any state to save, this state must be saved in global or static variables, but not on the stack; that is, normal control flow in an imperative language is limited. You are essentially limited to a state machine.

This can get pretty messy when you have nested subroutines which have to save, for example, a recursion level. Or are in the middle of reading a file, but the file is unavailable at the moment. Or are just in a long computation. In all these cases, it becomes desirable to save the state of the current execution and return to the main loop, and this is multithreading. Nothing more, nothing less.

The whole thing became a bit more convoluted with the introduction of preemptive multithreading (i.e. the operating system deciding when threads should yield control), and that's why the connection isn't immediately clear today.

So, to answer the final question: Yes, the state machine is an alternative, most GUIs work that way with the GUI thread. Just don't push the state machine too far, it becomes unmaintainable really quickly.

share|improve this answer

Asking whether using a state machine is viable in a high level language is a little like asking whether writing in assembler is a viable alternative to using a high level language. They both have their place, given the right situation.

The abstraction of using threading makes more complex parallel systems easier to implement, but ultimately all parallel systems have the same issues to deal with. Classic problems like Deadlock/Livelock and priority inversion are just as possible with state machine based systems as they are with a shared memory parallel, NUMA or even CSP based system, if it is complex enough.

share|improve this answer

I don't think it is - sure, state machines are a very 'elegant' computing concept but as you say, they're quite complicated. And complicated things are difficult to get right. And things that are not right are just broken, so unless you're a genius of Alan Cox's presumed stature, stick with stuff you know works - leave the 'clever coding' to learning projects.

You can tell when someone has made the vain attempt to do one, as (assuming it works well) when it comes to maintain it, you find that the task is next to impossible. The original 'genius' will have moved on leaving you with the lump of barely-understandable code (as these type of developers don't tend to leave too many comments let alone technical documentation).

Some cases, a state machine will be a better choice - I'm thinking of embedded type stuff now where some state machine patterns are used, and used repeatedly and in a more formalised way (ie proper engineering :) )

Threading can be difficult to get right too, but there are patterns to help you along - mainly by reducing the need to share data between the threads.

The last point about this is that modern computers run on many cores anyway, so a state machine will not really take good advantage of the resources available. Threading can do a better job here.

share|improve this answer
1  
State machines aren't complicated at all! Complex state machines are complicated, but so are all complex systems :o) –  MaR Sep 23 '11 at 11:10
1  
-1 for "don't try". that's the worst advice you can give. –  Javier Sep 23 '11 at 12:46
    
-1 "Don't try"? That's just foolish. I would also challenge your assertion that state machines are hard. Once you get into something like a Heirarchal Fuzzy State Machine... then yea, it's a bit more complicagted. But a simple state machine? That's pretty basic stuff that every 2nd year learned when I was in school. –  Steve Evers Sep 23 '11 at 14:25
    
let me rephrase the 'dont try' bit... –  gbjbaanb Sep 24 '11 at 14:48

Good example of a proper state machine usage instead of threads: nginx vs apache2. Generally you can assume that nginx handles all connections in one thread, apache2 makes a thread per connection.

But to me using state machines vs threads is quite similar using perfectly hand crafted asm vs java: you may achieve increadible results, but it takes a lot of programmers efforts, a lot of discipline, make the project more complex and worths only when used by a lot of other programmers. So if you are the one who wants to make a fast web server - use state machins and async IO. If you are writing the project(not the library to be used everywhere) - use threads.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.