November 27, 2014 at 18:57Protothread and cooperative multitasking
We continue to study the planning of small flows. I already talked about two tools in the Linux kernel that are often used for deferred interrupt handling. Today we will talk about a completely different essence - protothread Adam Dunkels, which, although they are out of order, but in the context of the topic under discussion are not unnecessary.
And:
It was not by chance that I decided to combine deferred interrupt handling and cooperative multitasking in one series of articles. The entities that I consider in the cycle, and the ideas that they implement, are of great importance not only in the context of the indicated tasks, but also in general for real-time systems.
They are mainly united by the issue of planning. The tasklets discussed in the first article, for example, work according to the rules of non-preemptive multitasking. By the way, about cooperative multitasking, I already spoke in some detail in one of the previous articles .
Protothreads are lightweight, stackless threads implemented on pure C. One of the possible uses is the implementation of cooperative multitasking, which does not require large overheads. For example, they can be used in embedded systems with a strict memory limit or in nodes of a wireless sensor network.
Habrahabr already has a good article ldir about multitasking based on protothreads, it discusses the practical side of the issue: the capabilities of the library, how to apply it. The article is accompanied by interesting and illustrative examples.
There will be more about how this works. Later in this section I will provide a free and somewhat reworked translation of information from the Adam Dunkels website., the creator of protothreads, which describes in detail both the library itself and the implementation details, so that anyone can enjoy the original and go to the next section.
Key features and benefits of protothreads:
Protothreads are implemented using continuation, which represent the current state of execution at a specific place in the program, but does not support call history and local variables. Here you need to be especially careful - you need to use local variables very carefully! Protothreads do not have a dedicated stack; there are nowhere to store local variables. If a stream is used only once, then variables can be declared as static. Otherwise, you can, for example, wrap protothread in your structure, and store the variables right there. In general, I want to say that you need to be aware that the misuse of local variables can lead to unpredictable results.
In this implementation, the role of the state is played by a positive integer - the current line number of the program. Control is done using switch (), similar to how it happens in the Duff method and co-programs for implementing Simon Tatham . Protothreads are similar to generators in Python, but they are designed for different purposes: protothreads provide a lock inside a function in C, while Python provides multiple exit from the generator.
An important limitation of the implementation: the code inside protothread itself cannot fully use the switch () statement. However, this limitation is possible using the capabilities of some compilers, for example, gcc.
The whole library is implemented on macros, since macros, unlike simple functions, can change the control flow only using standard C constructions.
The main API includes the following macros:
Now let's see how macros work. First, consider a program that uses protothreads. The Protothread example executes an eternal loop, where it first waits until the counter reaches a certain value, then displays a message and resets the counter.
Now take a look at a simplified version of the macros used in the example:
The pt structure consists of a single lc field (short for local continuation). Notice the PT_BEGIN and PT_END, which respectively open and close the switch statement, as well as the slightly more complex macro PT_WAIT_UNTIL. It uses the built-in macro __LINE__, which returns the current line number of the program file.
Compare the source and deployed versions of the example preprocessor:
The Protothread example now looks like a normal C function. The return value is used to determine the status of the protothread: whether it was locked in anticipation of something, completed, exited, or generated another value. The PT_BEGIN macro contains a case 0 instruction, so the code immediately after this macro will be executed first, because the initial value pt-> lc is 0.
See what the PT_WAIT_UNTIL macro expanded into. The pt-> lc field is now assigned 12, this is the line number, and case 12 appears immediately - thanks to this switch knows exactly where to jump. If the condition is not fulfilled, the function returns 0, which means that the stream is waiting (in the library itself, all these constants are rendered). The next time, when example () is called in main, execution, respectively, will continue with case 12, that is, by checking whether the waiting condition is fulfilled. As soon as the counter reaches 1000, the condition will become true, and example () will now not return 0, but print a message and reset the counter. Further, as expected, we go to the beginning of the body of the cycle.
In a previous articleI cited the code of a primitive cooperative scheduler (section “Non-preemptive scheduler with preserving the order of calls”). After making minor changes, you can adapt it to protothreads. This is quite simple, so I will not give the code. But I suggest that you play with it.
Finally, I propose to compare tasklet, workqueue and protothread. In fact, of course, on the one hand it is not very correct to compare protothread with the means of processing bottom-half interrupts - after all, they were created for different tasks, it is not so easy to replace one with another. On the other hand, the workqueue is also somewhat knocked out of the top three: unlike the rest, it works according to the rules of crowding out planning, its scope is much wider.
Comparison I bring more likely in order to extract useful ideas.
And here is a comparison table:
Each of these approaches has its pros and cons, they are used for different tasks, in the context of which they meet user requests.
For example, at Embox , we had the idea to implement our lightweight threads, which would not have their own stack, like protothread and tasklet, while being controlled by the main schedulers, as implemented in workqueue, and will also support the waiting mechanism in at least some form events (even more than that, use a subset of the same API that full threads use). This approach has several attractive applications for us:
About how we got it, what results we achieved, I will tell you next time, after a while.
And:
- Linux kernel multitasking: interrupts and tasklets
- Linux kernel multitasking: workqueue
- Protothread and cooperative multitasking
What is it and why is all this needed?
It was not by chance that I decided to combine deferred interrupt handling and cooperative multitasking in one series of articles. The entities that I consider in the cycle, and the ideas that they implement, are of great importance not only in the context of the indicated tasks, but also in general for real-time systems.
They are mainly united by the issue of planning. The tasklets discussed in the first article, for example, work according to the rules of non-preemptive multitasking. By the way, about cooperative multitasking, I already spoke in some detail in one of the previous articles .
Cooperative multitasking and protothread
Protothreads are lightweight, stackless threads implemented on pure C. One of the possible uses is the implementation of cooperative multitasking, which does not require large overheads. For example, they can be used in embedded systems with a strict memory limit or in nodes of a wireless sensor network.
Habrahabr already has a good article ldir about multitasking based on protothreads, it discusses the practical side of the issue: the capabilities of the library, how to apply it. The article is accompanied by interesting and illustrative examples.
There will be more about how this works. Later in this section I will provide a free and somewhat reworked translation of information from the Adam Dunkels website., the creator of protothreads, which describes in detail both the library itself and the implementation details, so that anyone can enjoy the original and go to the next section.
Key features and benefits of protothreads:
- Implementation of a control flow sequentially without the use of complex state machines and full multithreading,
- Using conditional locking inside functions in C,
- Protothreads are very light because they don’t have a stack,
- Protothreads can call other functions, but cannot be locked inside the called function, so you need to wrap each function that uses locking in a child protothread. Thus, only explicit blocking is used.
Protothreads are implemented using continuation, which represent the current state of execution at a specific place in the program, but does not support call history and local variables. Here you need to be especially careful - you need to use local variables very carefully! Protothreads do not have a dedicated stack; there are nowhere to store local variables. If a stream is used only once, then variables can be declared as static. Otherwise, you can, for example, wrap protothread in your structure, and store the variables right there. In general, I want to say that you need to be aware that the misuse of local variables can lead to unpredictable results.
In this implementation, the role of the state is played by a positive integer - the current line number of the program. Control is done using switch (), similar to how it happens in the Duff method and co-programs for implementing Simon Tatham . Protothreads are similar to generators in Python, but they are designed for different purposes: protothreads provide a lock inside a function in C, while Python provides multiple exit from the generator.
An important limitation of the implementation: the code inside protothread itself cannot fully use the switch () statement. However, this limitation is possible using the capabilities of some compilers, for example, gcc.
The whole library is implemented on macros, since macros, unlike simple functions, can change the control flow only using standard C constructions.
The main API includes the following macros:
- Initialization macro PT_INIT,
- The PT_BEGIN and PT_END macros declaring the beginning and end of protothread,
- Macros for waiting for condition PT_WAIT_UNTIL and PT_WAIT_WHILE,
- Macros of waiting for the execution of child protothreads PT_WAIT_THREAD and PT_SPAWN,
- Macros restart PT_RESTART and exit PT_EXIT,
- Macro of scheduling (essentially launching) PT_SCHEDULE,
- Macro of the product of the value PT_YIELD,
- Macros for using the semaphores PT_SEM_INIT, PT_SEM_WAIT and PT_SEM_SIGNAL.
Now let's see how macros work. First, consider a program that uses protothreads. The Protothread example executes an eternal loop, where it first waits until the counter reaches a certain value, then displays a message and resets the counter.
#include "pt.h"
static int counter;
static struct pt example_pt;
static
PT_THREAD(example(struct pt *pt))
{
PT_BEGIN(pt);
while(1) {
PT_WAIT_UNTIL(pt, counter == 1000);
printf("Threshold reached\n");
counter = 0;
}
PT_END(pt);
}
int main(void)
{
counter = 0;
PT_INIT(&example_pt);
while(1) {
example(&example_pt);
counter++;
}
return 0;
}
Now take a look at a simplified version of the macros used in the example:
struct pt { unsigned short lc; };
#define PT_THREAD(name_args) char name_args
#define PT_BEGIN(pt) switch(pt->lc) { case 0:
#define PT_WAIT_UNTIL(pt, c) pt->lc = __LINE__; case __LINE__: \
if(!(c)) return 0
#define PT_END(pt) } pt->lc = 0; return 2
#define PT_INIT(pt) pt->lc = 0
The pt structure consists of a single lc field (short for local continuation). Notice the PT_BEGIN and PT_END, which respectively open and close the switch statement, as well as the slightly more complex macro PT_WAIT_UNTIL. It uses the built-in macro __LINE__, which returns the current line number of the program file.
Compare the source and deployed versions of the example preprocessor:
| |
The Protothread example now looks like a normal C function. The return value is used to determine the status of the protothread: whether it was locked in anticipation of something, completed, exited, or generated another value. The PT_BEGIN macro contains a case 0 instruction, so the code immediately after this macro will be executed first, because the initial value pt-> lc is 0.
See what the PT_WAIT_UNTIL macro expanded into. The pt-> lc field is now assigned 12, this is the line number, and case 12 appears immediately - thanks to this switch knows exactly where to jump. If the condition is not fulfilled, the function returns 0, which means that the stream is waiting (in the library itself, all these constants are rendered). The next time, when example () is called in main, execution, respectively, will continue with case 12, that is, by checking whether the waiting condition is fulfilled. As soon as the counter reaches 1000, the condition will become true, and example () will now not return 0, but print a message and reset the counter. Further, as expected, we go to the beginning of the body of the cycle.
In a previous articleI cited the code of a primitive cooperative scheduler (section “Non-preemptive scheduler with preserving the order of calls”). After making minor changes, you can adapt it to protothreads. This is quite simple, so I will not give the code. But I suggest that you play with it.
Comparison
Finally, I propose to compare tasklet, workqueue and protothread. In fact, of course, on the one hand it is not very correct to compare protothread with the means of processing bottom-half interrupts - after all, they were created for different tasks, it is not so easy to replace one with another. On the other hand, the workqueue is also somewhat knocked out of the top three: unlike the rest, it works according to the rules of crowding out planning, its scope is much wider.
Comparison I bring more likely in order to extract useful ideas.
And here is a comparison table:
| Tasklet | Workqueue | Protothreads | |
|---|---|---|---|
| No - they are processed as softirq (on a dedicated stack common to all handlers, at least on Linux on x86) | Yes - they are executed on the stack of worker threads, the number of which is much less than the number of tasks | Not | |
| Fast - minimal extra processing | Fast, but not like tasklets, context switching is required when workers replace each other | Very fast - almost no additional processing, more room for optimization by the compiler | |
| None (except spinlock) | Present in full | Pseudo-semaphores; primitive event expectation | |
| Cooperative planner as softirq; tasklets are supplanted only by hardware interrupts | Workers play the role of a scheduler for work, they themselves are controlled by the main scheduler | Cooperative planner implemented by user |
Each of these approaches has its pros and cons, they are used for different tasks, in the context of which they meet user requests.
For example, at Embox , we had the idea to implement our lightweight threads, which would not have their own stack, like protothread and tasklet, while being controlled by the main schedulers, as implemented in workqueue, and will also support the waiting mechanism in at least some form events (even more than that, use a subset of the same API that full threads use). This approach has several attractive applications for us:
- Replacing the mechanism for deferred interrupt processing;
- Using only lightweight threads in the scheduler will allow using almost full multitasking even for resource-limited embedded systems;
- The previous scenario has one more good thing: when porting a system to a new processor architecture, you first want to get at least some workable system. The implementation of a full-fledged context_switch on the new assembler at this moment is an extra headache. To use only lightweight streams, this is not required.
About how we got it, what results we achieved, I will tell you next time, after a while.
