Your opinion on a kernel as a finite state machine

[Synon]

I've been toying with the idea. It seems to make thinking about an OS simpler - it boots, then it does kernel stuff, and then it exits.

What's your opinion?

[piranha]

You don't really have to have a kernel process - you can make it so that it sets up the system, and then spawns an init process and then exits, leaving code in memory for syscalls and whatnot.

-JL

[NickJohnson]

Basically, a FSM can't even use a proper stack, not to mention the tons of data structures you need for a kernel. Also, interrupts don't even fit into your typical type of computational model (at least for an FSM), nor do multiple processors. In short: not going to work.

Technically, of course, since memory in a real computer is finite, all systems are finite state machines. However, if you actually wanted to express that as a table, you would get something like 2^(2^35) entries of size 2^35, excluding input and disk stuff, on an 32-bit machine, not even counting processor register state.

[Synon]

Basically, a FSM can't even use a proper stack, not to mention the tons of data structures you need for a kernel. Also, interrupts don't even fit into your typical type of computational model (at least for an FSM), nor do multiple processors. In short: not going to work.

Technically, of course, since memory in a real computer is finite, all systems are finite state machines. However, if you actually wanted to express that as a table, you would get something like 2^(2^35) entries of size 2^35, excluding input and disk stuff, on an 32-bit machine, not even counting processor register state.

What if you simplify it a lot by just having an overall kernel state (e.g., booting, exiting, executing, idle)?

[NickJohnson]

If all you want to do is draw a flowchart of your kernel's boot sequence, be my guest, but there aren't any theoretical ramifications of that. The idea of a global kernel state (or at least global processor state) is already necessary for a lot of things, like multitasking, so you're not really accomplishing anything by recognizing that either.

All I was saying is that the actions of a kernel are not even close to computable on a finite state machine in general. For general algorithm/system design, drawing a flowchart can definitely be useful, and I think that's what you're really asking. However, the words "finite state machine" have specific theoretical implications, and are more restrictive than that. (An FSM with a mere two stacks added on is already Turing-complete, so adding any sort of extra stuff to an FSM matters a lot.)

[Synon]

If all you want to do is draw a flowchart of your kernel's boot sequence, be my guest, but there aren't any theoretical ramifications of that. The idea of a global kernel state (or at least global processor state) is already necessary for a lot of things, like multitasking, so you're not really accomplishing anything by recognizing that either.

All I was saying is that the actions of a kernel are not even close to computable on a finite state machine in general. For general algorithm/system design, drawing a flowchart can definitely be useful, and I think that's what you're really asking. However, the words "finite state machine" have specific theoretical implications, and are more restrictive than that. (An FSM with a mere two stacks added on is already Turing-complete, so adding any sort of extra stuff to an FSM matters a lot.)

Alright, that makes more sense. Also, I wasn't really looking for advice (but it is welcome), I was just interested in people's opinions.

[schilds]

Sure it makes it simpler, until you want to think more than just "it boots, then it does kernel stuff, and then it exits". You've obviously already had that thought.

[Combuster]

A kernel has multiple independent states (for each running program, each piece of hardware, each logical processor) making the total number of states impossible to fit on even an A1 sheet and get exceptional amounts of duplication. Or you will have to reduce the problem to a specific subsystem if a FSM applies there, or you get a FSM that is too generic to be meaningful at all (like the boot-operate-shutdown states you mentioned).

In other words: use the tools for the tasks for which they are designed.

[intx13]

I see two problems with an FSM kernel: interrupts and emulation.

1. You can't have interrupts because finite state machines don't have a concept of asynchronous input. Without interrupts you can't have userland threads, which means you can't run userland software unless your kernel only exists to emulate some virtual machine in which userland software runs.

2. You can't have emulation because an FSM can only emulate a machine of equal or lesser power, which in this case means just FSM. And then you're back to problem number 1.

(This post has recursion, which you also can't have in your FSM kernel!)

[gerryg400]

Whether or not you view interrupts as being asynchronous or synchronous is actually a system decision.

At the synchronous extreme many hobby OS's always have interrupts disabled in the kernel. In this case, interrupts are just like a system call and only ever happen when the kernel is in the RUNNING-A-USER-PROCESS state.

[orafy]

It's impossible. FSM has some theoretical limits. Eg: It can't count number of previous elements.
In brief, it can only make transition in finite state space.

[Synon]

Thanks for all the thoughts, it's interesting to see the different reasons people give.

Part of the reason I created this thread was because I've been trying to find ideas that would make an unusual - but hopefully, interesting - kernel. I'm not concerned with it now, though: I need to learn how to write a kernel first.

[JJeronimo]

You don't really have to have a kernel process - you can make it so that it sets up the system, and then spawns an init process and then exits, leaving code in memory for syscalls and whatnot.

In my last kernel trial, I didn't intend to have a kernel process. However, latter thinking brought me to the conclusion that I would better change my mind. I soon found a bunch of stuff for the kernel thread to do, even if it were only executing the hlt instruction when it's the only process.
It's kind of a sentinel, after all...

JJ

[rdos]

A kernel can be described as a collection of objects with methods that are responding to events. However, that is not really a state machine. State machines seems to be really lousy at solving typical control tasks, not to mention general programs. I've seen enough of state machines in embedded systems that aren't working, often because there is a conflict between the software's idea of the "state" and the "real" state. State machines often aren't modifiable either, rather often breaks as new inputs / outputs are added.