<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 followinghash = 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
endThis 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 happent1: read lock
t2: read lock
t1: write lock (deadlock, blocked by t2's read lock)
I disagree, write lock upgrade should throw an exception.
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 IIRCAnd 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
hereReadWriteLock (Java 2 Platform SE 5.0)
For the interested Wikipedia also has a number of pages on the matter
"locking":Lock (computer science) - Wikipedia
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] << itemWhile 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
endAdvantage 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
···
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:
--
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
