Menu
The Linux kernel stores the lists of processes in a circular doubly linked lists, called the task list. What is the reason behind it? Why was circular doubly linked lists used? What is the advantage of using this data structure? What were the creators trying to achieve by using this data structure?
917
Whenever someone needs a list in the Linux kernel they rely on this implementation to strung up any data structure they have. With very little modifications (removing hardware prefetching of list items) we can also use this list in our applications.
Circular linked lists (singly or doubly) are useful for applications that need to visit each node equally and the lists could grow. If the size of the list if fixed, it is much more efficient (speed and memory) to use circular queue.
Advantages of Circular Doubly Linked List: List can be traversed from both directions i.e. from head to tail or from tail to head. Ease of data manipulation. Jumping from head to tail or vice versa takes O(1) time.
The most common reason to use a doubly linked list is because it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug.
The reason to have a list of objects (such as processes) some form is that sometimes the kernel needs to enumerate all these objects, i.e. to go through each of them in turn. This means there must be a way to find all the objects of this type. If objects can be created and removed one at a time then a linked list is the simplest solution.
The list needs to be doubly linked in order to support removing an object. When removing an object, the code needs to update all the pointers that point to this object. Therefore the object needs to contain a pointer to all the other objects that point to it (or at least there needs to be a chain of pointers starting at the object itself). With a singly-linked list, to remove B from A→B→C, there's no way to discover the A whose pointer needs to be updated, short of going through all objects until the right one is found. With a doubly-linked list, to remove B from A↔B↔C, you follow the pointer from B to A and change A's pointer to B to point to C instead, and likewise with C.
84
Flexibility, so if you know for example what you're searching for is probably behind you you can use the list_for_each_entry_reverse macro instead of the usual forward one.
"you use linked lists when iterating over the whole list is important and the dynamic addition and removal of elements is required ... Using this type of linked list provides the greatest flexibility"
and no duplication of code
"In the old days, there were multiple implementations of linked lists in the kernel. A single, powerful linked list implementation was needed to remove duplicate code. During the 2.1 kernel development series, the official kernel linked-list implementation was introduced."
Source: Robert Love. "Linux Kernel Development" (3rd Edition). p.87-94
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
