Threads in Windows: A deep-dive

What is a thread?

A thread is a unit of execution belonging under a specific process. These are logical threads, specifically. Physical threads refer to actual threads in your CPU, while logical threads are the operating system's way of representing threads for easier management. We will be talking about logical threads.

Logical threads are how the operating system represents one line of execution, it contains all required information for execution. This allows the system to switch between threads mid-execution. With various programs running 1 or more threads, all at the same time, thread scheduling is critical.

The most important attributes of a thread are an access token, priority, context, state and affinity. There are two different priorities; there is the base priority which is inherited from the priority class of the process, then there is the dynamic priority which is determined at runtime and will adjust the base priority to form the final priority level_._ The priority levels range from 0 to 32. In addition to these attributes, threads have certain resources, such as a stack and local thread storage, as well as structures describing the thread.

There are primarily 3 states for a thread:

• Running: The thread is executing within one of the logical processors.
• Ready: The thread is ready to execute within one of the logical processors.
• Waiting: The thread is waiting on a signal from another Dispatcher Kernel Object.

There are also a few others, however they are just describing a transition such as initialization, beginning to execute, or termination.

A Dispatcher Kernel Object (a.k.a. Waitable Object) is an object which can be in a waiting state, until a signal is received from another object. Threads are also Dispatcher Kernel Objects.

Access tokens describe the access rights of a thread or process, they are used by the kernel to validate access rights to a securable object. When a user logs in, and their password is validated, the operating system creates an access token. This access token will be inherited by every process running on behalf of this user. There are mainly two types of tokens, primary tokens and impersonation tokens.

Context reflects the state of the CPU_._ It mainly consists of the current thread’s stack status and the current CPU registers' status, saved in a CONTEXT structure. By saving the context and switching to another context, the scheduler can pause a thread, execute another, and later resume where it left off. The most important parts of the context are the stack pointer (register ESP/RSP) and instruction pointer (register EIP/RIP).

Affinity is a 64-bit value (a bit mask), which tells the scheduler on which logical processors the threads of a process are allowed to run. There is soft affinity, which allows a process to run on every logical processor, and there is hard affinity, which restricts execution for a certain amount of logical processors. Hard affinity is not commonly used.

Another central component of the thread is the stack, which is primarily used for local variables, function call frames (call stack), and passing function parameters depending on the calling convention. Every thread has its own stack, two actually, one for user mode and one for kernel mode.

Important data structures

The Thread Environment Block (TEB) is the user mode representation of a thread. The current thread's TEB can be easily accessed through a pointer stored in the GS register on 64-bit systems or the FS register on 32-bit systems. It holds pointers to the PEB, the TLS, and some information about the thread, among other things. The TEBs of other threads can be accessed through the NtQueryInformationThread API, provided you have sufficient access rights.

The ETHREAD structure is the kernel mode representation of a thread, specifically of the higher part of the kernel, the executive. It is a thread object as exposed by the Object Manager. This structure begins with the core KTHREAD structure, but beyond this, it varies greatly across versions.

The KTHREAD structure is the kernel mode representation of a thread, specifically of the lower part of the kernel, the core kernel. It is actually a part of the larger ETHREAD structure, the core of it. This structure is not stable, it varies greatly across versions.

Thread Local Storage (TLS) is another central part of threads. While the stack stores local variables, the Thread Local Storage allows for the use of global variables.

Thread scheduling

The thread scheduling functionality is scattered through different kernel components, and it is collectively called the kernel scheduler. One of the primary factors in scheduling is the base priority and dynamic priority.

For sake of simplicity, let's imagine a system with only one CPU core. With only one core, all threads with the "Ready" state are arranged into a "Ready queue", sorted from highest to lowest priority level. If multiple threads in the ready queue have the same, highest priority, they will all be given time to execute. This happens in a concurrent fashion, they will be switching back and forth between tasks, creating the illusion of them running in parallel.

The scheduler maintains a set of data structures collectively referred to as the dispatcher database. It keeps track of threads' states, as well as the threads executed by each logical processor. Ready queues are maintained per each logical processor group, for functionality such as thread concurrency. A separate ready queue is maintained for each priority level. In addition, a ready summary is kept. It is a 32-bit bitmask where each bit represents a different priority ready queue. If a bit is set, it indicates that there is one or more ready threads in that priority level. This way you don't need to scan each queue, you can simply find the highest bit set.

The amount of execution time given to a thread before switching context, is called a quantum, and it can vary from system to system, and process to process. It's something like 31ms, to give a sense of the scale.

As Windows implements a pre-emptive scheduler, threads are not guaranteed to run for the full quantum. A context switch is primarily caused by the following events:

• The quantum finishing
• A higher priority thread switching state to "Ready"
• The running thread beginning to wait on a dispatcher kernel object, i.e. switching state to "Waiting"

Before switching to another thread, the logical processor in question will need to determine which thread to run next, and save the current logical thread's context, so it may be continued. Once this is out of the way, it can load the next threads context, i.e. start executing as that logical thread.

To select the next thread to be loaded for a logical processor, the scheduler can look at the ready queue of said logical processor and pick the one(s) with top priority. If none are found, execution will be given to an idle thread. We will not go into the internal workings of idle threads, as they are not very interesting to us, and the name is quite self-explanatory.

Threads may also be suspended explicitly with the SuspendThread API, and resumed with the ResumeThread API. These two APIs simply increment and decrement a suspension counter. Until this counter is at 0, the thread can not execute. Under the hood suspension happens by queuing a kernel APC to the thread. Once the thread is switched to execute, the APC will first run, putting the thread into a waiting state until the suspension counter reaches zero.

In addition, you may freeze a process, which puts all of its threads into a suspended state, which cannot be resumed with ResumeProcess. A frozen process can be resumed by thawing. Deep-freezing adds another constraint; new threads can not be created. Process and thread freezing is not directly exposed to user mode.

Multiprocessor systems

When the system has more than one core, scheduling becomes more complicated. Instead of simply running the highest priority threads, Windows tries to schedule threads in the most optimal logical processor for that thread, taking into account factors such as the threads preferred and previous processors.

In the kernel thread control block (KTHREAD), three CPU numbers are stored; the ideal processor, the processor that was last used, and the next processor that will be used or is in use currently. The ideal processor is chosen when a thread is created, by using a seed in the process control block (_KPROCESS_). For example, the 0th processes 0th thread is assigned an ideal processor of 0, the 1st thread an ideal processor of 1, and so on. In the next, 1st process the 0th thread will instead be assigned an ideal processor of 1, and so on. This way threads are spread across processors.