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

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

Re: Library for Escalable Locks, Slimmest API?

Show all headers | View raw

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

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