From: Robert Klemme <shortcutter@...>
Date: 2008-12-27T20:59:51+09:00
Subject: Re: Are all Ruby built-in objects thread safe?

On 26.12.2008 19:17, Robert Dober wrote:
> On Fri, Dec 26, 2008 at 11:24 AM, Robert Klemme
> <shortcutter@googlemail.com> wrote:

<snip>full quote</snip>

Please invest a bit more time in quoting and trimming.  I may speak for 
me only but I find it unnecessary hard to follow a discussion when there 
is a full quote and no clear indication of references in your reply.

> Robert, IIUC we do not want either the one, nor the other.

What are you referring to with "one" and "other"?

> For what I am concerned one would need Read/Write Locks.

Why?

> The built in methods like [] and []= would obtain read and write
> locks, while the read lock automatically obtains a write lock and only
> releases it when its count is to zero, the write lock would inhibit
> the read lock to be obtained.

Let's first talk about semantics not jump into implementation.  How the 
read write locking is implemented is rather unimportant for the question 
what kind of additional locking we want to propose for default 
collections (if any).  As far as I can see three variants are lying on 
the table with the lock free collection always be present as well:

1. none at all, locking needs to be explicitly done in client code

2. exclusive locking, no two methods can execute concurrently on the 
same instance

3. read write locking with the usual semantics, allowing multiple 
methods with read semantic to be executed concurrently or at most one 
"write" method at a time.  "write" lock excludes any "read" locks.

I'll follow up with discussion at the end.

> I do not know if one should allow user access to these locks? My first
> thought would be no, all we want to do is to have thread-safe Hash,
> Array, String but not to provide advanced synchronization mechanisms.
> OTOH one could expose the write_lock and read_lock of each object
> which would allow for the following
> 
> hash = TS_Hash::new
> ..
> dat = hash.read_synchronize do
>    if hash.has_key? key then
>       hash[ key ]
>    else
>       hash.write_synchronize do
>         hash[key] = compute_data( key )
>       end
>   end
> end

This is a bad idiom because it is prone to deadlocking.  When having 
multiple levels of locks you must only go from stronger to weaker locks, 
not the other way round.  Otherwise this can happen

t1: read lock
t2: read lock
t1: write lock (deadlock, blocked by t2's read lock)

See also 
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

> N.B. We have to solve the interlock problem here as normally the
> write_synchronize does not obtain the write_lock
> as the read_synchronize did get a read_lock. We would need to grant
> the write lock if the read_lock is obtained by the current thread
> *only*,

With this definition you force code to obtain a read lock before the 
write lock can be held.  I assume you mean that the rule should rather 
be "grant the write lock only if no other thread holds the read lock" - 
which is what rw locking usually does.

> but imagine two threads waiting for the write_lock while
> containing the read_lock, the good old
> philosophers-forks-spoon-spaghetti interlock. [ That is why we eat
> spaghetti with a fork only ;) ]

Exactly, as show above.

> Therefore I guess the RW-locking in a ThreadSafe Container class shall
> rather not be exposed as we avoiding interlocking is not that
> complicated IIRC
> 
> And if we expose read_synchronize &blk, and write_synchronize &blk we
> should probably raise something like an IllegalMonitorState exception
> if a thread tries to call the one inside the other.

Not necessarily: read_synchronize inside write_synchronize is perfectly 
ok although it has no noticeable effect.  But since it can occur in 
another method it is reasonable to allow it.

Some more remarks about the complexity of read write locking can be 
found here

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html

For the interested Wikipedia also has a number of pages on the matter 
"locking":

http://en.wikipedia.org/wiki/Lock_(computer_science)

Now, what would be reasonable to provide in a thread safe standard 
collection?  IMHO the discussion above and the complexity and wide 
variance in implementation choices for read write locking makes it next 
to impossible to come up with an optimal read write lock implementation 
in standard collections for most application scenarios.

This yields a bad cost benefit ratio for option 3 above.  This leaves us 
with options 1 and 2.  I lean toward option 1 because even the dead 
simple exclusive lock approach is of limited use only.  Even in light of 
default values or the default_proc of a Hash there are some things to note.

Consider

# assuming Synchronize() wraps an instance with a delegator
# which synchronizes all method calls on a single lock
$all_values = Synchronize(Hash.new {|h,k| h[k] = Synchronize([])})
...
# in multiple threads:
$all_values[some_key] << item

While our basic locking ensures internal state of all collections is
consistent the code has the disadvantage that every thread needs to 
obtain two locks and the number of locks is not limited (1 + no of 
keys).  A single lock would be sufficient here.

Another disadvantage of built in locking is that it might trick some 
people in believing that this is all they need to use to get thread safe 
code.  If there would be no such thing as a default thread safe Array 
and Hash people are forced to think about how they want to go about 
locking and I believe that way they will get better (i.e. more correct 
and more efficient) code.

As a compromise I suggest to provide something like the Synchronize() 
method I showed above which does two things: 1. it extends the object 
passed with MonitorMixin and 2. it wraps the instance with another 
instance which synchronizes all methods like this:

   class SynchWrapper
     def initialize(o)
       @obj = o.extend(::MonitorMixin)
     end

     # remove all Object methods

     def method_missing(*a,&b)
        @obj.synchronize { @obj.__send__(*a,&b) }
     end
   end

Advantage is that there is a single mechanism that uniformly works for 
_all_ classes not just collections.  And, the mechanism is made explicit 
while not requiring too much manual intervention or additional typing. 
For all cases where the logic requires other locking schemes explicit 
locking needs to be employed anyway.

Kind regards

	robert


PS: I just recognize we should probably move this discussion over to 
ruby-core...