Geek Answers Handbook

Queues in the Linux kernel

I was looking for information for the general implementation of kernel queues, i.e. data structures with first input. I thought there could be one, since this is probably something common to use, and there is a standard for linked lists (in the form of a list_head structure). Is there some kind of standard queue implementation that I cannot find, or perhaps it is common practice to just use linked lists as queues and hope for the best?

+3
source share
3 answers

You are right, the Linux kernel usually uses linked lists to implement queues. This makes sense because linked lists offer the required behavior. See this example from kernel / workqueue.c:

  INIT_LIST_HEAD(&wq->list);
  // ...
   case CPU_UP_CANCELED:
            list_for_each_entry(wq, &workqueues, list) {
                    if (!per_cpu_ptr(wq->cpu_wq, hotcpu)->thread)
+5
source

Are you looking for include / linux / kfifo.h? From the title:

Simple implementation of the FIFO kernel.

This is fairly new, so it's easy to find direct use of linked lists. In addition, they have a completely different implementation (FIFOs are implemented as circular buffers), so they have different applications.

Please note that they are also designed with multi-threaded use (think in the lineup of producers / consumers), but you can use them without blocking with __kfifo_put / __ kfifo_get.

Btw: , lwn.net - : lwn.net/Kernel/Index kfifo: -).

, Blaisorblade

+7

It seems you are confusing the abstraction (fifo queue) with the implementation (linked list). They are not mutually exclusive - in fact, queues are most often implemented as linked lists - there is no "hope for the best."

+3
source

More articles:


All Articles