Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #35225 > unrolled thread
| Started by | Jan Burse <janburse@fastmail.fm> |
|---|---|
| First post | 2016-08-07 18:55 +0200 |
| Last post | 2016-08-31 07:54 -0400 |
| Articles | 6 on this page of 46 — 7 participants |
Back to article view | Back to comp.lang.java.programmer
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 3 of 3 — ← Prev page 1 2 [3]
| From | Andreas Leitgeb <avl@logic.at> |
|---|---|
| Date | 2016-08-31 10:13 +0000 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <slrnnsdbem.456.avl@login.logic.tuwien.ac.at> |
| In reply to | #35514 |
Just a clarification added inline ...
Andreas Leitgeb <avl@logic.at> wrote:
> 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".
The mistake is:
"upgrading a read lock to a write lock *while preserving context*"
(An "upgradeable lock" is really a different thing, where the situation
of two threads trying to upgrade is safely avoided by never having two
threads at the same time trying to upgrade any read lock. In the context
of the current example, such a upgradeable lock wouldn't help, though,
because the "upgradeable read" is itself an exclusive lock, and thus
the threads would see no concurrency at all, even after eventually all
the caches are initialized.)
> 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]
| From | j4n bur53 <janburse@fastmail.fm> |
|---|---|
| Date | 2016-08-31 14:00 +0200 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <nq6gsq$10l$1@news.albasani.net> |
| In reply to | #35514 |
Andreas Leitgeb schrieb:
> 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.
Yes, redoing the if is a solution.
But we have also to consider the cost of calculating
idx. I didn't mention that we have:
idx = some not so cheap computation
So in the end overwriting the cache could be the
better solution. I am currently benchmarking this
solution:
Current Benchmark:
write lock (ops that read from
cache and ops that invalidate cache)
- versus -
read lock (ops that read from
cache) write lock (ops that invalidate
cache)
But you are right, I could try what you suggest,
doing a re-evaluation. Was thinking about this also!
Bye
[toc] | [prev] | [next] | [standalone]
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Date | 2016-08-31 07:49 -0400 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <nq6g8s$kba$1@dont-email.me> |
| In reply to | #35502 |
On 8/30/2016 7:45 PM, 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
Even if new Cache(idx) is cheap, there might be trouble
if different threads use different Cache instances instead
of sharing just one.
> What should be done?
synchronized(cache) {
if (cache[idx] == null)
cache[idx] = new Cache(idx);
}
cache[idx].useTheCache();
Fancier schemes exist, but I would suggest you not bother with
them until and unless the above simple approach proves inadequate.
If actual measurement shows that you need something else, *then*
it will be time to consider alternatives.
--
esosman@comcast-dot-net.invalid
The Tooth Fairy has gone high-tech, now pays in Bitecoin.
[toc] | [prev] | [next] | [standalone]
| From | j4n bur53 <janburse@fastmail.fm> |
|---|---|
| Date | 2016-08-31 14:13 +0200 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <nq6hm1$2it$1@news.albasani.net> |
| In reply to | #35517 |
If cache[idx] can be invalidated by another thread
by setting cache[idx]=null then your code is wrong.
> synchronized(lock) {
> if (caches[idx] == null)
> caches[idx] = new Cache(idx);
> }
/* here is a problem other thread could interfer */
> caches[idx].useTheCache();
After the synchronized block you might get a null
pointer error. Correct code would be:
Cache cache;
synchronized(lock) {
cache = caches[idx];
if (cache == null)
cache = new Cache(idx);
caches[idx] = cache.
}
}
cache.useTheCache();
In my case I have invalidation by another thread.
See also my answer to Andreas Leitgeb.
Eric Sosman schrieb:
> On 8/30/2016 7:45 PM, 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
>
> Even if new Cache(idx) is cheap, there might be trouble
> if different threads use different Cache instances instead
> of sharing just one.
>
>> What should be done?
>
> synchronized(cache) {
> if (cache[idx] == null)
> cache[idx] = new Cache(idx);
> }
> cache[idx].useTheCache();
>
> Fancier schemes exist, but I would suggest you not bother with
> them until and unless the above simple approach proves inadequate.
> If actual measurement shows that you need something else, *then*
> it will be time to consider alternatives.
>
[toc] | [prev] | [next] | [standalone]
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Date | 2016-08-31 12:55 -0400 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <nq725j$jg2$1@dont-email.me> |
| In reply to | #35520 |
On 8/31/2016 8:13 AM, j4n bur53 wrote:
> If cache[idx] can be invalidated by another thread
> by setting cache[idx]=null then your code is wrong.
>
>> synchronized(lock) {
>> if (caches[idx] == null)
>> caches[idx] = new Cache(idx);
>> }
> /* here is a problem other thread could interfer */
>> caches[idx].useTheCache();
>
> After the synchronized block you might get a null
> pointer error. Correct code would be:
>
> Cache cache;
> synchronized(lock) {
> cache = caches[idx];
> if (cache == null)
> cache = new Cache(idx);
> caches[idx] = cache.
> }
> }
> cache.useTheCache();
Okay; your post didn't mention nulling of caches[] elements
as a consideration. (Note that if another thread sets "caches"
itself to null -- or "lock" or "idx", for that matter -- both
code versions are in trouble.)
> In my case I have invalidation by another thread.
This seems a peculiar way to invalidate a cache. Observe that
even after thread T1 sets caches[idx] = null, threads T2,T3,...
may still be using the old, stale Cache instance. Normally, one
would have a cache.invalidate() method, or something like it: Keep
the Cache object, but tell it to adjust its own state.
--
esosman@comcast-dot-net.invalid
The Tooth Fairy has gone high-tech, now pays in Bitecoin.
[toc] | [prev] | [next] | [standalone]
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Date | 2016-08-31 07:54 -0400 |
| Subject | Re: I dont see a deadlock (Re: Library for Escalable Locks, Slimmest API?) |
| Message-ID | <nq6gia$l2v$1@dont-email.me> |
| In reply to | #35498 |
On 8/30/2016 7:23 PM, j4n bur53 wrote:
> 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.
Drop-and-reacquire is not what is usually meant by
"escalation" or "upgrade" of a read/write lock. You can
do drop-and-reacquire with the locks already provided in
Java; no new development needed.
The usual intent in "upgrading" a lock from read (shared)
to write (exclusive) is to do so *without* releasing the lock,
so the state of the protected resource does not change during
the upgrade. With drop-and-reacquire, the state may change in
the interval while the lock is not held.
--
esosman@comcast-dot-net.invalid
The Tooth Fairy has gone high-tech, now pays in Bitecoin.
[toc] | [prev] | [standalone]
Page 3 of 3 — ← Prev page 1 2 [3]
Back to top | Article view | comp.lang.java.programmer
csiph-web