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 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

The deadlock scenario for ordinary read write locks (RW)
is even simpler than for escalable read write locks (ERW).
It simply reads (See java.util.concurrent spec):

     r_l.acquire();
     w_l.acquire();

So why do force ERW more deadlocks compared to RW
in your view? Higher likelihood? This doesn't make
any sense to me.

Bye

Robert Klemme schrieb:
> 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

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

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

j4n bur53 schrieb:
> The deadlock scenario for ordinary read write locks (RW)
Corr. The simplest deadlock scenario for ordinary read write locks (RW)

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

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

j4n bur53 schrieb:
> j4n bur53 schrieb:
>> The deadlock scenario for ordinary read write locks (RW)
> Corr. The simplest deadlock scenario for ordinary read write locks (RW)

Anyway, see my "Simpler requirements on the horizon!" post,
I don't need escalable RW locks anymore.

But nevertheless I don't like the use of the work "likelihood",
after all programming is not rain dance.

Bye

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

#35322

On 14.08.2016 11:42, j4n bur53 wrote:
> Robert Klemme schrieb:

Thank you for the following explanations!

>> 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.

That is possible with a ReadWriteLock: if you hold the write lock the 
resource is yours to write but of course also to read.

> 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

This sounds as if there are dedicated threads for loading.  If this is 
the case then acquiring the write lock right away for these would be 
sufficient it seems.

You only then could face starvation issues which you can remedy by using 
fair mode:
http://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

> <>: 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

In case there are no dedicated loading threads:

If you are trying to optimize this, then a different scheme might work 
as well: you could hold the resource in an AtomicReference.  Whenever a 
thread reads null, it needs to load the resource and update the 
reference.  The object representing the loaded file content then should 
of course be immutable.  Downside is that sometimes multiple threads 
might be reading but you can ensure that only one of them updates the 
reference.

Alternatively the algorithm without any need for lock escalation could 
be like this (pseudo code):

final boolean needsLoading
acquire r-l
needsLoading = resourceNeedsLoading()

if (!needsLoading) {
    useIt()
}
release r-l

if (needsLoading) {
   acquire w-l
   if ( resourceNeedsLoading() ) {
     loadFromFile()
     updateResource()
   }
   release w-l

   acquire rl
   assert !resourceNeedsLoading()
   useIt()
   release rl
}

resourceNeedsLoading() could then either check whether the resource has 
been loaded at all or also include modified time checks on the file.

I do not know though how consistency requirements are in your 
application on a larger scale - especially since you mention 
"re-loading".  Under which circumstances is a file reloaded?

Kind regards

	robert

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

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

#35323

 > Alternatively the algorithm without any need for lock
 > escalation could be like this (pseudo code):

I need a library where additionaly to that:

   acquire w-l
   if ( resourceNeedsLoading() ) {
     loadFromFile()
     updateResource()
   }
   release w-l

Inside loadFromFile() the loading thread can also do an
acquire r-l and then a release r-l.

Robert Klemme schrieb:
> I do not know though how consistency requirements are in your
> application on a larger scale - especially since you mention
> "re-loading".  Under which circumstances is a file reloaded?

When it has been changed. We know this already from JSP.
But JSP is a special case, since under the hood, its a
class which is not used by any other class.

But here re-load can also happen for classes that are somewhere
inside the class hierarchy, means that the interface changes
are notified through the whole class hierarchy.

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

#35324

Hint: Doug Lea is aware that his ReentrantReadWrite
locks are not escalable. I my first post there is an
SO link, and there you find a reference to a discussion.

So don't think java.util.concurrent is some
ultimatum, and its mandatory to use existing
synchronization primitives.

j4n bur53 schrieb:
> I need a library where additionaly to that:
>
>    acquire w-l
>    if ( resourceNeedsLoading() ) {
>      loadFromFile()
>      updateResource()
>    }
>    release w-l
>
> Inside loadFromFile() the loading thread can also do an
> acquire r-l and then a release r-l.

But this escallation, in memo style <A_w_T A_r_T>,
i.e. A_w_T=Thread A acquires write lock on T,
A_r_T=Thread A acquires read lock on T, is very
easy to implement:

Ordinary read lock (we get the read lock if
there is no writer):

         synchronized (parent) {
             while (parent.write.locked!=null)
                 parent.wait();
             /* acquire */
         }

Escalable read lock (we get the read lock if
there is no OTHER writer):

         synchronized (parent) {
                 throw new IllegalStateException("read lock unbalanced");
             while (parent.write.otherWriter(thread))
                 parent.wait();
             /* acquire */
         }

Whereby other write is implemented as simple as:

     boolean otherWriter(Thread thread) {
         return (locked != null && locked != thread);
     }

Similarly for the other escalation,
in memo style <A_r_T A_w_T>.

Bye

Jan Burse wrote (13.08.16, 11:37):
 > 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

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

#35330

On 14.08.2016 12:25, j4n bur53 wrote:
>> Alternatively the algorithm without any need for lock
>> escalation could be like this (pseudo code):
>
> I need a library where additionaly to that:
>
>   acquire w-l
>   if ( resourceNeedsLoading() ) {
>     loadFromFile()
>     updateResource()
>   }
>   release w-l
>
> Inside loadFromFile() the loading thread can also do an
> acquire r-l and then a release r-l.

You can do that with Java's ReentrantReadWriteLock:

"Additionally, a writer can acquire the read lock, but not vice-versa."

But you do not need to because the thread has an exclusive lock already 
(the write lock) and the write lock excludes read locks.  You do not 
gain anything from that unless you want to do lock downgrading.

> Robert Klemme schrieb:
>> I do not know though how consistency requirements are in your
>> application on a larger scale - especially since you mention
>> "re-loading".  Under which circumstances is a file reloaded?
>
> When it has been changed.

Well, yes.  Then see my suggestion.

Regards

	robert

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

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

#35325

Robert Klemme schrieb:
> That is possible with a ReadWriteLock: if you hold the write lock the
> resource is yours to write but of course also to read.

Yeah, it seems to be coupled with the reentrancy.

I read:

    Lock downgrading

    Reentrancy also allows downgrading from the write lock to a read 
lock, by acquiring the write lock, then the read lock and then releasing 
the write lock. However, upgrading from a read lock to the write lock is 
not possible.

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html 


Hm.

But I have both requirements R->W, and W->R. But I don't have
a requirement of reentrancy, or do I? Have to check!

Thanks! Robert Klemme! Thanks!

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

#35326

j4n bur53 schrieb:
> But I have both requirements R->W, and W->R. But I don't have
> a requirement of reentrancy, or do I? Have to check!

R+W, W+R

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

#35331

Robert Klemme schrieb:
> resourceNeedsLoading() could then either check whether the resource has
> been loaded at all or also include modified time checks on the file.

No I don't have a dedicated load thread.

Yes it might happen that two threads try to read the
same resource at the same moment.

The write lock is used to serialize the read and update
of the resource, and a modified time check is used to
avoid a double read.

There are still issues here. Since before the resource
content is updated, both threads might already have
a reader handle and thus a modified time.

I recently moved getting the reader handle outside
of the write lock block. Maybe this is not a good
idea. Have to work on this also.

So its not exactly:

   acquire w-l
   if ( resourceNeedsLoading() ) {
     loadFromFile()
     updateResource()
   }
   release w-l

More along:

   if ( resourceNeedsLoading() ) {
      acquire w-l
      loadFromFile()
      updateResource()
      release w-l
   }

But I guess the optimal code is along:

  if ( resourceNeedsLoading() ) {
     acquire w-l
     if ( resourceNeedsLoading() ) {
        loadFromFile()
        updateResource()
     }
     release w-l
  }

This kind of double checking a condition is often
seen in MT code since acuiring a lock might take time
and meanwhile condition can have changed.

The double checking makes the thing also slightly
faster, since without acquiring a lock by the first
if, we can already decide.

This double checking works best for caches. As
I said in the particular case of loading, there
might be still some slight issues here.

Bye

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

#35333

j4n bur53 schrieb:
>
> This kind of double checking a condition is often
> seen in MT code since acuiring a lock might take time
> and meanwhile condition can have changed.
>
> The double checking makes the thing also slightly
> faster, since without acquiring a lock by the first
> if, we can already decide.
>
> This double checking works best for caches. As
> I said in the particular case of loading, there
> might be still some slight issues here.

You have the double check here:

    if (!needsLoading) {
       useIt()
    }
    release r-l

Yes thats it!

Oki Doki.

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

#35340

On 14.08.2016 13:45, j4n bur53 wrote:
> Robert Klemme schrieb:
>> resourceNeedsLoading() could then either check whether the resource has
>> been loaded at all or also include modified time checks on the file.
>
> No I don't have a dedicated load thread.
>
> Yes it might happen that two threads try to read the
> same resource at the same moment.
>
> The write lock is used to serialize the read and update
> of the resource, and a modified time check is used to
> avoid a double read.
>
> There are still issues here. Since before the resource
> content is updated, both threads might already have
> a reader handle and thus a modified time.
>
> I recently moved getting the reader handle outside
> of the write lock block. Maybe this is not a good
> idea. Have to work on this also.
>
> So its not exactly:
>
>   acquire w-l
>   if ( resourceNeedsLoading() ) {
>     loadFromFile()
>     updateResource()
>   }
>   release w-l
>
> More along:
>
>   if ( resourceNeedsLoading() ) {
>      acquire w-l
>      loadFromFile()
>      updateResource()
>      release w-l
>   }
>
> But I guess the optimal code is along:
>
>  if ( resourceNeedsLoading() ) {
>     acquire w-l
>     if ( resourceNeedsLoading() ) {
>        loadFromFile()
>        updateResource()
>     }
>     release w-l
>  }

That is not optimal.  That is slow and error prone.  Slow, because you 
call the method for checking at most three times while my code only 
calls it at most two times per execution.  Wrong, because you invoke the 
check method without holding a lock.  That is precisely the reason why 
my suggested code remembers the state when obtained inside the lock and 
reevaluates when holding the read lock.

> I said in the particular case of loading, there
> might be still some slight issues here.

I can confirm that there are issues in your suggestion.

Regards

	robert

PS: Noted some more messages which I haven't yet read.

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

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

#35341

Robert Klemme schrieb:
>>  if ( resourceNeedsLoading() ) {
>>     acquire w-l
>>     if ( resourceNeedsLoading() ) {
>>        loadFromFile()
>>        updateResource()
>>     }
>>     release w-l
>>  }
>
> That is not optimal.  That is slow and error prone.  Slow, because you
> call the method for checking at most three times while my code only
> calls it at most two times per execution.  Wrong, because you invoke the
> check method without holding a lock.  That is precisely the reason why
> my suggested code remembers the state when obtained inside the lock and
> reevaluates when holding the read lock.

Yes, maybe this is a good approach, to use a read lock
for the resourceNeedsLoading().

Since we have learnt that if a thread holds a write lock
he is also entitled to acquire a read lock, the whole
thing could be coded more modular:

boolean resourceNeedsLoading() {
     aquire r-l
     res=checkResource();
     release r-l
     return res;
}

But my problems are not refacroring problems. The issue
is that checkResouce() das a URL get() with if_modified_since,
how can I reduce the number of URL() get?

(BTW: I am not only using if_modified_since , I am also
checking the expiration against last modified , and some
more stuff )

I was already thinking about:

   if ( "URL head()" ) {
      acquire w-l
      if ( "URL get()" ) {
         loadFromFile()
         updateResource()
      }
      release w-l
   }

But I have not yet experimented with 304 in HEAD,
I am only able to handle 304 in GET for the moment,
lets see.

(BTW: Don't worry, also some further caching is possible,
so I can also reduce the number of URL head(), since there
are import maps)

Bye

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

#35342

j4n bur53 schrieb:
> But I have not yet experimented with 304 in HEAD,
> I am only able to handle 304 in GET for the moment,
> lets see.

This SO entry says it should work:
http://stackoverflow.com/questions/5400180/what-response-should-if-modified-since-http-header-return-if-request-is-head

But configuration of the URLConnection can be tricky etc...

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

#35343

j4n bur53 schrieb:
> But I have not yet experimented with 304 in HEAD,
> I am only able to handle 304 in GET for the moment,
> lets see.

Here is a first draft, testing still ongoing:
http://stackoverflow.com/a/38943910/502187

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

#35328 — Simpler requirements on the horizon! (Re: Library for Escalable Locks, Slimmest API?)

Dear All,

Was going through my application again, it seems that I don't
need R+W, only W+R. I am not yet 100% sure, but it looks like
this is the case.

So now I have the problem of removing this extra functionality
from my homegrown library. I could throw an exception as an
assertion violation when R+W is demanded!

Oki, Doki.

Bye

Jan Burse schrieb:
 > 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] | [prev] | [next] | [standalone]

#35498 — I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?)

Strange, I took a look again at your example. It seems
to me that its not a deadlock under the following
circumstances:

    A thread escalates from read to write, by releasing
    the read and then acquiring the write.

What happens is the following in the SO example:

1) thread 1 acquire read lock

2) thread 2 acquire read lock

3) thread 1 ask to upgrade lock to write

4) thread 2 ask to upgrade lock to write

In step 3) thread 1 will release its read lock, but
not yet get the write lock since there is still another
reader.

In step 4 thread 2 will also release its read lock,
now either thread 1 or thread 2 can acquire the write
lock.

When the one who got the write lock has finished
its work and released the write lock, then the other
thread can get the write lock.

If there are more readers around then the step 3)
requiest should drain the readers, provided they
finish their work and release the read lock.

So no deadlock and no starvation.


Robert Klemme wrote:
 > 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

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

#35501 — Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?)

I am stuck in the read to write update problem.
First I thought I don't need it.

Then I needed it in one situation and it turned
out to only be the other direction, i.e. write to read,

Now I am faced again with read to write in a new
situation, and found the following funny solution:

   don't lock the write, but make it kind of 
   an indempodent disposable lockless operation, 
   possibly generating overhead in that 
   multiple threads will do it

Typical example:

   if (cache == null)
       cache = new Cache();

Pattern often seen in Java, if new Cache() is 
cheap there is not much harm.

 

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

#35502 — Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?)

My example is rather:

    if (cache[idx] == null)
       cache[idx] = new Cache(idx)

And new Cache(idx) is expensive, and it can
happen that a large number of threads choose
the same idx

What should be done?

> Typical example:
>
>   if (cache == null)
>       cache = new Cache();
>
> Pattern often seen in Java, if new Cache() is
> cheap there is not much harm. 

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

#35514 — Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?)

bursejan@gmail.com <bursejan@gmail.com> wrote:
> My example is rather:
>     if (cache[idx] == null)
>        cache[idx] = new Cache(idx)
> And new Cache(idx) is expensive, and it can
> happen that a large number of threads choose
> the same idx

> What should be done?

Your program is essentially this:

aquire read lock
if (cache[idx] == null) {
   attempt to upgrade to write
   cache[idx] = new Cache(idx)
}

Now we have two threads who both have the read lock and found
cache[idx] == null (with both threads looking at same idx).

Both threads then give up the read, and one of them gets the write
lock, sets cache[idx] and is done. 

Now, the other thread gets the write lock, and what does it do?
It recreates a new Cache(idx) and overwrites cache[idx], exactly
what you didn't want to happen.

What's the mistake?
The mistake is "upgradeable lock".

What's the solution?
The threads essentially need to redo the "if", after having
aquired the write lock, just like I wrote long ago to this
topic.

So, in this example the correct solution is: if a thread has
a read lock, but sees a need to write, then it must bail out,
aquire write lock, then redo *the whole thing*, just because
the condition that made it even *want* a write lock might
completely change during the "upgrade".

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

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

csiph-web