D const enables multi-reader synchronization

[Robert Jacques]

On Tue, 15 Jun 2010 14:47:08 -0400, Jérôme M. Berger <jeberger at free.fr>  
wrote:

> Robert Jacques wrote:
>> On Mon, 14 Jun 2010 15:17:57 -0400, Tomek Sowiński <just at ask.me> wrote:
>>> This is a continuation of a recent thread "Synchronized const methods"
>>> on D.learn.
>>>
>>> Currently only one thread at a time can execute a synchronized method.
>>> But think about D's const -- it's deep, so if a method is const, it
>>> can't possibly mutate its object. So many synchronized const method
>>> calls could safely look-but-not-touch the same object at the same time.
>>>
>>> The chain of questions that stems from the above is:
>>> 1. Is letting many readers in on an object really safe? Know any
>>> multi-threading quirk that would make sh*t hit the fan?
>>> 2. If answer to 1. is yes, would there be room in the current
>>> implementation of synchronized keyword for a readers-writer lock?
>>> 3. If answer to 2. is yes, how do we tackle write-starvation? In a
>>> read-mostly scenario the mutating thread may be held up forever.
>>>
>>> More on readers-writer lock:
>>> http://en.wikipedia.org/wiki/Readers-writer_lock
>>>
>>>
>>> Tomek
>>
>> This has been suggested before and has been rejected. The major issue is
>> that CREW (concurrent-read exclusive-write) locks are known to be not
>> composite and therefore its trivial to write code which results in a
>> deterministic dead-lock. The problem lies in that the const method can
>> have access to a non-const reference to its object via method arguments
>> and/or globals. Thus, a read-lock can be obtained first and then later a
>> write lock is attempted. Since the first read lock will never be
>> released, the write lock can never be taken and a deadlock occurs.
>
> 	Unless the write lock can be acquired when the only thread holding
> the read lock is the same as the one wanting the write lock.
> Something similar is already done for the "standard" lock used by
> synchronized methods (otherwise, a synchronized method would be
> unable to call another synchronized method without deadlocking).
>
> 		Jerome

Correct in theory, wrong in practice. There's an elegant way of storing  
this information at zero cost in the case of simple locks; there's no  
equivalent for CREW locks.