Operating System Design, 2nd Edition

Chapter Contents

• 4.1 Introduction
• 4.2 A Unified Structure for Linked Lists of Processes
• 4.3 A Compact List Data Structure
• 4.4 Implementation of the Queue Data Structure
• 4.5 Inline Queue Manipulation Functions
• 4.6 Basic Functions To Extract A Process From A List
• 4.7 FIFO Queue Manipulation
• 4.8 Manipulation of Priority Queues
• 4.9 List Initialization
• 4.10 Perspective
• 4.11 Summary

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, managing lists ...