Introduction

As the end of the year approaches, many people start to think of Christmas and Santa. In 1994, John Trono introduced the Santa Claus Problem to address the challenge of Santa concurrently delivering gifts when the reindeer are ready and helping the little elves when they encounter issues in the workshop.

In this blog post, we will use Scade One to solve this problem by leveraging the native and intuitive support of state machines and iterators.

We will begin by explaining the problem as stated by John Trono, then implement all the necessary elements step by step, and finally, create a small visual dashboard to run the program.

So, let’s embark on our journey to the North Pole and our quest to help Santa.

The Santa Claus Problem

The Santa Claus Problem is a synchronization problem in concurrent programming.

It involves Santa’s Team (Santa Claus🎅🏻, his elves🧝, and his reindeer🦌) and it is used to illustrate the complexities of managing multiple concurrent processes.

The problem can be described as such:

• Santa Claus: Sleeps until woken up by either all his reindeer being back from vacation or by a group of elves needing his help.
• Reindeer: Stay on a beach for their vacation. After all of them are back, they wake up Santa to get hitched to the sleigh.
• Elves: Work independently but occasionally need Santa’s help. They form groups of three and wake up Santa for assistance.

The problem has the following requirements:

• Santa should only be woken up by either all nine reindeer or a group of three elves.
• If Santa is helping three elves, the other elves must wait until he is done.
• If Santa is preparing the sleigh, elves must wait (i.e. reindeer take priorities over elves).
• Reindeer should not wait indefinitely if there are elves needing help.

The Santa Claus Problem illustrates the synchronization challenges in managing shared resources, prioritizing tasks, and preventing issues such as:

• Fairness: Ensuring all threads get a chance to execute.
• Deadlock: Processes wait indefinitely due to resource contention.
• Starvation: Some processes never get served.

Most of the implementations of this problem use multi-threading and semaphores.

With Scade One, we will use a different approach based on state machines. Thanks to the synchronous dataflow nature of Swan and its dataflow paradigm, parallel processing is straightforward: we can simply place several state machines next to each other. All state machines will execute in parallel, synchronously, and communicate using Boolean flags with no extra effort on our part. The nature of the language thus prevents fairness and deadlock issues. Starvation can also easily be avoided.

Implementation of the TEAM

Before we start implementing each team member, let’s create the types we need.

We will need one status for each team member (Santa, reindeer, and elves) as well as a message that Santa carries to the other team members to call them for action.

For the statuses, we have 3 possible values for each team member.

For that message, we will use a variant type: it is a type that can hold a value (possibly empty) from one of several predefined types, each identified by a unique tag (ID), with only one type being used at a time. In our case, it can be to either “continue what you do”, “talk to reindeer in a given status” or “talk to an elf in a given status”.

These are the different types we need:

type SantaStatus = enum { S_SLEEPING, S_DELIVERING, S_HELPING };

type ReindeerStatus = enum { R_VACATION, R_READY, R_FLYING };

type ElfStatus = enum { E_WORKING, E_ISSUE, E_SOLVING };

type Message = Nothing {} | ToReindeer { ReindeerStatus } | ToElf { ElfStatus };

Implementation of a reindeer

A reindeer is basically a state machine with 3 states:

1. Vacation at the beach (initial state)
2. Back from vacation
3. Flying with Santa

To transition from state #1 (vacation) to state #2 (back from vacation), we can use an external trigger. For the other transitions, we will check if the message from Santa is addressed to the current reindeer state.

The Reindeer operator will return the status of the reindeer, resulting in the following prototype:

node Reindeer (endVacation: bool;
               message: Message;)

The status will be updated at each state of the State Machine.

Note that we use a strong transition so that as soon as the Reindeer gets a message from Santa, he will move to the next state.

Implementation of an elf

The elf’s states are the following:

1. Working hard (initial state)
2. Has a problem
3. Fixing issue with the help of Santa

The signature and implementation are very similar to the reindeer:

Implementation of Santa

As stated in the problem, Santa Claus has three states, depending on the reindeer and the elves:

1. Sleeping (initial state)
2. Helping the Elves
3. Delivering the Gifts (priority over helping the elves)

This leads to the following simplified diagram with conditions for the transitions:

The program execution will proceed as follows:

1. At the beginning of the program, Santa is in “Sleeping” mode
2. If all reindeer are back:
   • Change Santa to “Delivering Gifts” mode
   • Send a message to the reindeer (to ask them to fly)
   • When the delivery is finished, change Santa back to “Sleeping” mode and send another message to the reindeer (for going back to vacation)
3. Otherwise, if at least 3 elves need help:
   • Change Santa to “Helping Elves” mode
   • Send a message to the elves needing help
   • When the problem is solved, change Santa back to “Sleeping” mode and send a message to the elves being helped
4. If at least one reindeer is not back and fewer than 3 elves need help, Santa continues sleeping
5. Move to next cycle and return to step 2

For our Santa operator, we need the following inputs:

• Whether all reindeer are ready (Boolean)
• Whether a group of 3 elves need help (Boolean)
• Whether Santa has finished delivering the gifts (Boolean)
• Whether Santa has been able to fix the issue of the elves (Boolean)

We will return the status of Santa and the message to send to the elves and reindeer (which, by default, is to continue to do what they are doing):

node Santa (allReindeersReady: bool;
            elvesNeedHelp: bool;
            stopDelivery: bool;
            stopFixing: bool;)
  returns (status: SantaStatus;
           message : Message default = Nothing;)

We will set the message to send when we perform a transition, with the state of the reindeer/elf to update in the value of the message (e.g. ToElf { E_ISSUE } will trigger the transition from the state where the elf is in E_ISSUE) .

The implementation is the following:

Note that we use here some weak transitions because Santa needs to wait for the reindeer / elves reaction after he has sent a message.

Implementation of North Pole Control Center

Now that we have implemented each team member, let’s implement the control center that will coordinate all these people.

Let’s first do a simplified implementation with only a single elf and a single reindeer to understand how we can make it work.

Simplified Implementation of Control Center (1🧝 and 1 🦌)

The Control Center will return the status of Santa, the reindeer and the elf based on the different inputs:

• The reindeer needs to come back from vacation,
• The elf has met an issue,
• Santa has finished delivering the gifts,
• Santa has finished fixing the issue.

node NorthPole_1_1 (endVacation: bool;
                    meetIssue: bool;
                    stopDelivery: bool;
                    stopFixing: bool;)
  returns (status: SantaStatus;
           statusReindeer: ReindeerStatus;
           statusElf: ElfStatus;)

For the instantiation, we can start by instantiating Santa with 2 commands as textual inputs.

As we implement a version with a single reindeer and elf, the 2 other inputs will be simply:

• Check whether our single reindeer is back from vacation
• Check whether our single elf has an issue

Note that we can simply connect all the blocks for data exchange, and the code generator will produce the code in the correct order. Additionally, for the reindeer and elf we need to use the previous message from Santa with the pre operator to avoid a circular dependency.

Now that Santa knows how to handle 1 reindeer and 1 elf, let’s add the other staff members.

Control Center Implementation with 9 reindeer and a given number of elves

First, we need to change the signature of the operator to accommodate a given number of elves (as a size parameter) by using arrays for commands and status of elves and reindeer:

node NorthPole <‍<‍NB_ELVES‍>‍> (endVacation: bool^NB_REINDEERS;
                             meetIssue: bool^NB_ELVES;
                             stopDelivery: bool;
                             stopFixing: bool;)
  returns (status: SantaStatus;
           statusReindeer: ReindeerStatus^NB_REINDEERS;
           statusElves: ElfStatus^NB_ELVES;) 

Note that the number of reindeer is a constant defined outside, as we all know there are nine reindeer (after Rudolph joined in 1939).

In our operator implementation, we need to update three elements:

• Computation of the Boolean inputs of Santa: the computation of the Boolean value requires to combine the different status of reindeer / elves with a fold iterator
• Multiple instances of the reindeer and elves: we use for that the map iterator, as it maintains distinct memory for each instance (unlike using a forward operator)
• Array Inputs for the elves and reindeer: while it is straightforward for the reindeer, for the elves we need to construct an array of messages for only the elves to change

The computation of the Boolean inputs with the fold would look like this:

For building the message to send to the selected elves (that will be helped or go back to work), we need to compute an array of messages: we will implement an operator selectElves that returns the input message for the first 3 elves in the given state of the message:

function selectElves <‍<‍NB_ELVES‍>‍> (message: Message;
                                   statusElves: ElfStatus^NB_ELVES;)
  returns (messageElves: Message^NB_ELVES default=Nothing^NB_ELVES;)

We will use an ActivateWhen to filter based on the ID of the variant and a partial forward construct with a counter nb: int32 last = 0 that will stop when this counter reaches 3 elves. Moreover, to avoid starvation of the elves needing help, we will record the index of the last elf who got help and start from that one the next time.

Using this operator, we can finally implement our final North Pole Control Center:

Now that we can compute the status of the whole team, let’s run our program!

Let’s monitor the team!

We will first implement a simple operator that controls when the reindeer come back from vacation, when the elves encounter issues, and when Santa stops helping or delivering gifts (based on the status from the previous cycle).

For better visualization of the results, we can create a Dashboard with SCADE Rapid Prototyper and generate the corresponding Panel for Scade One.

We can then create a Test Harness with all these blocks and run a debug to see how it executes. Thanks to the synchronous mode and the debugger, we can easily understand how the blocks interact with each other and adjust the model accordingly.

With the debugger, we can also observe the state of Santa in the State Machine and the transition that are/will be triggered:

If we press Play in the debug panel, we can see the different changes of states:

Explore Further

Download the example from this blog here (compatible with Scade One 2025 R1 and above). If you are a SCADE user, access Scade One Essential with your existing licenses on the Ansys Download Portal and experiment with this example! You can also use Scade One Student.

This blog showcases how to implement the Santa Claus Problem using Scade One, leveraging its support of State Machines, signals, and iterators. We demonstrated that the implementation is straightforward, and the language’s features effectively address the challenges of concurrent programming.

You can also schedule a live demo of Scade One… or track Santa during his trip to deliver the gifts.

Merry Christmas and Happy Hanukkah to everyone!

About the author