Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Queues in the Linux Kernel

I've been searching for information for a common kernel implementation of queues, that is, first-in-first-out data structures. I thought there may be one since it's likely something that's common to use, and there's a standard for linked lists (in the form of the list_head structure). Is there some standard queue implementation I can't find, or is it perhaps common practice to just use linked lists as queues and hope for the best?

like image 905
Dan Fego Avatar asked Dec 23 '08 17:12

Dan Fego


People also ask

What is queuing in Linux?

Message queues allow one or more processes to write messages which will be read by one or more reading processes. Linux maintains a list of message queues, the msgque vector; each element of which points to a msqid_ds data structure which fully describes the message queue.

What is wait queue in Linux kernel?

Wait queue is a mechanism provided in the kernel to implement the wait. As the name itself suggests, waitqueue is the list of processes waiting for an event. In other words, A wait queue is used to wait for someone to wake you up when a certain condition is true.

What is a kernel message queue?

A message queue is a kernel object that implements a simple message queue, allowing threads and ISRs to asynchronously send and receive fixed-size data items.

How do I create a kernel queue?

In the init function we need to first create the proc entry and then intialize the linked list that we will be using for the queue. create_new_proc_entry: Function for creation of the proc entry. Next we need to define the file operations for the proc entry. To manipulate the queue we need two operations push and pop.


1 Answers

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

A simple kernel FIFO implementation.

It's rather new anyway, so it's not hard to find direct usages of linked lists. Also, they have a quite different implementation (FIFOs are implemented as circular buffers), so they have different applications.

Note also they are designed with multithreaded usage in mind (think to producer/consumer queues), but you can use them without locking with __kfifo_put/__kfifo_get.

Btw: I remember I learned about them on lwn.net - bookmark this: lwn.net/Kernel/Index, and read the entry about kfifo :-).

From your ex-kernel developer, Blaisorblade

like image 156
Blaisorblade Avatar answered Sep 30 '22 23:09

Blaisorblade