List and Queue
As some day it may happen that a victim must be
found, I’ve got a little list ....
— W. S. Gilbert
Linked list processing is fundamental in operating systems, and pervades each
component. Linked structures enable a system to manage sets of objects efficiently
without searching or copying. As we will see, process management is especially impor-
This chapter introduces a set of functions that form the backbone of a linked list
manipulation system. The functions represent a unified approach — a single data struc-
ture and a single set of nodes used by all levels of the operating system to maintain lists
of processes. We will see that the data structure includes functions to create a new list,
insert an item at the tail of a list, insert an item in an ordered list, remove the item at
the head of a list, or remove an item from the middle of a list.†
The linked list functions are easy to understand because they assume that only one
process executes a list function at a given time. Thus, a reader can think of the code as
being part of a sequential program — there is no need to worry about interference from
other processes executing concurrently. In addition, the example code introduces
several programming conventions used throughout the text.
†Although linked list manipulation is usually covered in texts on data structures, the topic is included
here because the data structure is unusual and because it forms a key part of the system.
50 List and Queue Manipulation Chap. 4
4.2 A Unified Structure For Linked Lists Of Processes
A process manager handles objects called processes. Although at any time a pro-
cess appears on only one list, a process manager moves a process from one list to
another frequently. In fact, a process manager does not store all details about a process
on a list. Instead, the process manager merely stores a process ID, a small, nonnegative
integer used to reference the process. Because it is convenient to think of placing a pro-
cess on a list, we will use the terms process and process ID interchangeably throughout
An early version of Xinu had many lists of processes, each with its own data struc-
ture. Some consisted of first-in-first-out (FIFO) queues, and others were ordered by a
key. Some lists were singly linked; others needed to be doubly linked to permit items
to be inserted and deleted at arbitrary positions efficiently. After the requirements had
been formulated, it became clear that centralizing the linked-list processing into a single
data structure would reduce code size and eliminate many special cases. That is, in-
stead of six separate sets of linked list manipulation functions, a single set of functions
was created to handle all situations.
To accommodate all cases, a representation was selected with the following proper-
All lists are doubly linked, which means a node points to its prede-
cessor and successor.
Each node stores a key as well as a process ID, even though a key
is not used in a FIFO list.
Each list has head and tail nodes; the head and tail nodes have the
same memory layout as other nodes.
Non-FIFO lists are ordered in descending order; the key in a head
node is greater than the maximum valid key value, and the key
value in the tail node is less than the minimum valid key.
Figure 4.1 illustrates the conceptual organization of a linked list data structure by
showing an example list with two items.
– –425 214
previous process key next
greater than maximum key less than minimum key
Figure 4.1 The conceptual organization of a doubly-linked list containing
processes 4 and 2 with keys 25 and 14, respectively.