Chris Smith said:
I'm going to try to shorten this again to the core issues to avoid an
ever-growing thread that I have no time to answer. Let me know if I
leave out something that you think is important.
I know what you mean. this is a busy time of year for me too
Do you really mean that high-level languages with looping constructs are
a mistake?
No. I mean that 'trivial loops will always look like trivial loops
and complex loops which are implemented in some haphazard way
would be better off as a state-diagram'.
'while' considered harmful?
Nope.
Or, in any case, it sounds like
you're saying that at worst a state diagram of a loop is just as good as
the loop itself.
not that either.
I'm afraid you're going to have to make a very good
case for that one. Decades of empirical evidence demonstrate that
programmers prefer to work with normal loops and conditional statements.
yes, when they *are* normal loops and conditional statements. when
the body of the loop contains many conditional clauses which either
break, continue or set some flag and *then* break/continue, then
I would think that it wuold be better as a state machine.
And then I've spent five minutes trying to understand a piece of code,
only to find it doesn't do what I was expecting anyway! Wouldn't it be
easier if I knew this at a glance from the code itself?
if the programmer named his states, his routines and his variables
nicely, then you would have no problem knowing what the code
is *supposed* to do. its perfectly possible for a well-meaning
programmer to write code which is obfuscated by naming conventions.
e.g: you find a state machine called "sio_service". is it not obvious
that that state-machine is supposed to /service/ the serial port ?
It may not do what you are expecting (service the serial port) because
of a bug; but it is very clear what it is *supposed* to be doing.
Sure, but you can find out what you really need to know.
you agree then that its mightily difficult to draw diagrams to
check the flow of execution in a multi-threaded proggy ?
How else will I know where a/the bug might possibly be ? how else
am I supposed to figure out what the code is *supposed* to do ?
at least with state-machines, even if the original programmer
named everything in tamil, I can draw a state-machine and figure-out
exactly what it does in a few minutes for each machine.
That's the
point: you don't need to see the whole state of an application at once,
and threads give you the tools you need to separate concerns based on
process distinctions, without chaining yourself to a sequential form. I
just have to ensure that shared state is modified atomically to avoid
race conditions (which, incidentally, I also have to do when deciding
when it's appropriate to interrupt one task and resume another under
*any* approach to such a problem).
That's odd, because 1 and 3 seem to me exactly like *clear* advantages
of separating unrelated processing into multiple threads instead of
multiplexing state machines on a single thread.
ok. we have a processor that executes *exactly* 4 million clock
cycles per second. this processor is controlling a life-support
system that needs servicing *at* *least* 100 times a second.
Our processor has instructions that execute in mostly 4 clock cycles,
some in 8 clock cycles and a few in 12 clock cycles. lets also
assume that the life-support system communicates at 9600 bits per
second, that the code to take a full byte out of the incoming
register and place it elsewhere takes 8 - 80 clock cycles, and the code
to place a full byte into the tx IO register takes 8 - 80 clock cycles.
the "logic" thread can take between 80 and 800 clock cycles.
the rudimentry OS that you have allows thread creation, thread
deletion and the setting of thread priorities. however, like every
threaded environment that exists, you cannot tell how many instructions
of a thread will execute before being preempted. lets also assume
that context switching takes no more than 80 clock cycles
that leaves us with a worse case scenario of using 960 clock cycles
to use for a single recieve byte, process it and transmit byte, out
of a possible 4 million without threading, and 960 + 240 with threading
if we assume that we use threads.
lets look at point 1, real-time reactions.
you create a thread to tx data to the life-support hardware (from
now on the IO), another to rx data from the IO, and the last one
to do the processing (make the decisions).
a byte comes in from the IO. the rx-thread collects it and stores it
somewhere where the logic-thread can read it. the logic thread then
starts processing it, but at this point at least 80 + 80 cycles have
occurred. while the logic-thread is executing it is preempted, and the
tx-thread runs, finds that there is nothing to tx, so yields the
execution with only 8 clock cycles used, the thread-manager then runs
the rx-thread, which finds no byte in the rx holdnig register, and yields
the execution once again, then the logic-thread runs again for a specified
number of cycles, and the whole process is repeated.
after 1 full-second, it is not possible to know *exactly* how long
(how many micro-seconds) the logic-thread has been running for, *or*
*exactly* when the tx-thread will run. if the IO needs to get a byte
within, say, 8 microseconds, the preemption may not occur fast enough,
or may occur /just/ /before/ the byte is ready to be transmitted. i.e.
the logic-thread is preempted 1 clock cycle before the byte is ready to
be transmitted, the tx-thread finds nothing to transmit, the rx-thread
runs and recovers a byte, then logic-thread then runs and makes a byte
available to transmission, /then/ the tx-thread runs.
the life-support may have by then gone over the 8 microsecond barrier,
and something evil happens.
that is real-time with threads. you cannot foretell when anything
will run, so you cannot say with certainty that you application
can respond within a very tight timescale.
lets use the same example for point 2. if you stop the application
at *exactly* x clock cycles from the start, how do you know which
thread is executing, if you know the input that the program has had ?
it is almost impossible without tediously working out all possible
thread preemptions.
with a state-machine, you *know* for certain when something will
run. an interrupt routine will run *only* when the interrupt is
generated, not when a thread-manager decides to give it time.
there is also the problem that you may *overrun* a byte, due to
the thread-manager running some other thread when two bytes in
quick succession come in.
I don't even understand
what you mean by item 2.
Errr... well, that's because it doesn't actually *do* anything; you
haven't written any functional code, because all the functional bits
(that is, basically the whole application) go in the place of those
short comments. Besides that, there are only six states there. Try
implementing an actual application that way, even a trivial one, and let
me know if it fits on one page.
yes, theres six states. the thread example you gave had only three
threads.
On the other hand, I can write some trivial procedural applications
using loops that fit on one page.
And then, to get back to the original problem, show me the code for
putting together multiple state machines that can interrupt each other,
state-machines dont need to interrupt each other, only threads do.
telling me that threads are better because state-machines cannot
interrupt each other is kinda like telling me that submarines
are better than cars and asking me to show you how cars can "dive".
cars dont need to.
dont snip the following 4 lines
which use some shared data; and show me your strategy for arranging
exclusive access to that shared data, especially when some state
machines sometimes have to wait for data to be made available by other
state machines or from unpredictable external sources like keyboards.
keyboards are interrupt-driven, not thread-driven. keypads need to
be debounced, so a thread there does not make any sense, states do.
When you've actually taken difficult tasks that cause the now-famous
problems in multithreading and solved them with state machines,
like what ? all the famous multi-threading problems were *first*
solved with state-machines, not threads.
then you
can tell me about how the state machine solution is always better than
threads on a uniprocessor.
(once again, you use the word "always", not me).
ok, since you asked so nicely:
(i assume you wont understand mpasm assembly, so i'll use
a rough explanation + pseudocode).
I have an LCD module, a keypad module and a "main program" module.
after the appropriate setup routines have been run (lcd_init and
keypad_init), I only ever run lcd_state_machine and
keypad_state_machine (from the main program.
to display a character, I copy it into a buffer that can be
read by the lcd_module. the keypad module places the input
into a buffer that can be read from my main program.
main:
call lcd_state_machine
call keypad_state_machine
if (keypad_data) {
; process data state
}
bra main
now, the maximum time (from the main label) that it will take
to reach "process data state" is the worst-case-state-for-lcd +
the worst-case-state-for-keypad. if lcd needs to be serviced
*at* *least* every x microseconds, I can guarantee it so by
creating more states for keypad/process data with fewer instructions
in each state.
please dont snip this bit:
show me how threads can give this guarantee.
Oh yeah, then you can go about explaining how you plan to use third-
party libraries that are not aware of your radical plan for handling
concurrent tasks.
what radical plan? which third-party library cannot work with the
above? if real-time is needed, most real-time libraries come
/with/ guarantees about their execution. a few come with callbacks
instead, so you can supply you own IO code for some of it.
What if one of them spends too much time doing some
calculation and doesn't return to your control routine so as to let
another more important task run.
that is a problem in your states, split them up.
Which, it seems obvious, is only necessary because it's *not*
immediately clear from the code what the programmer had in mind.
it depends on the programmer who wrote the original. a state-machine
called "uart_service" is very obvious.
A
state diagram is no easier to understand than high-level code in most
languages, if that high-level code is written naturally using block-
style flow control.
Not bloody likely.
why not ?
most real-time environments *demands* it.
Are you still writing code using non-optimizing
compilers for 6052 processors?
no. i *do* write code for a few microcontrollers, and
a lot of the code is written in assembly. one can usually
persuade a c compiler to generate an assembly listing at the
drop of a command-line flag.
Modern environments include multiple
levels of data caches, very complex pipelining, and smart optimizing
compilers that reorder and rearrange most operations anyway.
no, only the more powerfull processors. you are possibly thinking
only in terms of desktop/server computers ?
your microwave does not possibly have anything more substantial
than an 8-bitter. these low cast chips *dont* have all those things.
Simply
put, except in hard real-time environments where you disable most all
features of modern computing environments, benchmarking is the way to
measure performance.
very true, but I *am* talking hard real-time environments.
Is this a problem in your code?
no. but you *did* mention writing a protocol stack that was
/recursive/. how can you easily guarantee that the thread does
not hang forever on malformed input ?
(the recursive bit, istr, was to show why it *had* to be a
seperate thread).
Most people have no problem writing
for/while loops that finish either. Threads don't make that appreciably
harder.
no, they dont, but neither to they make it any easier.
Basically, I think you're taking some problems that arise from very
complex applications written using threads, and then pointing out that
it's easier to write very simple state machine apps than to solve those
hard problems.
ok. wrt to simple problems: they are easier to write *without* threads.
wrt to complex problems: they *may* be easier to write without threads.
the main problem that I see here is that you think only in terms
of threads : "show me how you can do X without threads" have been
the tone of some of your posts, nevermind the fact that X is not
an issue if you dont use threads.
(please do not snip this either, respond to it).
as an example, consider your request for me to show you exclusive
access to shared data without threads. it has not even occurred
to you that without threads, *all* accesses are exclusive.
goose,
