The following events might require thread dispatching:. A thread becomes ready to execute—for example, a thread has been newly created or has just been released from the wait state.
A thread leaves the running state because its time quantum ends, it terminates, it yields execution, or it enters a wait state. At each of these junctions, Windows must determine which thread should run next. When Windows selects a new thread to run, it performs a context switch to it. As already noted, Windows schedules at the thread granularity.
Because scheduling decisions are made strictly on a thread basis, no consideration is given to what process the thread belongs to. To understand the thread-scheduling algorithms, you must first understand the priority levels that Windows uses. As illustrated in Figure , internally Windows uses 32 priority levels, ranging from 0 through These values divide up as follows:.
Thread priority levels are assigned from two different perspectives: those of the Windows API and those of the Windows kernel. In the Windows API, each thread has a base priority that is a function of its process priority class and its relative thread priority.
The mapping from Windows priority to internal Windows numeric priority is shown in Figure Whereas a process has only a single base priority value, each thread has two priority values: current and base. Scheduling decisions are made based on the current priority. As explained in the following section on priority boosting, the system under certain circumstances increases the priority of threads in the dynamic range 1 through 15 for brief periods.
Windows never adjusts the priority of threads in the real-time range 16 through 31 , so they always have the same base and current priority. A process, by default, inherits its base priority from the process that created it. This behavior can be overridden on the CreateProcess function or by using the command-line start command.
A process priority can also be changed after being created by using the SetPriorityClass function or various tools that expose that function, such as Task Manager and Process Explorer by right-clicking on the process and choosing a new priority class. For example, you can lower the priority of a CPU-intensive process so that it does not interfere with normal system activities.
Changing the priority of a process changes the thread priorities up or down, but their relative settings remain the same. Normally, the process base priority and therefore the starting thread base priority will default to the value at the middle of each process priority range 24, 13, 10, 8, 6, or 4. However, some Windows system processes such as the Session Manager, service controller, and local security authentication server have a base process priority slightly higher than the default for the Normal class 8.
This higher default value ensures that the threads in these processes will all start at a higher priority than the default value of 8. These system processes use an internal system call NtSetInformationProcess to set their process base priority to a numeric value other than the normal default starting base priority. For more information, see the Windows API reference documentation. Sets attributes for a job; some of the attributes affect scheduling, such as affinity and priority.
See the Job Objects section later in the chapter for a description of the job object. Returns details about processor hardware configuration for hyperthreaded and NUMA systems. Returns or sets the ability for Windows to boost the priority of a thread temporarily. This ability applies only to threads in the dynamic range. Returns or sets the default priority boost control state of the current process. This function is used to set the thread priority boost control state when a thread is created.
Yields execution to another thread at priority 1 or higher that is ready to run on the current processor. Puts the current thread into a wait state for a specified time interval figured in milliseconds [msec]. You can change and view the base process priority with Task Manager and Process Explorer. You can kill individual threads in a process with Process Explorer which should be done, of course, with extreme care. While it might be useful to increase or lower the priority of a process, it typically does not make sense to adjust individual thread priorities within a process because only a person who thoroughly understands the program in other words, typically only the developer himself would understand the relative importance of the threads within the process.
The only way to specify a starting priority class for a process is with the start command in the Windows command prompt. This runs the command prompt, executes the command on the command line, and terminates the command prompt. Notepad should open. Run Process Explorer and select Notepad. Double-click on Notepad. Notice that the dynamic priority of the thread in Notepad is This matches the real-time value shown in this image:.
Task Manager can show you similar information. Right-click on the Notepad. It permits the administrator to configure policies that specify CPU utilization, affinity settings, and memory limits both physical and virtual for processes. In addition, WSRM can generate resource utilization reports that can be used for accounting and verification of service-level agreements with users. Policies can be applied for specific applications by matching the name of the image with or without specific command-line arguments , users, or groups.
The policies can be scheduled to take effect at certain periods or can be enabled all the time. After you have set a resource-allocation policy to manage specific processes, the WSRM service monitors CPU consumption of managed processes and adjusts process base priorities when those processes do not meet their target CPU allocations.
The virtual memory limit is implemented by the service checking the private virtual memory consumed by the processes. See Chapter 9 for an explanation of these memory limits. This behavior could be used to detect a process with a memory leak before it consumes all the available committed virtual memory on the system. You can raise or lower thread priorities within the dynamic range in any application; however, you must have the increase scheduling priority privilege to enter the real-time range.
Be aware that many important Windows kernel-mode system threads run in the real-time priority range, so if threads spend excessive time running in this range, they might block critical system functions such as in the memory manager, cache manager, or other device drivers. As illustrated in the following figure showing the x86 interrupt request levels IRQLs , although Windows has a set of priorities called real-time , they are not real-time in the common definition of the term.
For a description of how Windows uses interrupt levels, see Chapter 3. User-mode code always runs at IRQL 0. Because of this, no user-mode thread, regardless of its priority, blocks hardware interrupts although high-priority real-time threads can block the execution of important system threads.
For more information on APCs, see Chapter 3. Threads running in kernel mode can raise IRQL to higher levels, though—for example, while executing a system call that involves thread dispatching. Before you can comprehend the thread-scheduling algorithms, you need to understand the various execution states that a thread can be in.
Figure illustrates the state transitions for threads. The numeric values shown represent the value of the thread state performance counter. More details on what happens at each transition are included later in this section. Ready A thread in the ready state is waiting to execute. When looking for a thread to execute, the dispatcher considers only the pool of threads in the ready state. Deferred ready This state is used for threads that have been selected to run on a specific processor but have not yet been scheduled.
This state exists so that the kernel can minimize the amount of time the systemwide lock on the scheduling database is held.
Standby A thread in the standby state has been selected to run next on a particular processor. When the correct conditions exist, the dispatcher performs a context switch to this thread. Only one thread can be in the standby state for each processor on the system.
Note that a thread can be preempted out of the standby state before it ever executes if, for example, a higher priority thread becomes runnable before the standby thread begins execution. Running Once the dispatcher performs a context switch to a thread, the thread enters the running state and executes. Gate Waiting When a thread does a wait on a gate dispatcher object see Chapter 3 for more information on gates , it enters the gate waiting state instead of the waiting state.
Transition A thread enters the transition state if it is ready for execution but its kernel stack is paged out of memory. Once its kernel stack is brought back into memory, the thread enters the ready state. Terminated When a thread finishes executing, it enters the terminated state. Once the thread is terminated, the executive thread block the data structure in nonpaged pool that describes the thread might or might not be deallocated.
The object manager sets policy regarding when to delete the object. Initialized This state is used internally while a thread is being created. You can watch thread-scheduling state changes with the Performance tool in Windows. To watch thread-scheduling state changes by using the Performance tool, follow these steps:. Start the Performance tool by selecting Programs from the Start menu and then selecting Reliability and Performance Monitor from the Administrative Tools menu.
Click on the Performance Monitor entry under Monitoring Tools. Click the Graph tab, and change the chart vertical scale maximum to 7.
Click OK. Click the Add button on the toolbar to bring up the Add Counters dialog box. Select the Thread performance object, and then select the Thread State counter. Select the Show Description check box to see the definition of the values:. Before you click Add, you should see something like the following dialog box. You should see the state of the Notepad thread the very top line in the following figure as a 5, which, as shown in the explanation text you saw under step 7, represents the waiting state because the thread is waiting for GUI input :.
Notice that one thread in the Mmc process running the Performance tool snap-in is in the running state number 2. To make thread-scheduling decisions, the kernel maintains a set of data structures known collectively as the dispatcher database , illustrated in Figure The dispatcher database keeps track of which threads are waiting to execute and which processors are executing which threads.
To improve scalability, including thread-dispatching concurrency, Windows multiprocessor systems have per-processor dispatcher ready queues, as illustrated in Figure In this way each CPU can check its own ready queues for the next thread to run without having to lock the systemwide ready queues. Versions of Windows before Windows Server used a global database. The per-processor ready queues, as well as the per-processor ready summary, are part of the processor control block PRCB structure.
To see the fields in the PRCB, type dt nt! The names of each component that we will talk about in italics are field members of the PRCB structure. The dispatcher ready queues DispatcherReadyListHead contain the threads that are in the ready state, waiting to be scheduled for execution.
There is one queue for each of the 32 priority levels. To speed up the selection of which thread to run or preempt, Windows maintains a bit bit mask called the ready summary ReadySummary.
Each bit set indicates one or more threads in the ready queue for that priority level. Bit 0 represents priority 0, and so on. Instead of scanning each ready list to see whether it is empty or not which would make scheduling decisions dependent on the number of different priority threads , a single bit scan is performed as a native processor command to find the highest bit set. Regardless of the number of threads in the ready queue, this operation takes a constant amount of time, which is why you may sometimes see the Windows scheduling algorithm referred to as an O 1 , or constant time, algorithm.
Bitmask of priority levels that have one or more ready threads. For an explanation of interrupt priority levels, see the Trap Dispatching section in Chapter 3. However, on a multiprocessor system, more is required than just raising IRQL because other processors can simultaneously raise to the same IRQL and attempt to operate on the dispatcher database.
How Windows synchronizes access to the dispatcher database is explained in the Multiprocessor Systems section later in the chapter. As mentioned earlier in the chapter, a quantum is the amount of time a thread gets to run before Windows checks to see whether another thread at the same priority is waiting to run. If a thread completes its quantum and there are no other threads at its priority, Windows permits the thread to run for another quantum.
On Windows Vista, threads run by default for 2 clock intervals; on Windows Server systems, by default, a thread runs for 12 clock intervals.
The rationale for the longer default value on server systems is to minimize context switching. By having a longer quantum, server applications that wake up as the result of a client request have a better chance of completing the request and going back into a wait state before their quantum ends. The length of the clock interval varies according to the hardware platform. The frequency of the clock interrupts is up to the HAL, not the kernel.
For example, the clock interval for most x86 uniprocessors is about 10 milliseconds, and for most x86 and x64 multiprocessors it is about 15 milliseconds. This clock interval is stored in the kernel variable KeMaximumIncrement as hundreds of nanoseconds. Because of changes in thread run-time accounting in Windows Vista briefly mentioned earlier in the thread activity experiment , although threads still run in units of clock intervals, the system does not use the count of clock ticks as the deciding factor for how long a thread has run and whether its quantum has expired.
Instead, when the system starts up, a calculation is made whose result is the number of clock cycles that each quantum is equivalent to this value is stored in the kernel variable KiCyclesPerClockQuantum. This calculation is made by multiplying the processor speed in Hz CPU clock cycles per second with the number of seconds it takes for one clock tick to fire based on the KeMaximumIncrement value described above. The end result of this new accounting method is that, as of Windows Vista, threads do not actually run for a quantum number based on clock ticks; they instead run for a quantum target , which represents an estimate of what the number of CPU clock cycles the thread has consumed should be when its turn would be given up.
On the other hand, because interrupt cycles are not charged to the thread, the actual clock time may be longer. To determine the clock interval, download and run the Clockres program from Windows Sysinternals www. Each process has a quantum reset value in the kernel process block. This value is used when creating new threads inside the process and is duplicated in the kernel thread block, which is then used when giving a thread a new quantum target.
As a thread runs, CPU clock cycles are charged at different events context switches, interrupts, and certain scheduling decisions. If at a clock interval timer interrupt, the number of CPU clock cycles charged has reached or passed the quantum target, then quantum end processing is triggered.
If there is another thread at the same priority waiting to run, a context switch occurs to the next thread in the ready queue. Internally, a quantum unit is represented as one third of a clock tick so one clock tick equals three quantums.
For this reason, the KiCyclesPerClockQuantum value is divided by three at the end of the calculation previously described, since the original value would describe only CPU clock cycles per clock interval timer tick.
The reason a quantum was stored internally as a fraction of a clock tick rather than as an entire tick was to allow for partial quantum decay on wait completion on versions of Windows prior to Windows Vista.
Prior versions used the clock interval timer for quantum expiration. If this adjustment were not made, it would have been possible for threads never to have their quantums reduced. For example, if a thread ran, entered a wait state, ran again, and entered another wait state but was never the currently running thread when the clock interval timer fired, it would never have its quantum charged for the time it was running.
Because threads now have CPU clock cycles charged instead of quantums, and because this no longer depends on the clock interval timer, these adjustments are not required.
Obtain your processor frequency as Windows has detected it. Here is a sample output of a dual-core Intel system running at MHz. Convert the number to Hertz Hz. This is the number of CPU clock cycles that occur each second on your system.
In this case, 2,,, cycles per second. Obtain the clock interval on your system by using clockres. This measures how long it takes before the clock fires. On the sample system used here, this interval was Convert this number to the number of times the clock interval timer fires each second.
One second is ms, so divide the number derived in step 3 by In this case, the timer fires every 0. Multiply this count by the number of cycles each second that you obtained in step 2. In our case, 44,, Remember that each quantum unit is one-third of a clock interval, so divide the number of cycles by three. In our example, this gives us 14,,, or 0xEE in hexidecimal.
This is the number of clock cycles each quantum unit should take on a system running at MHz with a clock interval of around 15 ms. To verify your calculation, dump the value of KiCyclesPerClockQuantum on your system—it should match. You can change the thread quantum for all processes, but you can choose only one of two settings: short 2 clock ticks, the default for client machines or long 12 clock ticks, the default for server systems.
By using the job object on a system running with long quantums, you can select other quantum values for the processes in the job. For more information on the job object, see the Job Objects section later in the chapter.
The dialog box displayed is shown in Figure The Programs setting designates the use of short, variable quantums—the default for Windows Vista. If you install Terminal Services on Windows Server systems and configure the server as an application server, this setting is selected so that the users on the terminal server will have the same quantum settings that would normally be set on a desktop or client system.
You might also select this manually if you were running Windows Server as your desktop operating system. The Background Services option designates the use of long, fixed quantums—the default for Windows Server systems. The only reason you might select this option on a workstation system is if you were using the workstation as a server system. One additional difference between the Programs and Background Services settings is the effect they have on the quantum of the threads in the foreground process.
This is explained in the next section. When a window is brought into the foreground on a client system, all the threads in the process containing the thread that owns the foreground window have their quantums tripled. Thus, threads in the foreground process run with a quantum of 6 clock ticks, whereas threads in other processes have the default client quantum of 2 clock ticks. In this way, when you switch away from a CPU-intensive process, the new foreground process will get proportionally more of the CPU, because when its threads run they will have a longer turn than background threads again, assuming the thread priorities are the same in both the foreground and background processes.
Note that this adjustment of quantums applies only to processes with a priority higher than Idle on systems configured to Programs in the Performance Options settings described in the previous section. Thread quantums are not changed for the foreground process on systems configured to Background Services the default on Windows Server systems.
In addition to specifying the relative length of thread quantums short or long , this registry value also defines whether or not threads in the foreground process should have their quantums boosted and if so, the amount of the boost. This value consists of 6 bits divided into the three 2-bit fields shown in Figure The fields shown in Figure can be defined as follows:.
Short vs. Long A setting of 1 specifies long, and 2 specifies short. A setting of 0 or 3 indicates that the default will be used short for Windows Vista, long for Windows Server systems. Variable vs. A setting of 0 or 3 means that the default which is variable for Windows Vista and fixed for Windows Server systems will be used.
Foreground Quantum Boost This field stored in the kernel variable PsPrioritySeperation must have a value of 0, 1, or 2. A setting of 3 is invalid and treated as 2. It is used as an index into a three-element byte array named PspForegroundQuantum to obtain the quantum for the threads in the foreground process.
The quantum for threads in background processes is taken from the first entry in this quantum table. Table shows the possible settings for PspForegroundQuantum. Windows uses a round-robin technique with a multi-level feedback queue for priority scheduling ever since NT, Though in Vista there were some smart heuristic improvements to ensure that some processes, such as the disk defragmenter, are at a lower priority in order to not interfer with foreground processes.
FIFO scheduling algorithm The FIFO scheduling algorithm is still the most common one due to its simplicity, which is suitable for massive data processing. However, it ignores the different requirements of different type of applications. There is a fixed time interval during which each thread in the system must run at least once.
First come first serve FCFS scheduling algorithm simply schedules the jobs according to their arrival time. Windows uses a round-robin technique with a multi-level feedback queue for priority scheduling ever since NT, Though in Vista there were some smart heuristic improvements to ensure that some processes, such as the disk defragmenter, are at a lower priority in order to not interfer with foreground processes.
To the best of my knowledge, Windows 7 uses the same scheduler as Vista, though there may have been minor improvements. Windows NT-based operating systems use a multilevel feedback queue. So, I feel that Windows 7 must also be using the same scheduling algorithm. The scheduler was modified in Windows Vista with the inclusion of a priority scheduler and also to use the cycle counter register of modern processors to keep track of exactly how many CPU cycles a thread has executed.
On similar lines, there may be some improvements in Windows 7 too. But the algorithm may be the same. User-mode scheduling UMS is a light-weight mechanism that applications can use to schedule their own threads. An application can switch between UMS threads in user mode without involving the system scheduler and regain control of the processor if a UMS thread blocks in the kernel. UMS threads differ from fibers in that each UMS thread has its own thread context instead of sharing the thread context of a single thread.
The ability to switch between threads in user mode makes UMS more efficient than thread pools for managing large numbers of short-duration work items that require few system calls. Sign up to join this community. The best answers are voted up and rise to the top. Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more. Scheduling algorithm used in Windows 7 Ask Question.
Asked 9 years, 3 months ago.
0コメント