A well-known concurrency problem known as Santa Claus problem is originally attr

Question

A well-known concurrency problem known as Santa Claus problem is originally attributed to Trono1. The original problem definition is as follows: Santa Claus sleeps in his shop up at the North Pole, and can only be wakened by either all nine reindeer being back from their year long vacation on the beaches of some tropical island in the South Pacific, or by some elves who are having some difficulties making the toys. One elf's problem is never serious enough to wake up Santa (otherwise, he may never get any sleep), so, the elves visit Santa in a group of three. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop's door, along with the last reindeer having come back from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready as soon as possible. (It is assumed that the reindeer don't want to leave the tropics, and therefore they stay there until the last possible moment. They might not even come back, but since Santa is footing the bill for their year in paradise ... This could also explain the quickness in their delivering of presents, since the reindeer can't wait to get back to where it is warm.) The penalty for the last reindeer to arrive is that it must get Santa while the others wait in a warming hut before being harnessed to the sleigh. Simplified Santa & the Reindeer Problem In this simplified version, there are no elves at all. Santa sleeps till the last of the nine reindeers arrives. Santa and the reindeers are simulated by processes executing the following logic:

Santa

Forever Do {
Sleep till all 9 reindeers have arrived from the tropics; Harness all reindeers to the sleigh;
Shout “Ho Ho Ho, Let’s Distribute Toys” ;
Pilot the flying sleigh;
Come back after Christmas;
Thanks the reindeers and set them all free;

}

Reindeer( int id )

Forever Do {
Enjoy some time at the tropics;
Travel to the North Pole;
IF (I am not the last of 9 reindeers) THEN

Wait in the Warm Hut; ELSE

Discharge previously waiting reindeers from the Warm Hut;

Wake-up Santa;
Wait for Santa to shout “Ho Ho Ho, Let’s Distribute Toys” ; Fly with Santa;
Come back after Christmas;
Wait to be set free by Santa ;

}

-------------

Write pseudo-code for the Santa and the Reindeer processes using any needed semaphores and shared data so that these processes execute in synchronization as described earlier. Define the required semaphores and shared data at the beginning of your solution.

Explanation / Answer

Using semaphore it is difficult to solve the problem sice it assumes that assumes that "a process released from waiting on a semaphore will necessarily be scheduled for execution".
let us add a set of messages that can be reported by Santa, the Elves, and the Reindeer.
Each message is an indication of the state of a particular entity: Santa, an Elf, or a Reindeer.
The union set of these messages,S
Let SR be the subset of S that includes the set of messages that the Reindeer can print and that Santa can print while dealing with the Reindeer. We define here a message ordering on SR, and by the transitivity property we get a complete ordering on SR:

1. Reindeer < id >: on holiday . . . wish you were here, :)
2. Reindeer < id >: back from holiday . . . ready for work, :(
3. Santa: Ho-ho-ho . . . the reindeer are back!
4. Santa: harnessing reindeer < id > . . .
5. Santa: mush mush . . .
6. Reindeer < id >: delivering toys
7. Santa: woah . . . we’re back home!
8. Reindeer: < id >: all toys delivered
9. Santa: un-harnessing reindeer < id > . . .

Let SL be the subset of S that includes the set of messages that the Elves can print and
that Santa can print while dealing with the Elves. We define here a message ordering on SL,
and by the transitivity property we get a complete ordering on SL:
1. Elf < id >: need to consult santa, :(
2. Santa: Ho-ho-ho . . . some elves are here!
3. Santa: hello elf < id > . . .
4. Elf < id >: about these toys . . . ???
5. Santa: consulting with elves . . .
6. Santa: OK, all done - thanks!
7. Elf < id >: OK . . . we’ll build it
8. Santa: goodbye elf < id > . . .
9. Elf < id >: working, :)

using java threads :

// notify elves of "OK" message
try {
m_elfBarrierTwo.await();
}
catch (InterruptedException e) {
e.printStackTrace();
}
catch (BrokenBarrierException e) {
e.printStackTrace();
}
// wait for elves to say "ok we’ll build it"
try {
m_elfBarrierThree.await();
}
catch ... // exception handling logic
And the corresponding Elf code:
// wait for santa to say "ok all done"
try {
m_elfBarrierTwo.await();
}
catch ... // exception handling logic
System.out.println("Elf " + this + ": OK ... we’ll build it ");
// notify santa of "ok" message
try {
m_elfBarrierThree.await();
}
catch ... // exception handling logic

santa query o elves and reindeer in case of missing notifications
if (elfQueue.size() % 3 == 0) {
synchronized (m_santaLock) {
m_santaLock.notify();
notifiedCount++;
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.