Thread scheduler and deferred procedure calls

NTDEV
1

Hi

I know that The Windows thread scheduling and DPCs(I mean DPCForIsr) run at at IRQL DISPATCH_LEVEL.

“When the clock interrupt is generated, the clock interrupt handler generally increments the counter of the current thread to calculate the total execution time of that thread, and decrements its quantum time remaining by 1. When the counter drops to zero, the thread scheduler has to be invoked to choose the next thread to be executed on that processor and dispatcher to perform a context switch. Since the clock interrupt occurs at a much higher IRQL, it will be desirable to perform this thread dispatching which is a less critical task at a later time when the processor’s IRQL drops. So the clock interrupt handler requests a DPC object and adds it to the end of the DPC queue which will process the dispatching when the processor’s IRQL drops to DPC/Dispatch level.”

and

“By default, all DPCs are set to medium priority. When the processor drops to an IRQL of Dispatch/DPC level, it checks the DPC queue for any pending DPCs and executes them until the queue is empty or some other interrupt with a higher IRQL occurs.”
http://en.wikipedia.org/wiki/Deferred_Procedure_Call

My question is:
If a DPC queue has one Thread scheduler and 2 DpcforIsr, How does windows execute these DPC routines?

I am asking this because if it executes Thread scheduler first and it schedule threads… This must be useless. Because there are 2 more DPCs in the queue and windows doesn’t execute thread while other DPCs are in the queue. While DPCForIsrs are working maybe another thread scheduler DPC will be sent.

So, Does windows execute drivers’ DPCs first and then if there is no drivers’ DPC in the queue, starts to execute thread scheduler and so threads are able to run in its quantas??

Is my explanation right?
Can you please help me the understand that mechanism.
Thanks.

2

xxxxx@gmail.com wrote:

Hi

I know that The Windows thread scheduling and DPCs(I mean DPCForIsr) run at at IRQL DISPATCH_LEVEL.
…
My question is:
If a DPC queue has one Thread scheduler and 2 DpcforIsr, How does windows execute these DPC routines?

The thread scheduler DPC will CHOOSE which normal thread to run next.
The thread it chooses will not actually run until all of the DPCs are
finished and the IRQL drops below DISPATCH_LEVEL.

So, Does windows execute drivers’ DPCs first and then if there is no drivers’ DPC in the queue, starts to execute thread scheduler and so threads are able to run in its quantas??

Not necessarily. The thread scheduler does not START the thread. It
merely prepares it for execution when the processor returns to its
normal passive level state and shifts back to user mode.

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

3

“The thread it chooses will not actually run until all of the DPCs are finished”

OK. I understand that “clock interrupt” is working permanently, and it always adds DPC for thread scheduler when counter drops to zero. And if am not wrong this how windows works.

But what will happen if all of the DPCs execution time expires quantum time of the previously selected thread? So new DPC for thread scheduler must be added to tail. And execution of previously DPC for thread scheduler is useless. Right?

Isn’t that possible situation? I mean can’t be execution time of other DPCs in queue greater than quantum time?

4

wrote in message news:xxxxx@ntdev…
> “The thread it chooses will not actually run until all of the DPCs are
> finished”
>
> OK. I understand that “clock interrupt” is working permanently, and it
> always adds DPC for thread scheduler when counter drops to zero. And if am
> not wrong this how windows works.
>
> But what will happen if all of the DPCs execution time expires quantum
> time of the previously selected thread? So new DPC for thread scheduler
> must be added to tail. And execution of previously DPC for thread
> scheduler is useless. Right?
>
> Isn’t that possible situation? I mean can’t be execution time of other
> DPCs in queue greater than quantum time?

There is an article by M. Russinovich on technet that explains how
the scheduler of NT6 was fixed to compensate threads for loss of interrupt &
DPC time.

Also, NT6 has a new type of “threaded” DPCs that can be preempted by
realtime threads
(it looks like they are run by some kernel worker thread, so they are
delayed at least
until this thread gets the CPU).

Regards,
–PA

5

> Also, NT6 has a new type of “threaded” DPCs that can be preempted by realtime threads

There is no such thing as “threaded DPC” - if you give DPCs a own stack that can get swapped, then it becomes already a workitem or dedicated thread, depending on whether you process multiple DPCs. in context of the same thread of give each DPC its own stack Execution unit like that becomes eligible for scheduling, and, hence, can block, get synchronized by dispatcher synchronization constructs, rather than spinlocks and, in all respects, is not a subject to limitations imposed by being a DPC.

In other words, this “new type of DPCs” had been around since the beginning of NT…

Anton Bassov

6

> So, Does windows execute drivers’ DPCs first and then if there is no drivers’

DPC in the queue

There is no difference between “driver’s” and no “driver’s” DPCs.

Usually, no thread can run on the CPU until it will execute all its scheduled
DPCs.

The only exception is low-importance DPCs, with which the CPU can return to
usual thread while having a low-importance DPC queued. They are only guaranteed
to be executed on a timer tick or when the CPU goes idle.

Quantum ends, as also switches to the preempted awakened thread, are only
executed on IRQL lower to below DISPATCH_LEVEL, only after all not-low
importance DPCs are executed.

So, timer interrupt can mark the quantum end situation while interrupting a
DPC, or KeSetEvent can awaken the thread from a DPC - but the actual thread
switch will be executed after DPC execution.

–
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com

7

Thanks for answers.

CLOCK_LEVEL IRQL = 28. So nothing can stop it to add DPC to DPC queue of the CPU. This DPC is related with Thread Scheduler.

But also drivers may queue DPCs. For example this is the queue:

DPC1
DPC2
DPC3
Thread Scheduler
DPC4
DPC5
DPC6
DPC7
Thread Scheduler

-DPC1-2-3 is started.
-Scheduler choose the thread.
-But thread can’t run because DPC4-5-6-7 etc is in the queue.
-While executing DPCs quantum time is expired and Timer sends another DPC for Scheduler.

So the step 2 is not necessary. Because step 4 will do the same thing.

Oh sorry. While i am writing i remembered :))
It does not queue the DPC a second time, and the DPC runs only once.
OK. I hope i am true.
So;
Step 4 never done. Because there is already one DPC for thread scheduler. If that is true.
Problem is solved. :))

Thanks…

8

xxxxx@gmail.com wrote:

CLOCK_LEVEL IRQL = 28. So nothing can stop it to add DPC to DPC queue of the CPU. This DPC is related with Thread Scheduler.

But also drivers may queue DPCs. For example this is the queue:

DPC1
DPC2
DPC3
Thread Scheduler
DPC4
DPC5
DPC6
DPC7
Thread Scheduler

-DPC1-2-3 is started.
-Scheduler choose the thread.
-But thread can’t run because DPC4-5-6-7 etc is in the queue.
-While executing DPCs quantum time is expired and Timer sends another DPC for Scheduler.

The quantum time is very long – 10ms or 16ms depending on several
factors. DPCs are very short. So, in practical terms, this situation
simply does not arise.

It IS true that a long-running DPC can have a substantial negative
impact on the responsiveness of the operating system.

So the step 2 is not necessary. Because step 4 will do the same thing.

Think about this. Even if this happened (and your analysis about why it
cannot is correct), so what? You make one unnecessary scheduler run
that gets redone shortly thereafter. Big deal.

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

9

> Step 4 never done. Because there is already one DPC for thread scheduler.

If that is true. Problem is solved. :))

Not really…

Please note that DPC can be rescheduled right after being removed from the queue. Although DPCs are short, they may be arriving at the high rate (just consider busy network traffic on the machine with gigabit Ethernet NIC). While you flush DPC queue, newly-arrived DPCs cannot get processed, but the moment
IRQL goes down, interrupt 0x41 will fire, and all DPCs thay got queued while previous queue was being flushed will get executed; meanwhile, new DPCs will get queued and so on and so forth - user thread just has no time to run. Therefore, the scenario that you have described is feasible.

This is why they have priority groups. Instead of processing all DPCs on the spot, the system processes only the urgent ones, and the rest gets processed when the next timer tick occurs, blocking call
is made or DPC queue exceeds the maximal allowed limit, whatever happens first…

Anton Bassov

10

>Tim Roberts

xxxxx@probo.com Join Date: 28 Jan 2005
Posts To This List: 2675

Re: Thread scheduler and deferred procedure calls

[…]

The thread scheduler DPC will CHOOSE which normal thread to run next.
The thread it chooses will not actually run until all of the DPCs are
finished and the IRQL drops below DISPATCH_LEVEL.

[…]

Not necessarily. The thread scheduler does not START the thread. It
merely prepares it for execution when the processor returns to its
normal passive level state and shifts back to user mode.

I’m wondering, wouldn’t it be possible that, once the dispatcher has selected a thread this DOES become the new current thread, then if there are more DPCs to process, they will be executed in the context of this new thread?

This may seem to contradict the fundamental truism that thread switching cannot occur at DPC level, but this assumption is for parts of code, like drivers routines, which are called by the DPC processing code of the kernel. In other words, Windows guarantees that while any DPC callback is executing, it will not be preempted in the middle of it.

To honour this, it is enough that the thread switching code is itself executed by means of a DPC and DPCs are processed sequentially. Thus, if Windows finds a DPC and calls the MyDpcCallback code it refers to, it will not call thread switching code while executing MyDpcCallback, because the thread switching code can only be fired by yet another DPC, which is waiting its turn.

On the other hand, when Windows is executing the scheduler, called by a DPC, it knows it has not interrupted any DPC callback to do this: it merely finished the previous DPC and will get to the one following the scheduler afterwards. Knowing this, it can safely switch thread and the newly selected thread will go on draining the DPC queue. DPCs can, after all, be run in the context of any thread.

Otherwise, the scheduler code would have to write somewhere that a thread switch must occur and which thread is going to be the next one, then the IRQL lowering code would have to check this information and eventually perform the actual context switch, which seems an unnecessary complication.

One of the reason I’m suggesting this is that both Mr. Roberts and Mr. Shatskih seem to be putting together the occurring of the context switch AND the execution of user mode code by the new current thread, which of course cannot take place until the IRQL drops to passive. What I’m suggesting is that the switch ONLY can occurr as part of the dispatcher code execution.

Just wondering…

I’m new to the list and this is my first post, so please cut me some slack :wink:

11

xxxxx@inrete.it wrote:

I’m wondering, wouldn’t it be possible that, once the dispatcher has selected a thread this DOES become the new current thread, then if there are more DPCs to process, they will be executed in the context of this new thread?

This may seem to contradict the fundamental truism that thread switching cannot occur at DPC level, but this assumption is for parts of code, like drivers routines, which are called by the DPC processing code of the kernel. In other words, Windows guarantees that while any DPC callback is executing, it will not be preempted in the middle of it.

I don’t see how it matters, one way or another. As long as each
individual DPC can hum about its business, confident in the knowledge
that it no switch will occur while it runs, then it doesn’t make any
difference whether two consecutive DPCs run in different threads.

I’m new to the list and this is my first post, so please cut me some slack :wink:

Ah, but that is not our way, honorable grasshopper.

–
Tim Roberts, xxxxx@probo.com
Providenza & Boekelheide, Inc.

12

> I’m wondering, wouldn’t it be possible that, once the dispatcher has selected
a

thread this DOES become the new current thread, then if there are more DPCs to
process, they will be executed in the context of this new thread?

The current thread context during which a DPC is executed is not defined and is
the implementation detail of the dispatcher.

To honour this, it is enough that the thread switching code is itself
executed by
means of a DPC and DPCs are processed sequentially.

It is enough for a switch to be executed on lowering < DISPATCH_LEVEL after
draning the DPC list.

Otherwise, the scheduler code would have to write somewhere that a thread
switch must occur and which thread is going to be the next one, then the IRQL
lowering code would have to check this information and eventually perform the
actual context switch, which seems an unnecessary complication.

Exactly.

I think there is a PCR/PRCB field of “which thread is going to be the next
one”.

–
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com