Re: Polling, Interrupts, DMA, Synchronous, Asynchronous I/O Definitions

From: Beth (BethStone21_at_hotmail.NOSPICEDHAM.com)
Date: 07/18/04 

Date: Sun, 18 Jul 2004 02:13:28 GMT

C wrote:
> Sorry, but even with blocking, polling is still polling
> (though blocking makes it less costly).

Of course it is...but, sorry, this isn't "polling" we're talking
about...

> Take this for example, ...
>
> .L1:
> call api_sleep, 50 ; call sleep API (blocks)
> in al, KB_DATA ; read kb status
> test al, 0x80 ; wait for key release
> jz .L1
>
> Even though a blocking API is called, the loop is still
> a polling loop -- whether the cpu resource is freed for
> other tasks to use or not is not important in a polling
> loop. (Though freeing the cpu is preferable from an
> engineering point of view.) What is important is
> whether the logical task is able to process other infor
> -mation (as with interrupts or DMA transfer), or not.

Ah, but this is _COMPLETELY DIFFERENT_...

In this example, you're NOT blocking on the actual data
itself...the use of "blocking" here is completely "incidental"
to the polling...quite separate and independent things...

What we're talking about is actually _blocking on the actual
condition of interest_...

For example:

------------------------

  call GetKeyRelease ; (blocking OS API)

------------------------

Where, in this case, the "GetKeyRelease" API works much like
"GetMessage" does with messages, but on the condition of "key
release"...when called, it blocks and the application surrenders
the CPU completely...then when the keyboard driver picks up a
key being released, then it unblocks the application...

And then there's no "polling" in this instance...in a sense, in
fact, as something like Windows turns all of these kinds of
things into an "event" then it _is_ doing something like this
already...but it deals with the whole lot with a generic
"message" idea to capture it all and then "GetMessage" is one
API that is able to "block" on all the various conditions...you
know, call everything an "event" and then have a
"BlockUntilEvent" API then you cover the whole thing in one
go...

Because, indeed, if we look at Windows, then - ignoring the
exception of "DirectInput" or whatever - then it does inform
applications of this kind of thing by sending a "WM_KEYUP"
message (or one of the equivalents like "WM_SYSKEYUP" because it
distinguishes between keys and "system keys" for other reasons
:)...and when we call "GetMessage", we are blocking on the
condition of a message being received...if the message is
"WM_KEYUP" then we've done the above without "polling"...

The point is that there are two techniques available for this
situation...the situation, namely, being that we're needing to
wait for a particular condition to happen...

The first technique is for the application to constantly look
for itself to see if the condition has changed...it "polls" in a
loop monitoring some variable or data port or whatever, waiting
for the condition to become true...

The second technique - but requires the system to be designed
this way, as it involves "co-operation" between application and
OS - is to implement a "blocking" technique instead...the
application blocks _on a condition_ of some sort...

If you like, it's phoned down to the hotel reception desk and
asked for a "wake up call": "Please wake me up when [ it's six
o'clock / my friend shows up and asks for me at the reception
desk / lunch is being served ]" (* delete as applicable
;)...then it can go to sleep...

When the condition for the "wake up call" happens, the reception
desk calls to wake it up...

Again, I repeat, we're talking about a _QUALITY_ difference, not
a quantity thing...it's a _different type_...an alternative
technique for the same problem...

And, generally, on a multi-tasking system, the second "blocking"
technique is preferred because it doesn't consume CPU
resources...but, yes, this is sometimes not possible...there is
"overhead" to blocking that means it might not be a good idea
for certain "real-time" situations...because, indeed, it takes
longer to respond to being woken up by the "wake up call" and
then getting ready to go downstairs to meet your friend, in
comparison to have done it in a "polling" fashion...that is, to
have just stood around in reception, waiting for your friend to
show up...indeed, in that situation, you can "react" almost
immediately and greet your friend the second they walk into
hotel reception...so, no, I'm not saying that "polling" has no
uses or is "always wrong" or whatever...

But, generally, if the "overhead" isn't problematic, then the
"blocking" solution has to be preferred...it releases the CPU
for other tasks...and, as we're talking about a machine here,
then you won't "miss" anything because it won't ever forget to
send the "wake up call"...

In fact, to counteract the example I've just given where
"polling" is better, there's another possibility where
"blocking" is the superior solution...and, in fact, it could
very well apply to something like your keyboard example (it
never does on a PC because the keyboard has a "buffer"...we'll
see why this important in a minute :)...

If there's an "event" which can happen incredibly quickly, then
a "polling" loop could actually potentially _MISS_ the
event...now, this is rare for something to happen so fast,
granted, especially with modern superfast CPUs...but then the
"real-time" instant reaction requirement doesn't typically show
up all that often (about as rare as each other in practice :)...

You check for the data (there is none)...then while testing AL
for the condition and looping back around, the key was actually
released...but, by the time you've returned to check again, the
event has passed and it says "no key release" again...oops, you
_missed_ the key release...

As noted, this particular example would never happen with a PC
keyboard because, realising the possibility, the keyboard uses a
one-byte "buffer"...and the buffer is not released until the
keyboard handler pulls the byte out of the buffer...but we can
imagine different hardware that doesn't do this...

In fact, I'll name you an example: the vertical blank...the bit
that signals the VGA vertical blank simply gets set while the
raster beam is resetting in a vertical blank and then is cleared
when it's actually drawing the screen...the state is NOT
maintained...

And, in fact - as a previous code example I've given shows - you
typically have to "poll" for _two_ conditions...that is, you
look for a vertical blank _AND_ you look for the vertical blank
completing...as there's a possibility, if your code runs too
fast, that it actually completes the whole rendering process
_inside_ one vertical blank and, therefore, when it looks again,
it still says "in vertical blank"...BUT it would be incorrect in
this instance where you've rendered far too quickly that you're
still in the same vertical blank to determine that this is the
next vertical blank...so, you "poll" for both conditions to
ensure you really are measuring one frame each time (say, check
for entering the vertical blank at the top, then the rendering
code, then check that you've _left_ the vertical blank before
looping back around...in the example code I posted before, I
re-arranged it so that the two were next to each other...no
particular reason for that but "convenience" :)...

Now, if you spent too long between checking for the vertical
blank condition, then you _CAN_ miss it completely...as this
happens typically say 60 or 75 or 80 times a second (depends
what refresh rate has been set :), then the CPU is usually fast
enough to catch it so long as there's not too much other things
going on...but it is a possibility...

> Polling loops continue looping and testing a condition
> until an external event occurs which allows the some
> other code to be executed.

Yes; I understand what polling is (indeed, at least you bothered
with "external event", which has been missing from some
definitions meaning that _ANY_ loop is a "polling" loop, that's
clearly going too far ;)...

That is not the issue...the issue is simply that "GetMessage" is
a blocking API...Windows (and other OSes) is designed with a
_blocking_ message processing scheme (as is - and so rarely I
defend Microsoft that you know I wouldn't state it lightly -
_GOOD PRACTICE_ for any event-driven multi-tasking OS like
Windows)...

We are simply not talking about "polling" in the particular
instance that spawned this discussion...and I stated at the time
and still state that I was making _NO_ comment on hutch's code
using "polling": If he has good reason to do so - and good
reasons undoubtedly exist (I've mentioned one and most certainly
the reasons include "it crashes", being amongst the top of "good
reasons" to do otherwise :) - then he should do so...

It's not "polling" in the instance mentioned, it's
blocking...and, no, it's not "block polling" either...it's pure
100% blocking..."polling" is a red herring, an irrelevence to
what this thread was originally discussing...it's as simple as
that, basically...

> Therefore, this is a polling loop...
>
> .L2:
> call GetMessage()
> if eax == ExposeEvent
> call RedrawWindow()
> else_if eax = QuitEvent
> call Exit()
> end_if
> jmp .L2

You're confusing X with Windows, C...

The typical Windows "message loop" is a call to "GetMessage" and
then a call to "DispatchMessage"...and it is the "window
procedure" which discriminates between messages...that's why you
must "register a window class" before creating a window: You
must specify the "window procedure"...and having a "window
procedure" is, unlike X, a non-optional matter...there are some
types of messages that Windows delivers _directly_ to the
"window procedure" without going near the "message queue"...

------------------

"Windows uses two methods to route messages to a window
procedure: posting messages to a first-in, first-out queue
called a message queue, a system-defined memory object that
temporarily stores messages, and sending messages directly to a
window procedure.

"Messages posted to a message queue are called queued messages.
They are primarily the result of user input entered through the
mouse or keyboard, such as WM_MOUSEMOVE, WM_LBUTTONDOWN,
WM_KEYDOWN, and WM_CHAR messages. Other queued messages include
the timer, paint, and quit messages: WM_TIMER, WM_PAINT, and
WM_QUIT. Most other messages, which are sent directly to a
window procedure, are called nonqueued messages."

[ "Message Routing", Microsoft Win32 SDK ]

------------------

X does not make this distinction (something I've always liked
about it :) so that there are no "window classes" and no "window
procedures"...you call "XSelectInput" to specify the "event
mask" of which events you want reported (unlike Windows, X
always the events to be specified and "filtered" :)...and then
you call "XNextEvent" to get the event...

Unlike Windows, X makes no demands on the structuring of the
program...there is no "window procedure" (though, if you _want_
that kind of thing then place your message processing code into
a procedure and call it :)...there are no "window classes"
(though, if you want that kind of thing then create a message
processing procedure and _re-use_ it for more than one window
:)...this is something I've always liked about the X
structure...it doesn't force you to do it in a particular way,
just providing the basic facilities which, at your option, you
could structure into "window procedures", if you so choose...

Anyway, the point is that the typical Windows message loop does
NOT have the conditions inside the loop...rather it calls
"DispatchMessage" (_BLINDLY_) with the returned message...which
passes the message to the "window procedure" to do any
"discriminating" between "interesting" and "uninteresting"
messages...

The code you're demonstrating as a "polling loop" here is an
X-style message loop, where the discrimination can optionally be
dealt with in the message loop itself...but, under
Windows...well, let's get it straight from the horse's mouth:

----------------------------------

A simple message loop consists of one function call to each of
these three functions: GetMessage, TranslateMessage, and
DispatchMessage.

MSG msg;

while( GetMessage( &msg, NULL, 0, 0 ) )
{
    TranslateMessage( &msg );
    DispatchMessage( &msg );
}

[ ... ]

An application's main thread starts its message loop after
initializing the application and creating at least one window.
Once started, the message loop continues to retrieve messages
from the thread's message queue and to dispatch them to the
appropriate windows. The message loop ends when the GetMessage
function removes the WM_QUIT message from the message queue.

Only one message loop is needed for a message queue, even if an
application contains many windows. DispatchMessage always
dispatches the message to the proper window; this is because
each message in the queue is an MSG structure that contains the
handle of the window to which the message belongs.

----------------------------------

[ From "message loop", the Microsoft Win32 SDK documentation
(this loops is actually a terrible example because there's no
check for an error condition on "GetMessage", which violates
Microsoft's own advice...but that is a separate issue :) ]

Note carefully what _Microsoft_ are saying and demonstrating
here: There is no discrimination of messages here (except for
WM_QUIT: "GetMessage" returns FALSE when this message is grabbed
so that it can be conveniently used in a "while" looop as the
example shows)...rather you call "DispatchMessage" _BLINDLY_
with whatever message Windows has provided: "DispatchMessage
always dispatches the message to the proper window"...this API
discriminates the window for you, the "window procedure"
discriminates the message that "DispatchMessage" sends it...

The only thing remotely "polling" in the example loop is the
"while" loop's dependence on the "GetMessage" return value to
terminate on WM_QUIT...this is only a convenience for a logical
"structured programming" layout...it's perfectly possible to do
thusly:

----------------------------------

MsgLoop:
    call GetMessage, NULL, NULL, NULL
    call DispatchMessage
    jmp MsgLoop

WndProc:

    if Msg == WM_QUIT

        ; termination code here

        call ExitProcess

    end_if

    ret

----------------------------------

...instead...and then the "message loop" is 100% blind, 100%
undiscriminating, 100% blocking...

You _CAN_, of course, choose to _MAKE_ a message loop that
"polls"...as has been stated by myself (and Wannabee) from the
start, call "PeekMessage" (with PM_REMOVE so that other than not
blocking, it acts the same as "GetMessage" :)...it doesn't
block...if you _want_ to "poll" for some reason then you can do
this...

Also, if you do use a "PeekMessage" loop to make it a "polling"
loop (though, this is not a usual Windows message loop but one
used for special purposes like games software that need to
control animations irrespective of "events" coming in or not),
then Windows also supplies the "WaitMessage" API specifically to
allow the programmer to optionally _make it block_...

So, for example, you might use "PeekMessage" in a game loop so
that you can control animating the sprites in the window...you
don't want to block because you have other things to do while
waiting for a message to appear...so you need to "poll" in that
instance because "blocking" surrenders the CPU completely and
you don't want to do that...but if at any point you do - say,
the game is put into "pause mode" - then you can explicitly ask
for the application to block until a message appears with the
"WaitMessage" API...

> And, this is _not_ a polling loop...
>
> .L3:
> call GetMessage()
> call Print( "A message has occured", eax )
> jmp .L3
>
> ...because it is interested in _all_ permutations
> of the external event -- not a subset.

This loop actually reflects the "typical Windows message loop"
that is under discussion closer than the "polling" loop you
mentioned...you can see this from the example code _from
Microsoft_ which demonstrates the typical Windows "message
loop"...

And I've demonstrated a "message loop" that entirely works like
the non-polling loop above, which is a perfectly valid way to do
things that any application could comfortably use...

hutch's original assertion that I was countering was that "ALL"
Windows message loops "poll"...I've demonstrated that this isn't
true with an example (one only needs a single example to counter
an "ALL" assertion :)...and the _CODE MICROSOFT PROVIDES_ (and
use in almost every single example I've seen from them...and
reflects the type of message loop used by most example code out
there (other than games with specific requirements...but even
some of them - card games - are happy to be 100% event-driven
:)) is far closer to the "non-polling" example than the
"polling" example because the message loop isn't discriminating:
That's the job of the "window procedure"...it just grabs a
message with "GetMessage" and then blasts it _BLINDLY_ (no
testing) to "DispatchMessage"...the "window procedure" takes it
from there to process and discriminate the different types of
message...

And, under Windows, as there are "nonqueued messages" too that
get delivered directly to a "window procedure" then the "window
procedure" is non-optional...which is why every window has to
"register a window class" before you can create it: Windows
needs to know where the "window procedure" is for _direct
delivery_ (not put on the message queue or retrieved by
"GetMessage" or dispatched by "DispatchMessage") of "nonqueued
messages"...

I've provided explanation...I've provided example...I've
provided quotations and examples from Microsoft themselves...

I've demonstrated that "blocking" in this instance is NOT
"polling" (which was being contended until I explained and
showed otherwise)...I've explained where "polling" has merits
and where "blocking" has merits...I've covered basic scheduler
theory surrounding the blocking matter...

If people want to carry this on then, fine, but you've got your
work cut out trying to counter it...this is not a case of
"misunderstanding" (at least, not on my part)...

It's simply a case that the original assertion by hutch of "ALL
message loops are polling loops"...no, sorry, the actual
assertion was more like: "If you want to learn about polling,
then ALL (Windows) message loops are polling loops so that's
where you should start learning about polling"...that this
assertion was not correct

And, thus, as hutch was advising newbies to "learn about
polling" from message loops then I stepped in to counteract that
before the newbies believed it and looked in the wrong place...

Indeed, this very discussion itself between some of the most
knowledgeable people here, where we're disagreeing clearly
proves it's hardly a "classic role model example" to learn from,
as originally stipulated...but, anyway, not all message loops
are "polling"...in fact, the typical message loop is _BLOCKING_,
exactly so as not to be "polling" and using up CPU time that
other threads could be using...far from "role model of polling",
it's arguably a far better example of the _opposite_ of
preferring to use _BLOCKING_ rather than polling...

Hence, if hutch's assertion was not countered and newbies took
his word there then they'd all actually be learning about a
blocking scheme and thinking that they were looking at a
"classic role model example of polling"...they could be mislead
by that, which is why I stepped in to correct hutch's assertion
before it mislead people into thinking what's actually closer to
being the _total opposite_ of what's actually the case...

> Also, this is _not_ a polling loop...
>
> mov eax, 1000000
> .L4:
> dec eax
> jnz .L4
>
> ...because it does not rely on an external event.

Well, thank you...at least you've correctly put in the "external
event", which was absent with Randy earlier and, indeed, ended
up suggesting that a "for" loop or a loop like the one above
would actually be "polling"...

> But, this is a polling loop...
[ snip; We've got the message...and, yes, you understand what
constitutes "polling" completely from your examples...now just
take a look at Microsoft's "standard message loop" and their
message processing system just to realise that it does not
operate by "polling" but through using a "blocking" scheme :) ]

> Remember...

[ And the following conditions are "logical AND", right? If we
fail one of them, then it's "non-polling"? ;) ]

> * A polling loop must test for an
> flag / variable / port set by an external
> event (eg. a hardware device or parallel
> task).

You can write a message loop (as I've done earlier) which does
not do so...hence, that loop has broken the "logical AND"
between these conditions (aborting the "IF" condition early
because we've hit a FALSE, so the whole thing must be a FALSE
:)...and, as I stepped in to originally point out, hutch's
assertion that "all message loops are polling loops" is also
FALSE...

There...case closed...next topic, please ;)

> * A polling loop will only be interested
> in a subset of the events which will can be
> signaled by the device / task.

The message loop provided by Microsoft themselves grabs _ANY_
message and passes that message _BLINDLY_ to
"DispatchMessage"...completely undiscriminating (_except_ for
terminating the loop on WM_QUIT...but this need not actually be
done: It's a simple "structured programming" convenience that
you can put it on the end of a "while" condition...the window
procedure can optionally deal with WM_QUIT instead...dropping
out of the loop on WM_QUIT like this actually has more to do
with staying in the same "WinMain" procedure so that all the
local variables are still in scope for "clean up" code rather
than that an application "must" do it that way)...

Windows message processing itself - the scheme that is used
system-wide for message delivery and processing - is
fundamentally based on _BLOCKING_...you _can_ "poll" if you
really insist (sometimes this is what should be done :) but that
is an incidental _optional_ point for the programmer to
choose...

The system uses _blocking_ exactly so that applications _don't_
"poll" and hog CPU time that could perfectly well have been
"released" for other applications multi-tasking alongside to
use...

Beth :)