Deadlock when calling two synchronized method

Question

class Downloader extends Thread {
    private InputStream in;
    private OutputStream out;
    private ArrayList<ProgressListener> listeners;
    public Downloader(URL url, String outputFilename) throws IOException {
        in = url.openConnection().getInputStream();
        out = new FileOutputStream(outputFilename);
        listeners = new ArrayList<ProgressListener>();
    }
    public synchronized void addListener(ProgressListener listener) {
        listeners.add(listener);
    }
    public synchronized void removeListener(ProgressListener listener) {
        listeners.remove(listener);
    }

    private synchronized void updateProgress(int n) {
        for (ProgressListener listener: listeners)
            listener.onProgress(n);
    }
    public void run() {
        int n = 0, total = 0;
        byte[] buffer = new byte[1024];
        try {
            while((n = in.read(buffer)) != -1) {
                out.write(buffer, 0, n);
                total += n;
                updateProgress(total);
            }
            out.flush();
        } catch (IOException e) { }
    }
}

The above code is from the book "seven concurrency models in seven weeks". The book says the above code is having potential for the deadlock as the the synchronized method updateProgress calls a alien method[onProgress] that might acquire another lock. Since we acquire two locks without right order, the deadlock might occur.

Can anyone explain how the deadlock happens in the above scenario?

Thanks in advance.

Answer 1

It's best to make the objects you use with synchronized private.

Since you synchronize on the Downloader, you don't know whether other threads synchronize on the Downloader too.

The following listener causes a deadlock:

MyProgressListener extends ProgressListener {

     public Downloader downloader;
     public void onProgress(int n) {
         Thread t = new Thread() {
             @Override
             public void run() {
                 synchronized(downloader) {
                     // do something ...
                 }
             }
         };
         t.start();
         t.join();
     }
}

Code that deadlocks:

Downloader d = new Downloader(...);
MyProgressListener l = new MyProgressListener();
l.downloader = d;
d.addListener(l);
d.run();

The following will happen if you run that code:

1. the main thread reaches the updateProgress and aquires a lock on the Downloader
2. the MyProgressListener's onProgress method is called and the new thread t is started
3. the main thread reaches t.join();

In this situation the main thread cannot procede until t is finished, but for t to finish, the main thread would have to release it's lock on the Downloader, but that won't happen since the main thread can't procede -> Deadlock

Answer 2

First off, recall that the keyword synchronized, when applied to a a class, implies locking the whole object this method belongs to. Now, let's sketch out another couple of objects triggering the deadlock:

class DLlistener implements ProgressListener {

  private Downloader d;

  public DLlistener(Downloader d){
      this.d = d;
      // here we innocently register ourself to the downloader: this method is synchronized
      d.addListener(this);
  }

  public void onProgress(int n){
    // this method is invoked from a synchronized call in Downloader
    // all we have to do to create a dead lock is to call another synchronized method of that same object from a different thread *while holding the lock*
    DLthread thread = new DLThread(d);
    thread.start();
    thread.join();
  }
}

// this is the other thread which will produce the deadlock
class DLThread extends Thread {
   Downloader locked;
  DLThread(Downloader d){
    locked = d;
  }
  public void run(){
    // here we create a new listener, which will register itself and generate the dead lock
    DLlistener listener(locked);
    // ...
  }
}

One way to avoid the dead lock is to postpone the work done in addListener by having internal queues of listeners waiting to be added/removed, and have Downloader taking care of those by itself periodically. This ultimately depends on Downloader.run inner working of course.

Answer 3

Probably the problem in this code:

for (ProgressListener listener: listeners)
            listener.onProgress(n);

When one thread, which holds a lock, calls an external method like this one (onProgress) then you cannot guarantee that implementation of this method won't try to obtain other lock, which could be held by different thread. This may cause a deadlock.

Answer 4

Here's a classic example that shows the kind of hard-to-debug problems the author is trying to avoid.

The class UseDownloader is created and downloadSomething is called.

As the download progresses, the onProgress method is called. Since this is called from within the synchronized block, the Downloader motinor is locked. Inside our onProgress method, we need to lock our own resource, in this case lock. So when we are trying to synchronize on lock we are holding the Downloader monitor.

If another thread has decided that the download should be canceled, it will call setCanceled. This first tests done so it synchronized on the lock monitor and then calls removeListener. But removeListener requires the Downloader lock.

This kind of deadlock can be hard to find because it doesn't happen very often.

  public static final int END_DOWNLOAD = 100;

  class UseDownloader implements ProgressListener {
    Downloader d;
    Object lock = new Object();
    boolean done = false;

    public UseDownloader(Downloader d) {
      this.d = d;
    }
    public void onProgress(int n) {
      synchronized(lock) {
        if (!done) {
          // show some progress
        }
      }
    }

    public void downloadSomething() {
      d.addListener(this);
      d.start();
    }

    public boolean setCanceled() {
      synchronized(lock) {
        if (!done) {
          done = true;
          d.removeListener(this);
        }
      }
    }
  }

Answer 5

The following example leads to a deadlock because the MyProgressListener tries to acquire the Downloader lock while it's already acquired.

class MyProgressListener extends ProgressListener {
    private Downloader myDownloader;

    public MyProgressListener(Downloader downloader) {
        myDownloader = downloader;
    }

    public void onProgress(int n) {
        // starts and waits for a thread that accesses myDownloader
    }
}

Downloader downloader = new Downloader(...);
downloader.addListener(new MyListener(downloader));
downloader.run();