Maker Pro
Maker Pro

Finites State Machine (OT?)

S

Stephen Sprunk

Jan 1, 1970
0
Active8 said:
GO/NOGO.

Wow! Well put. I'm glad I skipped to your post. Everyone else was
blathering on without answering the question.

I might add for future reference that the finite state machine can
be visualized with the aid of a state diagram which will aid in
defining the logic to be implemented.

Anything that interacts with the outside world (including external software)
is often best described as an FSM. A drink vending machine is probably on
the degenerate end since it only has two or three states, but imagine a
ticket vending machine that requires several steps to determine the correct
ticket to print and fare to collect.

Also, drawing a state diagram is often useful (as opposed to, say, drawing
flowcharts) even if one chooses not to actually use an FSM in the
implementation. It clarifies what is acceptable input at each stage,
whereas many coders neglect handling error conditions or illegal state
transitions.

FSMs are almost indispensible when writing software that needs to handle
multiple client connections per server thread. IRC servers, for instance,
handle tens of thousands of connections with a single server thread via an
FSM, whereas common HTTP server implementations require dozens of server
threads yet still grind to a halt when the number of active clients exceeds
the size of the thread pool.

S
 
R

R. Steve Walz

Jan 1, 1970
0
del said:
Well, schematics galore. Wasn't your sister in a james bond movie?
I should have trimmed followups. comp.arch has a tradition of spoofing
folks looking for help with homework or evidencing lazyness and
cluelessness. I guess you whiz bang circuit designers over in the other
groups didn't catch on, and have nothing better to do than be volunteer
tutors.

Thanks for letting me know that one can implement state machines in
microcode. It had never occurred to me.
 
A

Active8

Jan 1, 1970
0
Anything that interacts with the outside world (including external software)
is often best described as an FSM. A drink vending machine is probably on
the degenerate end since it only has two or three states, but imagine a
ticket vending machine that requires several steps to determine the correct
ticket to print and fare to collect.

Also, drawing a state diagram is often useful (as opposed to, say, drawing
flowcharts) even if one chooses not to actually use an FSM in the
implementation. It clarifies what is acceptable input at each stage,
whereas many coders neglect handling error conditions or illegal state
transitions.

You ain't s*@ttin'
FSMs are almost indispensible when writing software that needs to handle
multiple client connections per server thread. IRC servers, for instance,
handle tens of thousands of connections with a single server thread via an
FSM, whereas common HTTP server implementations require dozens of server
threads yet still grind to a halt when the number of active clients exceeds
the size of the thread pool.

S

I'd like to see an example of how an IRC server is implemented with
a FSM. I can't quite draw a mental picture. I don't know the IRC
protocol, either.
 
J

john jakson

Jan 1, 1970
0
R. Steve Walz said:
-------------
Why do we believe you?


-----------------
Your irrelevant off-topic posturing has you bending over the back
of the couch, asshole.

-Steve

You realize that you have made a complete fool of yourself.

Relax and read a few old c.a posts before insulting the prefects :)

regards

johnjakson_usa_com
 
J

Jeffrey C. Dege

Jan 1, 1970
0
IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*

I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.
 
T

Terje Mathisen

Jan 1, 1970
0
Jeffrey said:
I once tried to debug a program that consisted of a single 3500-line
while loop that _would_ have been a state machine, if the programmer
had known what a state machine was.

Hmmm... Wy do I get the feeling that 'tried' is the operative word here? :-(

Terje
 
S

Stephen Sprunk

Jan 1, 1970
0
Active8 said:
I'd like to see an example of how an IRC server is implemented with
a FSM. I can't quite draw a mental picture. I don't know the IRC
protocol, either.

When a client first connects to a server, there are all sorts of things the
server must do before it allows the client to start chatting, such as
checking DNS, IDENT, and an optional username/password. Since the standard
ways to check these things are blocking and the server only has one thread,
an FSM is very useful. Here's a pseudocode example:

IDLE:
client connects
send DNS request
start timer
move to DNS_WAIT

DNS_WAIT:
if timer expires, move to DNS_ERROR, otherwise:
update client_info with DNS response
send IDENT request
start timer
move to IDENT_WAIT

IDENT_WAIT:
if timer expires, move to IDENT_ERROR, otherwise:
update client_info with IDENT response
if anonymous users allowed, move to USER_CONNECTED
else start timer and move to USER_WAIT

USER_WAIT:
if timer expires, move to USER_ERROR, otherwise:
update client_info with username
start timer
move to PASS_WAIT

PASS_WAIT:
if timer expires, move to USER_ERROR, otherwise:
if password correct, move to USER_CONNECTED
else restart timer and move to USER_WAIT

USER_CONNECTED:
if timer expires, move to INACTIVE_ERROR
if input rate exceeds threshhold, move to USER_FLOOD
if username received, update client_info, start timer, and move to PASS_WAIT
if OPER command received and valid, move to OPER_CONNECTED
parse one user-level command in input buffer
restart timer

USER_FLOOD
if input rate below threshold, move to USER_CONNECTED
else discard any input

OPER_CONNECTED
if MODE -o command received, restart timer and move to USER_CONNECTED
(operator returning to user status)
parse multiple user- or operator-level commands in input buffer


Obviously there are a number of error states referenced which I didn't give
pseudocode for, but they either terminate the connection (and move to IDLE)
or kick back an error and move to another state depending on the admin's
configuration.

S
 
S

Stephen Sprunk

Jan 1, 1970
0
Terry Given said:
sounds terrible. I bet you couldnt convince the programmer that it was a
state machine, and therefore can be analysed as such.....

First you'd have to teach the original coder what a state machine is... It
certainly wasn't covered in the Comp Sci classes I took or in any of the
dozen books I've read on programming since then; I finally learned about
FSMs when trying to decipher some RFCs on routing protocols, and I still
don't think of them at first when approaching a problem.

S
 
D

del cecchi

Jan 1, 1970
0
Stephen Sprunk said:
First you'd have to teach the original coder what a state machine is... It
certainly wasn't covered in the Comp Sci classes I took or in any of the
dozen books I've read on programming since then; I finally learned about
FSMs when trying to decipher some RFCs on routing protocols, and I still
don't think of them at first when approaching a problem.

S

You would love the link/phy part of InfiniBand. One state machine after
another.del
 
K

Kevin McMurtrie

Jan 1, 1970
0
"pdx" <[email protected]> said:
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?

All computers are FSMs. A FSM diagram is a way to organize the exact
steps needed to process something. More complex diagrams have different
levels of detail; states within states. Diagrams are also good for
finding and resolving flaws/holes in the original logic.

How a diagram is translated into code is up to you. There are any
number of ways to implement it, some more suitable for a task than
others. Picking an appropriate one is part of the programming job.
 
R

Ronald H. Nicholson Jr.

Jan 1, 1970
0
Sorry if this is off topic but I have another question to help with the
revision for my exam (it's tomorrow).

Why would a finite state machine be an appropriate method of implementing
the control logic of a drinks vending machine?

Because a finite state machine is far easier for humans to debug and/or
verify than are infinite state machines.

Compare and contrast the frequency and size of OS patches for a typical
vending machine compared with Windows XP for some hints as to the asymtotic
behavior.


IMHO. YMMV.
 
R

Ronald H. Nicholson Jr.

Jan 1, 1970
0
A microprocessor *is* a finite state machine, no matter what software
you load it with.

None of the above. A microprocessor running software is actually a
collection of probablisticly behaved quantum particles which have been
abstracted into several levels of machines, given sufficiently bounded
operating conditions (below the melting point of Si, for instance).
Several of these abstraction levels are assumed to behave like finite state
machines: registers and memory elements, the CPU pipeline, CPU ISA,
microcode, library routines, OS, byte-code or script interpreters,
and application code.

Perhaps at Planck dimensions something finite is happening.


IMHO. YMMV.
 
R

Rich Grise

Jan 1, 1970
0
Stephen Sprunk said:
When a client first connects to a server, there are all sorts of things the
server must do before it allows the client to start chatting, such as
checking DNS, IDENT, and an optional username/password. Since the standard
ways to check these things are blocking and the server only has one thread,
an FSM is very useful. Here's a pseudocode example:

Pardon me, but what server do you have that has only one thread?

And any given thing can block its particular system call, yes, but
your main loop dispatches the functions and rather than waiting for
a particular link in the chain, it can go ahead and do something
else, and just check back whenever it wants to try thing 1 again.

Or are you saying that a FSM is indistinguishable from a flowchart?

Thanks,
Rich
 
J

Jeffrey C. Dege

Jan 1, 1970
0
First you'd have to teach the original coder what a state machine is... It
certainly wasn't covered in the Comp Sci classes I took or in any of the
dozen books I've read on programming since then; I finally learned about
FSMs when trying to decipher some RFCs on routing protocols, and I still
don't think of them at first when approaching a problem.

I don't see how you could possibly teach a compiler class without
either covering, or requiring as prerequisite, finite automata and
state machines.

And I don't see how a degree in Comp Sci could not include classes in
compiler technology and context-free grammars.

--
Be not afraid of any man
Who walks beneath the skies,
For be he tall or be he strong,
I will equalize.
- Samuel Colt
 
R

Rich Grise

Jan 1, 1970
0
john jakson said:
You realize that you have made a complete fool of yourself.

No, john jakson, unfortunately, Walz never seems to realize anything at all.

Good Luck!
Rich
 
T

Terry Given

Jan 1, 1970
0
Terry Given said:
The answer to your question is simple - because it can be made to work.

IME, programmers who dont understand state machines are talentless fools,
who tend to write lousy code. Alas, they can usually draw pretty GUIs so
people keep hiring them *sigh*

Terry

OK, Fred's explanation is better than mine. terse is bad?

Terry
 
R

R. Steve Walz

Jan 1, 1970
0
john said:
You realize that you have made a complete fool of yourself.
------------------------
That's merely your disingenuous lie.

Relax and read a few old c.a posts before insulting the prefects :)
------------------------
I AM among the prefects, you insipid little shit-mind!

(here since 1992)

-Steve
 
R

R. Steve Walz

Jan 1, 1970
0
Rich said:
Because why would he lie?

Cheers!
Rich
-----------------
Look, Rich, if you don't even GET the humor, don't try to re-tell
the joke, it embarrases us for you.

Joke explained (WHY do I bother?):
Since he knew and pretended he hadn't, saying "Why do we believe
you" is an amusing backhanded cut.

Then you trying to stick up for his honesty shows your ignorance,
because he was intentionally lying to be smug. Your notion that
*I* actually thought that he didn't know was simply your error
in the level of subtletly you perceieved in the convertsation.

-Steve
 
Top