Re: Arguments for single-mutex-exclusion on protected types

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Sun, 18 Mar 2007 18:15:13 +0100, Jacob Sparre Andersen wrote:

> Dmitry A. Kazakov wrote:
>> On Fri, 16 Mar 2007 15:29:15 +0100, Jacob Sparre Andersen wrote:
>>> Jeffrey R. Carter wrote:
> 
>>>> The last time I looked at the GNAT sources for protected objects,
>>>> each had a mutex associated with it that was obtained before any
>>>> action, even functions. I guess that hasn't changed.
>>> 
>>> Isn't that the most efficient implementation on a POSIX system?
>>
>> Even if it were, why Ada RTL should care?
> 
> Because my Ada run-time is running on top of a POSIX system.

But Ada RTL could take advantage of knowing what goes on behind POSIX,
which itself is most likely built on top of something else.

>>>  d) Since the protected function bodies can be assumed to be small
>>>     (b), there will be a relatively large overhead in keeping track of
>>>     the number of queued calls to protected functions and procedures.
>>
>> But queue is not the only possible implementation of a waitable object.
>> Protected functions and procedures do not necessarily need queues, they
>> could be implemented using a hierarchical (read-write) mutex. [*] For
>> example, when the processor has an atomic increment instruction, a
>> read-write mutex could be implemented very efficiently. The idea is that
>> you *first* change the read count and then check if there is a potential
>> writer without any locking. If everything is clear, you just continue 2-3
>> instructions later, otherwise you take a system mutex and manage all counts
>> safely.
> 
> Wouldn't we then expect our POSIX system to implement its mutexes
> using this feature?

I don't know. If POSIX were designed with Ada in mind, was it? In
particular, does it have read-write mutexes?

> With SMP systems and multi-core CPU's, I doubt
> that atomic increment instructions are popular among the hardware
> designers (but I may be wrong - this is not my strongest area of
> expertise).

Massively multiple-core systems could take ways quite different from what
we are accustomed now. Forgotten and gone architectures like transputers
could return.

[ Consider a "transaction"-like design of protected objects based on memory
replication (hardware-supported). The protected object state could then be
held in the processor's local memory. Protected function would compare the
change number of its copy and do everything without interlocking if it
hasn't been incremented. ]
 
>>>  e) Since the protected function bodies can be assumed to be small
>>>     (b), the probability of colliding calls to protected functions is
>>>     relatively small.
>>
>> That surely depends on the program logic.
> 
> For "small" = "smaller than the code using the result", it will be
> true up to at least two CPU cores (unless you force the callers to
> synchronise - and then protected objects seem somewhat misplaced - any
> other exceptions).

There are two sufficient parameters:

1. The number of processors which shifts the relation between protected /
unprotected actions code towards protected, if protected implies mutual
exclusion.

2. The number of distinct locks associated with protected objects. This is
especially the issue if you wanted to built it on top of expensive and
limited operating system resources.

> Please remember that the compiler should generate code which is most
> efficient in most cases.  We shouldn't expect it to optimise for a few
> special cases at the cost of the more common cases.

And which relation between protected function/procedure/entry is most
common? I doubt that anybody could have any reliable statistics of.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de