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

Groups > comp.lang.java.programmer > #35514

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

From Andreas Leitgeb <avl@logic.at>
Newsgroups comp.lang.java.programmer
Subject Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?)
Date 2016-08-31 09:23 +0000
Organization A noiseless patient Spider
Message-ID <slrnnsd8gb.456.avl@login.logic.tuwien.ac.at> (permalink)
References <no7p5p$11i$1@news.albasani.net> <nq54i4$eob$1@news.albasani.net> <b5cbcac6-a402-4bf2-aace-9e181c3e0bd4@googlegroups.com> <26083865-8e3e-4fb5-9767-4d638ade4b6f@googlegroups.com>

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web