COP 4600 Santa Threading

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 14 + 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:

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:

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:

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 Santas 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:

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:

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

Step 0 Starter Code

Elf.java

import java.util.Random;

public class Elf implements Runnable {

enum ElfState {
WORKING, TROUBLE, AT_SANTAS_DOOR
};

private ElfState state;
/**
* The number associated with the Elf
*/
private int number;
private Random rand = new Random();
private SantaScenario scenario;

public Elf(int number, SantaScenario scenario) {
this.number = number;
this.scenario = scenario;
this.state = ElfState.WORKING;
}


public ElfState getState() {
return state;
}

/**
* Santa might call this function to fix the trouble
* @param state
*/
public void setState(ElfState state) {
this.state = state;
}


@Override
public void run() {
while (true) {
// wait a day
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
switch (state) {
case WORKING: {
// at each day, there is a 1% chance that an elf runs into
// trouble.
if (rand.nextDouble() < 0.01) {
state = ElfState.TROUBLE;
}
break;
}
case TROUBLE:
// FIXME: if possible, move to Santa's door
break;
case AT_SANTAS_DOOR:
// FIXME: if feasible, wake up Santa
break;
}
}
}

/**
* Report about my state
*/
public void report() {
System.out.println("Elf " + number + " : " + state);
}

}

Reindeer.java

import java.util.Random;


public class Reindeer implements Runnable {

public enum ReindeerState {AT_BEACH, AT_WARMING_SHED, AT_THE_SLEIGH};
private ReindeerState state;
private SantaScenario scenario;
private Random rand = new Random();

/**
* The number associated with the reindeer
*/
private int number;

public Reindeer(int number, SantaScenario scenario) {
this.number = number;
this.scenario = scenario;
this.state = ReindeerState.AT_BEACH;
}

@Override
public void run() {
while(true) {
// wait a day
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
// see what we need to do:
switch(state) {
case AT_BEACH: { // if it is December, the reindeer might think about returning from the beach
if (scenario.isDecember) {
if (rand.nextDouble() < 0.1) {
state = ReindeerState.AT_WARMING_SHED;
}
}
break;
}
case AT_WARMING_SHED:
// if all the reindeer are home, wake up santa
break;
case AT_THE_SLEIGH:
// keep pulling
break;
}
}
};

/**
* Report about my state
*/
public void report() {
System.out.println("Reindeer " + number + " : " + state);
}

}

Santa.java

//import com.sun.org.apache.xml.internal.security.utils.HelperNodeList;


public class Santa implements Runnable {

enum SantaState {SLEEPING, READY_FOR_CHRISTMAS, WOKEN_UP_BY_ELVES, WOKEN_UP_BY_REINDEER};
private SantaState state;

public Santa(SantaScenario scenario) {
this.state = SantaState.SLEEPING;
}


@Override
public void run() {
while(true) {
// wait a day...
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
switch(state) {
case SLEEPING: // if sleeping, continue to sleep
break;
case WOKEN_UP_BY_ELVES:
// FIXME: help the elves who are at the door and go back to sleep
break;
case WOKEN_UP_BY_REINDEER:
// FIXME: assemble the reindeer to the sleigh then change state to ready
break;
case READY_FOR_CHRISTMAS: // nothing more to be done
break;
}
}
}


/**
* Report about my state
*/
public void report() {
System.out.println("Santa : " + state);
}
}

SantaScenario.java

import java.util.ArrayList;
import java.util.List;



public class SantaScenario {

public Santa santa;
public List< Elf> elves;
public List< Reindeer> reindeers;
public boolean isDecember;

public static void main(String args[]) {
SantaScenario scenario = new SantaScenario();
scenario.isDecember = false;
// create the participants
// Santa
scenario.santa = new Santa(scenario);
Thread th = new Thread(scenario.santa);
th.start();
// The elves: in this case: 10
scenario.elves = new ArrayList< >();
for(int i = 0; i != 10; i++) {
Elf elf = new Elf(i+1, scenario);
scenario.elves.add(elf);
th = new Thread(elf);
th.start();
}
// The reindeer: in this case: 9
scenario.reindeers = new ArrayList< >();
for(int i=0; i != 9; i++) {
Reindeer reindeer = new Reindeer(i+1, scenario);
scenario.reindeers.add(reindeer);
th = new Thread(reindeer);
th.start();
}
// now, start the passing of time
for(int day = 1; day < 500; day++) {
// wait a day
try {
Thread.sleep(100);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
// turn on December
if (day > (365 - 31)) {
scenario.isDecember = true;
}
// print out the state:
System.out.println("*********** Day " + day + " *************************");
scenario.santa.report();
for(Elf elf: scenario.elves) {
elf.report();
}
for(Reindeer reindeer: scenario.reindeers) {
reindeer.report();
}
}
}



}