State machines vs threads

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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 ([email protected])
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)

Answer 5

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.

Answer 6

• 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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.