Operating System Design

4

List and Queue

Manipulation

As some day it may happen that a victim must be

found, I’ve got a little list ....

— W. S. Gilbert

4.1 Introduction

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-

tant.

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.

49

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

the chapter.

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-

ties:

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

HEAD TAIL

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.