Difference between the Windows and Linux thread scheduler

Question

As far as I can tell, both use:

• Multilevel feedback queue
• Priority levels (different range)
• Both manage threads and not the process

But what are the big differences?

Answer 1

According to Scheduling Priorities at MSDN:

Threads are scheduled to run based on their scheduling priority. Each thread is assigned a scheduling priority. The priority levels range from zero (lowest priority) to 31 (highest priority). Only the zero-page thread can have a priority of zero. (The zero-page thread is a system thread responsible for zeroing any free pages when there are no other threads that need to run.)

The system treats all threads with the same priority as equal. The system assigns time slices in a round-robin fashion to all threads with the highest priority. If none of these threads are ready to run, the system assigns time slices in a round-robin fashion to all threads with the next highest priority. If a higher-priority thread becomes available to run, the system ceases to execute the lower-priority thread (without allowing it to finish using its time slice), and assigns a full time slice to the higher-priority thread. The priority of each thread is determined by the following criteria:

• The priority class of its process
• The priority level of the thread within the priority class of its process

I believe this thread scheduler describes an algorithm called multilevel queue, which is a much simpler scheduling algorithm than multilevel feedback queue. Note that Windows' process scheduler uses multilevel feedback queue, according to Wikipedia. Since Windows 7 and Windows Server 2008 R2, there is also User-Mode Scheduling which lets processes manage their own threads scheduling.

As mentioned by others, Linux treats process and threads the same from scheduling perspective. Process/thread scheduling in Linux is configurable, there are various scheduling algorithms and some can be configured by recompiling the kernel:

• An O(n) scheduler was default in 2.4
• An O(1) scheduler was default in 2.6 before 2.6.23
• Completely Fair Scheduler is default scheduler since 2.6.23 onwards
• Brain Fuck Scheduler is a popular third-party scheduler available as a set of patches
• Earliest Deadline-first scheduler is available since 3.14 designed for real-time workload

Note that default above means default in vanilla kernel. Some distros ship with a default kernel that is preconfigured to use different default scheduler.

In addition to the scheduling algorithm, there are also scheduler policies: SCHED_FIFO, SCHED_BATCH, SCHED_IDLE, SCHED_OTHER, and SCHED_RR; which can be changed at runtime which describes the kind of workload that a process has.

The current default scheduler Completely Fair Scheduler, uses a red-black tree to maintain scheduling fairness. From Inside the Linux 2.6 Completely Fair Scheduler:

The main idea behind the CFS is to maintain balance (fairness) in providing processor time to tasks. This means processes should be given a fair amount of the processor. When the time for tasks is out of balance (meaning that one or more tasks are not given a fair amount of time relative to others), then those out-of-balance tasks should be given time to execute.

To determine the balance, the CFS maintains the amount of time provided to a given task in what's called the virtual runtime. The smaller a task's virtual runtime—meaning the smaller amount of time a task has been permitted access to the processor—the higher its need for the processor. The CFS also includes the concept of sleeper fairness to ensure that tasks that are not currently runnable (for example, waiting for I/O) receive a comparable share of the processor when they eventually need it.

But rather than maintain the tasks in a run queue, as has been done in prior Linux schedulers, the CFS maintains a time-ordered red-black tree (see Figure 1). A red-black tree is a tree with a couple of interesting and useful properties. First, it's self-balancing, which means that no path in the tree will ever be more than twice as long as any other. Second, operations on the tree occur in O(log n) time (where n is the number of nodes in the tree). This means that you can insert or delete a task quickly and efficiently.

So main differences:

Windows

• Process scheduling using Multilevel feedback queue + Thread scheduling using Multilevel queue. The thread scheduler simply picks the highest priority thread, the process scheduler is smarter and uses feedback queue.

Linux

• Unified process and thread scheduler, configurable, by default uses CFS. The scheduler uses a metric of fairness and uses priority to skew the distribution of CPU to higher priority processes.

Answer 2

If you are refering to the kernel scheduler (and not a periodic task scheduler like some comments suggest), in Linux is pretty easy: in terms of scheduling, Linux makes no difference between threads and processes. From the kernel point of view, they are just scheduling units; the difference relies in the weight of the context switch. This is sometimes called a one-to-one threading model.

As there is less information available regarding Windows internals, little can be said. However, Windows has historically differentiated between processes and threads so it is more likely that they are treated differently in terms of scheduling.

Answer 3

C2H5OH, Why would you say there's no documentation on Windows Internals when everything is available? Beats me... You can read the most of the basics here, http://msdn.microsoft.com/en-us/library/windows/desktop/ms684259(v=vs.85).aspx

There's an article on Wikipedia (Threads (computing)) which states most of the differences, but without cited sources, so...