Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #35225 > unrolled thread

Library for Escalable Locks, Slimmest API?

Back to article view | Back to comp.lang.java.programmer

Contents

  Library for Escalable Locks, Slimmest API? Jan Burse <janburse@fastmail.fm> - 2016-08-07 18:55 +0200
    Re: Library for Escalable Locks, Slimmest API? Andreas Leitgeb <avl@logic.at> - 2016-08-08 01:10 +0000
      Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-08 09:38 +0200
        Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-08 09:47 +0200
        Re: Library for Escalable Locks, Slimmest API? Andreas Leitgeb <avl@logic.at> - 2016-08-10 14:39 +0000
          Re: Library for Escalable Locks, Slimmest API? Jan Burse <janburse@fastmail.fm> - 2016-08-10 18:05 +0200
            Re: Library for Escalable Locks, Slimmest API? Lew <lewbloch@gmail.com> - 2016-08-10 17:44 -0700
              Re: Library for Escalable Locks, Slimmest API? Jan Burse <janburse@fastmail.fm> - 2016-08-11 12:43 +0200
                Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-12 22:18 +0200
                  Re: Library for Escalable Locks, Slimmest API? Andreas Leitgeb <avl@logic.at> - 2016-08-13 05:56 +0000
                    Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-13 11:08 +0200
                  Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-13 11:37 +0200
                    Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-13 11:39 +0200
                    Re: Library for Escalable Locks, Slimmest API? Jan Burse <janburse@fastmail.fm> - 2016-08-13 12:27 +0200
                    Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-13 23:21 +0200
                      Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 11:42 +0200
                        Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 11:50 +0200
                          Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 12:06 +0200
                            Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 13:08 +0200
                              Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) Robert Klemme <shortcutter@googlemail.com> - 2016-08-14 13:45 +0200
                                Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 14:01 +0200
                                  Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 14:01 +0200
                                    Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 14:07 +0200
                        Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-14 12:13 +0200
                          Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 12:25 +0200
                            Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 12:36 +0200
                            Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-14 13:41 +0200
                          Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 12:45 +0200
                            Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 12:49 +0200
                          Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 13:45 +0200
                            Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 13:48 +0200
                            Re: Library for Escalable Locks, Slimmest API? Robert Klemme <shortcutter@googlemail.com> - 2016-08-14 14:29 +0200
                              Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 14:56 +0200
                                Re: Library for Escalable Locks, Slimmest API? j4n bur53 <janburse@fastmail.fm> - 2016-08-14 14:59 +0200
                                Re: Library for Escalable Locks, Slimmest API? Jan Burse <janburse@fastmail.fm> - 2016-08-14 18:10 +0200
    Simpler requirements on the horizon! (Re: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-14 13:18 +0200
    I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-31 01:23 +0200
      Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) bursejan@gmail.com - 2016-08-30 16:35 -0700
        Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) bursejan@gmail.com - 2016-08-30 16:45 -0700
          Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) Andreas Leitgeb <avl@logic.at> - 2016-08-31 09:23 +0000
            Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) Andreas Leitgeb <avl@logic.at> - 2016-08-31 10:13 +0000
            Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-31 14:00 +0200
          Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-31 07:49 -0400
            Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) j4n bur53 <janburse@fastmail.fm> - 2016-08-31 14:13 +0200
              Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-31 12:55 -0400
      Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-31 07:54 -0400

Page 1 of 3  [1] 2 3  Next page →

#35225 — Library for Escalable Locks, Slimmest API?

Dear Lazyweb,

Whats your favorite library for escalable read-write
locks? I read for the java.util.concurrent read-write
locks the following:


     EDIT to clarify this, as I don't think I explained
     it too well initially - I am aware that there is no
     built-in lock escalation in this class, and that I
     have to simply release the read lock and obtain
     the write lock.
 
http://stackoverflow.com/questions/464784/java-reentrantreadwritelocks-how-to-safely-acquire-write-lock

On the API side they should be ultra simple, but can
have a more complex inner working. Basically on the outside
it should not be a particular distinction between read
and updatable read.


Bye

[toc] | [next] | [standalone]

#35226

Jan Burse <janburse@fastmail.fm> wrote:
> http://stackoverflow.com/questions/464784/java-reentrantreadwritelocks-how-to-safely-acquire-write-lock
> On the API side they should be ultra simple, but can
> have a more complex inner working. Basically on the outside
> it should not be a particular distinction between read
> and updatable read.

It seems to me like your (or Andrzej Doyle's) wish is unfulfillable.
The whole idea of:

 - obtain a read lock.
 - try to upgrade the lock without actually leaving the context.

is flawed.

Even if you make a loop to release *all* the current thread's nested read
locks, your program's logic would pretty surely end up failing with strange
concurrency issues.

"One doesn't simply" release a lock while still in the critical path. And
the critical path isn't done, if after obtaining the write-lock you still
expect the state of the universe to be same as before the "upgrade".

The correct way out would be to completely exit the whole read-lock
guarded section (e.g. throw a custom exception that gets caught outside),
and only then obtain a write lock and once you got that, *redo* everything
previously done under the read-lock to make sure the current situation
is even still asking for that update, and only if so, then do the update.

Before your thread actually gets the write lock, some other thread might
have got it earlier and changed all the state that you wanted to update.

Now, for the question in the Subject:
if you were to write your own ReentrantReadUpgradeableWriteLock, then you'd
have an additional lock.getUpgradeableReadLock(), but this should really
throw some serious exception, if you tried to call it with a plain read-lock
already held - that's still better than an inevitable deadlock.

Of course this wouldn't help your tree-structure examining&updating threads
at all, because if each of them tried to start off with an upgradeable lock,
then they could just as well start with the write-lock in the first place:
only one of them could ever do its job at a time.  If instead you have a big
number of "only-examiners" and just one "eventually updater", then such
an upgradeable lock could be really useful.

hope it helped.

[toc] | [prev] | [next] | [standalone]

#35227

Andreas Leitgeb schrieb:
> It seems to me like your (or Andrzej Doyle's) wish is unfulfillable.
> The whole idea of:
>
>   - obtain a read lock.
>   - try to upgrade the lock without actually leaving the context.
>
> is flawed.

It is needed in a context with less consistency constraints. I
only want to assure that some datastructure is not damaged, the
end-user can still implement his domain consistency.

Basically the locks are only needed to create some serialization,
so the additional write should be permitted early on, even when
the thread has already a read and vice versa.

What is more bothersome is a deadlock actually. Meanwhile I
have a solution for both the escalation and the deadlock.

Escalation:
     For simplicity assume a non-reentrant read-write lock.
     Usually the locks can be implemented as simple as:
     Then the read is obtained after an await:
         !wlocked
     And the write is obtained after an await:
         rcount==0 && !wclocked

     With escalation I just do the following:
     Then the read is obtained after an await:
          wlocked==current_thread or wlocked==null
     And the write is obtained after an await:
          rcount except current_thread==0 && wlocked==null

     But for rcount except current_thread I need a HashSet.
     Lets see how this turns out.

Deadlock:
     I am using attempt(sleep) instead of acquire(), so
     if there are multiple locks, deadlock is solved by timeout.

Bye

[toc] | [prev] | [next] | [standalone]

#35228

Hi Andreas,

j4n bur53 schrieb:
> It is needed in a context with less consistency constraints. I
> only want to assure that some datastructure is not damaged, the
> end-user can still implement his domain consistency.

BTW consistency issues only appear if you have multiple
locks. Escalating from read to write is perfectly fine,
since when you had the read lock anyway no other thread
could obtain the write lock in the past.

So this fits your:
"If instead you have a big number of "only-examiners"
and just one "eventually updater", then such an
upgradeable lock could be really useful."

So consistency is automatically assured, also with escalable
locks, you don't need to leave the context. The issue
is only there if you have multiple regions, respectively
multiple locks.

If there are multiple regions then there is indeed inter-
ference, which can have many different incarnations!

Bye

[toc] | [prev] | [next] | [standalone]

#35243

j4n bur53 <janburse@fastmail.fm> wrote:
> Andreas Leitgeb schrieb:
>> It seems to me like your (or Andrzej Doyle's) wish is unfulfillable.
>> The whole idea of:
>>
>>   - obtain a read lock.
>>   - try to upgrade the lock without actually leaving the context.
>>
>> is flawed.
> It is needed in a context with less consistency constraints.

In that case, I'd label it as a specific solution for your 
unusually simple task, but not a "Library for Escalable Locks".

> What is more bothersome is a deadlock actually. Meanwhile I
> have a solution for both the escalation and the deadlock.
> Escalation:
>      For simplicity assume a non-reentrant read-write lock.
>      Usually the locks can be implemented as simple as:
>      Then the read is obtained after an await:
>          !wlocked
>      And the write is obtained after an await:
>          rcount==0 && !wclocked
> ...
Makes no sense to me. I thought you started out with a read lock,
so why is it obtained only "then"? and what is wlocked versus wclocked?

As long as you can be absolutely sure, that only a single predetermined
thread will ever even attempt a write action, you can even be successful
with a simpler locking concept, like some dirty tricks to upgrade a plain
read lock to a write lock without dropping context.

As your project/application grows, it will eventually no longer be that
simple, and then you'll be pretty screwed...

We can't prevent you from shooting in your foot.  All we can do
is warn you. It's your finger on the trigger and your foot in front
of the barrel.  At least we can laugh, when you eventually come back
here with a perforated foot.

[toc] | [prev] | [next] | [standalone]

#35246

Andreas Leitgeb schrieb:
> In that case, I'd label it as a specific solution for your
> unusually simple task, but not a "Library for Escalable Locks".

Maybe call it up your ass or what?

[toc] | [prev] | [next] | [standalone]

#35252

Jan Burse wrote:
> Andreas Leitgeb schrieb:
> > In that case, I'd label it as a specific solution for your
> > unusually simple task, but not a "Library for Escalable Locks".
> 
> Maybe call it up your ass or what?

How was that called for?

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#35254

Lew schrieb:
> Jan Burse wrote:
>> Andreas Leitgeb schrieb:
>>> In that case, I'd label it as a specific solution for your
>>> unusually simple task, but not a "Library for Escalable Locks".
>>
>> Maybe call it up your ass or what?
>
> How was that called for?
>

Hi,

I guess there is a small chance for a shit-storm
here. It was rather tit for tat.

I am planning to open source my new implementation
of ReadWrite locks, that do escalate.(*)

But besides testing, also publishing the code takes
some time, so please be patient.

Bye

(*)
I have like 3 variants of it, choices for open source:
- Non-Reentrant without Condition Variables
- Reentrant without Condition Variables
- Reentrant with Condition Variables

Possibly go with the first variant first, until
it is hardened.

[toc] | [prev] | [next] | [standalone]

#35275

On 11.08.2016 12:43, Jan Burse wrote:

> I am planning to open source my new implementation
> of ReadWrite locks, that do escalate.(*)

But please do it with a big, red warning sign "There may be deadlocks!"

> Possibly go with the first variant first, until
> it is hardened.

How do you harden something that inherently comes with the potential for 
deadlock?

Kind regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#35292

Robert Klemme <shortcutter@googlemail.com> wrote:
> How do you harden something that inherently comes with the potential for 
> deadlock?

Easy: just turn the potential into a guarantee.

That would make it pretty *hard* to make a working
multithreaded application, wouldn't it?

[toc] | [prev] | [next] | [standalone]

#35295

On 13.08.2016 07:56, Andreas Leitgeb wrote:
> Robert Klemme <shortcutter@googlemail.com> wrote:
>> How do you harden something that inherently comes with the potential for
>> deadlock?
>
> Easy: just turn the potential into a guarantee.
>
> That would make it pretty *hard* to make a working
> multithreaded application, wouldn't it?

I had not thought of that option.

While we are at it, I remember an anecdote from quite some time ago: 
that was with a multithreaded application that accessed a relational 
database.  At some point processing came to a halt.  No CPU consumption, 
no IO, no GC - it looked like a deadlock.  But then the RDMBs at hand 
had deadlock detection so whenever two transactions were interlocked one 
would be automatically rolled back with an error.  This did not happen.

It took us a while to figure that the deadlock was actually created via 
one resource in the database and one resource in application memory: the 
two involved threads acquired exclusive locks on these in different 
order and the database as well as the JVM were each only aware of one 
resource, so no automatic deadlock detection.  That was a valuable lesson.

Kind regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#35296

Robert Klemme schrieb:
> On 11.08.2016 12:43, Jan Burse wrote:
>
>> I am planning to open source my new implementation
>> of ReadWrite locks, that do escalate.(*)
>
> But please do it with a big, red warning sign "There may be deadlocks!"
>
>> Possibly go with the first variant first, until
>> it is hardened.
>
> How do you harden something that inherently comes with the potential for
> deadlock?
>
> Kind regards
>
>      robert
>

Deadlock-freeness is a property of the application program
that uses parallel components and some synchronization
primitives.

I am not the one who writes the application program, I am
only the one who is looking form some synchronization
primitives.

I am not giving any promises that the synchronization
primitives guarantee deadlock-freeness of all application
programs.

After all this cannot be guranteed.

Take for example the ordinary Java monitors, the simple
synchronized statement. You can very easily code a deadlock
via the following code:

Object lock_A
Object lock_B

Thread thread_A :
      synchronized (lock_A) {
         synchronized (lock_B) {
         }
      }

Thread thread_B :
      synchronized (lock_B) {
         synchronized (lock_A) {
         }
      }

If you read carefully what I wrote, you will see that
I am locking for synchronization primitives that time-out.
Synchronization primitives that time-out can also not guarantee
deadlock-freeness of all application programs.

But to some extend, when use with clean exception handling,
they can signal deadlocks, without some graph analysis.
But it is not guaranteeded that the deadlock is goes away,
when the transaction is tryed again.

By hardening I mean the synchronization primitives,
they might contain programming errors, especially since
as of now I didn't find a library and rolled my own. They
are already partially open source here:

     Package Miscellaneous
 
http://www.jekejeke.ch/idatab/doclet/blog/en/docs/05_run/01_kernel/misc/package.jsp
     See class AbstractLock
     See class ReadWrite
     See class ReadLock
     See class WriteLock

The source is incomplete since I have not yet uploaded SetHash.

The read and write lock are escalable in the sense that
a thread can have a read and a write lock at the same time,
but the read and write locks are currently not reentrant,
and condition variables are currently also not provided.

The application I have in mind, is not yet completely written.
I am already using the write locks successfully, but not yet
the read locks as planned. Hardenning the application towards
deadlock-freeness will make no sense, since we cannot
prove deadlock-freeness for the application I have in mind.

Bye

[toc] | [prev] | [next] | [standalone]

#35297

j4n bur53 schrieb:
> By hardening I mean the synchronization primitives,
> they might contain programming errors, especially since
> as of now I didn't find a library and rolled my own. They
> are already partially open source here:

Known error at the moment, I using System.currentTimeMillis()
which can have gaps, hence the time-out might sporadically not
work correctly. Should use System.nanoTime() or somesuch.

[toc] | [prev] | [next] | [standalone]

#35299

j4n bur53 schrieb:
> The source is incomplete since I have not yet uploaded SetHash.

See thread "DeDup an ArrayList" for a link. I just
uploaded SetHash as well.

Bye

[toc] | [prev] | [next] | [standalone]

#35310

On 13.08.2016 11:37, j4n bur53 wrote:
> Robert Klemme schrieb:

>> How do you harden something that inherently comes with the potential for
>> deadlock?

> Deadlock-freeness is a property of the application program
> that uses parallel components and some synchronization
> primitives.

Right.  But there are lock types with higher and lower likelihood of 
deadlocks.  As far as I can see your lock which allows escalation from 
shared read to exclusive write is one of the kind with higher likelihood.

> I am not the one who writes the application program, I am
> only the one who is looking form some synchronization
> primitives.

In a sense it is worse to provide a library with potential for serious 
issues than just including such functionality in a particular application.

OTOH:

> The application I have in mind, is not yet completely written.
> I am already using the write locks successfully, but not yet
> the read locks as planned. Hardenning the application towards
> deadlock-freeness will make no sense, since we cannot
> prove deadlock-freeness for the application I have in mind.

So are you writing the application or not?

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#35318

Robert Klemme schrieb:
>
>> Deadlock-freeness is a property of the application program
>> that uses parallel components and some synchronization
>> primitives.
>
> Right.  But there are lock types with higher and lower likelihood of
> deadlocks.  As far as I can see your lock which allows escalation from
> shared read to exclusive write is one of the kind with higher likelihood.

So then I repeat what I am doing:

I am not giving any promises that the synchronization
primitives guarantee deadlock-freeness of all
application programs.

Even if there were a sense to measure the distribution
of applications and from this derive some likelihood of
deadlock-freeness, then

and even if this likelihood would indicate that the
deadlock-freeness has lower probability for my
synchronization primitives I wouldn't still give
any promises.

 >> The application I have in mind, is not yet completely written.
 >> I am already using the write locks successfully, but not yet
 >> the read locks as planned. Hardenning the application towards
 >> deadlock-freeness will make no sense, since we cannot
 >> prove deadlock-freeness for the application I have in mind.
 >
 > So are you writing the application or not?

The application I need the locks for is a parallel Prolog
class loader. This loader will not have any guarantees
for deadlock-freeness.

If a deadlock happens, one of the threads will time-out
and the other thread will win. The parallel Prolog class
loader is already in production for a couple of years.

I am now doing a refinement, the old version was unsing
a mutex the new version will use read write pairs. The
refinement has to do with a performance optimization.

The performance optimization is such that Prolog can
distinguish between static and dynamic predicates. Do
avoid locks at runtime in static predicates I need a more
complicated Prolog class loader.

The more complicated Prolog class loader will use read
locks during predicate lookup, and write locks during
Prolog text consult. As a new benefit it will not anymore
happen that predicates see gradually loaded predicates.

Currently it is possible that a thread that does not do
the loading of the Prolog text, will see how a predicate
gradually is loaded. The new read lock will prevent this.

On the other hand the thread that does the loading, and
which has the write lock, should be permitted to also
read the predicate. This is needed durig loading.

So here in the following is a map what new scenarios are
needed, and how the different locks support that, and why I
need new synchronization primitives:

Thread A: Re-Loads Text T
Thread B1, .. Thread Bn: Executes Text T
<>: Atomic
RW: Ordinary Read Write Lock Pair
ERW: Escalable Read Write Lock Pair

Situation               Mutex   RW        ERW
<A_w_T>                 No(1)   Yes       Yes
<B1_r_T ... Bn_r_T>

<A_w_T A_r_T>           No(1)   No(2)     Yes
<B1_r_T ... Bn_r_T>

<A_r_T A_w_T>           No(1)   No(2)     Yes
<B1_r_T ... Bn_r_T>

(1) mutex cannot be used, since mutex does
not allow multiple readers
(2) ordinary read write pair cannot be used,
since ordinary read write pair does not
allow same thread to be reader and write

Pretty simple and effective. BTW here you see
some scaling of the new optimization, i.e. that
static predicates are not anymore synchronized after
the have been loaded:

New setup_balance/4 predicate on new hardware. (Jekejeke)
https://plus.google.com/+JanBurse/posts/Zcsyjf6FaeS

If you discount the turbo of a single core, we could
say on ideapad the CLP(FD) problem goes from ca. 4000 ms
to ca. 1000 ms on 4 cores. Very cool!

Bye

[toc] | [prev] | [next] | [standalone]

#35319

j4n bur53 schrieb:
> Currently it is possible that a thread that does not do
> the loading of the Prolog text, will see how a predicate
> gradually is loaded. The new read lock will prevent this.

BTW: The Erlang loader can do such things, block
a predicate until a module is re-loaded. Erlang is
a little bit the inspiration for my new loader.

Ordinary Java cannot do it, class loading is usually
serialized by a single lock. But there are also
parallel class loader options around.

[toc] | [prev] | [next] | [standalone]

#35321 — Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?)

j4n bur53 schrieb:
> Ordinary Java cannot do it, class loading is usually
> serialized by a single lock. But there are also
> parallel class loader options around.

They call this "heavy-handed" or "not sufficiently granular"
http://docs.oracle.com/javase/7/docs/technotes/guides/lang/cl-mt.html

You really need to think from another prespective about
the escalable locks. Deadlock-freeness is least of concern
at the moment.

The escalation problem is a problem inside the same thread.
So it doesn't have to do with deadlock per se. Its more a
problem of extending the transition matrix of the lock.

Of course this transition matrix takes also into account the
votes of other threads. But since we extend the transition
matrix, we allow more transitions.

But these more transitions do not considerably increase or
decrease some likelihood of deadlock-freeness. They only
allow to enlarge the atomic regions.

<>: Atomic

With RW, we would be forced to do:
<A_r_T> <A_w_T>
- or -
<A_w_T> <A_r_T>

With ERW, we can do:
<A_r_T A_w_T>
- or -
<A_w_T A_r_T>

So Robert Klemme(*) jumped to the following conclusions:

    larger atomics <=> lower deadlock-freeness

But he didn't give some concrete arguments or examples
for that. I don't believe in the above law. It could
be even vice versa.

Bye

(*)

Robert Klemme wrote (13.08.16, 23:21):
 > > Deadlock-freeness is a property of the application program
 > > that uses parallel components and some synchronization
 > > primitives.
 > Right.  But there are lock types with higher and lower likelihood of 
 > deadlocks.  As far as I can see your lock which allows escalation
 > from shared read to exclusive write is one of the kind with higher
 > likelihood.

[toc] | [prev] | [next] | [standalone]

#35327 — Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?)

Oops, I have to retract my allegations,
and I have to work on my memo style presentation.

I guess <A_w_T A_r_T> can pass as a memo style presentation
for first acquiring a write lock and then acquiring a read
lock. It also seems that java.util.concurrent can do it.

But I also guess that <A_r_T A_w_T> cannot pass as a memo
style presentation for an upgrade. Mostlikely the behaviour
is rather <A_r_T> <A_w_T>.

Hm.

j4n bur53 schrieb:
> j4n bur53 schrieb:
>> Ordinary Java cannot do it, class loading is usually
>> serialized by a single lock. But there are also
>> parallel class loader options around.
>
> They call this "heavy-handed" or "not sufficiently granular"
> http://docs.oracle.com/javase/7/docs/technotes/guides/lang/cl-mt.html
>
> You really need to think from another prespective about
> the escalable locks. Deadlock-freeness is least of concern
> at the moment.
>
> The escalation problem is a problem inside the same thread.
> So it doesn't have to do with deadlock per se. Its more a
> problem of extending the transition matrix of the lock.
>
> Of course this transition matrix takes also into account the
> votes of other threads. But since we extend the transition
> matrix, we allow more transitions.
>
> But these more transitions do not considerably increase or
> decrease some likelihood of deadlock-freeness. They only
> allow to enlarge the atomic regions.
>
> <>: Atomic
>
> With RW, we would be forced to do:
> <A_r_T> <A_w_T>
> - or -
> <A_w_T> <A_r_T>
>
> With ERW, we can do:
> <A_r_T A_w_T>
> - or -
> <A_w_T A_r_T>
>
> So Robert Klemme(*) jumped to the following conclusions:
>
>     larger atomics <=> lower deadlock-freeness
>
> But he didn't give some concrete arguments or examples
> for that. I don't believe in the above law. It could
> be even vice versa.
>
> Bye
>
> (*)
>
> Robert Klemme wrote (13.08.16, 23:21):
>  > > Deadlock-freeness is a property of the application program
>  > > that uses parallel components and some synchronization
>  > > primitives.
>  > Right.  But there are lock types with higher and lower likelihood of
>  > deadlocks.  As far as I can see your lock which allows escalation
>  > from shared read to exclusive write is one of the kind with higher
>  > likelihood.
>

[toc] | [prev] | [next] | [standalone]

#35332 — Re: Jumping to false Conclusions [Robert Klemme] (Was: Library for Escalable Locks, Slimmest API?)

On 14.08.2016 13:08, j4n bur53 wrote:
> Oops, I have to retract my allegations,

Thank you.

> and I have to work on my memo style presentation.

Sometimes terse is too short and more explicit wording helps communication.

>> So Robert Klemme(*) jumped to the following conclusions:
>>
>>     larger atomics <=> lower deadlock-freeness

I wouldn't know where you took that from.  Deadlocks is about locking 
order.  And the fact that a read write lock which allows lock escalation 
from read to write (better: from shared to exclusive) can _very_ easily 
deadlock on a single resource.  See this answer for an illustration:

http://stackoverflow.com/questions/2407558/pthreads-reader-writer-locks-upgrading-read-lock-to-write-lock#answer-2407677

>> But he didn't give some concrete arguments or examples
>> for that. I don't believe in the above law. It could
>> be even vice versa.

see above

Regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web