The Santa Claus Problem - Thread Synchronization

A thread synchronization computer programming problem and a solution using semaphores and mutexes. The solution shown in this video is a slightly modified version of the solution found in The Little Book of Semaphores by Allen B. Downey, which is an excellent free book on semaphores with lots of example problems and solutions.
http://greenteapress.com/semaphores/

The solution here is slightly over-constrained compared to that shown in Downey's book, but I find this version somewhat cleaner and more satisfying for reasons I can't quite articulate :)

How the visualization should proceed under other circumstances, such as when the 9th reindeer returns to the north pole, is left as an exercise for the viewer.

Music is "Wish Background" by Kevin MacLeod (incompetech.com) licensed under a creative commons attribution-only license.

Category:

Education

Tags:

• santa
• claus
• problem
• thread
• synchronization
• multithreading
• semaphore
• mutex
• elf
• reindeer
• programming

[tostrong4you]

I took a programming class in highschool, so im glad I can understand some 60% of this, interesting stuff.

You keep making good vids, but I keep slacking on the one I wanted to do. I already made a real-life 3-D version of the evolved virtual worm like 2 months ago! I just dont know were to start with the video editing. Should I play music? Should I get a mic and voice over?(rhetorical). I want to finish it sometime soon.

[kjlg74]

@tostrong4you Thanks a lot!

60% sounds about right. I don't imagine a high school programming class discusses thread synchronization - so the mutex and semaphore stuff probably seemed a little odd.

You built a 3D model of the end-over-end worm?! That's pretty AWESOME :D

I can't wait to see that! Very cool!

[Zetimenvec]

I'm fairly weak on programming, what are semaphore mutex variable types? or are those something specific to the function?

[kjlg74]

@Zetimenvec Even if you were a strong programmer, you'd never encounter mutexes and semaphores outside of thread synchronization - and even then, there are other synchronization mechanisms one might use instead.

You can think of a semaphore as a special kind of integer. The only thing you can do with it is increment it or decrement it (you can't even look inside to see its current value). If you decrement it and the result is negative, you (the thread) block. (continued)

[kjlg74]

@kjlg74 ..and if you increment it while there are thread(s) blocked on it, one of those threads will be unblocked and allowed to continue running.

Decrementing is often called "waiting" because you might block, and incrementing is often called "signaling".

A mutex is really just a semaphore with a maximum positive value of 1

It's too much to explain in YT comments, but it's quite interesting stuff. Check out the PDF Downey book (see video desc). I highly recommend it :)

[kjlg74]

@kjlg74 Some languages actually have semaphores as built-in primitive data types. Java has them, but you need to import them from java.util.concurrent

[YinPT]

That's how I would like my classes to be: simple and interesting. I finally understood semaphores, so thank you for that! :)

[turkishpower08]

Just 1 question: Why mutex for counters? What would happen if there were not mutex for counter access??

[kjlg74]

@Wysiwygnuttyjo51 Oh no, nothing like that. When I talked about Santa "sleeping", I just forgot to mention who with ;P

[kjlg74]

@Dullbedsitblogger If even a non-programmer can get something from this, I must be doing something right.

I should get my students drunk next time I teach this - maybe it helps! :D