SE 552: Homework

Deadline: 5.30pm, Tuesday May 18, 2004

Homework

This week's homework is to provide an optimistic implementation of mutable lists.

Download the source archive, and compile ajeffrey.teaching.test.TestMutableList, then run it with some command-line arguments, for example:

  java ajeffrey.teaching.test.TestMutableList fred barney wilma betty

The program should print the arguments out in some random order:

Got: barney
Got: betty
Got: wilma
Got: fred

The implementation of MutableList is thread-safe and uses a pessimistic implementation. You should write a new class OptimisticMutableList which uses an optimistic strategy for thread-safe mutable lists.

The optimistic implementation is given by using a commitment protocol, and only using locks in the commit method. You should use randomized bounded exponential backoff to deal with conflict, with inital delay 1 millisecond, and maximum delay 1 second.

(A reminder: for exponential backoff, each time you retry you delay by some amount, which doubles at every retry. For bounded backoff, you put some cap on the delay. For randomized delay, you multiply the delay amount by a random number to avoid lockstep behaviour.)

Submit OptimisticMutableList.java, and any other files you have edited, as a zip archive using Courses OnLine.

Reading

Lea Chapter 3.