Task Queues

   

  
Figure: A Task Queue

Task queues are the kernel's way of deferring work until later. Linux has a generic mechanism for queue work on queues and for processing them later.

Task queues are often used in conjunction with bottom half handlers; the timer task queue is processed when the timer queue bottom half handler runs. A task queue is a simple data structure, see figure  which consists of a singly linked list of tq_struct  data structures each of which contains the address of a routine and a pointer to some data.   The routine will be called when the element on the task queue is processed and it will be passed a pointer to the data.

Anything in the kernel, for example a device driver, can create and use task queues but there are three task queues created and managed by the kernel:

timer

This queue is used to queue work that will be done as soon after the next system clock tick as is possible. Each clock tick this queue is checked to see if it contains any entries and, if it does, the timer queue bottom half handler is made active. The timer queue bottom half handler is processed, along with all the other bottom half handlers, when the scheduler next runs. This queue should not be confused with system timers which are a much more sophisticate mechanism.

immediate

This queue is also processed when the scheduler processes the active bottom half handlers. The immediate bottom half handler is not as high in priority as the timer queue bottom half handler and so these tasks will be run later.

scheduler

This task queue is processed directly by the scheduler. It is used to support other task queues in the system and, in this case, the task to be run will be a routine which processes a task queue, say for a device driver.

When task queues are processed, the pointer to the first element in the queue is removed from the queue and replaced with a null pointer. In fact, this removal is an atomic operation, one that cannot be interrupted. Then each element in the queue has its handling routine called in turn. The elements in the queue are often statically allocated data, however there is no inherent mechanism for discarding allocated memory. The task queue processing routine simply moves onto the next element in the list. It is the job of the task itself to ensure that it properly cleans up any allocated kernel memory.