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 rtos_sleep(). If we were to follow the trace of execution (remember – we have only one Windows thread) we will see that it starts by entering first_thread, having the stack pointer pointing to the first thread’s stack. It will then increment the counter on first_thread’s stack and enter rtos_sleep. This kernel function will revoke the first_thread’s right to continue and then load the second_thread’s context (its stack and registers). The Windows thread will then continue to execute and, seeing how it loaded second_thread’s instruction pointer register, start running second_thread.

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 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

Download example (winContextSwitch.cpp, ~360 lines of commented code)