Comments by "LoneTech" (@0LoneTech) on "Santa gave me a concurrency problem for Christmas..." video.

The original problem is designed for semaphores as the only synchronization primitive, and expects to run only one thread per character, no spawning. But yes, you'd certainly build it differently with a modern language. It's still useful to understand how that could be built.
22
First paper cited in the description: DOI: 10.1145/187387.187391 It is wordy and vague, much like this video, and the sample implementation indeed simply checks reindeer first. Unlike the video presenter's variant, the paper doesn't let the reindeer go back on vacation before santa performs deliveries. As for the "sneaky" bug... it didn't seem to exist. Semaphores can hold values posted early, such as how many reindeer are let out by santa. And the single mutex (which overserializes the program) prevented races on reindeerCount. The architecture is pretty sad, but I guess that's to be expected of something to exercise only the semaphore primitive, thirty years ago.
5
This exercise is designed to demonstrate the flexibility of semaphores and test students' understanding of them. Unfortunately, it revealed flaws in your understanding, not a great point to start teaching from. This video didn't describe the challenge very well. Sadly, neither did the original paper. This is why you both missed relevant points of synchronization; in the original paper, santa may finish deliveries before the reindeer arrive at the sleigh. In yours, the sleigh does not exist and the reindeer may go back on vacation before santa finishes his deliveries. The "sneaky bug" reveals a notable misunderstanding of what semaphores do. This bug is imaginary, as semaphores can hold a number of posts. Santa posted 9 times, so 9 times a reindeer will get out. It doesn't matter that santa moved on, the count is in the semaphore; like a counting turnstile. The behaviour you worried about could occur with POSIX condition variables, where you can only wake already waiting threads. The use of mutexes missed the point that semaphores can do that too (it's why C++ named their methods release and acquire, instead of signal and wait). Perhaps more concerning is that you overserialized independent blocks by sharing the lock for different variables. The explanatory value of flashing up miniature pictures of large chunks of code, that we have neither the time nor resolution to read, is doubtful.
4
Given appropriate monitoring, yes. E.g. QuickCheck generates tests (known as fuzzing). One major issue is that people often aren't any better at writing specifications or tests than implementations. It's not much use to simulate thousands of different runs if you can't tell if any of them went wrong.
3
It's a deep topic. At its root is atomicity, which means something that won't be interrupted (may still be more than one cycle, but nothing affecting it should overlap). The precise mechanisms vary in complexity, but most CPUs have a feature where a sufficiently complicated operation can be performed without interruptions, even from other CPU cores (e.g. the LOCK signal on 386). Compare-and-swap is one of the easier to understand, and load-link/store-conditional is a more flexible variant. These aren't limited to CPUs either; there are memory chips that support operations like atomic increment, such that the value need not be loaded into the processor. For many programs, the entire concept can be abstracted away; STM (software transactional memory) allows focusing on the logic rather than the sequence. Some atomics are quite expensive, e.g. serializing all threads in a GPU work group or CPUs contending for one cache line (which may take hundreds of cycles to load), while others can be very fast (bitwise and/or in a workgroup can be as fast as a broadcast). A mutex is very simple with compare and swap: Acquire is compare to unlocked, if equal swap to locked, if not yield and repeat.
3
Like most youtube downgrades, they switched this on without creator consent.
3
@HyenaEmpyema It's often more effective to eliminate the potential for errors than to search for them. For instance, STM (software transactional memory) removes the issue of lock ordering, making deadlocks impossible (except iiuc for missing references, which can be detected early), and can speed some tasks up by speculative execution.
2
Spot on. The "sneaky bug" is so sneaky it never existed; the presenter may have been thinking of condition variables instead of semaphores.
2
That would simplify the task at least on the reindeer side, but it's part of the complexity in this actor model scenario exercise. Quite possibly one of the lessons it's intended to highlight. Also, this wasn't a deadlock (video presenter got that wrong) but a race condition (reindeer could lap each other). I haven't checked if any of the papers explained that properly.
2
1) You're thinking of logical CPUs, which limit how many threads may be running. Operating systems schedule threads such that they might also be waiting for CPU access (runnable) or sleeping (waiting for other conditions). Typically the CPU is regularly interrupted to share its time among runnable threads. 2) The independent parts are modelled by sleep; reindeer on vacation, elves making toys, santa sleeping. The task is about when they're interacting, e.g. needing to fit in the room or ask their question. It's a resource contention and synchronization task, not a labour division task. The idea is that is already done (e.g. by having elves work on different toys). One constraint is that santa's sleep is higher priority than one or two elves being stuck.
2
Creepy.
2
Just thought I'd inform you you're being way creepy.
2
Creepy.
1
Mapping this sort of thing is what a message sequence chart is for.
1
@artificialintelligencecoder Oddly, Rust have deprecated std::sync::Semaphore, with less motivation than when Python hid reduce. There are other tools available that would fit the task, like RwLock for the reindeer count, Mutex for the elf count, mpsc for santa's rest and Barrier for waking up the reindeer or elves from their respective rooms (Condvar is the one that could have led to the described race condition bug). A semaphore is similar in function to an asynchronous mpmc with empty messages. A variety of other libraries ("crates") also implement semaphores.
1
@RUSTisGOD The only part of the problem that Rust variant paid any attention to was waking santa. It doesn't have him interact with elves or reindeer, it doesn't have elves queue to join the panic room, etc. It guarantees the reindeer are already on vacation again when santa wakes up, for instance, and can count one reindeer as all 9 required to wake santa. And it's overserialized too. It's not a great look to be a frantic boot licker, even less so when it's your own boots.
1
@GreyZone7 I assume you copied tripe from a search engine, because the only thing they have in common is sleep.
1
@RUSTisGOD One run is not a proof of correctness, particularly when race conditions are involved. What you have is a Santa who finds traces of activity, e.g. a record of which elves have already left the panic room (possibly some straggler is still on his way out), or how many times any reindeer has come in (they leave immediately). You also have elves just give up on even entering the panic room. There's even a risk of deadlock if santa clears elf_help_ready before all the elves get out of the panic room. Try having them say when they're out too, not just in, or having one reindeer take extremely long vacations, to expose some of the issues.
1
@RUSTisGOD The code speaks for itself indeed. And you do not.
1
@RUSTisGOD With the way you've acted on other channels, you really should have a chat with your guardian about the difference between tomfoolery and harassment. If you don't, you'll eventually be having that conversation with law enforcement.
1
@johnneale3105 OpenCSF looks like a pretty good start for an overview from a programming perspective. When it comes to details of how to implement with an instruction set, computer architecture courses will have a section on that, e.g. tS5L1l_TI08 on youtube. Philipp Hagenlocher's course Haskell for Imperative Programmers presents STM rather well. I don't have particular books to refer to; I learned more from reference materials than guides.
1
There's something to that. On repeated (unnecessarily so) reflection, I've concluded the ghost reindeer scenario could occur, but would not deadlock. It would occur by having other reindeer double count; going on vacation, coming back, and going back on vacation using the permission santa posted the prior cycle for the not-yet-awakened ghost reindeer. It's counting entrances, not reindeer present. This isn't what the video described, but it might be what the second, pay-walled paper notes.
1
The proposed "fix" doesn't fix this, it just groups reindeer unnecessarily into ones that didn't wake santa and ones that did. A proper fix might involve e.g. a cycle count for flow control or a two-way synchronization (like having santa wait for all reindeer to reach the sleigh). The proper synchronization type here was a barrier.
1
The supposed bug (it didn't exist, sem_post is not pthread_cond_broadcast) indeed has nothing to do with the elves. Those were there to make the exercise a little more complicated, giving santa multiple wakeup reasons, and adding state (elf waiting for panic room access).
1
@monad_tcp It overserializes because it makes elves and reindeer wait for each other when they're trying to do independent accesses. I never claimed it had no function.
1
They are indeed distinct, and there are other definitions too. For instance, threading predates multithreading; it's when a set of instructions are assembled into one subprogram, like beads on a string, as used in threaded Forth implementations. Concurrency is multiple things (co-) existing at the same time (current). Multithreading or multiprocessing is when we have more than one thread of control in the same system. Parallelism usually refers to when processing might be concurrent, i.e. more than one thread is actually running (as opposed to time sharing), whether through SMT, SIMD, SMP, coprocessing or distribution; typically to speed computation up. In this example, no requirement of parallelism is present, but asynchronous concurrent multithreading is assumed. Santa is an example of single thread concurrency in that he may be awakened for multiple tasks. A more typical example might be a chat program awaiting either user or network input. It's a synchronization challenge, with unclear requirements, where you're expected to use shared memory and only the one synchronization tool (semaphores). In modern software (from about a decade before this problem was posed) we'd probably use a higher level construct, such as MVar or channels, to associate the relevant data (e.g. count in room or wakeup source) with the event.
1