scala notify() vs notifyAll()

Question

Given the following implementation of the producer-consumer problem in scala

class PC {
  var buffer = null.asInstanceOf[Int]
  var set = false

  def produce(value: Int) = synchronized {
    while (set) wait()
    buffer = value
    set = true
    notify() }

  def consume: Int = synchronized {
    while (!set) wait()
    val result = buffer
    set = false
    notify()
    return result; }
}

There are 3 things I don't quite manage to see:

1. Why, if I'm using notify instead of notifyAll, I end up in deadlock; Where should I use notifyAll, for in produce or consume?

2. Shouldn't I have an object e.g. lock, and call lock.synchronized, lock.wait and lock.notify? Why does it work like this, don't produce and consume have 2 different monitors associated? Why does 'notify' from produce notifies 'wait' from consume?

3. How does a monitor work exactly in scala (in our case)? Does it use a signal-and-continue policy? how do processes from a waiting queue on a certain condition get moved to a runnable queue? Is there a queue for each condition/lock (e.g. lock1.wait, lock2.wait, etc).

Answer 1

This is really a question mostly about Java concurrency. Scala concurrency is built on top of the Java concurrency model, but the syntax differs. In Scala, synchronized is a method of AnyRef, and the above syntax is equivalent to using the keyword synchronized to write synchronized methods as in the following Java code:

public class PC {
  public int buffer;
  public boolean set;
  public synchronized void produce(int value) { 
    while(set) wait();
    buffer = value;
    set = true;
    notify(); 
  }
  public synchronized int def consume { 
    while(!set) wait();
    int result = buffer;
    notify();
    return result; 
  }
}

For more detailed coverage of the Java concurrency model, peruse the Java Tutorials. You may want to investigate the Java Concurrency Library. For instance, you could implement the same thing using a Blocking Queue with a capacity of 1.

In answer to your questions:

1. Why, if I'm using notify instead of notifyAll, I end up in deadlock; Where should I use notifyAll, for in produce or consume?

You probably have a race condition (rather than a deadlock) because the notify() in the consumer() is received by some other consumer thread, rather than the producer thread, but that's just a guess. As far as whether to use notify() or notifyAll() and in which methods, some recommend that notifyAll() always be used. And, in this case, you can use notifyAll(), because you are waiting in a conditional while loop -- which you should always do for various reasons described in the documentation of wait(). However, you could also choose to use notify() as an optimization in the producer(), because I'm assuming you only want one consumer to consume the buffer contents. With the current implementation, you must still use notifyAll() in consume() or potentially expose yourself to a situation where one of the consumers is notified rather than the single waiting producer resulting in the producer waiting forever.

2. Shouldn't I have an object e.g. lock, and call lock.synchronized, lock.wait and lock.notify? Why does it work like this, don't produce and consume have 2 different monitors associated? Why does 'notify' from produce notifies 'wait' from consume?

You do have a lock. It's an implicit lock on the PC instance and in Java there's one and only one monitor per object although there may be many entry points. The wait() in consume() is notified by the notify() in produce(), because they are both waiting for a lock on the same resource -- the PC instance. If you want to implement more flexible or finer-grained locking, then you can use various strategies from the the Java Concurrency Library such as Locks.

3. How does a monitor work exactly in scala (in our case)? Does it use a signal-and-continue policy? how do processes from a waiting queue on a certain condition get moved to a runnable queue? Is there a queue for each condition/lock (e.g. lock1.wait, lock2.wait, etc).

For a good description of how the JVM performs thread synchronization, read this: How the Java virtual machine performs thread synchronization. For bit more detail from a chapter from the same author, you can read Inside the Java Virtual Machine.

Answer 2

Why, if I'm using notify instead of notifyAll, I end up in deadlock?

As you may have observed, the problem you are witnessing does not occur if there is only one producer and one consumer (because in that case, notify does the job you expect it to do, which is to let the next producer/consumer make its move).

If you have more than one producer or consumer however, the following problem occurs: Lets say there are 2 producers and a single consumer. In this scenario, the following is bound to happen if you use notify():

1. One of the producers runs, and calls notify()
2. Instead of the consumer, the other producer is notified
3. The producer awoken by notify() now waits infinitely, because the consumer will never get notified

If notifyAll is called instead, there will always be a consumer which gets notified, thus the problem that a producer or consumer waits indefinitely for the other party neverr arises.

Shouldn't I have an object e.g. lock, and call lock.synchronized, lock.wait and lock.notify?

Your lock object is the PC object. A Scala object is simply a singleton instance of a class which the compiler generates for you. Since your object is actually a class instance of the class Object, it also inherits its notify, notifyAll and wait methods.