Consequences of the scheduling algorithm: Low priority threads can run even when higher priority threads are running

Raymond Chen


Just because you have a thread running at a higher priority
level doesn’t mean that no threads of lower priority will ever run.

Occasionally, I see people write multi-threaded code and put
one thread’s priority higher than the other, assuming that
this will prevent the lower-priority thread from interfering
with the operation of the higher-priority thread
so that they don’t need to do any explicit synchronization.

BOOL g_fReady;
int g_iResult;
// high priority thread
SetResult(int iResult)
g_fReady = TRUE;
g_iResult = iResult;

// low priority thread
if (g_fReady)

Let’s ignore the cache coherency elephant in the room.
If there were a guarantee that the low priority thread will never
ever run while the high priority thread is running, this code looks
okay. Even if the high priority thread interrupts and sets
the result after the low priority thread has checked the ready flag,
all that happens is that the low priority thread misses out on the result.
(This is hardly a new issue, since

the principle of relativity of simultaneity

says that this was a possibility anyway.)

However, there is no guarantee that the low priority thread can’t
interfere with the high priority thread.

The scheduler’s rule is to look for the thread with the highest
priority that is “runnable”, i.e., ready to run,
and assign it to a CPU for execution.
To be ready to run, a thread cannot be blocked on anything,
and it can’t already be running on another CPU.
If there is a tie among runnable threads for the highest priority,
then the scheduler shares the CPU among them roughly equally.

You might think that, given these rules,
as long as there is a high priority thread that is runnable,
then no lower-priority thread will run.
But that’s not true.

Consider the case of a multi-processor system
(and with the advent of hyperthreading, this is
becoming more and more prevalent),
where there are two runnable threads, one with higher priority
than the other.
The scheduler will first assign the high-priority thread
to one of the processors.
But it still has a spare CPU to burn,
so the low-priority thread will be assigned to the second CPU.
You now have a lower priority thread running simultaneously
as a higher priority thread.

Of course, another way a lower priority thread can run even
though there are higher priority threads in the system is
simply that all the higher priority threads are blocked.
In addition to the cases you might expect, namely
waiting on a synchronization object such as a semaphore
or a critical section,
a thread can also block for I/O or for paging.
Paging is the wildcard here, since you don’t have any
control over when the system might decide to page out
the memory you were using due to memory pressure
elsewhere in the system.

The moral of the story is that thread priorities are not
a substitute for proper synchronization.

Next time, a reversal of this fallacy.

Raymond Chen
Raymond Chen

Follow Raymond