Posted by: Sue Loh

I got some great questions from one of our former Windows Embedded Student Challenge finalists, Gursharan.  I thought it would make a good blog post, so with his permission I'm answering his questions here.

Q1. The windows CE kernel has a scheduler working that is scheduling the processes(or threads) according to some parameters, per say priority or the quantum allocated to each one. So if I say that all processes have a priority level in CE and in all there are 256 priority levels, the system processes should occupy the highest place in the first slab( first slab is the 0-96 priority slab). So shell.exe , explorer.exe, gwes.exe etc.. occupy higher priority positions.

Q2. Then another thing that comes to my mind is is that where does the interrupt handler (another part of the kernel that loads the ISR vector and disables lower priority interrupts ) goes? It must be also at the highest priority! < Getting confused, but this confusion will yield something interesting, I know> So my question is where does the scheduler sit, at which priority level? Scheduler is scheduling various processes but in itself its also a process, so whats it priority?

Priority applies only to threads.  Not to processes and not to interrupt handlers.  Most threads in the OS that don’t handle interrupts are at THREAD_PRIORITY_NORMAL (=251) or one of the other few lowest-level priorities.  The 256 priority levels are specifically differentiated to that degree so that you (=the OEM or driver writer) have fine grained control over how interrupt handling for one kind of interrupt is prioritized over another.  For example, so that you can choose to say that the Ethernet interrupt service thread (IST) has priority over the USB IST.

When an interrupt occurs, it immediately interrupts whatever thread was running, no matter what.  The interrupt service routine (ISR) is supposed to be a very very short piece of code, whose sole purpose is to determine which IST needs to wake up and do a bare minimum of processing necessary, to get to the point where the IST can run.  At the very moment an interrupt occurs, the CPU goes into a special interrupt processing mode.  It disables all** interrupts, and passes execution to the kernel.  The kernel runs a common ISR handler, which branches off into interrupt-specific ISR handling until we know what interrupt it was.  That ISR does some preparation, and ends up returning a "SYSINTR" value which indicates what interrupt it was.  Based on the SYSINTR value, the kernel will set an event to wake the IST.

** (Actually on some CPUs, I think you can specify up to 4 ISR priority levels, and disable lower-priority ISRs while still allowing higher-priority ISRs interrupt them, but that is complicated.)

I am not completely sure, but I think the ISR re-enables interrupts.  It may be the IST which does that work however.  Possibly it varies depending on the interrupt; however the goal should be to get interrupts turned on as quickly as possible.  During the period of time that interrupts are disabled, no other interrupts can occur.  The ISR isn't a thread, and until the ISR completes, no threads can run.  So you can imagine, if the ISR does a really large amount of processing, it could break the system's real-time behavior.  That is why we try to keep the bulk of the work on an IST -- so that interrupts can be enabled as quickly as possible, and so that higher-priority ISTs can preempt lower-priority ISTs if necessary.  Note also that if an IST does a really large amount of processing, it breaks real-time behavior for all the ISTs below it, because those threads can't run until the higher-priority thread is done.

So, getting back to your questions.  Most of the threads in shell.exe, explorer.exe, gwes.exe are not ISTs, so they run at one of the 8 non-real-time priorities.  (248-255)  Many of the threads in device.exe are ISTs, however, so they are set to various places in the real-time range.  The interrupt handler isn't a thread and can run at any time.  The scheduler isn't a thread either, and typically runs either during an ISR or when a thread calls a rescheduling function like Sleep() or WaitForMultipleObjects().

Q3.  Windows Ce being a hard real time system ( I think it is), hands over control to processes after quantum expires. Had it  not been "hard", what mechanism would have been there to bring control back to scheduler if a process hanged?

First off, you mention quantum expiration.  The way that works is that the OS has a timer interrupt, which typically occurs at 1ms intervals, during which the scheduler checks if the current thread's quantum has expired or if any threads have expired a wait period (eg. Sleep() or WaitForMultipleObjects() timeout expires).  The scheduler adjusts threads as necessary and may reschedule to allow a new thread to run.

Yes, Windows CE is hard real-time, provided all of the ISRs and ISTs (which are not all implemented by Microsoft) do small, bounded amounts of work.  I forget at the moment whether the interrupt latency is defined as the time from the start of the ISR to time the IST starts running, or whether it's from the end of the ISR to the start of the IST, but it's one of those two.  An ISR that does a lot of processing can create big latencies for all interrupts, while an IST that does a lot of processing can create big latencies for all the ISTs that are lower-priority than it.  Since the code is not all ours, we provide kernel hooks for a test ("iltiming" which stands for Interrupt Latency Timing, yeah the name came from MARKETING) to measure interrupt latency.

Even in non-real-time systems the scheduling techniques I've described still apply.  The significance of real-time is that the interrupt latency is bounded (again, with the caveat of the ISRs and ISTs being implemented to do small, bounded amounts of work).  Part of that bounded-latency guarantee is implemented via the ISR/IST division and the many IST priorities.  The other part of the guarantee is provided by the fact that very smart people (= NOT ME) went through our scheduler and broke all of the "non-preemptible" sections into very small bounded chunks.  For example, the scheduler has to choose the next thread to run.  You could implement that by turning off interrupts, walking a list of who-knows-how-many sleeping threads to see if any timers have expired, then choosing the highest-priority runnable thread.  In the meantime, some interrupt may be pending and not get to run.  Instead, when the scheduler has to do any unbounded work, it is broken into small, non-preemptible steps.  Those steps are interruptible, meaning ISRs could execute.  And between each step the scheduler has to check if there is now an IST waiting to run, and schedule the IST if so.  So all of the scheduling operations themselves can be "disrupted" (I don't want to use the word "interrupted") by incoming ISTs if necessary.  So, real-time has nothing to do with "hanging" threads.  It has more to do with how quickly the interrupt-processing and scheduler themselves can react to incoming interrupts.

I would also be thankful if you could tell me the source file/directory where the code for the scheduler/other kernel processes reside. Would love to have a look at the implementation and design of it.

The kernel is under %_WINCEROOT%\private\winceos\coreos\nk\kernel, so if you have our shared source you should be able to look at it.  The scheduler code is in schedule.c there.  The non-preemptible sections of the scheduler are all done inside of invocations of KCall().

I wish I had companion documentation I could point you to, but I don't.  The only textbook I know of that explains how this part of the OS works is Inside Windows CE, which was written to go with CE 3.0 so the book is getting old.  However 3.0 was the first OS that supported real-time so the book probably goes into some detail about that.  (I don't have a copy to look at, unfortunately.)

As an added bonus, the book features pictures of Larry Morris with long hair, which I think is a hoot.  Larry is now the "head honcho" of Windows CE, and keeps his hair cut short.  I would insert a joke about him balding, if I didn't value my job -- oh dang, but I did mention it, now I'm doomed...