Where is deadlock

[puzzlecracker]

This example is taken from Java Concurrency in Practice. I am not sure
I see the deadlock. I also have a few follow up questions about the
classes commented


class Taxi
{
@GuardedBy("this") private Point location, destination; // what
is the story with @GuardedBy("this")

private final Dispatcher dispatcher; //does final here mean that
it can only be assigned once in a constructor only?

public Taxy (Dispatcher dispatcher)
{
this.dispatcher=dispatcher;
}

public synchronized Point GetLocation(){ return location;}

public synchronized void setLocation(Point location)
{
this.location=location;
if(location.equals(destination))
despatcher.notifyAvailable(this);
}
}

class Dispatcher
{
@GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;

public Dispatcher()
{
taxis=new HashSet<Taxi>();
availableTaxis=new HashSet<Taxi>();
}
public synchronize void notifyAvailable(Taxi taxi)
{
avaliableTaxis.add(taxi);
}
public synchronize Image GetImage()
{
Image image=new Image();
for(Taxi t:taxis)
image.drawMaker(t.getLocation);
return Image;
}
}

Ask me if anything needs a clarification.

Thanks.

 

[Mark Space]

class Taxi
{
public synchronized void setLocation(Point location)
{
this.location=location;
if(location.equals(destination))
despatcher.notifyAvailable(this);

Here and ...

class Dispatcher
{
public synchronize Image GetImage()
{
Image image=new Image();
for(Taxi t:taxis)
image.drawMaker(t.getLocation);

here.

Thread A calls getImage(), meanwhile thread B calls setLocation(). Boom.

 

[Lew]

This example is taken from Java Concurrency in Practice. I am not sure
I see the deadlock. I also have a few follow up questions about the
classes commented

Section 10.1.3 explains how the deadlock can occur:
"While no method /explicitly/ acquires two locks, callers of setLocation and
getImage can acquire two locks just the same. If a thread calls setLocation
in response to an update from a GPS receiver, it first updates the taxi's
location and then checks to see if it has reached its destination. If it has,
it informs the dispatcher that it needs a new destination. Since both
setLocation and notifyAvailable are synchronized, the thread calling
setLocation acquires the Taxi lock and then the Dispatcher lock. Similarly, a
thread calling getImage acquires the Dispatcher lock and then each Taxi lock
(one at a time). Just as in LeftRightDeadlock, two locks are acquired by two
threads in different orders, risking deadlock."
/Java Concurrency in Practice/, Brian Goetz, et al., Addison Wesley, 2006.

class Taxi
{
@GuardedBy("this") private Point location, destination; // what
is the story with @GuardedBy("this")

Explained in the book. It's an annotation to show what lock a synchronized
block uses. (/op.cit./, Appendix A.)

private final Dispatcher dispatcher; //does final here mean that
it can only be assigned once in a constructor only?

JLS ss. 8.3.1.2

public Taxy (Dispatcher dispatcher)
"Taxi"

{
this.dispatcher=dispatcher;
}

public synchronized Point GetLocation(){ return location;}

"getLocation", and the body is on its own lines.

public synchronized void setLocation(Point location)
{
this.location=location;
if(location.equals(destination))
despatcher.notifyAvailable(this);
"dispatcher"

}
}

class Dispatcher
{
@GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;

public Dispatcher()
{
taxis=new HashSet<Taxi>();
availableTaxis=new HashSet<Taxi>();
}
public synchronize void notifyAvailable(Taxi taxi)
{
avaliableTaxis.add(taxi);
"availableTaxis"

}
public synchronize Image GetImage()

"synchronized" and "getImage"

 

[Lew]

Frankly, it seems as
though either you've missed something in the text, or it's not a very
good text. Having an example of deadlock without _explaining_ the
deadlock, and without showing an alternative implementation that doesn't
have the deadlock, that doesn't seem like a great way to write about
deadlock.

The book explains in detail where the deadlock can occur, and is quite clear.

 

[Mark Space]

though either you've missed something in the text, or it's not a very
good text. Having an example of deadlock without _explaining_ the
deadlock, and without showing an alternative implementation that doesn't
have the deadlock, that doesn't seem like a great way to write about
deadlock.

He missed it. Java Concurrency in Practice is excellent. I pulled my
copy off the shelf just to check it.

"While no method explicitly acquires two locks, callers of setLocation
and getImage can acquire two locks just the same. If a thread calls
setLocation in response to an update from a GPS receiver, it first
updates the taxi's location and then checks to see if it has reached
it's destination. If it has, it informs the dispatchers that it needs a
new destination. Since both setLocation and notifyAvailable are
synchronized, the thread calling setLocation acquires the Taxi lock and
then the Dispatcher lock. Similarly, a thread calling getImage acquires
the Dispather lock and then the Taxi lock (one at a time). Just as in
LefRightDeadlock, two locks are acquired by two threads in different
orders, risking deadlock.

It was easy to spot the deadlock possibility in LeftRightDeadlock or
transferMoney by looking for methods that acquire two locks. Spotting
the deadlock possibility in Taxi and Dispatcher is a little harder: the
warning sign is that an alien method (defined on page 40) is being
called while holding a lock."

Section 10.1.3, second paragraph. Page 211 in my copy.

 

[Lew]

" [...] Just as in LefRightDeadlock, two locks are acquired by two
threads in different orders, risking deadlock.

Two great minds with the same quote.

 

[Lew]

" [...] Just as in LefRightDeadlock, two locks are acquired by two
threads in different orders, risking deadlock.

Two great minds with the same quote.

Well, almost. The quote had all the words spelled correctly in your
post.

It took several reviews to avoid mistakes and I still wasn't convinced I'd
caught them all. I made several in the transcription. Indeed, until you
pointed it out I hadn't even noticed any errors in Mark Space's transcription.

There's an existential question about whether the sameness of the quote
depends on the accuracy of the transcription.

More importantly, all the words are spelled correctly in the book itself, and
even more importantly, the concepts are spelled out very clearly in the book.

I've been through /Java Concurrency in Practice/ once so far, front to back,
and while it really helped my knowledge, its primary effects have been to let
me know how very careful I must be with concurrency issues, how far from
expert I still am in the matter, and how it will take continuous education for
me to gain that expertise, probably for the remainder of my programming career.

Already it's helped me in my projects, where concurrency issues are a major
focus of attention both for correctness and scalability of the applications.

 

[Mark Space]

" [...] Just as in LefRightDeadlock, two locks are acquired by two
threads in different orders, risking deadlock.

Two great minds with the same quote.

Well, almost. The quote had all the words spelled correctly in your
post.

I check my post twice, but obviously that wasn't enough. Oh well,
hopefully it didn't detract too much from the explanation.