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
In article <···············@lostwithiel.tfeb.org>,
Tim Bradshaw <···@tfeb.org> wrote:
> 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.
Andrew Cooke <······@andrewcooke.free-online.co.uk> wrote:
> In article <···············@lostwithiel.tfeb.org>,
> Tim Bradshaw <···@tfeb.org> wrote:
> > 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
···············@acm.org
http://www.schuerig.de/michael/
Tim Bradshaw <···@tfeb.org> writes:
> [...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.html
The `monitorenter' instruction:
http://java.sun.com/docs/books/vmspec/2nd-edition/html/Instructions2.doc9.html#monitorenter
The `monitorexit' instruction:
http://java.sun.com/docs/books/vmspec/2nd-edition/html/Instructions2.doc9.html#monitorexit
An example of a compiled `synchronized' statement:
http://java.sun.com/docs/books/vmspec/2nd-edition/html/Compiling.doc.html#13808
--
Samir Barjoud
·····@mindspring.com
Samir Barjoud <·····@mindspring.com> writes:
> Tim Bradshaw <···@tfeb.org> writes:
> > [...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:
@Article{Bacon:1998:TLF,
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.",
}
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.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
* Samir Barjoud wrote:
> 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