Thread Scheduling, Priorities and Affinities
August 11, 2011 Leave a comment
Windows is called a preemptive multithreaded operating system because a thread can be stopped at any time and another thread can be scheduled
Suspending and Resuming a Thread
Creating a thread in the suspended state allows you to alter the thread’s environment before the thread has a chance to execute any code. Once you alter the thread’s environment, you must make the thread schedulable. You do this by calling ResumeThread and passing it the thread handle returned by the call to CreateThread (or the thread handle from the structure pointed to by the ppiProcInfo parameter passed to CreateProcess):
DWORD ResumeThread(HANDLE hThread);
A single thread can be suspended several times. If a thread is suspended three times, it must be resumed three times before it is eligible for assignment to a CPU. In addition to using the CREATE_ SUSPENDED flag when you create a thread, you can suspend a thread by calling SuspendThread:
DWORD SuspendThread(HANDLE hThread);
SuspendThread is asynchronous with respect to kernel-mode execution, but user-mode execution does not occur until the thread is resumed.
In real life, an application must be careful when it calls SuspendThread because you have no idea what the thread might be doing when you attempt to suspend it.
SuspendThread is safe only if you know exactly what the target thread is (or might be doing) and you take extreme measures to avoid problems or deadlocks caused by suspending the thread.
Note: The concept of suspending or resuming a process doesn’t exist for Windows because processes are never scheduled CPU time.
Sleeping
A thread can also tell the system that it does not want to be schedulable for a certain amount of time. This is accomplished by calling Sleep:
VOID Sleep(DWORD dwMilliseconds);
There are a few important things to notice about Sleep:
- Calling Sleep allows the thread to voluntarily give up the remainder of its time slice.
- The system makes the thread not schedulable for approximately the number of milliseconds specified. That’s right—if you tell the system you want to sleep for 100 milliseconds, you will sleep approximately that long, but possibly several seconds or minutes more.
- You can call Sleep and pass INFINITE for the dwMilliseconds parameter. This tells the system to never schedule the thread.
- You can pass 0 to Sleep. This tells the system that the calling thread relinquishes the remainder of its time slice, and it forces the system to schedule another thread.
Windows is not a real-time operating system. Your thread will probably wake up at the right time, but whether it does depends on what else is going on in the system.
Switching to Another Thread
The system offers a function called SwitchToThread that allows another schedulable thread to run if one exists:
BOOL SwitchToThread();
When you call this function, the system checks to see whether there is a thread that is being starved of CPU time. If no thread is starving, SwitchToThread returns immediately. If there is a starving thread, SwitchToThread schedules that thread (which might have a lower priority than the thread calling SwitchToThread). The starving thread is allowed to run for one time quantum and then the system scheduler operates as usual.
This function allows a thread that wants a resource to force a lower-priority thread that might currently own the resource to relinquish the resource. If no other thread can run when SwitchToThread is called, the function returns FALSE; otherwise, it returns a nonzero value.
A Thread’s Execution Times
Sometimes you want to time how long it takes a thread to perform a particular task. What many people do is write code similar to the following, taking advantage of the new GetTickCount64 function:
// Get the current time (start time). ULONGLONG qwStartTime = GetTickCount64(); // Perform complex algorithm here. // Subtract start time from current time to get duration. ULONGLONG qwElapsedTime = GetTickCount64() - qwStartTime;
This code makes a simple assumption: it won’t be interrupted. However, in a preemptive operating system, you never know when your thread will be scheduled CPU time. When CPU time is taken away from your thread, it becomes more difficult to time how long it takes your thread to perform various tasks. What we need is a function that returns the amount of CPU time that the thread has received. Fortunately, prior to Windows Vista, the operating system offers a function called GetThreadTimes that returns this information:
BOOL GetThreadTimes( HANDLE hThread, PFILETIME pftCreationTime, PFILETIME pftExitTime, PFILETIME pftKernelTime, PFILETIME pftUserTime);
Using this function, you can determine the amount of time needed to execute a complex algorithm by using code such as the following.
__int64 FileTimeToQuadWord (PFILETIME pft) {
return(Int64ShllMod32(pft->dwHighDateTime, 32) | pft->dwLowDateTime);
}
void PerformLongOperation () {
FILETIME ftKernelTimeStart, ftKernelTimeEnd;
FILETIME ftUserTimeStart, ftUserTimeEnd;
FILETIME ftDummy;
__int64 qwKernelTimeElapsed, qwUserTimeElapsed,
qwTotalTimeElapsed;
// Get starting times.
GetThreadTimes(GetCurrentThread(), &ftDummy, &ftDummy,
&ftKernelTimeStart, &ftUserTimeStart);
// Perform complex algorithm here.
// Get ending times.
GetThreadTimes(GetCurrentThread(), &ftDummy, &ftDummy,
&ftKernelTimeEnd, &ftUserTimeEnd);
// Get the elapsed kernel and user times by converting the start
// and end times from FILETIMEs to quad words, and then subtract
// the start times from the end times.
qwKernelTimeElapsed = FileTimeToQuadWord(&ftKernelTimeEnd) -
FileTimeToQuadWord(&ftKernelTimeStart);
qwUserTimeElapsed = FileTimeToQuadWord(&ftUserTimeEnd) -
FileTimeToQuadWord(&ftUserTimeStart);
// Get total time duration by adding the kernel and user times.
qwTotalTimeElapsed = qwKernelTimeElapsed + qwUserTimeElapsed;
// The total elapsed time is in qwTotalTimeElapsed.
}
Thread Context
The CONTEXT structure allows the system to remember a thread’s state so that the thread can pick up where it left off the next time it has a CPU to run on.
Windows actually lets you look inside a thread’s kernel object and grab its current set of CPU registers. To do this, you simply call GetThreadContext:
BOOL GetThreadContext( HANDLE hThread, PCONTEXT pContext);
You should call SuspendThread before calling GetThreadContext; otherwise, the thread might be scheduled and the thread’s context might be different from what you get back.
It’s amazing how much power Windows offers the developer! But, if you think that’s cool, you’re gonna love this: Windows lets you change the members in the CONTEXT structure and then place the new register values back into the thread’s kernel object by calling SetThreadContext:
BOOL SetThreadContext( HANDLE hThread, CONST CONTEXT *pContext);
Again, the thread whose context you’re changing should be suspended first or the results will be unpredictable.
Before calling SetThreadContext, you must initialize the ContextFlags member of CONTEXT again, as shown here:
CONTEXT Context; // Stop the thread from running. SuspendThread(hThread); // Get the thread's context registers. Context.ContextFlags = CONTEXT_CONTROL; GetThreadContext(hThread, &Context); // Make the instruction pointer point to the address of your choice. // Here I've arbitrarily set the address instruction pointer to // 0x00010000. Context.Eip = 0x00010000; // Set the thread's registers to reflect the changed values. // It's not really necessary to reset the ContextFlags member // because it was set earlier. Context.ContextFlags = CONTEXT_CONTROL; SetThreadContext(hThread, &Context); // Resuming the thread will cause it to begin execution // at address 0x00010000. ResumeThread(hThread);
This will probably cause an access violation in the remote thread; the unhandled exception message box will be presented to the user, and the remote process will be terminated. That’s right—the remote process will be terminated, not your process. You will have successfully crashed another process while yours continues to execute just fine!
Thread Priorities
Every thread is assigned a priority number ranging from 0 (the lowest) to 31 (the highest). When the system decides which thread to assign to a CPU, it examines the priority 31 threads first and schedules them in a round-robin fashion. If a priority 31 thread is schedulable, it is assigned to a CPU. At the end of this thread’s time slice, the system checks to see whether there is another priority 31 thread that can run; if so, it allows that thread to be assigned to a CPU.
Starvation occurs when higher-priority threads use so much CPU time that they prevent lower-priority threads from executing.
Higher-priority threads always preempt lower-priority threads, regardless of what the lower-priority threads are executing.
when the system boots, it creates a special thread called the zero page thread. This thread is assigned priority 0 and is the only thread in the entire system that runs at priority 0. The zero page thread is responsible for zeroing any free pages of RAM in the system when there are no other threads that need to perform work.
Application developers never work with priority levels. Instead, the system maps the process’ priority class and a thread’s relative priority to a priority level. It is precisely this mapping that Microsoft does not want to commit to. In fact, this mapping has changed between versions of the system.
In general, a thread with a high priority level should not be schedulable most of the time. When the thread has something to do, it quickly gets CPU time. At this point, the thread should execute as few CPU instructions as possible and go back to sleep, waiting to be schedulable again. In contrast, a thread with a low priority level can remain schedulable and execute a lot of CPU instructions to do its work. If you follow these rules, the entire operating system will be responsive to its users.
To create a thread with an idle relative thread priority, you execute code similar to the following:
DWORD dwThreadID; HANDLE hThread = CreateThread(NULL, 0, ThreadFunc, NULL, CREATE_SUSPENDED, &dwThreadID); SetThreadPriority(hThread, THREAD_PRIORITY_IDLE); ResumeThread(hThread); CloseHandle(hThread);
Dynamically Boosting Thread Priority Levels
The system determines the thread’s priority level by combining a thread’s relative priority with the priority class of the thread’s process. This is sometimes referred to as the thread’s base priority level. Occasionally, the system boosts the priority level of a thread—usually in response to some I/O event such as a window message or a disk read.
For example, a thread with a normal thread priority in a high-priority class process has a base priority level of 13. If the user presses a key, the system places a WM_KEYDOWN message in the thread’s queue. Because a message has appeared in the thread’s queue, the thread is schedulable. In addition, the keyboard device driver can tell the system to temporarily boost the thread’s level. So the thread might be boosted by 2 and have a current priority level of 15.
The thread is scheduled for one time slice at priority 15. Once that time slice expires, the system drops the thread’s priority by 1 to 14 for the next time slice. The thread’s third time slice is executed with a priority level of 13. Any additional time slices required by the thread are executed at priority level 13, the thread’s base priority level.
Another situation causes the system to dynamically boost a thread’s priority level. Imagine a priority 4 thread that is ready to run but cannot because a priority 8 thread is constantly schedulable. In this scenario, the priority 4 thread is being starved of CPU time. When the system detects that a thread has been starved of CPU time for about three to four seconds, it dynamically boosts the starving thread’s priority to 15 and allows that thread to run for twice its time quantum. When the double time quantum expires, the thread’s priority immediately returns to its base priority.
