ULWOS2: A simple and lightweight cooperative OS (part 1)

Since I wrote my article on an alternative way to write state machines, I wanted to use them for more than simply writing state machines. Now, living in these times of COVID-19 and social distancing, I have decided to give it a try and design a 100% C cooperative thread scheduler, I present you the Ultra LightWeight Operating System 2 (ULWOS2)!

The idea was to use the macros designed for GPL FSMs and repurpose them to enable handling thread resuming and suspending.

Note that in this article we are gonna use the term thread instead of task or process, this is because a thread is a simpler and more limited version of a process. While different processes do not share memory with each-other and behave as independent entities, multiple threads share the same resources they inherited from their parent. In this sense, it makes more sense to think of ULWOS2 as a thread scheduler!

Task Scheduler 101

The basic building block of any multitasking operating system kernel is the task scheduler. Its purpose is to decide which tasks should run and share CPU time among multiple tasks or processes. There are two different models of multitasking: cooperative and preemptive.

On cooperative multitasking, the scheduler gives control to a task, which can run freely for as long as it wants. It is up to the task to decide when it had enough CPU time and when that happens, it gives control back to the scheduler, which decides the next task to run. A cooperative scheduler usually relies on software interrupts which call the scheduling code.

On preemptive multitasking, the scheduler can resume or suspend tasks without the cooperation from them. That happens based on time slices (quantum) or based on the priority. Preemptive schedulers rely on hardware interrupts (usually a timer interrupt) to call the scheduling code.

In both cases, the scheduler needs to keep track of each task’s state in terms of local variables and CPU registers. This is called “context” and the process of switching from one task context to another is called ” context switch”. We have described the whole process in details on my first implementation of ULWOS as a preemptive scheduler, but figure 1 should give an idea of what we are talking about.

The main idea here is: in order to successfully switch from one task to another, the scheduler needs to preserve the full context for each task, that means it needs to create a different stack for each task!

ULWOS2 Scheduler

The approach we used on ULWOS2 is different than what we stated above, mainly because ULWOS2 does not use any kind of interrupt for context switching. Another interesting characteristic of ULWOS2 is that we rely on pure C constructors to implement all the necessary context switching code, that means no assembly code whatsoever!

If we look at my GPL FSMs design, we already have some code that can store a basic state of a function, a constructor that we use to jump to a previous position in code and a constructor to exit the FSM while setting a new desired state for when the FSM runs again. All these elements can be utilized or repurposed to create a rudimentary thread suspend/resume system.

This new API includes several functions:

• ULWOS2_INIT – initializes ULWOS2 (should be called before creating any thread);
• ULWOS2_THREAD_CREATE – creates a new thread with a specific priority;
• ULWOS2_THREAD_KILL – to kill (destroy) a thread;
• ULWOS2_START_SCHEDULER – start ULWOS2 scheduler
• ULWOS2_THREAD_START – this is the constructor that enables jumping to a specific point within the thread when resuming;
• ULWOS2_THREAD_YIELD – yields back to the scheduler. This is used for giving  a chance of other threads to run (it doesn’t block the thread);
• ULWOS2_THREAD_SLEEP_MS – blocks the thread for a specific amount of milliseconds;
• ULWOS2_THREAD_SEND_SIGNAL – sends a signal to other threads;
• ULWOS2_THREAD_WAIT_FOR_SIGNAL – suspends the thread until the given signal arrives;
• ULWOS2_THREAD_RESET – reinitialize the thread internal pointer (but does not touch any local variable). This forces the thread to run from the beginning;

ULWOS2 also relies on a few different thread states:

• THREAD_NOT_READY – thread has not been created or was destroyed;
• THREAD_SLEEPING – thread is suspended (not currently used);
• THREAD_WAITING_FOR_SIGNAL – thread is suspended waiting for a signal;
• THREAD_WAITING_FOR_TIMER – thread is suspended waiting for its timer to timeout;
• THREAD_READY – thread is ready and can run if the priority is correct;

Operating Principle

Our scheduler is quite simple, it is basically a loop that keeps calling functions by using a function pointer. Deciding which function (thread) to run takes into account the current priority level the scheduler is and whether the thread is ready or not to run.

But that is not all. Have we implemented just this simple scheduler, a thread wouldn’t really be a thread but just a function that would run to completion. This is where our GPL FSM code comes handy, it allows each thread to keep track of where it was the last time it got suspended and when we can the function (thread) again, our code jumps to the next line of code following that point!

Let’s take a look at the code used for resuming a thread:

#define ULWOS2_THREAD_START() static void *jumper = NULL; if (jumper!=NULL) goto *jumper;

This code is not new and we detailed it in this article.

The new piece of code designed for ULWOS2 is the suspend (yield) code:

#define ULWOS2_THREAD_YIELD() ({jumper= &&GLUE3(LB,__FUNCTION__,__LINE__); return; GLUE3(LB,__FUNCTION__,__LINE__): while(0);})

It makes use of some pre-processor magic which requires some explanation: GLUE3(LB, __FUNCTION__, __LINE__) creates a label starting with LB followed by the name of the current function (in this case current thread), followed by the current line number. This essentially creates a unique symbol that we use as label indicating a while (0); statement.

The while(0) statement is used because a label must be followed by a valid C statement. The beauty here is that while(0) compiles to nothing (since 0 is always false). So basically our label indicates the next statement (the one that follows the while(0).

We assign that address to jumper variable and return, so the next time we call this thread, ULWOS2_THREAD_START is going to jump to the address following our ULWOS2_THREAD_YIELD, clever isn’t it?

Other Features

Along with switching and scheduling multiple threads with different priorities, ULWOS2 also includes some basic features such as an independent sleep timer for each thread and a basic signalling system.

We will cover those features and see some examples in our next article.

But if you are curious and want to check the code, feel free to visit ULWOS2 repository on Github.

See you next time!