Christmas is no doubt my favorite time of the year; there is something magical about the holidays. To be true to this festive time of year, I was looking for a good topic to share on the fantastic “F# Advent Calendar 2015” organized by Sergey Tihon.
Immediately, a paper that I read a little while ago came to mind. It is from the title “Beautiful Concurrency” by Simon Peyton Jones (Microsoft Research, Cambridge May 1, 2007). You can download the paper here.
In this paper is a section titled “The Santa Claus Problem”, a well-known example originally introduced by John Trono in 1994. The Santa Claus problem provides an excellent exercise in concurrent programming. Trono published the exercise and provided a solution based on semaphores, designed for low-level mutual exclusion. While semaphores can and should be used to introduce concurrency concepts, they are not necessarily appropriate for writing concurrent programs.
Being that concurrent and parallel computing are areas of interest for me, I have decided to solve “The Santa Claus Problem” using F#. Utilizing F# with it’s message passing semantic built in the MailboxProcessor will show the simplicity and readability that is possible to achieve by adopting these concurrent constructors. Also, it is of course an appropriate and festive topic for the holiday season.
Here the running WPF Santa Claus Problem in F#
INTRO
One of the main tenants of the functional paradigm is immutability. In computer programming, an object is immutable when it’s state cannot be updated after creation. In .NET for example, “Strings” are typically immutable objects.
Immutable objects are more thread-safe than mutable objects. Immutable data structures facilitate sharing data amongst otherwise isolated tasks in an efficient zero-copy manner. Functional programming excels in parallel computation for the reason that immutability is the default choice. The real benefit is that no multi-thread access synchronization is necessary.
Using immutable objects in a programming model forces each thread to process against its own copy of data. Furthermore, it is completely safe to have multiple threads accessing shared data simultaneously if that access is read-only.
Immutability is a key concept to write lock free multithreaded software. One other critically important concept for writing lock-less concurrent code is natural isolation. In a multithreaded program, isolation solves the problem of “share of state” by giving each thread a copied portion of data to perform local computation. When using isolation, there is no race condition because each task is processing an independent copy of its own data. Isolation can be achieved by process isolation, which is based on independent and separate memory address space.
F# is a great functional-first multi paradigm programming language with powerful concurrent constructors, which provide an enormous boost to productivity. More over, The F# programming language, is naturally parallelizable because it uses immutably as default type constructor. F# Async Workflow and MailboxProcessor (a.k.a. Agent) provides a simple concurrent programming model that is able to deliver fast and reliable concurrent programs, which are easy to understand.
The F# MailboxProcessor primitive is based on message passing also known as the “share nothing approach”. We will use these two contractors extensively to solve “The Santa Claus Problems”
The Problem
Santa Claus sleeps at the North Pole until awakened by either all nine reindeer collectively back from their holidays, or by a group of three out of ten elves.
In the case that Santa Claus is awakened by the reindeer, he harnesses each of them (9) to the sleigh to deliver the toys. When the toys have been delivered, Santa Claus then unharnesses the reindeer, and sends them off on vacation till next Christmas.
In the case that Santa Claus is awakened by a group of three or more elves, he meets them in his office to discuss the status of the toy production, solve existing problems and consult on toy R&D. When the meeting is over, Santa Claus allows the elves to go back to work. Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting. Marshalling the reindeer or elves into a group must not be done by Santa since his time is extremely valuable. One of the challenges of the Santa Clause problem is to ensure the order of execution by enforcing the rules mentioned. In fact, if Santa Clause is already consulting with elves in his office, the program should not allow any extra elves to join a group nor should Santa Clause be able to deliver the toys regardless of the number of reindeer available if he is occupied by the elves and vice versa.
Summary of Santa’s tasks
- Santa Claus sleeps at the North Pole until awakened by either (a) all of the nine reindeer, or (b) a group of three out of ten elves.
- If awakened by the group of reindeer, Santa harnesses them to a sleigh, delivers toys, and finally unharnesses the reindeer who then go on vacation.
- If awakened by a group of elves, Santa shows them into his office, consults with them on toy R&D, and finally shows them out so they can return to work constructing toys.
- A waiting group of reindeer must be attended to by Santa before a waiting group of elves.
- Since Santa’s time is extremely valuable, marshaling the reindeer or elves into a group must not be done by Santa.
The Solution
F# is a functional language with exceptional support for Asynchronous Workflow and with built-in message passing semantics with the MailboxProcessor.
To solve the Santa Claus Problem, we are using a message passing semantics, which show how the lack of shared state can simplify concurrent programming. The solution design uses the MailboxProcessor to create independents units, each responsible to coordinate and to marshal the groups of Elves or Reindeers. Each group has to organize among themselves without help from a Santa thread. One Agent is responsible to coordinate the Reindeer queue for when the Reindeer come back from vacation, and a separate and independent Agent to coordinate the Elf queue for when the Elves need to consult with Santa and join the waiting room.
One of the benefits of a system built using agents, is that the coordination and the synchronization between various threads can be implemented easily without sharing of state and therefore without locks, which removes pitfalls such as deadlock, livelock, and starvation.
Distributed memory systems using the message passing semantic, are simpler to write and prove correctness and also easier to refactor.
For example, in the Santa Claus problem, the constraint of having only three elves at time to consult with Santa, is implemented by a separate Elf queue, decoupling the Santa and Elf code further than the shared memory solutions.
The concurrency primitives of F# can be used to develop a sophisticated solution to the Santa Claus problem. The main problem is to synchronize a set of threads, that can be either reindeer or elves, and to manage them atomically by ensuring that one group of elves or reindeer does not overtake another group. This synchronization, by using the agent model, is particularly simple to ensure.
To easily terminate the program, we are using a ‘cancellation token’, which is generated and injected for each Agent and Async Operation. When the last year of Christmas is reached as expected, the ‘cancellation token’ is triggered provoking the cancellation and stop of all the processes involved, and consequentially to fire up the function registered to cleanup the resources and do some logging.
// The cancellation token is used to stop the execution as a whole // when the last Year of Christams is reached let cancellationTokenSource = new CancellationTokenSource() let cancellationToken = cancellationTokenSource.Token
// … reindeer function implementation if Interlocked.Increment(startingYear) = theEndOfChristams then cancellationTokenSource.Cancel()
// … santaClausProblem function
cancellationToken.Register(fun () ->
(queueElves :> IDisposable).Dispose()
(allReindeers :> IDisposable).Dispose()
(threeElves :> IDisposable).Dispose()
(elvesAreInspired :> IDisposable).Dispose()
(santasAttention :> IDisposable).Dispose()
log "Faith has vanished from the world\nThe End of Santa Claus!!") |> ignore
BarrierAsync
The BarrierAsync is a type whose job is to provide a re-entrance barrier for multiple threads to synchronize on. The purpose of BarrierAsync is to eliminate the need for an explicit shared state among synchronization threads.
// The BarrierAsync is a block synchronization mechanism, which instead of using
// low-level concurrency to lock primitives, it is using a MailboxProcessor with
// asynchronous message passing semantic to process messages sequentially.
// The BarrierAsync blocks the threads until it reaches the number of
// signals expected, then it replies to all the workers, releasing them to continue the work
type BarrierAsync(workers, cancellationToken, ?continuation:unit -> unit) =
let continuation = defaultArg continuation (fun () -> ())
let agent = Agent.Start((fun inbox ->
let rec loop replies = async {
let! (reply:AsyncReplyChannel<int>) = inbox.Receive()
let replies = reply::replies
// check if the number of workers waiting for a reply to continue
// has reached the expected number, if so, the reply functions
// must be invoked for all the workers waiting to be resumed
// before continuing and restarting with an empty reply workers list
if (replies.Length) = workers then
replies |> List.iteri(fun index reply -> reply.Reply(index))
continuation()
return! loop []
else return! loop replies }
loop []),cancellationToken)
interface IDisposable with
member x.Dispose() = (agent :> IDisposable).Dispose()
member x.AsyncSignalAndWait() = agent.PostAndAsyncReply(fun reply -> reply)
The purpose of the asynchronous barrier implementation is to suspend asynchronous workflow until the barrier rolls. This type is constructed with a given number of ‘workers’, which are threads that are blocked awaiting the barrier to roll, releasing the threads.
The implementation of the BarrierAsync is using a message passing approach with the F# MailboxProcessor to convert concurrently posted messages into a sequence of messages. The function ‘AsyncSignalAndWait’ is sending an asynchronous ‘PostAndAsyncReply’ request to the agent using a ‘AsyncReplyChannel’ type, which is blocking the Asynchronous Workflow until all the workers have signaled the Barrier, which is rolling and releasing the threads by replying back to the channel of each worker.
For example, the BarrierAsync is used to synchronize the “three elves at a time” constraint. The Elf threads share state in the form of a counter so that every third elf in the waiting room will go and wake Santa. Each time an elf needs help from Santa, he sends an ‘AsyncSignalAndWait’ to the BarrierAsync, when the workers counter reaches the expected number, in this case three, the Barrier rolls and replies to all the workers to continue.
SyncGate
The SyncGate type, is to deliver a threads synchronization equivalent to a Semaphore, but with specific interest in targeting the asynchronous workflow. The purpose of the SyncGate is to allow a given number of an asynchronous workflow to run simultaneously, and blocking further requests until a running workflow sends a request of release to the SyncGate. This type is constructed with a given number of ‘locks’, which is the number of threads that are allowed to execute in parallel. The remaining threads are put in a queue and blocked awaiting for the SyncGate to receive a release signal when an executing thread terminates the work.
The implementation of the SyncGate, like the BarrierAsync, is using a message passing approach with the F# MailboxProcessor. There are two functions exposed, respectively to ‘Acquire’ a lock asynchronously, and to ‘Release’ a lock.
For example, in the implementation of the “Santa Claus Problem”, there is a SyncGate representing Santa Claus. In this case the SyncGate is constructed with only one lock available, to ensure that Santa is awakened either by the ninth reindeer or each third elf.
type SynGateMessage =
| AquireLock of AsyncReplyChannel<unit>
| Release
// SynGate uses a MailboxProcessor to emulate the synchronization
// lock of a Semaphore maintaing the asynchronous semantic of F# Async Workflow
type SyncGate(locks, cancellationToken, ?continuation:unit -> unit) =
let continuation = defaultArg continuation (fun () -> ())
let agent = Agent.Start((fun inbox ->
let rec aquiringLock n = async {
let! msg = inbox.Receive()
match msg with
| AquireLock(reply) -> reply.Reply()
// check if the number of locks aquisition
// has reached the expected number, if so,
// the internal state changes to wait the relase of a lock
// before continuing
if n < locks - 1 then return! aquiringLock (n + 1)
else return! releasingLock()
| Release -> return! aquiringLock (n - 1) }
and releasingLock() =
inbox.Scan(function
| Release -> Some(aquiringLock(locks - 1))
| _ -> None)
aquiringLock 0),cancellationToken)
interface IDisposable with
member x.Dispose() = (agent :> IDisposable).Dispose()
member x.AquireAsync() = agent.PostAndAsyncReply AquireLock
member x.Release() = agent.Post Release
The complete source code can be found here.
There are two implementations, one is a console application which logs the output into the console, the second one is a WPF application.
This solution in the end ensures a Merry Christmas for all and for all a good night!