November 25, 2014 at 17:38Linux kernel multitasking: workqueue
Continuing the theme of multithreading in the Linux kernel. Last time I talked about interrupts, their processing and tasklets, and since it was originally supposed to be one article, in my story about workqueue I will refer to tasklets, believing that the reader is already familiar with them.
Like last time, I will try to make my story as detailed and detailed as possible.
Cycle Articles:
Workqueues are more complex and heavy entities than tasklets. I will not even try to describe here all the subtleties of the implementation, but the most important, I hope, I will analyze in more or less detail.
Workqueues, like tasklets, are used for deferred processing of interrupts (although they can be used for other purposes), but, unlike tasklets, they are executed in the context of the kernel process, respectively, they are not required to be atomic and can use sleep () function, various synchronization tools, etc.
Let's first understand how the workqueue processing process is generally organized. In the picture, it is shown very approximately and simplistically, as everything actually happens, is described in detail below.
There are several entities involved in thisdark matter.
Firstly, a work item (for short, just work) is a structure that describes a function (for example, an interrupt handler) that we want to schedule. It can be taken as an analogue of the tasklet structure. When planning tasks were added to the queues hidden from the user, now we need to use a special queue - workqueue .
Tasklets are raked by the scheduler function, and workqueues are handled by special threads called workers.
Worker's provide asynchronous execution of work'ov from workqueue. Although they call work'i in the order of the queue, in the general case there is no question of strict, sequential execution: nevertheless, there are crowding out, sleep, waiting, etc.
In general, workers are kernel threads, that is, they are controlled by the main Linux kernel scheduler. But workers partially interfere in planning for additional organization of parallel execution of work'ov. More about this below.
To outline the main features of the workqueue mechanism, I suggest exploring the API.
Parameters fmt and args are the printf format for the name and its arguments. The max_activate parameter is responsible for the maximum number of jobs that from this queue can be executed in parallel on one CPU.
A queue can be created with the following flags:
Particular attention should be paid to the WQ_UNBOUND flag . By the presence of this flag, queues are divided into tethered and untethered.
In attached queues, work is attached to the current CPU when added, that is, in such queues, work is executed on the kernel that plans it. In this regard, the attached queues resemble tasklets.
In untethered queues, work can be executed on any core.
An important property of the workqueue implementation in the Linux kernel is the additional organization of parallel execution, which is present in the attached queues. More about it is written below, now I’ll say that it is implemented in such a way that as little memory as possible is used, and that the processor does not stand idle. This is all implemented with the assumption that one work does not use too many processor cycles.
For untethered queues, this is not. In essence, such queues simply provide context for the work and start them as early as possible.
Thus, untethered queues should be used if intense processor load is expected, since in this case the scheduler will take care of parallel execution on several cores.
By analogy with tasklets, work'am can be assigned the priority of execution, normal or high. Priority is common for the whole turn. By default, the queue has normal priority, and if you set the WQ_HIGHPRI flag , then, accordingly, high.
The WQ_CPU_INTENSIVE flag only makes sense for bound queues. This flag is a refusal to participate in an additional parallel execution organization. This flag should be used when it is expected that the work will consume a lot of processor time, in this case it is better to shift the responsibility to the scheduler. About this in more detail below.
Flags WQ_FREEZABLE and WQ_MEM_RECLAIMare specific and go beyond the scope of the topic, so we will not dwell on them in detail.
Sometimes it makes sense not to create your own queues, but to use common ones. The main ones are:
Now we will deal with work'ami. First, take a look at the initialization, declaration, and preparation macros:
In the queue, work is added using the functions:
Here it is worth stopping in more detail. Although we specify the queue as a parameter, in fact, the work is not placed in the workqueue itself, as it may seem, but in a completely different entity - in the queue list of the worker_pool structure. The worker_pool structure is , in fact, the most important entity in organizing the workqueue mechanism, although for the user it remains behind the scenes. Workers work with them, and they contain all the basic information.
Now let's see what pools are in the system.
To start, the pools for the attached queues (in the picture). For each CPU, two worker pools are statically allocated: one for high-priority work'ov, the other - for work'ov with normal priority. That is, if we have four cores, then there will be only eight attached pools, despite the fact that the workqueue can be any number.
When we create a workqueue, a service pool_workqueue (pwq) is allocated for each CPU . Each such pool_workqueue is associated with a worker pool, which is allocated on the same CPU and matches the priority of the queue type. Through them, the workqueue interacts with the worker pool.
Workers perform work from the worker pool indiscriminately, without distinguishing which workqueue they originally belonged to.
For untethered queues, worker pools are allocated dynamically. All queues can be divided into equivalence classes according to their parameters, and for each such class its own worker pool is created. Access to them is carried out using a special hash table, where the key is a set of parameters, and the value, respectively, worker pool.
In fact, for untethered queues, everything is a little more complicated: if pwq and queues for each CPU were created for attached queues, then they are created for each NUMA node , but this is an additional optimization, which we will not discuss in detail.
I’ll also give a few functions from the API to complete the picture, but I won’t talk about them in detail:
Now, as we became acquainted with the API, let's try to understand in more detail how this all works and is managed.
Each pool has a set of workers who rake tasks. Moreover, the number of workers changes dynamically, adapting to the current situation.
As we have already seen, workers are threads that perform work in the context of the kernel. Worker gets them in order one after another from the worker pool associated with it, and work, as we already know, can belong to different source queues.
Workers can conditionally be in three logical states: they can be idle, running, or managing.
Worker may be idleand do nothing. This, for example, when all work'i already executed. When the worker enters this state, he falls asleep and, accordingly, will not be executed until he is woken up;
If pool management is not required and the list of scheduled jobs is not empty, then the worker starts to execute them. Such workers will conditionally be called running .
If necessary, worker assumes the role of pool manager . A pool can either have only one manager worker, or not at all. Its task is to maintain the optimal number of workers per pool. How he does it? Firstly, workers who are idle for a long time are deleted. Secondly, new workers are created if three conditions are satisfied at once:
However, the last condition has its own nuances. If the pool queues are untethered, then running workers are not taken into account, for them this condition is always true. The same is true if a worker executes a task from an attached queue , but with the WQ_CPU_INTENSIVE flag . At the same time, in the case of attached queues, since workers work with work from a common pool (which is one of two for each core in the picture above), it turns out that some of them are considered as working, and some are not. From the same it follows that the execution of work'ov from WQ_CPU_INTENSIVEqueues may not start immediately, but they themselves do not interfere with other work'am. Now it should be clear why this flag is so called and why it is used when we expect that the work will take a long time.
Accounting of working workers is carried out directly from the main scheduler of the Linux kernel. Such a control mechanism provides an optimal concurrency level, preventing the workqueue from creating too many workers, but also not causing the work to wait too long without need.
Those who are interested can see the worker function in the kernel, it is called worker_thread ().
All the described functions and structures can be found in more detail in the include / linux / workqueue.h , kernel / workqueue.c andkernel / workqueue_internal.h . Also on workqueue there is documentation in Documentation / workqueue.txt .
It is also worth noting that the workqueue mechanism is used in the kernel not only for deferred interrupt processing (although this is a fairly common scenario).
Thus, we examined the deferred interrupt processing mechanisms in the Linux kernel - tasklet and workqueue, which are a special form of multitasking. You can read about interrupts, tasklets, and workqueues in the book " Linux Device Drivers " by Jonathan Corbet, Greg Kroah-Hartman, Alessandro Rubini, although the information there is sometimes outdated.
In a comment by Zyomato the article about tasklets, the Linux kernel is also advised. Description of the development process ”R. Lava.
In the next part, I will talk about protothread and cooperative multitasking, try to compare all considered at first glance, different entities and extract some useful ideas.
Like last time, I will try to make my story as detailed and detailed as possible.
Cycle Articles:
- Linux kernel multitasking: interrupts and tasklets
- Linux kernel multitasking: workqueue
- Protothread and cooperative multitasking
Workqueue
Workqueues are more complex and heavy entities than tasklets. I will not even try to describe here all the subtleties of the implementation, but the most important, I hope, I will analyze in more or less detail.
Workqueues, like tasklets, are used for deferred processing of interrupts (although they can be used for other purposes), but, unlike tasklets, they are executed in the context of the kernel process, respectively, they are not required to be atomic and can use sleep () function, various synchronization tools, etc.
Let's first understand how the workqueue processing process is generally organized. In the picture, it is shown very approximately and simplistically, as everything actually happens, is described in detail below.
There are several entities involved in this
Firstly, a work item (for short, just work) is a structure that describes a function (for example, an interrupt handler) that we want to schedule. It can be taken as an analogue of the tasklet structure. When planning tasks were added to the queues hidden from the user, now we need to use a special queue - workqueue .
Tasklets are raked by the scheduler function, and workqueues are handled by special threads called workers.
Worker's provide asynchronous execution of work'ov from workqueue. Although they call work'i in the order of the queue, in the general case there is no question of strict, sequential execution: nevertheless, there are crowding out, sleep, waiting, etc.
In general, workers are kernel threads, that is, they are controlled by the main Linux kernel scheduler. But workers partially interfere in planning for additional organization of parallel execution of work'ov. More about this below.
To outline the main features of the workqueue mechanism, I suggest exploring the API.
About the queue and its creation
alloc_workqueue(fmt, flags, max_active, args...)
Parameters fmt and args are the printf format for the name and its arguments. The max_activate parameter is responsible for the maximum number of jobs that from this queue can be executed in parallel on one CPU.
A queue can be created with the following flags:
- WQ_HIGHPRI
- WQ_UNBOUND
- WQ_CPU_INTENSIVE
- WQ_FREEZABLE
- WQ_MEM_RECLAIM
Particular attention should be paid to the WQ_UNBOUND flag . By the presence of this flag, queues are divided into tethered and untethered.
In attached queues, work is attached to the current CPU when added, that is, in such queues, work is executed on the kernel that plans it. In this regard, the attached queues resemble tasklets.
In untethered queues, work can be executed on any core.
An important property of the workqueue implementation in the Linux kernel is the additional organization of parallel execution, which is present in the attached queues. More about it is written below, now I’ll say that it is implemented in such a way that as little memory as possible is used, and that the processor does not stand idle. This is all implemented with the assumption that one work does not use too many processor cycles.
For untethered queues, this is not. In essence, such queues simply provide context for the work and start them as early as possible.
Thus, untethered queues should be used if intense processor load is expected, since in this case the scheduler will take care of parallel execution on several cores.
By analogy with tasklets, work'am can be assigned the priority of execution, normal or high. Priority is common for the whole turn. By default, the queue has normal priority, and if you set the WQ_HIGHPRI flag , then, accordingly, high.
The WQ_CPU_INTENSIVE flag only makes sense for bound queues. This flag is a refusal to participate in an additional parallel execution organization. This flag should be used when it is expected that the work will consume a lot of processor time, in this case it is better to shift the responsibility to the scheduler. About this in more detail below.
Flags WQ_FREEZABLE and WQ_MEM_RECLAIMare specific and go beyond the scope of the topic, so we will not dwell on them in detail.
Sometimes it makes sense not to create your own queues, but to use common ones. The main ones are:
- system_wq - attached queue for fast work'ov
- system_long_wq - an attached queue for jobs that are supposed to be executed for a long time
- system_unbound_wq - untethered queue
About work'i and their planning
Now we will deal with work'ami. First, take a look at the initialization, declaration, and preparation macros:
DECLARE(_DELAYED)_WORK(name, void (*function)(struct work_struct *work)); /* на этапе компиляции */
INIT(_DELAYED)_WORK(_work, _func); /* во время исполнения */
PREPARE(_DELAYED)_WORK(_work, _func); /* для изменения исполняемой функции */
In the queue, work is added using the functions:
bool queue_work(struct workqueue_struct *wq, struct work_struct *work);
bool queue_delayed_work(struct workqueue_struct *wq, struct delayed_work *dwork, unsigned long delay); /* work будет добавлен в очередь только по истечению delay */
Here it is worth stopping in more detail. Although we specify the queue as a parameter, in fact, the work is not placed in the workqueue itself, as it may seem, but in a completely different entity - in the queue list of the worker_pool structure. The worker_pool structure is , in fact, the most important entity in organizing the workqueue mechanism, although for the user it remains behind the scenes. Workers work with them, and they contain all the basic information.
Now let's see what pools are in the system.
To start, the pools for the attached queues (in the picture). For each CPU, two worker pools are statically allocated: one for high-priority work'ov, the other - for work'ov with normal priority. That is, if we have four cores, then there will be only eight attached pools, despite the fact that the workqueue can be any number.
When we create a workqueue, a service pool_workqueue (pwq) is allocated for each CPU . Each such pool_workqueue is associated with a worker pool, which is allocated on the same CPU and matches the priority of the queue type. Through them, the workqueue interacts with the worker pool.
Workers perform work from the worker pool indiscriminately, without distinguishing which workqueue they originally belonged to.
For untethered queues, worker pools are allocated dynamically. All queues can be divided into equivalence classes according to their parameters, and for each such class its own worker pool is created. Access to them is carried out using a special hash table, where the key is a set of parameters, and the value, respectively, worker pool.
In fact, for untethered queues, everything is a little more complicated: if pwq and queues for each CPU were created for attached queues, then they are created for each NUMA node , but this is an additional optimization, which we will not discuss in detail.
All sorts of little things
I’ll also give a few functions from the API to complete the picture, but I won’t talk about them in detail:
/* Принудительное завершение */
bool flush_work(struct work_struct *work);
bool flush_delayed_work(struct delayed_work *dwork);
/* Отменить выполнение work */
bool cancel_work_sync(struct work_struct *work);
bool cancel_delayed_work(struct delayed_work *dwork);
bool cancel_delayed_work_sync(struct delayed_work *dwork);
/* Удалить очередь */
void destroy_workqueue(struct workqueue_struct *wq);
How workers do their job
Now, as we became acquainted with the API, let's try to understand in more detail how this all works and is managed.
Each pool has a set of workers who rake tasks. Moreover, the number of workers changes dynamically, adapting to the current situation.
As we have already seen, workers are threads that perform work in the context of the kernel. Worker gets them in order one after another from the worker pool associated with it, and work, as we already know, can belong to different source queues.
Workers can conditionally be in three logical states: they can be idle, running, or managing.
Worker may be idleand do nothing. This, for example, when all work'i already executed. When the worker enters this state, he falls asleep and, accordingly, will not be executed until he is woken up;
If pool management is not required and the list of scheduled jobs is not empty, then the worker starts to execute them. Such workers will conditionally be called running .
If necessary, worker assumes the role of pool manager . A pool can either have only one manager worker, or not at all. Its task is to maintain the optimal number of workers per pool. How he does it? Firstly, workers who are idle for a long time are deleted. Secondly, new workers are created if three conditions are satisfied at once:
- there are still tasks to perform (work'i in the pool)
- no idle workers
- there are no working workers (that is, active and not sleeping at the same time)
However, the last condition has its own nuances. If the pool queues are untethered, then running workers are not taken into account, for them this condition is always true. The same is true if a worker executes a task from an attached queue , but with the WQ_CPU_INTENSIVE flag . At the same time, in the case of attached queues, since workers work with work from a common pool (which is one of two for each core in the picture above), it turns out that some of them are considered as working, and some are not. From the same it follows that the execution of work'ov from WQ_CPU_INTENSIVEqueues may not start immediately, but they themselves do not interfere with other work'am. Now it should be clear why this flag is so called and why it is used when we expect that the work will take a long time.
Accounting of working workers is carried out directly from the main scheduler of the Linux kernel. Such a control mechanism provides an optimal concurrency level, preventing the workqueue from creating too many workers, but also not causing the work to wait too long without need.
Those who are interested can see the worker function in the kernel, it is called worker_thread ().
All the described functions and structures can be found in more detail in the include / linux / workqueue.h , kernel / workqueue.c andkernel / workqueue_internal.h . Also on workqueue there is documentation in Documentation / workqueue.txt .
It is also worth noting that the workqueue mechanism is used in the kernel not only for deferred interrupt processing (although this is a fairly common scenario).
Thus, we examined the deferred interrupt processing mechanisms in the Linux kernel - tasklet and workqueue, which are a special form of multitasking. You can read about interrupts, tasklets, and workqueues in the book " Linux Device Drivers " by Jonathan Corbet, Greg Kroah-Hartman, Alessandro Rubini, although the information there is sometimes outdated.
In a comment by Zyomato the article about tasklets, the Linux kernel is also advised. Description of the development process ”R. Lava.
To be continued
In the next part, I will talk about protothread and cooperative multitasking, try to compare all considered at first glance, different entities and extract some useful ideas.
