COP 4600 - Homework 4

COP 4600 - Homework 4

Total points: 6 + 1 bonus point
In this homework, you will implement a famous synchronization problem in Java. The
problem is concerned with Santa Claus, elves and reindeer.
The goal is to:
• Understand how to implement deferred termination of threads from scratch
• Learn how to use semaphores
WARNING:
This homework is not about learning functions available in the Java libraries. You will get
ZERO points if you use:
-the Java monitor based synchronization primitives (wait(), notify(), etc on the class).
-the Java thread cancellation techniques (interrupt(), InterruptedException)
The only synchronization primitive you should use is java.util.concurrent.Semaphore
and its acquire() and release() functions (which correspond to wait() and signal() in other
semaphore implementations,.
The problem:
Santa Claus sleeps in his shop at the North Pole and can only be woken by either:
• All nine reindeer being back from their vacation in the South Pacific or
• Some of the elves having difficulties making toys.
To allow Santa to get some sleep, the elves can only wake him when three of them are
having problems. When three elves are having their problems solved, any other elves
wishing to visit Santa must wait for those elves to return. It is assumed that the reindeer
do not want to leave the tropics, and therefore stay there until the last possible
moment – they only return in December. The last reindeer to arrive must get Santa
while the others wait in a warming hut before being harnessed to the sleigh.
As this is a relatively complex problem, I have decomposed it in a number of steps. You
need to submit solutions to Steps 1…4 + bonus if you choose to. The way to proceed is
to solve step n in a directory called Stepn, then copy what you have to Stepn+1, start
working on that copy etc. You will need to submit the intermediate steps as well.
Step 0:
Download the Santa.zip file from the webpage. Compile and run (the main function is in
SantaScenario.java). Study the code and the output. Notice that in many places in the
code there are FIXME comments which give you an idea of what is supposed to go
there. You might make changes in places outside the TODO and FIXME comments as
well, but try to keep it to minimum. Also note that, for the time being, there are no
semaphores or other synchronization primitives in the code.
Step 1: (1 pt)
Observe that the threads corresponding to Santa, the reindeer and the elves never
terminate. Implement a way to terminate these threads at day 370 using deferred
termination (i.e. do not kill the threads explicitly).
Note: the main thread with the counting of the days will continue, that is fine.
Step 2: (1 pt)
Starting from step 1, create a version where:
-there is no reindeer present
-as soon as an elf runs into a problem, it goes to Santa’s door
-as soon as an elf is at Santa’s door and Santa is sleeping, he wakes up Santa
-if woken up, Santa solves the problems of all elves who are at the door.
Step 3: (1 pt)
Starting from step 2, create a version where
-there is no reindeer present
-unless there are three elves which are in TROUBLE, the elves stay in TROUBLE. When
the third elf gets in TROUBLE, they go to Santa’s door.
-if there is any elf at Santa’s door, the elves who get into TROUBLE, they stay in
TROUBLE, and only go to Santa’s door when the previous elves came back.
-as soon as an elf is at Santa’s door and Santa is sleeping, he wakes up Santa
-if woken up, Santa solves the problems of the three elves who are at the door.
Step 4: (1 pt)
Now, notice that Step 3 still did not use any synchronization primitives – even when in
TROUBLE or at Santa’s door, the elf threads are spinning.
Using semaphores, create a new version starting from the code from Step 3 in such a
way that the threads of the Elves are waiting in the acquire() function of a semaphore
when they are in the TROUBLE mode.
Bonus Step 5: (1 pt - bonus)
Now, bring in the reindeers, and implement the code necessary such that:
-the first 8 reindeers to come back from BEACH stay at the WARMING_SHED.
-the reindeers in the WARMING_SHED are in the waiting in the acquire() function of a
semaphore
-the last reindeer wakes up Santa
-Santa hooks up the reindeers to the SLEIGH and wakes their thread up
What to submit:
• The code as a zipped Java code with the subdirectories: Step1, Step2, … Step5.
• A Microsoft Word file describing a journal of your work on the homework.
Include the days you worked on it, how much, the challenges you encountered,
screenshots etc.