Search code examples
linux-kernelprocess-management

Why does the Linux kernel use circular doubly linked lists to store the lists of processes?


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?


Solution

  • 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