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?
State machines vs threads
finite-state machinemultithreading
Best Answer
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.
[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.