Protothread and cooperative multitasking
We continue to study the planning of small streams. I already told you about two tools in the Linux kernel that are often used for deferred interrupt handling. Today we will talk about a completely different entity - protothread Adam Dunkels, which, although out of line, are not at all superfluous in the context of the topic under consideration.
And:
I decided to combine deferred interrupt handling and cooperative multitasking in one cycle of articles not by chance. Those entities that I consider in the cycle, and the ideas that they implement, are of great importance not only in the context of the designated tasks, but also in general for real-time systems.
Mostly they are united by the question of planning. Tasklets discussed in the first article, for example, work according to the rules of non-preemptive multitasking. By the way, about cooperative multitasking, I have already described in some detail in a previous article .
')
Protothreads are lightweight chainless streams implemented on pure C. One of the possible applications is the implementation of cooperative multitasking, which does not require large overheads. For example, they can be used in embedded systems with severe memory constraints or in nodes of a wireless sensor network.
On habrahabr there is already a good ldir article about multitasking based on protothreads, it addresses the practical side of the question: the ability of the library, how to use it. The article is accompanied by interesting and illustrative examples.
There will also be more about how it works. Later in this section, I will provide a free and somewhat revised translation of information from the site of Adam Dunkels , the creator of protothreads, which describes in detail both the library itself and implementation details, so that anyone can enjoy the original and go on to the next section.
The main features and benefits of protothreads:
Protothreads are implemented using continuations, which represent the current state of execution in a particular place in a program, but it does not support call history and local variables. Here you need to be especially careful - you need to use local variables very carefully! There is no allocated stack for protothreads, there is no place to store local variables. If the stream is used only once, the variables can be declared as static. Otherwise, you can, for example, wrap the protothread in your structure, and store the variables right there. In general, I want to say that you need to be aware that improper use 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 takes place with the help of switch (), similar to how it happens in the Duff method and with the co-programs of the Simon Tatham implementation . Protothreads are similar to generators in Python, they are only intended for different purposes: protothreads provide a lock inside a function in C, while Python provides multiple output from a generator.
An important limitation of the implementation: the code inside the protothread itself cannot fully use the switch () operator. However, this limitation is possible using the capabilities of some compilers, for example, gcc.
The entire library is implemented on macros, since macros, unlike simple functions, can change the control flow only by means of standard C constructs.
The main API includes the following macros:
We will understand now how macros work. To begin, consider a program that uses protothreads. Protothread example performs an eternal loop, where it first waits until the counter reaches a certain value, then displays a message and resets the counter.
Now let's take a look at the simplified version of the macros used in the example:
The pt structure consists of a single lc field (abbreviated from local continuation). Note 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 embedded macro __LINE__, which returns the current line number of the program file.
Let's compare the source and the expanded version of example by the 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 is blocked waiting for something, completed, exited, or generated the next value. The PT_BEGIN macro contains a case 0 instruction, so the code that goes right after this macro will be executed first, because the initial value pt-> lc is 0.
See what the PT_WAIT_UNTIL macro is deployed to. The pt-> lc field is now assigned 12, this is the line number, and then case 12 appears - thanks to this switch knows exactly where to jump. If the condition is not fulfilled, the function returns 0, which means that the thread is waiting (in the library itself, all these constants are stored). The next time, when example () is called in main, the execution will proceed accordingly with case 12, that is, from checking whether the waiting condition is met. As soon as the counter reaches 1000, the condition will become true, and example () will now not return 0, but will print a message and reset the counter. Further, as expected, go to the beginning of the body of the cycle.
In one of the previous articles, I gave the code of a primitive cooperative scheduler (section “Non-displacing scheduler with preserving the order of calls”). By making minor changes, you can adapt it for protothreads. It's pretty simple, so I will not give the code. But wishing to propose to play.
Finally, I propose to compare the tasklet, workqueue and protothread. In fact, of course, on the one hand, it is not very correct to compare protothread with the bottom-half interrupt handling tools — after all, they are designed for different tasks, you cannot just replace one with another. On the other hand, the workqueue is also somewhat knocked out of the troika: unlike the others, it works according to the rules of repressive planning, its scope is much broader.
Comparison I give more likely to extract useful ideas.
Here is the comparative table:
Each of these approaches has its own pros and cons, they are used for different tasks, in the context of which they respond to user requests.
For example, in Embox , we had an idea to implement our light threads that do not have their own stack, like protothread and tasklet, and will be managed by the main schedulers, as implemented in workqueue, and will also support the waiting mechanism in some form. events (even more so - use a subset of the same API that uses full-fledged threads). This approach has several attractive applications for us:
About how we did it, what results we have achieved, I will tell you next time, after a while.
And:
- Multitasking in the Linux kernel: interrupts and tasklets
- Multitasking in the Linux kernel: workqueue
- Protothread and cooperative multitasking
What is it and why is all this necessary?
I decided to combine deferred interrupt handling and cooperative multitasking in one cycle of articles not by chance. Those entities that I consider in the cycle, and the ideas that they implement, are of great importance not only in the context of the designated tasks, but also in general for real-time systems.
Mostly they are united by the question of planning. Tasklets discussed in the first article, for example, work according to the rules of non-preemptive multitasking. By the way, about cooperative multitasking, I have already described in some detail in a previous article .
')
Cooperative multitasking and protothread
Protothreads are lightweight chainless streams implemented on pure C. One of the possible applications is the implementation of cooperative multitasking, which does not require large overheads. For example, they can be used in embedded systems with severe memory constraints or in nodes of a wireless sensor network.
On habrahabr there is already a good ldir article about multitasking based on protothreads, it addresses the practical side of the question: the ability of the library, how to use it. The article is accompanied by interesting and illustrative examples.
There will also be more about how it works. Later in this section, I will provide a free and somewhat revised translation of information from the site of Adam Dunkels , the creator of protothreads, which describes in detail both the library itself and implementation details, so that anyone can enjoy the original and go on to the next section.
The main features and benefits of protothreads:
- Implementing sequentially control flow without using complex state machines and full multithreading,
- Using conditional locking inside functions on C,
- The protothreads are very light, since they have no stack,
- Protothreads can call other functions, but cannot be locked inside the called function, so you need to wrap each function that uses the lock into a child protothread. Thus, only explicit blocking is used.
Protothreads are implemented using continuations, which represent the current state of execution in a particular place in a program, but it does not support call history and local variables. Here you need to be especially careful - you need to use local variables very carefully! There is no allocated stack for protothreads, there is no place to store local variables. If the stream is used only once, the variables can be declared as static. Otherwise, you can, for example, wrap the protothread in your structure, and store the variables right there. In general, I want to say that you need to be aware that improper use 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 takes place with the help of switch (), similar to how it happens in the Duff method and with the co-programs of the Simon Tatham implementation . Protothreads are similar to generators in Python, they are only intended for different purposes: protothreads provide a lock inside a function in C, while Python provides multiple output from a generator.
An important limitation of the implementation: the code inside the protothread itself cannot fully use the switch () operator. However, this limitation is possible using the capabilities of some compilers, for example, gcc.
The entire library is implemented on macros, since macros, unlike simple functions, can change the control flow only by means of standard C constructs.
The main API includes the following macros:
- Initialization macro PT_INIT,
- PT_BEGIN and PT_END macros declaring the beginning and end of the protothread,
- The macros to wait for the condition PT_WAIT_UNTIL and PT_WAIT_WHILE,
- Wait execution macros for child protothreads PT_WAIT_THREAD and PT_SPAWN,
- PT_RESTART restart and PT_EXIT exit macros,
- Planning macro (essentially launch) PT_SCHEDULE,
- Macro of the product of the PT_YIELD value,
- Macros for using the semaphores PT_SEM_INIT, PT_SEM_WAIT and PT_SEM_SIGNAL.
We will understand now how macros work. To begin, consider a program that uses protothreads. Protothread example performs 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 let's take a look at the 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 (abbreviated from local continuation). Note 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 embedded macro __LINE__, which returns the current line number of the program file.
Let's compare the source and the expanded version of example by the 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 is blocked waiting for something, completed, exited, or generated the next value. The PT_BEGIN macro contains a case 0 instruction, so the code that goes right after this macro will be executed first, because the initial value pt-> lc is 0.
See what the PT_WAIT_UNTIL macro is deployed to. The pt-> lc field is now assigned 12, this is the line number, and then case 12 appears - thanks to this switch knows exactly where to jump. If the condition is not fulfilled, the function returns 0, which means that the thread is waiting (in the library itself, all these constants are stored). The next time, when example () is called in main, the execution will proceed accordingly with case 12, that is, from checking whether the waiting condition is met. As soon as the counter reaches 1000, the condition will become true, and example () will now not return 0, but will print a message and reset the counter. Further, as expected, go to the beginning of the body of the cycle.
In one of the previous articles, I gave the code of a primitive cooperative scheduler (section “Non-displacing scheduler with preserving the order of calls”). By making minor changes, you can adapt it for protothreads. It's pretty simple, so I will not give the code. But wishing to propose to play.
Comparison
Finally, I propose to compare the tasklet, workqueue and protothread. In fact, of course, on the one hand, it is not very correct to compare protothread with the bottom-half interrupt handling tools — after all, they are designed for different tasks, you cannot just replace one with another. On the other hand, the workqueue is also somewhat knocked out of the troika: unlike the others, it works according to the rules of repressive planning, its scope is much broader.
Comparison I give more likely to extract useful ideas.
Here is the comparative table:
| Tasklet | Workqueue | Protothreads | |
|---|---|---|---|
| No - are processed as softirq (on a specially allocated stack shared by all handlers, at least in Linux on x86) | Yes - are executed on the stack of worker-threads, the number of which is much less than the number of tasks | Not | |
| Fast - minimal additional 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 waiting for events | |
| Cooperative scheduler like softirq; tasklets are only supplanted by hardware interrupts | Workers play the role of scheduler for work, managed by the main scheduler themselves. | Cooperative scheduler, implemented by the user |
Each of these approaches has its own pros and cons, they are used for different tasks, in the context of which they respond to user requests.
For example, in Embox , we had an idea to implement our light threads that do not have their own stack, like protothread and tasklet, and will be managed by the main schedulers, as implemented in workqueue, and will also support the waiting mechanism in some form. events (even more so - use a subset of the same API that uses full-fledged threads). This approach has several attractive applications for us:
- Replacement delayed interrupt handling mechanism;
- Using only light streams in the scheduler will allow the use of almost full-fledged multitasking, even for resource-constrained embedded systems;
- The previous scenario is good for something else: when porting a system to a new processor architecture, you first want to get at least some workable system. Implementing a full context_switch on a new assembler at this moment is an extra headache. For the use of lightweight threads only, this is not required.
About how we did it, what results we have achieved, I will tell you next time, after a while.
Source: https://habr.com/ru/post/244361/
All Articles