Michael Brudno
Lecture Notes for 7/11

Consider the following  List of StuffToDo, called a WorkList. This is a List of different tasks. We will have some people inserting StuffToDo into this list, while others are removing and actually doingthe stuff. The definitions are:

class WorkListItem {
    StuffToDo item;
    WorkListItem next;
    WorkListItem(StuffToDo item0, WorkListItem next0) {... }
}

class WorkList {
    private WorkListItem first, last;
    void addWork(StuffToDo x) {
        if (first == null)
             first = last = new WorkListItem(x, null);
        else
              last = last.next = new WorkListItem(x, null);    //(1)
    }

    StuffToDo getWork(StuffToDo x) {
        if (first == null)
            return null;
        StuffToDo result = first.item;
        first = first.next;  // (2)
        return result;
   }
}
 

The method addWork adds another element to the end of the list, while  getWork returns the first element. which we have to do. Draw the box & pointers to make sure this works!

Allright, looks ok, but it has a couple of problems. The first is that if we have nothing to do, the person asking for work is getting null back. What is he to do? Ask for work again & again & again? Then he is wasting CPU cycles. Just sleep for a while and then ask again? Then the work may not be done quickly enough.

The second problem is even more important. What happens if we have one element in the list, and while we are taking it out (in the middle of statement 2) Someone else tries to put one in (using statement 1).  Just as we add an element to the end of last, first goes to null, and the computer will from now on think that the list has no elemnts, while it has one: an element is lost, something won't be done. So now we need to solve the two problems. The solution to the first is quite trivial: we put synchronized in the method headers, thus not allowing one of them to run while the other one is running. The second one requires a bit more ingenuity: we need to have getwork wait until there is more work, and addwork notify one of the threads waiting by using the notify() method. The final solution is:

class WorkList {
    private WorkListItem first, last;
    synchronized void addWork(StuffToDo x) {
        if (first == null)
             first = last = new WorkListItem(x, null);
        else
              last = last.next = new WorkListItem(x, null);
        notify();
    }

    synchronized StuffToDo getWork(StuffToDo x) {
        while (first == null)
        try {
            wait();
          }
         catch(InterruptedException e) {
            return null;   //Something went wrong, so just return null to indicate this
        }
        StuffToDo result = first.item;
        first = first.next;  // (2)
        return result;
   }
}

The reason we use notify() rather than notifyAll() is that we only need to tell one of the workers that there is a new thing to do in the list, we don't have to tell all of them and then have them fight for the work.