Coroutines? The simplest implementation in C, protothread and Arduino
*sometimes you want to escape from the controlled everyday life
Coroutines are functions that can pause their execution and resume it later, preserving their state between calls. This allows you to perform multiple tasks simultaneously without having to create separate threads or processes.
And then the usual blah-blah begins about how to write these most crappy words in the language, problems and crutches for solving them.
But no, the purpose of the article is to dig into “how it works” at a level close to the hardware. As an example of hardware, let's take Arduino with 1 thread.
Let's start from afar, let's start with Duff's Device.
Tom was working on the issue of how to speed up seemingly simple code.
send(to, from, count)
register short *to, *from;
register count;
{
do{
*to = *from++;
}while(--count>0);
}The natural move was to think in the direction of reducing the number of iterations in while. Because… describing all this would take a lot and a long time. In general, if you look at it in the most stupid way, the generated assembler has too many transitions, precisely because of while. You just need to replace the cycle from 0 to n with lines like *to = *from++; (it smells like vectorization, but we only have an arduino chip, so let's forget this smart word for a while). And then Tom had a brilliant idea, what if I just change the comparisons to goto (sounds of ugh and eye rolling). But using an interesting feature of the C compiler switch case, it's like syntax sugar around GOTO, that is, you can freely and without worrying write code logically torn by these transitions and it will compile. And this is what he got:
send(to, from, count)
register short *to, *from;
register count;
{
register n=(count+7)/8;
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n>0);
}
}As he himself wrote: It amazes me that after 10 years of writing C there are still little corners that I haven't explored fully. (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.) (I think no translation needed)
As a result, he significantly reduced the number of checks and transitions, and was able to accelerate the code. In addition, this code is indicative of state management.
Implementation of Coroutines with the Simplest Round Robin
Let's consider the implementation of coroutins with the simplest Round Robin. With a few exceptions, we will not complicate the matter, we will discard time quantization management, etc., and take only: Cyclic order (tasks are processed in the order they arrive and without the possibility of interruption without special syntax. After the task execution time is over, it is placed at the end of the queue, and the processor moves on to the next task).
Below, for simplicity, we will call these flows.
Let's go back to the Duff machine code, let's say we have 2 threads. Thread 1 writes “hello” and waits for the second thread to set the global variable to 1. And the second waits for tickcount to increase by 50 and sets global to 1.
Let's try to do this on pseudo C.
we need to somehow understand where we should return to. We have unique … line numbers.
we need to store it somewhere. Let's have a structure like this
struct context { unsigned short line_number; };
enum { WAITING, YIELDED, EXITED };Then the flow will look like this:
int thread1(struct context * context) {
switch(context -> line_number) {
case 0:;
printf("Привет\n");
context -> line_number = __LINE__; // Запоминаем текущую строку
case __LINE__: //при следующем заходе switch сможет перекинуть сюда
if (global !=1){ // Проверяем условие
return WAITING; // Возвращаемся, если условие не выполнено
}
printf("Мир\n");
}//закрываем switch
context -> line_number // Обнуляем line_number в конце
return EXITED;
}Stream 2:
int thread1(struct context * contex, int *start_tick_count) {
switch(context -> line_number) {
case 0:;
context -> line_number = __LINE__; // Запоминаем текущую строку
case __LINE__: //при следующем заходе switch сможет перекинуть сюда
printf("waiting");
if ((current_ticks() - *start_tick_count) < 50){ // Проверяем условие
return WAITING; // Возвращаемся, если условие не выполнено
}
}//закрываем switch
context -> line_number // Обнуляем line_number в конце
return EXITED;
}And our super advanced round robin scheduler:
int global = 0;
int start_ticks=0;
void main(…){
context c1;
context c2;
start_ticks = current_ticks();
while(true){
thread1(c1);
thread2(c2, & start_ticks)
}
}The output will be “hello”, several times “waiting” and “peace”
How it works: inside functions, before exiting return WAITING; the state to return to is saved. The next time switch is called, it will simply jump to the case LINE we need and continue execution.
All that's left is to wrap it all in macros, and we've invented simple lightweight coroutins that will even work for arduino. But… it's all been done for us.
Protothreads
https://dunkels.com/adam/pt/ a project that is magnificent in its simplicity.
Let's try writing some code for Arduino as if it were a multithreaded system.
The idea is simple: we spin the wheels until the sonar sensor shows that the distance is less than 25 cm. Then we try to turn until the distance increases.
In total we need 3 coroutins
1. Reads the sonar sensor distance
static PT_THREAD(read_distance(struct pt *pt)) {
PT_BEGIN(pt);
while(1) {
int currentDistance = sonarForward.ping_cm();
if(currentDistance == 0) {
currentDistance = 100;
}
#ifdef DEBUG_DISTANCE
printDistance(currentDistance);
#endif
distance = currentDistance;
PT_SLEEP(pt, 100);
}
PT_END(pt);
}Moves forward while the distance to the object is more than 25 cm
static PT_THREAD(move_forward(struct pt *pt)) {
PT_BEGIN(pt);
while(1) {
PT_WAIT_UNTIL(pt, distance > MIN_DISTANCE_FORWARD);
printText("forward");
#ifndef EMULATION
motor1.run(FORWARD);
motor2.run(FORWARD);
motor1.setSpeed(200);
motor2.setSpeed(200);
#endif
PT_SLEEP(pt, 100);
}
PT_END(pt);
}Turns around if the distance is less than 25 cm
static PT_THREAD(try_rotate(struct pt *pt)) {
PT_BEGIN(pt);
while(1) {
PT_WAIT_UNTIL(pt, distance < MIN_DISTANCE_FORWARD);
printText("rotate");
#ifndef EMULATION
motor1.run(BACKWARD);
motor2.run(FORWARD);
motor1.setSpeed(150);
motor2.setSpeed(150);
#endif
PT_SLEEP(pt, 100);
}
PT_END(pt);
}For portability of the solution, for example, on phreads you can wrap calls in similar macros, for example:
#define PT_THREAD(name) void *name(void *arg)
#define PT_WAIT_UNTIL(pt, condition) \
do { \
if (!(condition)) { \
(pt)->condition = false; \
pthread_cond_wait(&(pt)->cond, &(pt)->mutex); \
} \
} while (0)And then it will even be possible to switch between operating modes from co-threaded to multi-threaded… but that's a completely different story.
