Date: Tue, 14 Jan 1997 22:48:23 GMT Server: NCSA/1.4.1 Content-type: text/html Last-modified: Wed, 06 Nov 1996 19:32:45 GMT Content-length: 4126 Programming WWW fall'96 -- Assignment #5 Programming for the World-Wide Web
Homework 5
Due November 19

You don't have to hand in any code for this assignment. Just write your answers to the following questions and mail them to the grader, Igor.

When a question asks you to describe a situation, describe in sequence the actions that one or more threads might perform. For example: "There are two threads. First, thread 1 does this. Then thread 2 does these two things. Then thread 1 does this other thing."

  1. (1 point). What can go wrong if the code
    while (condition) 
      wait();
    
    is replaced by
    if (condition) 
      wait();
    
    Describe a situation in which this problem occurs.
  2. (2 points). Here is the complete source code to Java's Vector class. Describe a situation in which the following code returns the element in position 5:
    ...
    static void m(Vector v) {
       i = 3;
      return v.elementAt(i);
    }
    
    Can the same problem happen with this code? Why or why not?
    static synchronized void m(Vector v) {
       i = 3;
      return v.elementAt(i);
    }
    
    Can the same problem happen with this code? Why or why not?
    static void m(Vector v) {
       int i = 3;
      return v.elementAt(i);
    }
    
    Can the same problem happen with this code? Why or why not?
    static void m(Vector v) {
      synchronized (v) {
         i = 3;
        return v.elementAt(i);
      }
    }
    
    
  3. (1 point). The size() method of Vector is not synchronized. Is this a bug? Why or why not? What if elementCount were a long instead of an int? If you think there is a bug, describe a situation that exhibits the bug.
  4. (1 point). Assuming that the elementAt() method were not synchronized, describe a situation where a call to it would throw an ArrayIndexOutOfBoundsException saying that the index was negative even though the index was actually positive.

  • (5 points). In the lecture, I mentioned that threads could be used to improve the latency for balanced binary tree operations by doing rebalancing in the background. Design a system for doing this. You don't have to understand balanced binary trees to do this problem; all you have to know is the following:

    A balanced binary tree is a data structure with three operations: insert, delete and lookup. Insert puts an item into the tree, delete removes an item, and lookup finds an item based on a key. Insert and delete can both result in an unbalanced tree. Such a tree still behaves correctly, but if the unbalancing becomes too severe, performance can suffer. Here are the signatures of these methods:

    public class BalancedBinaryTree {
      public synchronized void insert(String key, Object value);
      public synchronized void delete(String key);
      public synchronized Object lookup(String key);
    }
    

    In your design, insert and delete should return immediately after performing their respective operations; they should not wait around for the rebalancing to happen. Aside from that, the design is up to you. Keep in mind that there might be many threads, each of which may be using many trees.

    You should submit an English-language description of your design. Clearly specify all the relevant methods on the BalancedBinaryTree class and any other classes you might use. Don't forget to say which methods are synchronized. For each thread in your design, give an approximate priority for the thread, and say whether or not it is a daemon thread. You may supply code snippets if you wish, but you must describe everything in English -- a completely correct but uncommented implementation is worth zero. Your solution will be graded on correctness, efficiency, clarity and good object-oriented design.


    Last Updated 11/6/96