On Sat, Dec 27, 2008 at 12:59 PM, Robert Klemme
<shortcutter / googlemail.com> wrote:
> 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.
Oh this was bad work, I messed up, my apologies.
>
>> Robert, IIUC we do not want either the one, nor the other.
>
> What are you referring to with "one" and "other"?
IIRC, because I indeed lost context, sorry again, I meant that your
observations, however useful and learned, did not have a direct impact
to what Charles wants here. Look e.g. at the synchronized containers
in Java. They are thread safe and yet all your concerns are still
valid. In other words you are already talking about problems of the
next level of abstraction while the level below still has problems. So
all I wanted to say is that we still should tackle the low level
thread-safety.
>
>> For what I am concerned one would need Read/Write Locks.
>
> Why?
Because we want simultaneous read access. And that was the other point
I referred to in my reply, we do not want to do exclusive reads.
>
>> 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:
>
>
> 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.
3 by all means
>
>> 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.
That was my point to show why I am against exposure of the internal RW lock.
I guess I did not make that clear either :(
>  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)
I disagree, write lock upgrade should throw an exception.
>
> See also
> http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html
I am quite fond of Doug Lea's Read Write Lock from Java Threads but I
will definitely have a look.
>
>> 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.
Here I messed up again, you got it right, but this was not a stupid
error, I just got it wrong :(
>
>> 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.
>
Yup
>> 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.
Hmm we have not yet defined the semantics of this, you were right when
complaining about my jump to implementation, right now I do not see
the need for this but I will try to make my home work.
>
> 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.
I agree but we should opt for a down the middle road.
>
> 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.
I fail to see why 3 is so costly, I mean why optimize. Thread
programming is complex (that's why we all love immutable objects,
right ;) and I fail to see why one could hope that it becomes less
complex just because we add
a small but still useful feature.
>
> 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.
No please that really could be said against any progress. Furthermore
I believe that folks asking for
thread safe collections know mostly why they do that, after all thread
safety is not a hype.
>
> 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.
However there is too big a prise to pay, ok we could get rid of the
metaprogramming and just follow the idea you have presented, but
exclusive read access just will make the wrapped collection unusable
for any heavy weight parallel read access.
>
> Kind regards
>
>        robert
>
>
> PS: I just recognize we should probably move this discussion over to
> ruby-core...
Hmm  maybe
Anyway thanks for your time.

Robert
-- 
Il computer non una macchina intelligente che aiuta le persone
stupide, anzi, una macchina stupida che funziona solo nelle mani
delle persone intelligenti.
Computers are not smart to help stupid people, rather they are stupid
and will work only if taken care of by smart people.

Umberto Eco