CS>time-critical routines.  If you are really
CS>concerned about this possibility,
CS>there are ways that OS/2 can lock small amounts of
CS>memory so they will never
CS>paged.  This can be done from device drivers,for instance.

 LR> How small?

OS/2 2.x for Intel systems manages memory in 4096 byte pages. That is the
smallest unit of memory that you can lock.

CS>Indeterminate in this context means that you cannot
CS>state an upper ceiling for execution time.

 LR> I think Peter gave me a similar definition as well, Craig

 LR> Would it be clearer, and more comprehensible, to state that
 LR> "indeterminate" means that it can not be determined, with any
 LR> specific certainty, (a unique mathematical solution) due to the varying
 LR> length of internal computer process times that might occur such that
 LR> any particular response will be (to a certainty) *within* the given
 LR> timing specs (time domain) for responding to a certain (digital - A/D)
 LR> stimulus?

That's too specific.  It's not just responding to stimuli (interrupts or
I/O) that matters.  Also non-I/O activities such as heap management and
search algorithms have to be considered.  You also have to consider the
effects of multiple tasks (threads) and how they can make normally
deterministic behavior appear to be non-deterministic.

 LR> When I read your definition I tended to be puzzled.  The puzzle was in
 LR> trying to understand your meaning as to *why* an "upper ceiling
 LR> execution time" could NOT be stated.

If you know everything that can happen in the system, know exactly when
everything will happen, and also know that maximum system capacity and
other operating limits aren't exceeded then I suppose you could nearly
always come up with a deterministic way to predict maximum execution time. 
But the problem is that you often can't know all of those things and even
if you did predicting the maximum execution time can involve so many
variables that it quickly becomes unworkably difficult.  So what you do is
try to limit the complexity by avoiding certain routines and methods that
introduce lots of potential variable length delays.

 LR> For instance, what came to my mind was the thought that one could just
 LR> note when a stimulus occurs and then simply wait for the longest
 LR> response time - empirically - and that could be the "upper ceiling
 LR> execution time" to be stated for a response.

That's not good enough.  You can't depend solely on empirical results
unless you are able to test for all possible cases.  Usually this is
impossible to do because there are so many possibilities.  For example, if
you are testing a real-time system and your tests happen to miss the TCAL
(thermal calibration) periods on the hard disks that you are using in your
run-time system, you could conclude some maximum response time that is
actually far less than what it would be if a TCAL happens in the middle of
your test.  Also there are
hard-to-control variables such as network traffic (even if it isn't
directed to your node) to consider.

 LR> In other words it seems to me that stating a "upper ceiling execution
 LR> time" cannot be stated is somehwat vague in that it doesn't fully
 LR> qualify that a specifc outer timing domain does exist in most RT apps -
 LR> and that specific domain time must not be exceeded - by specification.

The difference is that a real-time application is written to avoid using
code with indeterminate execution time.  There are generally algorithms
available that can be used that can be given an upper bounds on execution
time, but they may not be the "intuitive" methods or the easiest
ones to use.

 LR> And that "indeterminate" means that response time MUST be
*within* that
 LR> specific timing domain or that response will be invalid.  Would you
 LR> agree with that what I have just said might be clearer - if more wordy
 LR> - for the uninitiated?

Yes, I think what you are saying is about right, but it is too specifically
focused on I/O events.

 LR> What also might not be clear to the uninitiated is why responding
 LR> (D/A) to a (Analog to Digital(A/D) stimulus within that specific time
 LR> domain would be viewed, even if it was not a constant response time to
 LR> the same stimulus, as being valid?

 LR> Would you care to address this issue, Craig?

I would if I was clear on what you said in the preceding paragraph. I think
what you are asking is why is it OK to have variable response times.  It is
OK as long as you never exceed the maximum allowable response time.

CS>I ran into big problems last year with memory allocation
CS>routines in C Set++ being extremely indeterminate because I was
CS>allocating a deallocating memory on multiple threads.

 LR> You mean dynamic memory allocation on the heap, right?  What does
 LR> extremely indeterminate mean to you, Craig?

In this case, it means that you cannot be sure if the memory allocation
will return before the system starts loosing data. While I can't be sure of
exactly how long some of these memory allocations were taking, it was clear
that they were ruining the data acquisition by loosing data even at speeds
as low as 38400 bps using 16550 chips with buffers enabled on the serial
ports.

CS>The heap is mutex protected by a single semaphore.

 LR> I am not familar with the "mutex" term relative to the heap.

Mutex is a shortened version of the phrase "mutual exclusion"
which is generally used to denote data structures or resources that should
only be accessed by one task at a time or else the consistency of the data
structure will be destroyed.

 LR> And I can never remember what a semiphore is tho I have run into it
 LR> enough.  Could you please explain both as you use them here.  Thanks.

A mutex semaphore is like a flag that allows one task to use a resource and
makes other tasks wait for that resource until no task is using the
resource.  There are other types of semaphores, also. OS/2 implements three
types -- mutex, event, and muxwait.  Muxwait is basically a way to way on
more than one semaphore at a time.  Event semaphores are usually used for
coordinating timing between threads. For example, you might use an event
semaphore to make one thread wait to do a certain action until another
thread has prepared a resource that will be needed to do perform the
action.

CS>The result was
CS>that I was having problems with time-critical threads being
CS>blocked and loosing data because they were waiting around for
CS>heap access and additional I/O buffers couldn't be allocated until
CS>they got mutex on the heap which was taking long enough that data
CS>was being lost.

 LR> Why were the time critical threads being blocked (delayed)?  Doesn't
 LR> OS/2 give priority to time critical threads in an appropiate manner?

Yes, OS/2 uses prioritized scheduling.  But this is a classic case of
priority inversion where a lower priority thread had exclusive access to a
resource needed by a higher priority thread, thereby making the higher
priority thread effectively become a lower priority thread. VxWorks has a
type of mutex semaphore that implements priority inversion protection where
the low priority thread would be boosted to a high priority until the
resource is released and the high priority thread can use it.  OS/2 does
not have this feature.

CS>The solution was to preallocate more I/O buffers than needed and to
CS>write a non-blocking buffer allocation routine that used 486
CS>atomic test-and-set, test-and-reset, increment, and decrement
CS>instructions.

 LR> What is "486 atomic test-and-set" and how did you use
this from C++?

It allows you to test the status of bit and then turn the bit on in one
machine instruction.  Machine instructions are considered to be atomic --
i.e., there will not be a thread context switch during execution of a
machine instruction.  I used this by writing short little routines in
Borland TASM for OS/2 and then calling those routines from C++ code.

CS>I made these routines SMP safe by LOCK prefixing the
CS>atomic instructions in expectation that we will eventually be
CS>running this software SMP hardware using OS/2.

 LR> Could you make this a little plainer for those of us who are not
 LR> intimately familar, as you are, with C++ and OS/2?  What is SMP for
 LR> instance?

SMP means symmetric multiprocessing.  Putting a LOCK prefix on an
instruction means that the processor will lock the memory bus such that
other processors cannot mess up the operation by trying to access the
memory address upon which a read-modify-write type of operation is being
done until the operation is complete.

CS>any language can be used for real-time programming,
CS>but you have to pay a lo
CS>of attention to maintaining determinism in the application design.

 LR> Could you explain why this is so?

Languages are merely a construct for expressing ideas.  As long as you can
express the idea in such a way that will meet specified timing constraints
then you can (in theory) use a particular language for a particular
real-time project.  But just because you can express the idea in a way that
will meet timing constraints doesn't mean that you will do so.  For
instance, you might decide to use an algorithm that will on average perform
a task in 100ms rather than an algorithm that will on average perform the
same task in 250ms.  While that sounds like a smart choice, for a real-time
system it could be a disaster if the 100ms average algorithm can sometimes
takes up to 1000ms to do the task but the time limit is 500ms.  If the
250ms average algorithm is guaranteed to never take longer than 300ms, it
is the better choice for this particular system even though it will usually
be slower.

As a particular example, consider search algorithms.  Binary searches gives
O(log n) performance.  Hashing can often do better than O(log n)
performance.  But if you use chained hashing, depending on the data your
search times could approach O(n).

CS>You cann
CS>just assume that new, delete,malloc(), free(), and
CS>other basic library routi
CS>are going to be deterministic.

 LR> You mean they will be "indeterminate"?

Yes, they can be.

CS>predict how much time they will take.  Sometimes they might take 0.1
CS>milliseconds, other times they may take 120
CS>milliseconds, and in extreme
CS>situations they could even take over a second to complete.

 LR> That sounds indeterminate to me if the "upper ceiling
execution time"
 LR> for the response time must be determinate and it is found not to be
 LR> determinate.

Yes.

CS>I don't think OS/2 is suitable for applications
CS>that require response times
CS>the order of a few microseconds.  Frankly, I'm not
CS>sure if VxWorks is even
CS>suitable such applications.

 LR> Someone told me that 400us + about ten instruction cycles is the best
 LR> interrupt latency time for time critical for OS/2.

I doubt that you could guarantee such performance on 486 or probably even
Pentium hardware, although you might get such sub-millisecond interrupt
service times in some cases.
But I haven't figured this out in detail, so I could be wrong.

 LR> Craig, it is possible the client won't need microsec response times.
 LR> I can't determine this right now, nor give you specifc information on
 LR> the actual circumstances for this application.

I'd say that your #1 priority right now should be figuring out the general
design of the system and performance constraints.  After that is done, then
think about picking the operating system to use.


--- Maximus/2 2.01wb