`synchronized' in java and Lisp 
Author Message
 `synchronized' in java and Lisp

I have a macro which implements critical sections for CL (it's
obviously not quite portable, but it's pretty easy to make work
anywhere that has locks):

        (synchronized
          ...
          ...)

makes sure that only one thread executes the body at once.

I was looking at the Java locking stuff (which was where I got the
name `synchronized' from in the first place), and they seem to have
a thing that looks superficially quite nice.  As I understand it, for
any object A you can say:

        synchronized (A) { ... }

which makes sure that only one person is doing things to A at once.

I thought about how to do this in CL, and it seems to me to be a
serious horror case:

        Either every object has a lock, which would work OK, but bloat
        everything.  (In CL you could obviously do a hack solution
        where only some classes where lockable with a LOCK-MIXIN
        class, but Java can't really do that as it doesn't have
        multiple inheritance so you'd end up with multiple pll class
        hierarchies.)

        Or objects don't have locks, but they can grow them on demand,
        probably by being associated with a lock in a hashtable.
        However for this to work the hashtable has to be protected by
        a lock, which needs to be grabbed and released, probably
        twice, every time you say `synchronized' (grab global lock,
        possibly create lock for object, grab lock for object, release
        global lock ... grab global lock, release object lock, release
        global lock).  You need weak hashtables for this as well.
        That sounds like horrible if you want it to scale.

Does anyone know how Java does this?  The book I have gives no real
details unfortunately.

--tim



Fri, 26 Apr 2002 03:00:00 GMT  
 `synchronized' in java and Lisp


Quote:
> I was looking at the Java locking stuff (which was where I got the
> name `synchronized' from in the first place), and they seem to have
> a thing that looks superficially quite nice.  As I understand it, for
> any object A you can say:

>    synchronized (A) { ... }

> which makes sure that only one person is doing things to A at once.

> I thought about how to do this in CL, and it seems to me to be a
> serious horror case:

I can't help, but Lee's book on Concurrency in Java might be worth
looking at (although I don't remember it going into implementation
details).

Also, are you aware of the Occam/CSP way of doing things?  I have never
used Occan, and never finished Hoare's book, but the papers I've read
from http://archive.comlab.ox.ac.uk/csp.html made me wish we'd known of
this work before writing a lot of code in Java using the "traditional"
support it provides.

Andrew
http://www.andrewcooke.free-online.co.uk/andrew/writing/compjava.html#th
reads <- a more enthusiastic version of this post!

Sent via Deja.com http://www.deja.com/
Before you buy.



Fri, 26 Apr 2002 03:00:00 GMT  
 `synchronized' in java and Lisp

Quote:

> [...locking a single object...]

> I thought about how to do this in CL, and it seems to me to be a
> serious horror case:

>    Either every object has a lock, which would work OK, but bloat
>    everything.  (In CL you could obviously do a hack solution
>    where only some classes where lockable with a LOCK-MIXIN
>    class, but Java can't really do that as it doesn't have
>    multiple inheritance so you'd end up with multiple pll class
>    hierarchies.)

>    Or objects don't have locks, but they can grow them on demand,
>    probably by being associated with a lock in a hashtable.
>    However for this to work the hashtable has to be protected by
>    a lock, which needs to be grabbed and released, probably
>    twice, every time you say `synchronized' (grab global lock,
>    possibly create lock for object, grab lock for object, release
>    global lock ... grab global lock, release object lock, release
>    global lock).  You need weak hashtables for this as well.
>    That sounds like horrible if you want it to scale.

> Does anyone know how Java does this?  The book I have gives no real
> details unfortunately.

Java does it like that.  Every object has a monitor associated with
it.  Whether it is actually allocated as part of the object or is
allocated on demand is up to the implementation of the virtual
machine.  The monitor maintains a reference count - it represents the
times the object has been locked by the thread that initially locked
the object.  When that count is zero the object is available for
locking.

I don't think you need weak hashtables.  The UNWIND-PROTECT within
SYNCHRONIZED should take care of REMHASHing the monitor when it is no
longer needed.

Some URLS follow.

The Java Virtual Machine Specification:

http://java.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc....

The `monitorenter' instruction:

http://java.sun.com/docs/books/vmspec/2nd-edition/html/Instructions2....

The `monitorexit' instruction:

http://java.sun.com/docs/books/vmspec/2nd-edition/html/Instructions2....

An example of a compiled `synchronized' statement:

http://java.sun.com/docs/books/vmspec/2nd-edition/html/Compiling.doc....

--
Samir Barjoud



Fri, 26 Apr 2002 03:00:00 GMT  
 `synchronized' in java and Lisp

Quote:



> > I was looking at the Java locking stuff (which was where I got the
> > name `synchronized' from in the first place), and they seem to have
> > a thing that looks superficially quite nice.  As I understand it, for
> > any object A you can say:

> >     synchronized (A) { ... }

> > which makes sure that only one person is doing things to A at once.

> > I thought about how to do this in CL, and it seems to me to be a
> > serious horror case:

> I can't help, but Lee's book on Concurrency in Java might be worth
> looking at (although I don't remember it going into implementation
> details).

That is

Doug Lea
Concurrent Programming in Java
Addison-Wesley 1996

See Doug's web site at <http://g.oswego.edu/dl/> as well.

Michael

--
Michael Schuerig

http://www.schuerig.de/michael/



Fri, 26 Apr 2002 03:00:00 GMT  
 `synchronized' in java and Lisp

Quote:


> > [...locking a single object...]

> > I thought about how to do this in CL, and it seems to me to be a
> > serious horror case:

[...]

> > Does anyone know how Java does this?  The book I have gives no real
> > details unfortunately.

> Java does it like that.  Every object has a monitor associated with
> it.  Whether it is actually allocated as part of the object or is
> allocated on demand is up to the implementation of the virtual
> machine.  The monitor maintains a reference count - it represents the
> times the object has been locked by the thread that initially locked
> the object.  When that count is zero the object is available for
> locking.

It also seems to me that this particular feature of Java is causing a
bit of a headache to implementors.  It is complicated by the fact that
the Java libraries are thread-safe, and therefore locking performance
is also impacting single-threaded applications.

An interesting research paper, which not only describes the problems
and usual implementation techniques but also a new approach to deal
with this problem is:

  author =       "David F. Bacon and Ravi Konuru and Chet Murthy and
                 Mauricio Serrano",
  title =        "Thin Locks: Featherweight Synchronization for {Java}",
  journal =      "ACM SIG{\-}PLAN Notices",
  volume =       "33",
  number =       "5",
  pages =        "258--268",
  month =        may,
  year =         "1998",
  coden =        "SINODQ",
  ISBN =         "0-89791-987-4",
  ISSN =         "0362-1340",
  bibdate =      "Thu May 13 12:37:28 MDT 1999",
  url =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/277650/p258-bacon/",
  acknowledgement = ack-nhfb,
  annote =       "Published as part of the Proceedings of PLDI'98.",
  keywords =     "algorithms; languages; measurement; performance",
  subject =      "{\bf D.3.2} Software, PROGRAMMING LANGUAGES, Language
                 Classifications, Java. {\bf D.2.8} Software, SOFTWARE
                 ENGINEERING, Metrics, Performance measures. {\bf D.4.0}
                 Software, OPERATING SYSTEMS, General, AIX.",
  abstract =     "Language-supported synchronization is a source of
                  serious performance problems in many Java programs.
                  Even single-threaded applications may spend up to half
                  their time performing useless synchronization due to the
                  thread-safe nature of the Java libraries.  We solve this
                  performance problem with a new algorithm that allows
                  lock and unlock operations to be performed with only a
                  few machine instructions in the most common cases.  Our
                  locks only require a partial word per object, and were
                  implemented without increasing object size.  We present
                  measurements from our implementation in the JDK 1.1.2
                  for AIX, demonstrating speedups of up to a factor of 5
                  in micro-benchmarks and up to a factor of 1.7 in real
                  programs.",

Quote:
}

This paper is available in the usual ways from ACM, e.g. from their
Digital Library if you are a subscriber to the DL.

Regs, Pierre.

--

  "One smaller motivation which, in part, stems from altruism is Microsoft-
   bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]



Fri, 26 Apr 2002 03:00:00 GMT  
 `synchronized' in java and Lisp

Quote:

> I don't think you need weak hashtables.  The UNWIND-PROTECT within
> SYNCHRONIZED should take care of REMHASHing the monitor when it is no
> longer needed.

That's true of course, but I think it doubles the number of global
lock/unlocks you need.  I hadn't thought of this yesterday, but if the
hashtable is weak then the synchronized macro can find/allocate the
lock just once (requiring a global lock): it doesn't then need to get
at the table again to release the lock.  Still sounds like a major
pain to me, I think the slot-per-object approach must be better.

Thanks for the pointers.

--tim



Sat, 27 Apr 2002 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. Any way to synchronize functions in lisp?

2. Java Integration with Lisp using Corman Lisp

3. Java in frame can't get instance of Java EAI + VRML in another frame

4. Running Koza's GP1 Lisp code on Common Lisp

5. why we aren't using lisp (was New to Lisp)

6. Parsers for Lisp - was: I don't understand Lisp

7. Running Koza's GP1 Lisp code on Common Lisp

8. Smalltalk 'perform:' in Java

9. Maritz: Why Microsoft won't ship Sun's Java Class Libraries

10. Equivalent of Java 'throws'

11. JPython/imported java class 'instanceof'

12. Date manipulation and Java 'interface' equivalents

 

 
Powered by phpBB® Forum Software