Multitasking in Continuation Based Microcontrollers
C programmers are not spoiled by the language features anymore, and developers of embedded systems on microcontrollers are limited even more, often their programs run on bare hardware, without OS support.
The possibility of using C coroutines, generators, cooperative multitasking can often greatly simplify the program and save power, but these capabilities of the language are not obvious and many do not know about them.
Continuations (contionuation) allow you to remember the status of the program flow (function), and return to this place in the future.
Using continuations, we can get coroutines (coroutine) , and these are practically ready-made generators , iterators, and cooperative multitasking .
Here are some ways to implement C continuations and examples of libraries that use these methods:
In this article, I look at the Adam Dunkels protothreads library. It is simple and minimalist, consists of a set of macros in several header files, compatible with C ++. The library contains everything you need; it has no dependencies on other libraries, the platform and the compiler. Does not use dynamic memory. If you have gcc, the library will provide additional features through the use of variable labels. In general, this library seemed to me the most convenient for programming embedded applications, where there is a wide variety of architectures, compilers and operating systems.
How the library works is well described on its website, I will give only a brief description of the API and a few examples of use. Of course, the use of the library is only “syntactic sugar” and everything that it can be can be implemented using, for example, finite automata (in fact, the library transforms your functions into implicit finite automata). But in a number of tasks, the library reduces the amount of program text, increases linearity, clarity and, as a result, can reduce development time and the likelihood of errors. If you solve a problem using a finite state machine and you have a dozen or more states, many of them go sequentially, then, most likely, protothreads can greatly simplify your life, and in any case it is useful to have an alternative. In my experience, the source code of a program using protothreads is about 20 to 50% less than the equivalent written using state machines.
The examples given in the article were written under Windows, they work in MinGW and Visual Studio, but attention! In Visual Studio, in the DEBUG configuration, the protothreads library, as it is, is not compiled!
The reason is that the __LINE__ macro in the DEBUG configuration in VS for some reason turns from a constant into a function call, it is easily treated if you replace in the lc-switch.h file
on
In gcc, the library works without changes for all platforms and processors.
To use the library, you need to download and unpack .h files into your project and connect the header:
So, what can we get from the library:
The continuations themselves are not very useful, but they are the basis for other program structures.
The function with the possibility of continuation is declared as:
or using a macro like this:
The pt argument is a pointer to the continuation context, which, in one way or another, stores the place where the function was interrupted.
The function can return the result through additional arguments, by reference.
Before the beginning of the statements, there should be a macro PT_BEGIN (pt) , at the end of the stream - PT_END (pt) . If you need to perform some actions with each function call - they are put before the macro PT_BEGIN (pt) . This may be, for example, updating the value of a timer, counter, etc.
The PT_YIELD (pt) command returns the result and the next time the function is called, the function will continue from the next statement.
The stream interrupts (for example, in case of an error) are performed by the macro PT_EXIT (pt) . After reaching the end of the stream or after interruption ( PT_END (pt) and PT_EXIT (pt) macros ) , restarted with the PT_RESTART command (pt) , the function “rewinds” to the beginning and starts the work again after the next call.
The function returns a constant - the cause of the function interruption: PT_WAITING - waiting for an event, PT_YIELDED - returning a value, PT_EXITED - output using the PT_EXIT command (pt) , PT_ENDED - the function reached the end of PT_END (pt) .
Before the first use of the continuation, it is necessary to initialize its context with the PT_INIT macro (pt) .
Variables that must maintain their values ​​between calls must be declared as static, or passed to the function by reference.
When you need to get a sequence of some data on a complex algorithm and the method of obtaining each next element depends on certain conditions and previous values, it is convenient to use a generator.
Here is an example of generating Fibonacci numbers:
Classical coroutines are program threads that can transfer control to each other, and then return to the interrupt location. Coroutines are used when among several program streams (functions) it is not clear what should be the main program and what should be the subroutine (Knut, Volume I of the book “The Art of Programming”). For example, a part of your program somehow produces data, another part somehow consumes it. And the consumer and the manufacturer is quite complicated. When you are writing a program of a data producer, you want to cause data consumption as a function when you have part of the data ready. But when you are programming a data consumer, you already want to make the consumer the main program, and call the generation function when there is an opportunity to receive and process data. In this case, instead of the program-subprogram relations, the coroutine-coroutine relations are quite appropriate. You can still first generate all data in memory, and then consume them all at once, but there may be more data than memory, this is especially true for embedded systems. Coroutines are also easy to get with continuations.
For example, we need to generate a large amount of xml data, then archive it, then save it to a file or transfer it over the network. For the sake of simplicity, we only implement generation and save. Various error checks for memory and file operations are also omitted. makeXmlLine is our manufacturer. Parses the input clause and generates an XML string for each call. writeXmlLine is a consumer, with each call it saves a line to a file. Coroutines are called alternately until the manufacturer's coroutine ends (returns the result PT_EXITED ).
In embedded systems, you always need to wait for something - the arrival of data at the port, freeing the buffer, triggering the timer, completing another operation, pressing buttons, keeping pauses, etc. The use of multitasking allows you to move from an asynchronous programming model to a synchronous one. Whether this is appropriate or not depends on the situation.
Cooperative multitasking is easily obtained using coroutines with a simple thread manager. In the simplest case, a dispatcher is an infinite loop that sequentially calls coroutines. For more complex dispatchers, you can add / remove tasks, a priority system, etc.
The use of coroutine-based multitasking gives the following advantages over preemptive multitasking:
For multitasking, Protothreads provides the following primitives:
If you want to run many identical threads, pass to the stream function a link to the structure that stores all the data and variables that the stream should use, for each thread. For a single thread, all variables can be stored inside a function, simply by declaring them to be static.
For an example of multithreading, let's make a simple console Arkanoid under windows (a little more than 100 lines). Pastebin file: arkanoid.c
')
We will have 3 threads: a racket, a ball and a playing field. Another auxiliary subtask pauseThread will pause.
The scheduler will be simple: we transfer control to each of the streams, then a 10ms pause. The game ends if any of the streams ends (the ball may fly off the field, or we can knock out all the bricks).
The printField stream first creates a playing field in memory, then, in a loop, waits for the field change flag and redraws the entire field on the screen. If the bricks run out, the flow ends.
The controlThr thread draws a bit on the field, waits for the button to be pressed, and moves the bit. Or interrupt the game by pressing "q".
The pauseThread thread simply pauses the necessary time, made for an example of calling one task from another and using PT_SPAWN .
The ballThread stream moves the ball across the field at a given speed, knocking bricks and making bounces off the walls and bits. This stream is completed if the ball flies over the field.
Just a couple of tips:
If you are using gcc, I recommend putting one #define before connecting the library, like this:
This will allow you to use the gcc extension “Labels as Values”, and you can interrupt and switch the execution flow inside the switch statement. Otherwise, the continuations themselves will be built with the help of the switch operator, they will not get along with your switch.
Please note that after the end of the stream, it automatically starts over. After SCHEDULE returns 0, you must either stop calling it or, at the end of the stream, block it permanently: PT_WAIT_WHILE (pt, 1)
The possibility of using C coroutines, generators, cooperative multitasking can often greatly simplify the program and save power, but these capabilities of the language are not obvious and many do not know about them.
Continuations (contionuation) allow you to remember the status of the program flow (function), and return to this place in the future.
Using continuations, we can get coroutines (coroutine) , and these are practically ready-made generators , iterators, and cooperative multitasking .
Here are some ways to implement C continuations and examples of libraries that use these methods:
- Saving the current stack and processor registers using assembler inserts (coro library), or standard POSIX context save / restore context getcontext / setcontext or save / restore setjmp / longjmp stack (libpcl, libcoroutine, libconcurrency, libcoro libraries).
- The cunning use of the switch statement (known as the “Duff Device” ).
These include, for example, the protothreads library (a canonical version from Adam Dunkels , and its extended counterpart from Larry Ruane ), the coroutine library from Simon Tatham, author of PuTTY. - Extend GCC Tag Variables, (protothreads library).
In this article, I look at the Adam Dunkels protothreads library. It is simple and minimalist, consists of a set of macros in several header files, compatible with C ++. The library contains everything you need; it has no dependencies on other libraries, the platform and the compiler. Does not use dynamic memory. If you have gcc, the library will provide additional features through the use of variable labels. In general, this library seemed to me the most convenient for programming embedded applications, where there is a wide variety of architectures, compilers and operating systems.
How the library works is well described on its website, I will give only a brief description of the API and a few examples of use. Of course, the use of the library is only “syntactic sugar” and everything that it can be can be implemented using, for example, finite automata (in fact, the library transforms your functions into implicit finite automata). But in a number of tasks, the library reduces the amount of program text, increases linearity, clarity and, as a result, can reduce development time and the likelihood of errors. If you solve a problem using a finite state machine and you have a dozen or more states, many of them go sequentially, then, most likely, protothreads can greatly simplify your life, and in any case it is useful to have an alternative. In my experience, the source code of a program using protothreads is about 20 to 50% less than the equivalent written using state machines.
The examples given in the article were written under Windows, they work in MinGW and Visual Studio, but attention! In Visual Studio, in the DEBUG configuration, the protothreads library, as it is, is not compiled!
The reason is that the __LINE__ macro in the DEBUG configuration in VS for some reason turns from a constant into a function call, it is easily treated if you replace in the lc-switch.h file
#define LC_SET(s) s = __LINE__; case __LINE__: on
#define LC_SET(s) s = __COUNTER__+1; case (__COUNTER__): In gcc, the library works without changes for all platforms and processors.
To use the library, you need to download and unpack .h files into your project and connect the header:
#include "pt.h" So, what can we get from the library:
Continuations
The continuations themselves are not very useful, but they are the basis for other program structures.
The function with the possibility of continuation is declared as:
int name(struct pt *pt [, ]) or using a macro like this:
PT_THREAD(name(struct pt *pt [, ])) The pt argument is a pointer to the continuation context, which, in one way or another, stores the place where the function was interrupted.
The function can return the result through additional arguments, by reference.
Before the beginning of the statements, there should be a macro PT_BEGIN (pt) , at the end of the stream - PT_END (pt) . If you need to perform some actions with each function call - they are put before the macro PT_BEGIN (pt) . This may be, for example, updating the value of a timer, counter, etc.
The PT_YIELD (pt) command returns the result and the next time the function is called, the function will continue from the next statement.
The stream interrupts (for example, in case of an error) are performed by the macro PT_EXIT (pt) . After reaching the end of the stream or after interruption ( PT_END (pt) and PT_EXIT (pt) macros ) , restarted with the PT_RESTART command (pt) , the function “rewinds” to the beginning and starts the work again after the next call.
The function returns a constant - the cause of the function interruption: PT_WAITING - waiting for an event, PT_YIELDED - returning a value, PT_EXITED - output using the PT_EXIT command (pt) , PT_ENDED - the function reached the end of PT_END (pt) .
Before the first use of the continuation, it is necessary to initialize its context with the PT_INIT macro (pt) .
Variables that must maintain their values ​​between calls must be declared as static, or passed to the function by reference.
Generators
When you need to get a sequence of some data on a complex algorithm and the method of obtaining each next element depends on certain conditions and previous values, it is convenient to use a generator.
Here is an example of generating Fibonacci numbers:
#include "pt.h" #include <stdio.h> static int fib(struct pt *pt, int max, int* res) { static int a,b; PT_BEGIN(pt); a=0;b=1; while (a<max) { *res=a; PT_YIELD(pt); b+=a; a=ba; } PT_END(pt); } int main(void) { int value; struct pt pt1; PT_INIT(&pt1); while( fib(&pt1, 1000, &value) < PT_EXITED ){ printf("Value %d\n",value); } return 0; } Coroutines
Classical coroutines are program threads that can transfer control to each other, and then return to the interrupt location. Coroutines are used when among several program streams (functions) it is not clear what should be the main program and what should be the subroutine (Knut, Volume I of the book “The Art of Programming”). For example, a part of your program somehow produces data, another part somehow consumes it. And the consumer and the manufacturer is quite complicated. When you are writing a program of a data producer, you want to cause data consumption as a function when you have part of the data ready. But when you are programming a data consumer, you already want to make the consumer the main program, and call the generation function when there is an opportunity to receive and process data. In this case, instead of the program-subprogram relations, the coroutine-coroutine relations are quite appropriate. You can still first generate all data in memory, and then consume them all at once, but there may be more data than memory, this is especially true for embedded systems. Coroutines are also easy to get with continuations.
For example, we need to generate a large amount of xml data, then archive it, then save it to a file or transfer it over the network. For the sake of simplicity, we only implement generation and save. Various error checks for memory and file operations are also omitted. makeXmlLine is our manufacturer. Parses the input clause and generates an XML string for each call. writeXmlLine is a consumer, with each call it saves a line to a file. Coroutines are called alternately until the manufacturer's coroutine ends (returns the result PT_EXITED ).
#include "pt.h" #include <stdio.h> #include <string.h> #include <malloc.h> static int makeXmlLine(struct pt *pt, char* dst, char* src) { static char* text; // static char * pch; PT_BEGIN(pt); strcpy(dst,"<?xml version=\"1.0\" encoding=\"Windows-1251\"?>"); PT_YIELD(pt); strcpy(dst,"<text>"); PT_YIELD(pt); text=strdup(src); // strtok , pch = strtok (text," ,.!?:"); while (pch != NULL){ sprintf(dst," <word>%s</word>",pch); PT_YIELD(pt); pch = strtok (NULL, " ,.!?:"); } strcpy(dst,"</text>"); PT_YIELD(pt); *dst=0; // , PT_YIELD(pt); free(text); PT_END(pt); } static int writeXmlLine(struct pt *pt, char* fileName, char* str) { static FILE* file; PT_BEGIN(pt); file=fopen(fileName,"w"); // while(*str){ fprintf(file,"%s\n",str); PT_YIELD(pt); } fclose(file); PT_END(pt); } int main(void) { struct pt pt1,pt2; char xmlString[128]; PT_INIT(&pt1); PT_INIT(&pt2); // , while (makeXmlLine(&pt1,xmlString, "Hello, world! Pleased to meet you!") < PT_EXITED) writeXmlLine(&pt2,"file.xml",xmlString); return 0; } Multitasking
In embedded systems, you always need to wait for something - the arrival of data at the port, freeing the buffer, triggering the timer, completing another operation, pressing buttons, keeping pauses, etc. The use of multitasking allows you to move from an asynchronous programming model to a synchronous one. Whether this is appropriate or not depends on the situation.
Cooperative multitasking is easily obtained using coroutines with a simple thread manager. In the simplest case, a dispatcher is an infinite loop that sequentially calls coroutines. For more complex dispatchers, you can add / remove tasks, a priority system, etc.
The use of coroutine-based multitasking gives the following advantages over preemptive multitasking:
- all operations are atomic, data does not need to be protected by critical sections and mutexes. The primitives of thread synchronization are either not needed, or implemented elementarily, and completely programmatically.
- low overhead flow. Memory consumption per thread can be limited to two bytes that store the return point; threads do not have their own stack. Switching between threads is the read instructions of the processor in user space. This means that the number of threads can be in the millions.
- You can block the stream until a combination of several events occurs. For example, waiting for any of the events: a data packet came, or a timer started, or a user canceled the operation, or an error occurred
- a blocked thread can be interrupted, whereas standard blocking operations cannot usually be interrupted
For multitasking, Protothreads provides the following primitives:
- the PT_WAIT_UNTIL and PT_WAIT_WHILE macros for blocking a thread until a certain event occurs
- macro PT_WAIT_THREAD , stops the stream until another thread ends
- macro PT_SPAWN allows one thread to start another thread from the beginning and wait for its completion
- macro PT_SCHEDULE , primitive stream manager, performs the next step of the coroutine and returns whether it has completed its work or not yet
- pt_sem structure, PT_SEM_INIT , PT_SEM_WAIT , PT_SEM_SIGNAL - primitives for working with semaphores are practically useless
If you want to run many identical threads, pass to the stream function a link to the structure that stores all the data and variables that the stream should use, for each thread. For a single thread, all variables can be stored inside a function, simply by declaring them to be static.
For an example of multithreading, let's make a simple console Arkanoid under windows (a little more than 100 lines). Pastebin file: arkanoid.c
')
We will have 3 threads: a racket, a ball and a playing field. Another auxiliary subtask pauseThread will pause.
The scheduler will be simple: we transfer control to each of the streams, then a 10ms pause. The game ends if any of the streams ends (the ball may fly off the field, or we can knock out all the bricks).
while (PT_SCHEDULE(printField(&fieldPt)) && PT_SCHEDULE(controlThr(&ctrlPt)) && PT_SCHEDULE(ballThread(&ballPt))) Sleep(10); The printField stream first creates a playing field in memory, then, in a loop, waits for the field change flag and redraws the entire field on the screen. If the bricks run out, the flow ends.
The controlThr thread draws a bit on the field, waits for the button to be pressed, and moves the bit. Or interrupt the game by pressing "q".
The pauseThread thread simply pauses the necessary time, made for an example of calling one task from another and using PT_SPAWN .
The ballThread stream moves the ball across the field at a given speed, knocking bricks and making bounces off the walls and bits. This stream is completed if the ball flies over the field.
Just a couple of tips:
If you are using gcc, I recommend putting one #define before connecting the library, like this:
#define LC_INCLUDE "lc-addrlabels.h" #include "pt.h" This will allow you to use the gcc extension “Labels as Values”, and you can interrupt and switch the execution flow inside the switch statement. Otherwise, the continuations themselves will be built with the help of the switch operator, they will not get along with your switch.
Please note that after the end of the stream, it automatically starts over. After SCHEDULE returns 0, you must either stop calling it or, at the end of the stream, block it permanently: PT_WAIT_WHILE (pt, 1)
Source: https://habr.com/ru/post/143318/
All Articles