Windows Thread Scheduler - Inserting Soft-Interrupt into executionstack

[Anthony Paul]

Hello,

There's been something that I've always been curious about but have
not been able to find an answer on. From what I've read, the OS's
thread scheduler determines how much time a particular thread should
execute and inserts a software interrupt into the execution stack at a
particular location. My question is two-fold : 1) how does it know
where to insert the interrupt (ie. does it enter a loop at the first
instruction and sum up the actual number of execution cycles each
instruction would take? Sounds expensive! Also, isn't this expensive
if, by inserting an instruction into the middle of a set of
instructions, all address references would have to be incremented by
one in order to compensate?) and 2) how does it know that the
interrupt will be reached?

For example, if I have the following pseudo-code :

10 goto 20
20 do something here

and compile this into an exe and run it, isn't it conceivable that the
scheduler could put a soft-interrupt between the machine-code
corresponding to lines 10 and 20, such that it would never be reached?
Or even simpler still, if I just have one line of code that loops to
itself (an infinite loop) and the scheduler inserts the soft-interrupt
right after the infinite loop, doesn't that mean the thread containing
the infinite-loop will never EVER reach the soft-interrupt, thereby
never give up cpu time to any other thread, locking up the machine for
good?

Basically, I'm confused as to what good pre-emptive multi-tasking is
for since it seems to be non-premptive in the sense that it still
seems dependent on the thread to give control back to the OS. Why not
just base it completely on a timer interrupt? Seems a lot more fool-
proof to me unless I'm missing something here... I can't seem to find
any material explaining how this works in any detail, not even the
Windows Internals book I just ordered. Anyone?

Regards,

Anthony

 

[Pentalon]

The kernel's thread scheduler does not analyze or modify any program code. It
instead uses a combination of the chip's hardware timer interrupt and the
scheduling code that is built into OS calls to execute scheduling as needed.

The hardware timer interrupt is used to interrupt threads that "consume too
much time". E.g., a thread that's involved in a long calculation or an
infinite loop will be interrupted by the hardware when the timer fires (about
every 15 milliseconds), and control will be transferred back to the thread
scheduler code in the kernel. The scheduler can then pick another thread to
run (if one is ready to run), or return control back to the original thread
if nothing else needs to run. In either case, the timer is "reset" and will
fire again in 15 ms, giving control back to the kernel to check for other
threads again. This happens continuously and repeatedly. The 15 ms interval
is known as the "quantum", and the exact duration depends on how the system
is configured.

Now a lot of times a thread doesn't need the full 15 ms to run its
calculation before it has nothing to do again and is ready to enter a waiting
state. For example, pressing the equals button in a calculator on screen
might trigger a thread to add 2 numbers together and put the result on
screen. That whole calculation on that thread could take just a few
microseconds and then the thread has nothing to do again except wait in a
non-executing state for more input (i.e. another button press). If the kernel
had to wait 14.99 milliseconds after the thread completed it's work just for
the kernel to regain control and schedule another thread, a colossal amount
of CPU time would be wasted and the UI and computer would be practically
unusable.

So what's done in this case is that after the thread is done its
calculation, it makes a call to wait for a button press, and internally this
call is eventually implemented in terms of system calls to the kernel like
WaitForSingleObject() or Sleep(). These system calls imply that the thread
could potentially enter a wait state (non-executing state), and since these
calls are implemented by the operating system (though triggered by the user's
thread), the OS now has the opportunity to see if the thread should be put to
sleep or if another higher priority thread needs to run. If so, the kernel
thread scheduler can take control again and schedule something else, put the
original thread to sleep, etc. If there's nothing else to run, it can also
return control to the original thread to continue execution.

Essentially, the soft interrupts that you are talking about are already
built into the program by the program's use of system calls to do things like
sleep, wait for signals, and signal other waiting threads. If a thread does
not contain any of these calls, or does not contain any of these calls in a
long-running section of code, then the hardware timer will interrupt the
thread in the worst case of it running too long.

Frequently, these OS calls that can yield to the kernel and affect thread
scheduling are built into other operations or functions that you may not
realize have them. For example, a thread may write something to disk with the
imaginary system call WriteFile(). WriteFile() may put the data in an I/O
queue, then signal the OS that the queue should be written to disk, then wait
for a signal from the OS that the operation was completed before returning to
the user. WriteFile() may be implemented internally as something like:

void WriteFile( char *pData )
{
PutDataOnDiskQueue( pData ); // Put user data someplace where kernel
can find it.
SignalOSWriteQueueToDisk(); // Tell an internal high-priority kernel
thread to physically write the queue to disk.
WaitForDiskWriteToComplete(); // Wait for kernel to complete the
physical write.
}

When the user calls this function, it will run on the user's thread, even
though it's implemented in a system DLL. There are 2 interesting things here:

1. There is clearly at least one call in here that could yield or interrupt
the user's thread, WaitForDiskWriteToComplete(), though it's not necessarily
apparent from WriteFile()'s API description that the user's thread may yield
when calling this function. So, any given program is probably playing nice
and yielding up the processor more often than one would expect at first
sight. This is good for the most part, because from WriteFile()'s
description, it's not supposed to return until the write is complete, and
there is nothing else for it to do after it signals the OS to write the
queue, so it should wait (yielding the processor back to the kernel) and not
waste CPU cycles.

2. While WaitForDiskWriteToComplete() could yield the current thread's
execution, SignalOSWriteQueueToDisk() could also. SignalOSWriteQueueToDisk()
probably calls the system's SetEvent() at some point to signal a
high-priority kernel thread to wake up and physically write the queue to
disk. Since SetEvent() is a system call, it can contain scheduling code that
determines whether the signal will wake a higher-priority thread, and if so,
immediately transfer call to that higher-priority thread. The point here is
that the action of signaling other threads can cause a kernel rescheduling
event.

That's basically it. This is an ultra-rough description, but hopefully it
covers the basic ideas that:

1. The soft interrupts are built into the system calls that (almost) every
program makes.

2. The base system calls that can cause rescheduling events -- Sleep(),
WaitForSingleObject(), WaitForMultipleObjects(), SetEvent(), and a host of
others -- are often called inside other system and user calls, so threads may
yield more often than you expect.

3. For the user code between system calls, there's the hardware timer
interrupt, in case that code takes too long.

Hope that helps.

Derek

 

[Anthony Paul]

Hello Derek!

Thank you for taking your time and replying to my post, your answer
was very informative. However, I still am confused since you (and
other sources) say one thing while other sources say another. For
example, if you would go to the following link :

http://www.codeproject.com/KB/threads/ThreadingDotNet.aspx

Under the Thread Local Storage/Interrupts section, it is said
specifically that software-interrupts are inserted into the executable
code at run-time, by the windows thread scheduler no less. This
article is based on the books "VB .NET Threading Handbook" or "C#
Threading Handbook", and I have read the part of it that states this
for a fact, so I know that it wasn't a misunderstanding on the
article's author's behalf.

Personally, I don't believe that the scheduler inserts these soft-
interrupts into the executable code... that opens up a whole can of
worms and simply doesn't make sense to me. However, these books are
making that claim and I can't sleep until I know for sure, lol.

If you or anyone else can shed some light on this, I would love to
know!

Cheers!

Anthony

 

[Anthony Paul]

FYI, I was able to find the particular section of the book and am
quoting it here... so the windows thread scheduler actually inserts an
interrupt into the execution sequence! I emailed the author for the
reference, hopefully he'll get back to me soon, I've been going nuts
about this lol! This is definitely new to me!

Interrupts
Remember that we said that processes don't necessarily need to know
about other processes on the same computer. If that were the case, how
would the thread know that it's supposed to give way to anther
process? This scheduling decision nightmare is handled by the
operating system for the most part. Windows itself (which after all is
just another program running on the processor) has a main thread,
known as the system thread, which is responsible for the scheduling of
all other threads.
Windows knows when it needs to make a decision about thread scheduling
by using interrupts. We've used this word already, but now we are
going to define exactly what an interrupt is. An interrupt is a
mechanism that causes the normally sequential execution of CPU
instructions to branch elsewhere in the computer memory without the
knowledge of the execution program. Windows determines how long a
thread has to execute and places an instruction in the current
thread's execution sequence. This period can differ from system to
system and even from thread to thread on the same system. Since this
interrupt is obviously placed in the instruction set, it is known as a
software interrupt. This should not be confused with hardware
interrupts, which occur outside the specific instructions being
executed. Once the interrupt is placed, Windows then allows the thread
to execute. When the thread comes to the interrupt, Windows uses a
special function known as an interrupt handler to store the thread's
state in the TLS. The current program counter for that thread, which
was stored before the interrupt was received, is then stored in that
TLS. As you may remember, this program counter is simply the address
of the currently executing instruction. Once the thread's execution
has timed out, it is moved to the end of the thread queue for its
given priority to wait its turn again. Look at Figure 6 for a diagram
of this interruption process:

Figure 6

The TLS is not actually saved to the queue; it is stored in the memory
of the process that contains the thread. A pointer to that memory is
what is actually saved to the queue.

This is, of course, fine if the thread isn't done yet or if the thread
needs to continue executing. However, what happens if the thread
decides that it doesn't need to use all of its execution time? The
process in context switching (that is switching from the context of
one thread to another) is slightly different initially, but the
results are the same. A thread may decide that it needs to wait on a
resource before it can execute again. Therefore, it may yield its
execution time to another thread. This is the responsibility of the
programmer as well as the operating system. The programmer signals the
thread to yield. The thread then clears any interrupts that Windows
may have already placed in its stack. A software interrupt is then
simulated. The thread is stored in TLS and moved to the end of the
queue just as before. We will not diagram this concept as it's quite
easy to understand and very similar to the diagram opposite. The only
thing to remember is that Windows may have already placed an interrupt
on the thread's stack. This must be cleared before the thread is
packed up; otherwise, when the thread is again executed, it may be
interrupted prematurely. Of course, the details of this are abstracted
from us. Programmers do not have to worry about clearing these
interrupts themselves.

Cheers!

Anthony

 

[Jack Jackson]

FYI, I was able to find the particular section of the book and am
quoting it here... so the windows thread scheduler actually inserts an
interrupt into the execution sequence! I emailed the author for the
reference, hopefully he'll get back to me soon, I've been going nuts
about this lol! This is definitely new to me!

While I don't know how Windows does this, I do not think this
description can be accurate. Inserting a software interrupt
instruction into the thread's instruction stream simply makes no sense
at all. The word ludicrous comes to mind.

The author's word choices make me think he does not have a very good
understanding of execution scheduling and CPU interrupt handling.