Re: Ada Protected Object Tutorial #1

[kaz@ashi.footprints.net (Kaz Kylheku)]

On Sat, 18 Dec 1999 20:55:05 GMT, Robert A Duff <bobduff@world.std.com> wrote:
>kaz@ashi.footprints.net (Kaz Kylheku) writes:
>
>> This is practical. The condition variable wait might be done inside a
>> protected kernel. It would be impractical to have, say, a UNIX kernel
>> call back into application code to determine if some predicate is true.
>
>Please explain that in more detail.  I'm not sure what you're getting at
>(efficiency, security, something else...).

All of the above. Think about  implementations in which all synchronizaiont
and scheduling is done in a protected kernel. 

>> >in even more unnecessary context switches, and/or bugs if the
>> >programmer neglects to build the evaluation of the boolean condition
>> >into a loop around the condition-variable "wait" operation.
>> 
>> That loop around a condition variable wait is needed to resolve
>> spurious wakeups and race conditions.
>
>But the point is that with an Ada protected object, the loop is *not*
>necessary -- when the task wakes up after waiting for some barrier
>condition, it already owns the lock, and the condition is necessarily
>True, because no other task can sneak in and modify things.

I believe that this either requires Hoare monitor semantics, or
it requires the compiler to generate a loop as necessary. 
E.g. if you were implementing Ada over POSIX threads, the loop would
be necessary, so your compiler would have to generate it.

>To be more precise, I should say that when an entry body is executed,
>its barrier condition is True -- this execution can be done by any
>task/thread, so it doesn't necessarily involve "waking up" as I said
>above.  The point is that there's a piece of code depending on (say) the
>fact that "this queue is empty", and when that code runs, the system
>ensures that the queue is, in fact, empty -- that piece of code need not
>check.

But the compiler may have to generate the loop nevertheless, depending
on the semantics of the underlying system interface. All it does is hide the
loop from the programmer, so it's a form of syntactic sugar.

It's not that the run-time is guaranteeing Hoare monitor semantics.

>I understand why the loop is needed with Posix threads.
>
>> I believe that providing guarantees against this sort of occurence introduces
>> overhead; that is, the cure may be worse than the ailment, particularly
>> on multiprocessors.
>
>I'm not convinced.  It seems to me that repeatedly checking the same
>condition is a cost, and the extra context switches (because one thread

It is a cost. I'm not convinced that it's not a cost that is also present
in Ada implementations, albeit hidden from the programmer. Unless the Ada
implementation has complete control over thread scheduling, which is obviously
not true of Ada implementations that run on top of many kinds of operating
systems.

In other words, it's not always easy to implement the operation ``select this
thread to be the next owner of this lock''. It also may mean delaying a thread
which is more ready to be the owner, because it is already running on another
processor and is a few instructions away from trying to grab the lock.

The cost of evaluating predicates should be weighed against the cost of forcing
a particular execution order, and the scheduling overheads that implies.

>can't check barriers on behalf of other threads) is another cost, which
>Ada avoids.  Am I missing something?

I see; to put this into perspective, doing this in a language that doesn't have
explicit support for these barriers, what you could do (for example) have each
waiting thread register a pointer to a callback function which evaluates the
predicate on behalf of that thread. It's an intriguing technique. I don't
see how it can eliminate redundant predicate evaluations though, unless
the implementation controls scheduling. You need to implement some sort of
``atomically pass ownership of the protected object to this thread'' operation.