Implementing a preemptive kernel within a single Windows thread

About three years ago I developed a real-time operating system aimed at the new generation of 32 bit microcontrollers. Seeing how I am a devotee of developing/testing embedded software on a PC and only then porting/testing to the target, one of my goals was to get a working simulation environment under Windows. I had thought at the time that I would have a lot of reference, seeing how most real-time operating systems (FreeRTOS, for example) have Windows ports. To my surprise no port implemented true preemption, instead opting for simply wrapping the Windows API with the equivalent RTOS API (for example, creating an RTOS thread would call Windows’ CreateThread).

Functionally this allows users to develop under Windows, calling the RTOS API as they would on the target and testing their application under Windows. However, there are two drawbacks to this:

1. The result of such a simulation, while usually sufficient, is quite synthetic. A lot of behavior is due to change when porting back to the target because Windows cannot be (easily) made to behave like an RTOS – especially in the aspect of predictable scheduling
2. As an RTOS developer you can’t write and test kernel code under Windows and as an application developer you cannot familiarize yourself with the underlying kernel state at a given time, seeing how no such state exists

It is therefore beneficial to have as much of the RTOS kernel as possible running under Windows and for the most part this is quite straightforward. Most context switches occur when the application calls an OS API – like sleep() or giving a semaphore. Let’s assume we have a single Windows thread and we implement the following piece of code:

// the first thread entry
first_thread()  
{
    unsigned int counter = 0;

    // forever
    while (TRUE)
    {
        // increment counter
        counter++;

        // sleep for a period of 0 (yield the scheduler)
        rtos_sleep(0);
    }
}

// the second thread entry
second_thread()  
{
    unsigned int counter = 0xFFFFFFFF;

    // forever
    while (TRUE)
    {
        // decrement counter
        counter--;

        // same as first_thread
        rtos_sleep(0);
    }
}

In this simple scenario, we create two RTOS threads and expect them to work concurrently. Seeing how we only have one Windows thread, we need to be able to switch between the two contexts (each thread has a stack and different register states). In this case, actual context switch will occur on the call to rtossleep(). If we were to follow the trace of execution (remember – we have only one Windows thread) we will see that it starts by entering firstthread, having the stack pointer pointing to the first thread’s stack. It will then increment the counter on firstthread’s stack and enter rtossleep. This kernel function will revoke the firstthread’s right to continue and then load the secondthread’s context (its stack and registers). The Windows thread will then continue to execute and, seeing how it loaded secondthread’s instruction pointer register, start running secondthread.

Such behavior can allow for simulating a LOT of functionality – thread priority, thread state, waitable objects like semaphores, and the like – but all of the context switches can only be made when the user calls an RTOS API. Effectively, we have simulated a cooperative kernel, in which the user must call the kernel every so often to enable other threads to run. There are so many examples of implementing a cooperative context switching mechanism in Windows out there that I am not going to go into the details of how we actually do the magic behind this example (creating the thread, swapping contexts and the like). I’m sure Google can provide many excellent sources.

From cooperative to preemptive

We are interested in allowing for these two threads above to share CPU without calling an RTOS API. We want to be able to have the firstthread loop in place and still allow for secondthread to run. This will allow us to implement timers, interrupts and time-slice scheduling (that is, sharing CPU fairly among same priority ready-to-run threads). To be honest I was quite stumped with this for a few days. I needed to find a way to somehow alter the flow of execution of the Windows thread running the kernel, whichever block of code it may be running. When I figured out how to do this I was pretty awe struck at how simple it is.
We start by spawning a second Windows thread – this thread will serve as the interrupt thread. Overall, we will only need two Windows threads: the interrupt thread (running in high Windows priority) and the kernel thread (running in normal Windows priority), which will run the RTOS threads, however many they may be. Whenever we’d like interrupted rescheduling to be performed we post a message into the interrupt thread’s Windows message queue. This will be either periodically (using an auto-renewing timer) or deferred (using a one-shot timer).

The magic occurs once the interrupt thread receives the request to interrupt. At this point in time, the interrupt thread will simply hi-jack the kernel thread – changing its current point of execution to a block of code that performs saving the current context and loading the next one. This is done by using GetThreadContext and SetThreadContext.

// hijack the windows thread running our kernel - once
// it becomes ready it will jump to wcs_isr_reschedule
void wcs_intsim_do_interrupt()  
{
    // initialize context flags 
    CONTEXT ctx;
        memset(&ctx, 0, sizeof(ctx));
        ctx.ContextFlags = CONTEXT_FULL;

    // suspend the kernel thread
    SuspendThread(wcs_intsim_thread_to_interrupt_handle);

    // get its windows thread context
    GetThreadContext(wcs_intsim_thread_to_interrupt_handle, &ctx);

    // push the address we want to return to 
    // (which is wherever the RTOS thread is now)
    // after our simulated ISR to the RTOS thread's stack
    ctx.Esp -= sizeof(unsigned int *);
    *(unsigned int *)ctx.Esp = ctx.Eip;

    // set the instruction pointer of the kernel 
    // thread to that of the ISR routine
    ctx.Eip = (DWORD)wcs_tick_isr;

    // set context of the kernel thread, 
    // effectively overriding the instruction ptr
    SetThreadContext(wcs_intsim_thread_to_interrupt_handle, &ctx);

    // resume the kernel thread
    ResumeThread(wcs_intsim_thread_to_interrupt_handle);
}

We push the current kernel thread’s instruction pointer register to the top of its stack (so that the current RTOS thread can resume execution once its ready again) and then override it with a pointer to our (naked) routine performing the save and switch context. Once the interrupt thread goes back to pending on its message queue, the kernel thread will resume and effectively handle the interrupt (again, by saving current context and loading the next RTOS thread).

And now some code

The RTOS I implemented was very feature rich – it supported waiting on multiple objects, a variable tick timer (that is, a tick only occured when needed), a zero overhead heap, and many other cool things – all fully simulated. I extracted the essence of this article from that RTOS into a single C++ module (360 lines of commented code, I didn’t even attach a header) that was tested under x86 running Windows 7, compiled with VS 2008. In this example I only show the simplest form of preemption – a constant tick that time slices between two threads which are created before the kernel starts running. This is only a proof of concept – building atop of this, one can implement pretty much everything an RTOS offers (dynamic thread creation/deletion, waitable objects, timers, etc).

Get the demo from github.