Re: Improving Ada's Image

["Robert I. Eachus" <rieachus@comcast.net>]

David Starner wrote:

> I'm not sure I would take a noticeable speed hit versus Linux for
> improvement of its security or crashes (which I encounter once every two
> weeks or so). It just wouldn't make enough difference for me. If I
> were running something besides a purely personal computer, I might
> analyze things differently of course.

Let me speak as someone who has been there and done that.  Stratus VOS 
was/is written in PL/I.  To support Ada on VOS, I had to put a change in 
the kernel to allow PL/I condition handlers and Ada exception handlers 
exist together gracefully on any stack.

Rather than take the high road, here is why we need this change, and it 
won't impact performance that much, yadda, yadda, yadda, I cheated. 
There was an open bug report about a race condition involving multiple 
conditions.  In effect if you hit the break key often enough, you could 
catch the race window and end up in the default error handler.

So I "fixed" the bug and proved that it did indeed eliminate the 
possibility of a race condition.  I also demonstated a test program that 
threw tens of thousands of external conditions per minute at a running 
program, without ever ending up in the DEH.  So the fix was accepted.

It reduced the OS overhead by 2% in benchmarks.  (In other words if the 
system time on some benchmark had been 10.0% of total time, it was now 
9.8%.)  This was considered to be pretty huge, especially for a change 
in condition handling.  There weren't that many PL/I conditions (Ada 
exceptions) handled by the OS during normal operation.  So what gives?

I had to make the operation of entering or leaving the scope of a PL/I 
condition handler (or an Ada exception handler) atomic.  No other way to 
fix the race condition.  Once I had decided how to do that, (a RMW cycle 
on one word in a stack frame) it allowed me to throw away a lot of now 
unnecessary code. ;-)  It wasn't quite that simple, in Ada, there is a 
nesting relationship between exception handlers, but in PL/I you could 
exit the scope of one handler while leaving a later handler active. 
That did require making a copy of the list of handlers.  (If you had Ada 
style nested scopes, you could change where you entered an otherwise 
constant list of handlers.)  Of course, most handlers for Ada or PL/I, 
once entered stay active until the scope is left.  Popping a stack frame 
took its associated handlers with it.

Whenever I have worked on or with Ada operating systems, the customers 
   have been amazed by the lack of overhead.  (You might prefer to call 
these bare machine run-times, or real-time OSes, depending on your 
viewpoint.  We are not talking about a Unix or Windows like system at 
all.)  Every time we looked, it was like that case at Stratus.  The cost 
of "doing it right" was to reduce overhead.

I should probably give another example.  One of the most time-consuming 
parts of a real-time operating system is the scanning of queues to 
determine which task must be run next.  In one real-time system we had 
to turn that around to meet timing requirements.  It turned out that 
when a task became eligible to run, there were three things that could 
happen:

    It was higher in priority than the running task.  Run it.
    The new task is higher in priority than any eligible task other than 
the running task.  Put its handle in the "Ready_Task" variable.  (Two 
comparisons now.  The priority of the running task, and the priority of 
the ready task.)
    The new task doesn't meet those criteria, attach it to the end of 
the appropriate queue.

The complicated part, and it wasn't too complex, was that if the 
currently running task became inelegible for whatever reason.  It 
started the ready task, and marked the Ready_Task as invalid.  The next 
task to come along that was lower in priority than the running task 
caused the Ready_Task to be recomputed.  Otherwise the value was 
recomputed when the currently executing task completed.  Since low 
priority tasks could not become eligible during the highest priority 
tasks--Interrupts were disabled of course--we could meet some pretty 
hairy timing deadlines.  (The idle task never completed of course, so if 
it was running, you could put it into Ready_Task, and take over.)

But we also found that the overhead of scheduling was cut more than in 
half.  By putting counters in the loop that scanned the priority queues, 
we found that there was a huge amount of scanning that went away.  The 
tasks that were most frequently scheduled when the Ready_Task was 
invalid were high-priority tasks.  They only had to scan at most the 
list between the currently executing task's priority and the newly 
eligible task's priority.  When the clock "ticked" and scheduled a new 
bunch of tasks they were scheduled in priority order, so only the first 
one might have to do a scan.

I probably went into more detail than necessary.  The real advantage was 
no kludges to maintain backward compatibility. ;-)

-- 

                                           Robert I. Eachus

"Reason and experience both forbid us to expect that national morality 
can prevail in exclusion of religious principles." -- George Washington