show_menu logo_rd
Taras Kushnir

Software engineer at ELEKS

Solving the Santa Claus Problem Using OCaml

0

Santa’s problem

Not much time left till Xmas… Have you ever wondered how Santa manages to do his hard work with elves and reindeer? And why does he keep doing it?

These questions bothered professor John Trono of St. Michael’s College in Vermont. He was worried about how Santa handles all that stuff so much, that he decided to emulate Santa’s work and wrote a simplified scenario of Santa’s life:

Santa Claus sleeps in his shop at the North Pole and can only be awakened in 2 cases:

  1. If all nine reindeer are back from their vacation in the South Pacific.
  2. Some of the elves are having trouble making toys.

To allow Santa to get some sleep, elves can only wake him up when they are 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. (It is assumed that the reindeer do not want to leave the tropics, and therefore they stay there until the last moment possible.) The last reindeer to arrive must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

Besides the given scenario, lets create additional specifications:

  • After the ninth reindeer arrives, Santa must invoke prepare_sleigh, and then all nine reindeer must invoke get_hitched.
  • After the third elf arrives, Santa must invoke help_elves. Concurrently, all three elves should invoke get_help.
  • All three elves must invoke get_help before any additional elves enter.

As you can see, not very complicated, but only utill you try implementing it. To make the solution not that boring, I’ve decided to implement it in OCaml. OCaml is an ML-derived functional language with static typing, pattern matching and automatic garbage collection. It has a fairly big standard library and a nice native code compiler for a number of platforms. At the moment, I haven’t managed to find an OCaml solution on the Internet, so, I chose it to make solving Santa’s problem a bit more challenging and interesting, in other words, just for fun. I’ll try to comment the lines of code that look weird so don’t panic.

Pseudocode solution

First, let’s solve Santa’s problem using pseudocode. We’ll use elves and reindeer counters protected by a mutex, a semaphore for Santa (he waits until either an elf or reindeer signals him), a semaphore for reindeers (they wait until Santa signals them to get hitched), semaphore for elves (they wait until Santa helps them) and a mutex to prevent additional elves to enter while three elves are being helped.

Santa’s code is the easiest one (it runs in an infinite loop)

santa_sem.wait()
mutex.wait()
if reindeer == 9
{
    prepare_sleigh()
    reindeer_sem.signal(9)
}
else if elves == 3
{
    help_elves()
    elf_sem.signal(3)
}
mutex.signal()

Santa checks two conditions and either deals with elves or with reindeer. If there’re nine reindeer waiting, Santa prepares sleigh and signals reindeer semaphore nine times, allowing the reindeer to invoke get_hitched. If there are elves waiting, Santa invokes help_elves. The code for reindeer is also not that complicated:

mutex.wait()
reindeer += 1
if reindeer == 9
{
    santa_sem.signal()
}
mutex.signal()

reindeer_sem.wait()
get_hitched()

The ninth reindeer signals Santa and then joins the others waiting for reindeer_sem. When it’s signalled, they invoke get_hitched. The code for elves is quite similar, but it uses another turnstile for the three-elf-stuff:

elf_mutex.wait()
mutex.wait()
elves += 1
if elves == 3
{
    santa_sem.signal()
}
else
{
    elf_mutex.signal()
}
mutex.signal()

elf_sem.wait()
get_help()

mutex.wait()
elves -= 1
if elves == 0
{
    elf_mutex.signal()
}
mutex.signal()

The first two elves release elf_mutex at the same time they release the mutex, but the last elf holds elf_mutex, preventing other elves from entering until all three elves have invoked get_help. The last elf to leave releases elf_mutex, allowing the next batch of elves to enter.

The OCaml part

Now it is time to have some fun with OCaml. The first thing to mention is that OCaml does not have any semaphore built-in classes due to it’s rich standard library. But it’s not a big issue since OCaml has Mutex and Condition classes (yes, OCaml is Objective Caml and it does have classes) in the Threads library and we can use them to write our own semaphore. To make the semaphore more or less serious, let’s write it in a separate module.

module Semaphore = struct
  class semaphore initial_count initial_name =
    object (self)
      val mutable count = initial_count
      val name = initial_name
      val sync = Mutex.create()
      val cond = Condition.create()
          
      method inc n = count <- count + n
      method dec n = count <- count - n

      method signal ?(n=1) () =
        Mutex.lock sync;
        self#inc n;
        for i = 1 to n do
          Condition.signal cond
        done;
        Mutex.unlock sync

      method wait =
        Mutex.lock sync;
        while count = 0 do
          Condition.wait cond sync
        done;
        self#dec 1;
        Mutex.unlock sync
    end
end;;

My semaphore has internal mutable (yeah, OCaml is not a pure functional language like Haskell) field count (used for the “gate width” for threads to enter semaphore simultaneously), internal name (used it for logging when I was looking for a deadlock in my code before), one mutex and one condition variable. It has two primary methods: signal with an optional parameter N and wait which are just usual increment-decrement/lock-unlock methods of the semaphore. Signal increments the internal counter and, if it is positive, allows threads to enter the critical section which given semaphore guards and wait decrements counter. If it is zero, calling thread is blocked until the counter becomes positive.

If an OCaml program is split into modules then you can expect big fun trying to compile that program. First, you have to generate interfaces for that module. Secondly, you have to compile both interface and the module itself:

ocamlc -thread unix.cma threads.cma -i semaphore.ml > semaphore.mli
ocamlc -thread unix.cma threads.cma -c semaphore.mli
ocamlc -thread unix.cma threads.cma -c semaphore.ml

To enable multithreading support (in terms of Posix compatible threads), you have to compile your code with the -thread key and include unix and threads compiled modules.

Now, let’s write the main program. Since we’re dealing with logging and multithreading, I’ve written a function-helper that uses our Semaphore class to synchronize printing to stdout:

let stdout_sem = new Semaphore.semaphore 1 "stdout_sem";;
let puts s =
  stdout_sem#wait;
  Printf.printf "%sn" s;
  flush stdout;
  stdout_sem#signal ();;

Next, I’m using some kind of a transport structure for Santa, reindeer and elves functions (shared between them and protected by the semaphore). This structure (a record in terms of OCaml) contains counters and semaphores as discussed earlier:

type santa_counters = { mutable elves : int;
                        mutable reindeer : int;
                        santa_sem : Semaphore.semaphore;
                        reindeer_sem : Semaphore.semaphore;
                        elf_sem : Semaphore.semaphore;
                        elf_mutex : Semaphore.semaphore;
                        mutex : Semaphore.semaphore };;

and a simple initializer:

let new_santa_counters () = { elves = 0;
                              reindeer = 0;
                              santa_sem = new Semaphore.semaphore 0 "santa_sem";
                              reindeer_sem = new Semaphore.semaphore 0 "reindeer_sem";
                              elf_sem = new Semaphore.semaphore 0 "elf_sem";
                              elf_mutex = new Semaphore.semaphore 1 "elf_mutex";
                              mutex = new Semaphore.semaphore 1 "mutex" };;

To make our example more realistic I’ve implemented functions prepare_sleigh and others to see what’s actually happens using my helper for synchronized printing:

let prepare_sleigh () = puts "Prepare sleigh";;
let help_elves () = puts "Help Elves";;
let get_hitched () = puts "Get Hitched";;
let get_help () = puts "Get Help";;

You might have thought that braces () an the end of each function are kind of usual braces like in Java, C++, etc, but actually it’s an argument of a type unit of each function. Please, refer to the tutorials for more details.

Let’s take a look at our pseudocode solutions implemented in OCaml:

let santa_role_func c =
  c.santa_sem#wait;
  c.mutex#wait;

  if c.reindeer = 9 then (
    prepare_sleigh ();
    c.reindeer_sem#signal ~n:9 ();
    c.reindeer <- 0;
   )
  else if c.elves = 3 then (
    help_elves ();
    c.elf_sem#signal ~n:3 ()
   );

  c.mutex#signal ();;


let reindeer_role_func (c, i) =
  let s = Printf.sprintf "Starting reindeer (%d)" i in
  puts s;
 
  c.mutex#wait;
  c.reindeer <- c.reindeer + 1;
  if c.reindeer = 9 then c.santa_sem#signal ();
  c.mutex#signal ();

  c.reindeer_sem#wait;
  get_hitched ();;


let elves_role_func (c, i) =
  let s = Printf.sprintf "Starting elf [%d]" i in
  puts s;
 
  c.elf_mutex#wait;
  c.mutex#wait;
  c.elves <- c.elves + 1;
  if c.elves = 3 then
    c.santa_sem#signal ()
  else
    c.elf_mutex#signal ();
  c.mutex#signal ();
 
  c.elf_sem#wait;
  get_help ();

  c.mutex#wait;
  c.elves <- c.elves - 1;
  if c.elves = 0 then c.elf_mutex#signal ();
  c.mutex#signal ();;

You may notice that santa_role_func accepts one parameter c (our transport structure), but two others accept two parameters. It’s because Santa’s role function is running in a loop and others are running just once. The second parameter in elves and reindeer functions is an index of the thread they are running in (for debug and visualization purposes).

The last step to implement (except for compilation) is to make all this stuff work together:

let c = new_santa_counters () in
let santa_loop () =
  puts "Starting Santa loop";
  while true do
    santa_role_func c;
  done
in
let santa_array = [| Thread.create santa_loop () |]
and
reindeer_array = Array.init 9
(fun i -> Thread.create reindeer_role_func (c, i))
and
elf_array = Array.init 20
(fun i -> Thread.create elves_role_func (c, i))
in
Array.iter Thread.join
(Array.concat [santa_array; reindeer_array; elf_array]);;

The code above creates three arrays of threads: santa_array (always contains just one element), reindeer_array (always contains 9 reindeer threads) and elf_array (contains 20 fairly chosen elf threads). After each thread is started, the main program joins all of them using humble functional magic with Array.Iter.

What happened at the North Pole

Below, I’ve copied typical stdout from the santa_problem solution (and the OCaml version for the clarification).

*> ocaml -version*
The OCaml toplevel, version 4.01.0
*> ./build.sh*
*> ./santa_problem*
*Starting santa loop*
Starting reindeer (4)
Starting reindeer (5)
Starting reindeer (6)
Starting reindeer (3)
Starting reindeer (7)
Starting reindeer (8)
Starting elf [0]
Starting reindeer (2)
Starting elf [1]
Starting elf [2]
Starting elf [3]
Starting elf [4]
Starting reindeer (1)
Starting elf [5]
Starting elf [6]
Starting elf [7]
Starting elf [8]
Starting elf [9]
Starting elf [10]
Starting elf [11]
Starting elf [12]
Starting reindeer (0)
Starting elf [13]
Starting elf [14]
Starting elf [15]
Starting elf [19]
*Prepare sleigh*
Starting elf [16]
Starting elf [18]
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Get Hitched
Starting elf [17]
*Help Elves*
Get Help
Get Help
Get Help
*Help Elves*
Get Help
Get Help
Get Help
*Help Elves*
Get Help
Get Help
Get Help
*Help Elves*
Get Help
Get Help
Get Help
*Help Elves*
Get Help
Get Help
Get Help
*Help Elves*
Get Help
Get Help
Get Help
......

Merry Xmas

Santa’s problem is one of the classical synchronization problems and is worth looking into. A lot of solutions exist nowadays. For example, there is an interesting approach to solve it in Haskell using Software Transactional Memory (STM). Although OCaml does not provide us with such cool features as STM, we can see that building parallel programs in OCaml is easy fun! As far as I see, the solution above is the first pure OCaml solution of Santa’s problem.
You can download the whole code from Santa’s gist.

Taras Kushnir

Taras Kushnir is a software engineer at ELEKS. He is enthusiastic about Ruby, C++ and .NET and likes participating in programming contests like ACM/ICPC. Competitiveness takes over his hobbies too: Taras likes long-distance running, table tennis and mountaineering. Entomology and drawing are also his hobbies. Taras has always liked writing and with enough experience to share with readers, he started blogging.

tags

Comments: 0