This is a great example of why a Computer Science education is a good idea, even for a game programmer. It's been awhile for me, but we had two very relevant classes.

One was something like "Concurrent Programming", where we learned all about synchronization primitives and the theoretical underpinnings. Perhaps most importantly, all the things that can go wrong, conflicts, deadlocks, race conditions, and the like.

The second was "Operating Systems", where we learned all about process and thread management and scheduling. In particular, as I believe is common, we implemented parts of a toy OS (I think it was NachOS, in my case). This totally removed the mystery of how these "magic" synchronization primitives work. Threads and processes are just "things" that can be manipulated, same as any other part of a machine.

So, get your degree, kids! It will be worth it in the end.

The one reason I always try to avoid using mutex is that it causes use/kernel mode switch which is expensive, and I think that's why in some cases spinlock acquire/release can be much much faster than using mutex.

A context switch between processes is expensive (mainly because each process has it's own memory space that must be saved/restored). A context switch between threads within the same process should be fairly efficient.

If your producer and consumer threads are all in the same process, then you should be perfectly fine using condition variables and letting the OS handle it.

So when I want to implement a threadpool myself, I was thinking using spinlock to protect the job queue. But soon I realize that if my job queue is empty, I will saturate CPU. And then I find condition variable can avoid this busy-waiting pretty good, however how cv achieve it is a little disappointing to me: first it require a lock (I guess I can use spinlock too, right?).... and now it seems its thread wakeup mechanism involve another kernel call.... I was thinking of use a hybrid spinlock to achieve both fast lock acquire/release while avoiding busy-wait by calling sleep after around 4000 spin on spinlock, however my threads may not be super responsible (since incoming job is not waking up sleeping thread but is waiting the thread to wake up....)

The other thing you may want to watch out for is premature optimization. You make design decisions to avoid problems that yet do not exist. That is a highly dangerous game, where expensive mistakes are often made. The simple reason for that is, we humans cannot predict where the bottleneck of the processor is going to end up. I play the game of guessing where it is, just before I profile, and in the past 30 years, I have been consistently wrong. In other words, there is a big chance you are incorrect in your assumptions.

Build the thing first, then profile and fix if necessary.

The popular OSes we know are interrupt-driven. That means the OS schedules themselves to the CPU "wake me up in 16ms". The interrupt causes the CPU to execute kernel code at the scheduled point in time. When woken up, the OS will go through a list of threads it needs to run and execute them. If there's nothing to run, then it puts the core back to sleep (not without rescheduling itself before sleeping). On Windows, how frequent the OS schedule interval itself is controlled (more like hinted) by timeBeginPeriod (it's a dreaded system-wide value). On Linux, it's defined at compile time. Both Linux & Windows now support tickless kernel (which means the OS won't schedule itself). But beware that means all but one core are tickless. There must be at least one core rescheduling itself periodically.

Thanks Matias for such a detailed reply :)

so you mean there isn't truly 'immediate wakeup' even you use condition-variable to wake up thread rather than wait timer by calling 'Sleep(ms)". So using condition-variable seems you are just asking OS scheduler to do this 'periodical checking', and calling 'Sleep()' is doing the checking yourself? If that is the case, I would assume waiting on condition-variable won't be any better if you call Sleep with right param in terms of responsiveness. (please correct me if I am wrong)

Thanks

This is a great example of why a Computer Science education is a good idea, even for a game programmer. It's been awhile for me, but we had two very relevant classes.

One was something like "Concurrent Programming", where we learned all about synchronization primitives and the theoretical underpinnings. Perhaps most importantly, all the things that can go wrong, conflicts, deadlocks, race conditions, and the like.

The second was "Operating Systems", where we learned all about process and thread management and scheduling. In particular, as I believe is common, we implemented parts of a toy OS (I think it was NachOS, in my case). This totally removed the mystery of how these "magic" synchronization primitives work. Threads and processes are just "things" that can be manipulated, same as any other part of a machine.

So, get your degree, kids! It will be worth it in the end.

Thanks for pointing the right courses for me~ (I am currently a graduate student in CS, but the course I've taken "parallel program" "Operating System" haven't cover such low level detail) Any idea where I can find good online course for this? :) thanks

A context switch between processes is expensive (mainly because each process has it's own memory space that must be saved/restored). A context switch between threads within the same process should be fairly efficient. If your producer and consumer threads are all in the same process, then you should be perfectly fine using condition variables and letting the OS handle it.

But this post suggest context switch between threads seems also very costly (Please correct me if I missed something important)

Thanks

I think you're over-engineering. If you spend most of the time in a mutex, you are either using them too much (very fine-grained access to shared data is a bad idea), or your work-jobs are not big enough.

I think I won't spend too much time inside a mutex. The concern is 'touching' mutex is very costly: think about a busy-waiting threadpool implementation with tiny jobs or with jobqueue empty, the jobqueue will be frequently accessed, so with mutex, the overhead is seems scary....

The other thing you may want to watch out for is premature optimization. You make design decisions to avoid problems that yet do not exist. That is a highly dangerous game, where expensive mistakes are often made. The simple reason for that is, we humans cannot predict where the bottleneck of the processor is going to end up. I play the game of guessing where it is, just before I profile, and in the past 30 years, I have been consistently wrong. In other words, there is a big chance you are incorrect in your assumptions.

That's definitely true for me most of the time. But my advantage is that I am still in school, so no industry deadline pushes me :-) And I have found always_thinking_for_the_best_solution way forced me keep learning new thing while doing fun development~ But I will definite take your advise on that once I go to industry :)

Thanks for pointing the right courses for me~ (I am currently a graduate student in CS, but the course I've taken "parallel program" "Operating System" haven't cover such low level detail) Any idea where I can find good online course for this? :) thanks

That is discouraging. Well, I can't personally vouch for it, but MIT's OS class seems to hit all of the right areas: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-828-operating-system-engineering-fall-2012/

Good luck!
Geoff

But this post suggest context switch between threads seems also very costly (Please correct me if I missed something important)

That post is really on the subject of kernel mode vs user mode synchronization, which is related to, but separate from the subject of context switching. Either method will block and potentially switch out a thread. On a side note, if you only ever create no more threads than there are cores to run on, you'll never have a thread switched out, but you will still have to deal with synchronization.

Regarding synchronization, if the overhead of the synchronization is genuinely an issue, then the solution isn't in the method of synchronization but the design of the system. Specifically, you've broken your tasks down too small. Take the trivial task of summing a million floats as an example. In the extreme, if we break the problem down to passing and summing pairs of floats to the worker threads, then synchronization becomes a major overhead no matter what solution you use. Never mind that you've completely destroyed your cache hit rate in the process (another topic entirely). If instead we block out large chunks of floats for each worker to process (ie send blocks of 250k floats to each of 4 workers), then synchronization becomes insignificant no matter what solution you use.

But this post suggest context switch between threads seems also very costly (Please correct me if I missed something important)

A Win32 critical section is a user-mode spinlock which will after a thousand iterations block on a NtKeyedEvent. Which is a lightweight process-specific kernel object that is able to block with a "key" (usually an address, but needs not be). Very much like a futex under Linux with FUTEX_PRIVATE_FLAG given(only just, to be truthful, one must say a futex is like a keyed event, not the other way around -- kev was there first). The keyed event does not need to fulfill the same guarantees as the Win32 mutex below.

A Win32 mutex is a heavyweight kernel object which can be duplicated and shared between different processes and guarantees that any access to it is synchronized accordingly, and overall order (across processes) is correct. This is a much, much different thing.

In short, a critical section means "8-9 cycles best case" if there is zero lock contention, "few dozen to a hundred cycles" in the normal case, and ten thousand cycles followed by a mode switch in the very worst case. A mutex means a mode switch, and rescheduling every single time. User/kernel transitions are not as expensive as they used to be with modern operating systems and modern processors since they are no longer (necessarily) context switches but merely mode changes. However, they are by no means cheap operations, rescheduling is not free, and in case a different thread is switched to, the mode change becomes a context switch (with TLB gone and everything). Whenever you call a function that goes into the kernel, assume that you are possibly/probably burning something like 5,000-10,000 cycles.

Now, a context switch between two processes also includes moving pages from the working set to the standby list and the other way around, and killing the caches. Which, again, is not a free operation.