by In the first part of this article we introduced ULWOS2 and its cooperative thread scheduler. In this second part we continue discussing the scheduler, how we deal with thread suspension/resuming and take a look at a first example.
We already discussed the macros that enable thread suspension/resuming and we saw that each thread is in charge of storing its basic context awareness state, which is the “jumper” static variable. Now let’s take a look at the scheduler’s core:
void ULWOS2_startScheduler()
{
tULWOS2threadHandler queueHead;
tULWOS2threadPriority currentPriority = ULWOS2_PRIO_MIN;
void (*threadToRun)(void);
while(1) {
if (invalidateThreadPriorityQueue) {
ULWOS2_orderPriority(THREAD_READY);
queueHead = currentQueueHead;
if (currentQueueHead != ULWOS2_INVALID_HANDLER) currentPriority = ULWOS2_threads[currentQueueHead].priority;
else currentPriority = ULWOS2_PRIO_MIN;
} else currentQueueHead = queueHead;
// Runs all threads in READY state
while (currentQueueHead != ULWOS2_INVALID_HANDLER && ULWOS2_threads[currentQueueHead].priority <= currentPriority) {
threadToRun = ULWOS2_threads[currentQueueHead].address;
if (threadToRun != NULL) threadToRun();
currentQueueHead = ULWOS2_threads[currentQueueHead].nextThread;
}
ULWOS2_checkTimers();
}
}
The while(1) loop executes three basic operations:
- Check if we need to perform a new sorting of thread priority. This is controlled by invalidateThreadPriorityQueue flag. Note that only threads that are ready to run are enqueued. Threads are enqueued according to their priority order (higher priority first). At this point we also set the current priority which is the one read from the first thread in the queue;
- Run all threads within the current priority setting. Keep in mind that as a cooperative scheduler, ULWOS2 expects all threads to return control as soon as possible;
- Once all ready threads were called, we check the timers. If any thread waiting for a timer has its timer expired, that thread is set as ready and queue priority is invalidated;
Thread Control Block
As mentioned in the past article, ULWOS2 uses a very simple and small TCB. There are only 7 fields as we can see below:
typedef struct {
void (*address)(); // thread entry point
tULWOS2threadPriority priority; // priority
eULWOS2threadState state; // current state
tULWOS2threadHandler nextThread; // handler of the next thread
tULWOS2Timer timerStart; // milliseconds when timer was set
tULWOS2Timer timerInterval; // desired timer interval in ms
tULWOS2threadSignal signal; // the signal this thread is waiting for
} tULWOS2threadControlBlock;
One interesting feature here is the nextThread field. It enables the creation of a virtual linked list which is used for sorting the priority queue in place. With the use of a global variable which acts as the head of the list. Each entry’s nextThread holds the index of the next thread in a given sorting order. This approach is a simpler alternative to implementing a full min heap which would be the usual method for designing a priority queue.
The TCB also includes the usual fields such as priority (which holds thready priority) and state. ULWOS2 currently supports the following thread states:
- THREAD_NOT_READY – this is the default state of a thread that has just been created or was destroyed;
- THREAD_SLEEPING – this state signals the thread is sleeping and not ready to run, it is not currently used;
- THREAD_WAITING_FOR_SIGNAL – used when the thread is suspended and waiting for a signal (the signal ID is specified by signal field). A thread enters this state after a call to ULWOS2_THREAD_WAIT_FOR_SIGNAL();
- THREAD_WAITING_FOR_TIMER – used when the thread is suspended for a specific amount of time. Use ULWOS2_THREAD_SLEEP_MS() to set the thread sleep timer and suspend it for that amount of time;
- THREAD_READY – thread is ready to run. Threads in this state are scheduled to run according to their priority;
ULWOS2 Thread Anatomy
On ULWOS2, a thread must follow some basic rules:
- It must include a call to ULWOS2_THREAD_START() in the beginning of its code. This is necessary in order to make sure the thread is going to resume properly following a suspension. An exception to this statement are the special cases of run-to-completion threads: if a thread is supposed to run and return at once and will not get suspended by any means, then it is possible to omit this section;
- It must either implement a internal infinite loop (with appropriate yielding so that other threads can have a chance to run) or, if a thread is supposed to run to completion, it must call ULWOS2_THREAD_KILL() before exiting;
- Yielding or any kind of thread suspension can only happen inside the main thread code. This means it is not possible to yield or suspend a thread from code called by the thread;
- Any local variable whose contents needs to be persisted across multiple calls (think of suspending/resuming the thread at least once) need to be declared as static;
This is what a typical ULWOS2 thread looks like:
void myThread(void)
{
// variable declarations
ULWOS2_THREAD_START();
while (1) {
// do something
ULWOS2_THREAD_YIELD(); // yield to scheduler so another thread can run
}
}
A run-to-completion thread will look like this:
void myThread2(void)
{
// variable declarations
ULWOS2_THREAD_START(); // this can be omitted if the thread will not suspend at all
// do something
<span class="pl-en">ULWOS2_THREAD_KILL</span>();
}
First Example
Now that we discussed how ULWOS2 works, let’s take a look at a simple example which demonstrates its main features. The example within Linux folder creates four threads which print dots on the terminal screen. Thread 1 runs every 200ms, thread 2 runs every 300ms, thread 3 waits for a signal from thread 1 (which is send when it reaches 10 on its internal dot counter) and then prints every 250ms and finally thread 4 waits for a signal from thread 2, which is send when the thread completes its processing. Thread 4 then prints every 250ms.
This is the example file (ULWOS2_demo1.c):
/******************************************************************************
ULWOS2 example with four threads
Author: Fábio Pereira
Date: Apr, 23, 2020
embeddedsystems.io
*******************************************************************************/
#include <stdio.h>
#include "../../src/ULWOS2.h"
#define SIGNAL_RUN_THREAD3 1
#define SIGNAL_RUN_THREAD4 2
#define CLEAR_TERMINAL() printf("\x1B[2J")
#define PRINT_RED() printf("\x1B[31m")
#define PRINT_GREEN() printf("\x1B[32m")
#define PRINT_BLUE() printf("\x1B[34m")
#define PRINT_WHITE() printf("\x1B[0m")
void asciiCursorXY(uint8_t x, uint8_t y)
{
printf("\x1B[%hu;%huH",y,x);
}
void printCharXY(uint8_t x, uint8_t y, char ch)
{
asciiCursorXY(x,y);
printf("%c",ch);
fflush(stdout);
}
void testThread1(void)
{
static uint8_t posX = 0;
const uint8_t posY = 2;
PRINT_RED();
ULWOS2_THREAD_START();
asciiCursorXY(0,posY);
printf("Thread 1:");
while (1) {
if (posX<20) {
printCharXY(10+posX,posY,'.');
ULWOS2_THREAD_SLEEP_MS(200);
if (posX == 10) ULWOS2_THREAD_SEND_SIGNAL(SIGNAL_RUN_THREAD3);
posX++;
} else break;
}
asciiCursorXY(10+posX,posY);
printf(" Done!\n");
ULWOS2_THREAD_KILL();
}
void testThread2(void)
{
static uint8_t posX = 0;
const uint8_t posY = 3;
PRINT_BLUE();
ULWOS2_THREAD_START();
asciiCursorXY(0,posY);
printf("Thread 2:");
while (1) {
if (posX<20) {
printCharXY(10+posX,posY,'.');
ULWOS2_THREAD_SLEEP_MS(300);
posX++;
} else break;
}
asciiCursorXY(10+posX,posY);
printf(" Done!\n");
ULWOS2_THREAD_SEND_SIGNAL(SIGNAL_RUN_THREAD4);
ULWOS2_THREAD_KILL();
}
void testThread3(void)
{
static uint8_t posX = 0;
const uint8_t posY = 4;
PRINT_GREEN();
ULWOS2_THREAD_START();
asciiCursorXY(0,posY);
printf("Thread 3:");
ULWOS2_THREAD_WAIT_FOR_SIGNAL(SIGNAL_RUN_THREAD3);
while (1) {
if (posX<20) {
printCharXY(10+posX,posY,'.');
ULWOS2_THREAD_SLEEP_MS(250);
posX++;
} else break;
}
asciiCursorXY(10+posX,posY);
printf(" Done!\n");
ULWOS2_THREAD_KILL();
}
void testThread4(void)
{
static uint8_t posX = 0;
const uint8_t posY = 5;
PRINT_WHITE();
ULWOS2_THREAD_START();
asciiCursorXY(0,posY);
printf("Thread 4:");
ULWOS2_THREAD_WAIT_FOR_SIGNAL(SIGNAL_RUN_THREAD4);
while (1) {
if (posX<20) {
printCharXY(10+posX,posY,'.');
ULWOS2_THREAD_SLEEP_MS(250);
posX++;
} else break;
}
asciiCursorXY(10+posX,posY);
printf(" Done!\n");
ULWOS2_THREAD_KILL();
}
int main()
{
CLEAR_TERMINAL();
asciiCursorXY(0,1);
printf("ULWOS2 demo!\n");
ULWOS2_INIT();
ULWOS2_THREAD_CREATE(testThread1, 10);
ULWOS2_THREAD_CREATE(testThread2, 10);
ULWOS2_THREAD_CREATE(testThread3, 1);
ULWOS2_THREAD_CREATE(testThread4, 2);
ULWOS2_START_SCHEDULER();
}
You can also test it using an online compiler by using the window below.
Or you can check the animation below which I recorded from my own local terminal.
Final Considerations
ULWOS2 shows a very simple implementation of a cooperative thread scheduler written 100% in C. This approach comes with pros and cons as anything in life, let’s start with the pros:
- There is no need for an independent stack for each thread! This is because each ULWOS2 thread has always a single entry and a single exit point. Resuming code from the point it left is performed by a tiny constructor included in the beginning of every thread. This means that in ULWOS2, the scheduler is not really aware of the execution point of a given thread, each thread is responsible for keeping a very basic level of “context awareness”;
- The Thread Control Block (TCB) is very small, when compared to ordinary schedulers;
- ULWOS2 is extremely portable and can be easily implemented alongside any existing OS or RTOS!
Now let’s take a look at the cons:
- Context switching can be slower than in an ordinary scheduler. This is because ULWOS2 does not preserve the context and cannot resume code execution directly from the point it left before. The constructor that enables thread resuming adds a small amount of code space and a tiny delay (that is not present on an ordinary cooperative or preemptive scheduler);
- A thread can only get suspended by code running inside its main function. This means you can’t perform ULWOS2 calls from other functions inside a thread;
- Since there is no context saving, local non-static variables are always destroyed when a thread is suspended. One must use static or references to variables in order to keep their state throughout thread’s life-cycle;
I hope you enjoy it! I will be back with more examples for other platforms!
ULWOS2 repository: https://github.com/fabiopjve/ULWOS2