Fair Critical Section
A critical section is fair, if all threads entering a critical section exit in the same order in which they arrived.
Every time a thread enters sleep to wait, the sleeping time can be slightly different from thread to thread. The same variable time situation happens when the kernel is switching between threads (thread context switch). This non-determinism results in dice-throwing-like decision making process about which thread will enter next. A special design is required to guarantee that all threads are passed through the critical section in the order in which they arrived.
The problem develops when the number of threads waiting in the critical sections "Enter" waiting lock increases to "large" numbers. This happens, when most of the time spent by the algorithm is spent within the single threaded block of code, rather than in the multi-threaded block of code:
There can be different scenarios, where the queue of threads inside of the cs.Enter becomes large.
Performance degradation for unfair critical sections
If the critical section is not fair, a performance penalty of 2-3x for 16 core CPUs can sometimes be observed. This penalty grows with increasing CPU core count. The performance is also expected to vary considerably from run to run due to the dice throwing (random) nature of threads passing the Enter lock.
The primary cause of the performance degradation is that some threads remain stuck in the waiting loop of the critical sections Enter lock, while other threads may pass this lock multiple times. This can result in
- The CPU is underutilized, because not all CPU cores are used even though sufficient threads have been launched.
- Because some threads are stuck in the waiting loop, others cannot continue until they obtain the processing results of those which are stuck.
Implementation of a fair critical section
Although this code is open source, the license remains commercial and is included with the MtxVec Math library.