Module a4_context_switch

BSB - A4: Context Switch

Add simple thread management to RStuBS, where user threads voluntarily give up the CPU to the scheduler. This cooperative scheduling follows the coroutine concept.

You have to implement the Thread class, low-level functions for the context switch, and the Scheduler, which provides the scheduling policy and the dispatching mechanism. We recommend splitting the assignment into three parts:

• Implement the low-level context switch
• Implement the Scheduler::dispatch() mechanism
• Implement the Scheduler, which realizes the scheduling policy

Test each step thoroughly before moving on to the next one. Disable interrupts for now and ignore synchronization between ISRs and the normal control flow.

Learning Objectives

• Refresh your assembly knowledge
• Understand the procedure of thread-switching
• Distinguish between active and passive objects

Overview

The general procedure of a context switch is shown below.

Thread 1   Scheduler/Dispatcher   Thread 2
  |                                  .
call resume --> call switch          .
                     |               .
                    ret -- resume    .
                             |       .
                            ret -----o
                                     |

A running Thread 1 can call Scheduler::resume(). The scheduler chooses the next thread and calls Scheduler::dispatch(), which in turn calls context::switch(). The latter changes the context of the thread so that it returns into the next thread (Thread 2). Which again returns from Scheduler::dispatch() and Scheduler::resume() and continues execution.

In the first task, we implement the context::switch() function

1. Low-Level Context Switch

The context context::switch() function is called by the current thread and should return to the next thread. Consequently, it has two parameters: the sets of CPU Registers for the current and the next threads (callee-saved registers). Part of these registers is the stack pointer (ESP), which contains a return address that is jumped to when context::switch() returns. So, if you change the ESP, you also change the return address to the one of the next thread.

Your task is to implement and context::switch() function. This requires inline assembly to save and restore the CPU state of a thread. You only need mov instructions for that and the options(nostack) attribute.

There are different types of mov:

• Direct: mov eax, esp: eax = esp;
• Indirect: mov eax, [esp]: eax = *esp;, Dereferences pointer in esp
• Direct: mov eax, [esp+4]: eax = *(esp + 4);, Add and dereference

Also, implement the context::launch() function. It only loads the new context (without saving the current one) and is called when the scheduling starts.

Switching to a new thread for the first time needs a bit of preparation. Remember, the switch function works by changing the CPU registers, including the stack pointer (ESP) and then returns, which pops the return pointer from the (changed) stack and jumps to it. For a new thread, we want to jump to Thread::kernel_kickoff(), which calls the threads action function. This can be achieved by “faking” (preparing) the stack of new threads (in Thread::init()) so that they return from switch into the kickoff function. For this, put the Thread::kernel_kickoff() as the return address on the stack (including any arguments).

Allocate the stacks statically from the system image (just create a global static array with the stacks, e.g., in scheduler.rs). APPS contains the maximum number of supported threads (which you can change).

For testing purposes, create several threads, which all call context::switch() after a few lines of code to switch to the next thread. Hardcode the successor threads for these tests and turn off interrupts for debugging. With breakpoints (or stepping), you can observe if the context switch works.

2. Dispatching Threads

Next, implement the Scheduler::dispatch() function, which calls context::switch() and updates the active index in the CPU-local data. In your tests, you can now switch between threads by calling Scheduler::dispatch().

3. Scheduling Threads

Finally, implement the remaining parts of the Scheduler. The threads are stored in a simple array, and the ready list is a simple array-based queue with indices into the thread array. Threads are given to the scheduler with the Scheduler::add(), which puts the threads into the array and ready list and calls Thread::init(). The Scheduler::ready() enqueues threads into the ready list.

The Scheduler::next() should implement a simple first-come-first-serve (FCFS) scheduling policy. It should be called by Scheduler::schedule() and Scheduler::resume().

Threads are managed in a single ready list. However, on multicore systems, different cores may access the data structure of the scheduler at the same time. Hence, calls to the Scheduler need to be synchronized in RStuBS, even in the case of cooperative scheduling. In particular, you must ensure that a thread running on the current core will not be made available for execution prematurely on another core. Putting the scheduler into Guarded might be a good idea.

Now, before calling resume, an app has to enter the guard and leave afterward. But what about the first start of an app? During the context switch, the scheduler was locked (either by the previous thread or the main function that starts the scheduler). Consequently, the new thread has to leave the guard when it starts execution. A good point for that would be the Thread::kernel_kickoff() function, which could leave() before calling action.

Hints

In assignment 4, we always assume that the system has enough threads ready to be executed, so the ready list should never run empty. Make sure that this assumption holds in your test system! Test your code intensively with a variable number of threads. We recommend testing your code on a single core at first; if that works, switch on scheduling on the others as well.