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
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."
is replaced bywhile (condition) wait();
Describe a situation in which this problem occurs.if (condition) wait();
Can the same problem happen with this code? Why or why not?... 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); }
static void m(Vector v) { synchronized (v) { i = 3; return v.elementAt(i); } }
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.