Operating System Design: The Xinu Approach, Second Edition, 2nd Edition (e-Book) book cover

Operating System Design

The Xinu Approach, Second Edition, 2nd Edition

By Douglas Comer, Douglas Comer

Chapman and Hall/CRC

701 pages | 65 Color Illus.

Purchasing Options:$ = USD
Pack - Book and Ebook: 9781498712439
pub: 2015-02-18
eBook (VitalSource) : 9781498712460
pub: 2015-01-13
from $49.98

FREE Standard Shipping!


An Update of the Most Practical A-to-Z Operating System Book

Widely lauded for avoiding the typical black box approach found in other operating system textbooks, the first edition of this bestselling book taught readers how an operating system works and explained how to build it from the ground up.

Continuing to follow a logical pattern for system design, Operating System Design: The Xinu Approach, Second Edition removes the mystery from operating system design and consolidates the body of material into a systematic discipline. It presents a hierarchical design paradigm that organizes major operating system components in an orderly, understandable manner.

The book guides readers through the construction of a conventional process-based operating system using practical, straightforward primitives. It gives the implementation details of one set of primitives, usually the most popular set. Once readers understand how primitives can be implemented on conventional hardware, they can then easily implement alternative versions.

The text begins with a bare machine and proceeds step-by-step through the design and implementation of Xinu, which is a small, elegant operating system that supports dynamic process creation, dynamic memory allocation, network communication, local and remote file systems, a shell, and device-independent I/O functions. The Xinu code runs on many hardware platforms. This second edition has been completely rewritten to contrast operating systems for RISC and CISC processors. Encouraging hands-on experimentation, the book provides updated code throughout and examples for two low-cost experimenter boards: BeagleBone Black from ARM and Galileo from Intel.


"What sets this book aside from the mass of books on operating systems is its focus on a single real-world operating systems, namely Xinu, which is a commercially used, yet lean, clearly designed, modular operating system for embedded, single-core systems. … The book is surprisingly easy to read; essential data structures and algorithms are presented in source code and discussed adequately, allowing for a very good understanding of the entire operating system. … an ideal book for anyone who aims to understand one operating system in detail, in particular for those working with embedded systems."

Zentralblatt MATH 1314

Praise for the First Edition:

"Operating System Design: The Xinu Approach is the best book for students and professionals to learn how a computer operating system works. The computer code, along with clear, concise explanations, is simply the best way to learn OS. Readers who study this book carefully will benefit greatly and find it time well spent."

—John C. Lin, Bell Labs

"… [the author’s] focused, clear, and thorough writing have given ‘systematic’ a new meaning (or perhaps restored its original one). … non-OS specialists also stand to learn much of what they generally need to know from this excellent book. Furthermore, it is no faint praise for me to say that the book’s seamless integration of source code listings into the text … is the best I’ve encountered and works very well indeed. Superior and consistently followed C-language coding conventions give further evidence of the meticulousness with which this book was written. … a most outstanding and practical A-to-Z OS book. It has my highest recommendation."

—George Hacken, Computing Reviews, April 2012

"This Xinu book is the best operating systems book on the market because it removes the black magic and explains how to build an OS from the ground up. It’s not like other books I tried to read — they gave me a headache. I have already started telling friends how great it is."

—David Bafumba-Lokilo, École Polytechnique de Montréal

"Understanding an operating system is a very difficult and time-consuming task because it is one of the most complex software systems ever built. Its architecture has multiple layers of software components to manage the underline hardware and provide the system call services to the applications at the top. Knowing the host processor hardware features, the machine languages, compilers, the tool chain, and the procedure calling standard are part of the prerequisites. As a consequence, operating system books can take a black box approach to cover the interface of the system call services and the operating system algorithms in a short time. However students wishing to program an embedded system must learn the details of the implementation. This Xinu book removes the black magic and explains how to build an OS from the ground up. It explains the underlying design policies behind each of the primary components of an operating system kernel and provides the concrete implementation of source code. The Xinu design principles can be found on other commercially available platforms. A device driver on Linux platform is one example. Students majoring in embedded systems are highly recommended to read this book."

—Donald D Kim, Information and Communication Engineering Department, Dongguk University, South Korea

Table of Contents

Introduction and Overview

Operating Systems

Approach Used In The Text

A Hierarchical Design

The Xinu Operating System

What An Operating System Is Not

An Operating System Viewed From The Outside

Remainder Of The Text

Concurrent Execution and Operating System Services

Programming Models For Multiple Activities

Operating System Services

Concurrent Processing Concepts And Terminology

Distinction Between Sequential And Concurrent Programs

Multiple Processes Sharing A Single Piece Of Code

Process Exit And Process Termination

Shared Memory, Race Conditions, And Synchronization

Semaphores And Mutual Exclusion

Type Names Used In Xinu

Operating System Debugging With Kputc And Kprintf

An Overview of the Hardware and Run-Time Environment

Physical And Logical Organizations Of The E2100L

Processor Organization And Registers

Bus Operation: The Fetch-Store Paradigm

Direct Memory Access

The Bus Address Space

Contents Of Kernel Segments KSEG0 and KSEG1

Bus Startup Static Configuration

Calling Conventions And The Run-Time Stack

Interrupts And Interrupt Processing

Exception Processing

Timer Hardware

Serial Communication

Polled vs. Interrupt-Driven I/O

Memory Cache And KSEG1

Storage Layout

Memory Protection

List and Queue Manipulation

A Unified Structure For Linked Lists Of Processes

A Compact List Data Structure

Implementation Of The Queue Data Structure

Inline Queue Manipulation Functions

Basic Functions To Extract A Process From A List

FIFO Queue Manipulation

Manipulation Of Priority Queues

List Initialization

Scheduling and Context Switching

The Process Table

Process States

Ready And Current States

A Scheduling Policy

Implementation Of Scheduling

Implementation Of Context Switching

State Saved In Memory

Context Switch On A MIPS Processor

An Address At Which To Restart A Process

Concurrent Execution And A Null Process

Making A Process Ready And The Scheduling Invariant

Deferred Rescheduling

Other Process Scheduling Algorithms

More Process Management

Process Suspension And Resumption

Self-Suspension And Information Hiding

The Concept Of A System Call

Interrupt Control With Disable And Restore

A System Call Template

System Call Return Values SYSERR And OK

Implementation Of Suspend

Suspending The Current Process

Suspend Return Value

Process Termination And Process Exit

Process Creation

Other Process Manager Functions

Coordination of Concurrent Processes

The Need For Synchronization

A Conceptual View Of Counting Semaphores

Avoidance Of Busy Waiting

Semaphore Policy And Process Selection

The Waiting State

Semaphore Data Structures

The Wait System Call

The Signal System Call

Static And Dynamic Semaphore Allocation

Example Implementation Of Dynamic Semaphores

Semaphore Deletion

Semaphore Reset

Coordination Across Parallel Processors (Multicore)

Message Passing

Two Types Of Message Passing Services

Limits On Resources Used By Messages

Message Passing Functions And State Transitions

Implementation Of Send

Implementation Of Receive

Implementation Of Non-Blocking Message Reception

Basic Memory Management

Types Of Memory

Definition Of A Heavyweight Process

Memory Management In A Small Embedded System

Program Segments And Regions Of Memory

Dynamic Memory Allocation In An Embedded System

Design Of The Low-Level Memory Manager

Allocation Strategy And Memory Persistence

Keeping Track Of Free Memory

Implementation Of Low-Level Memory Management

Allocating Heap Storage

Allocating Stack Storage

Releasing Heap And Stack Storage

High-Level Memory Management and Virtual Memory

Partitioned Space Allocation

Buffer Pools

Allocating A Buffer

Returning Buffers To The Buffer Pool

Creating A Buffer Pool

Initializing The Buffer Pool Table

Virtual Memory And Memory Multiplexing

Real And Virtual Address Spaces

Hardware For Demand Paging

Address Translation With A Page Table

Metadata In A Page Table Entry

Demand Paging And Design Questions

Page Replacement And Global Clock

High-Level Message Passing

Inter-Process Communication Ports

The Implementation Of Ports

Port Table Initialization

Port Creation

Sending A Message To A Port

Receiving A Message From A Port

Port Deletion And Reset

Interrupt Processing

The Advantage Of Interrupts

Interrupt Dispatching

Vectored Interrupts

Assignment Of Interrupt Vector Numbers

Interrupt Hardware

IRQ Limits And Interrupt Multiplexing

Interrupt Software And Dispatching

The Lowest Level Of The Interrupt Dispatcher

The High-Level Interrupt Dispatcher

Disabling Interrupts

Constraints On Functions That Interrupt Code Invokes

The Need To Reschedule During An Interrupt

Rescheduling During An Interrupt

Real-Time Clock Management

Timed Events

Real-Time Clocks And Timer Hardware

Handling Real-Time Clock Interrupts

Delay And Preemption

Emulating A Real-Time Clock With A Timer

Implementation Of Preemption

Efficient Management Of Delay With A Delta List

Delta List Implementation

Putting A Process To Sleep

Timed Message Reception

Awakening Sleeping Processes

Clock Interrupt Processing

Clock Initialization

Interval Timer Management

Device-Independent Input and Output

Conceptual Organization Of I/O And Device Drivers

Interface And Driver Abstractions

An Example I/O Interface

The Open-Read-Write-Close Paradigm

Bindings For I/O Operations And Device Names

Device Names In Xinu

The Concept Of A Device Switch Table

Multiple Copies Of A Device And Shared Drivers

The Implementation Of High-Level I/O Operations

Other High-Level I/O Functions

Open, Close, And Reference Counting

Null And Error Entries In Devtab

Initialization Of The I/O System

An Example Device Driver

The Tty Abstraction

Organization Of A Tty Device Driver

Request Queues And Buffers

Synchronization Of Upper Half And Lower Half

Hardware Buffers And Driver Design

Tty Control Block And Data Declarations

Minor Device Numbers

Upper–Half Tty Character Input (ttyGetc)

Generalized Upper–Half Tty Input (ttyRead)

Upper–Half Tty Character Output (ttyPutc)

Starting Output (ttyKickOut)

Upper–Half Tty Multiple Character Output (ttyWrite)

Lower–Half Tty Driver Function (ttyInterrupt)

Output Interrupt Processing (ttyInter_out)

Tty Input Processing (ttyInter_in)

Tty Control Block Initialization (ttyInit)

Device Driver Control

DMA Devices and Drivers (Ethernet)

Direct Memory Access And Buffers

Multiple Buffers And Rings

An Example Ethernet Driver Using DMA

Device Hardware Definitions And Constants

Rings And Buffers In Memory

Definitions Of An Ethernet Control Block

Device And Driver Initialization

Allocating An Input Buffer

Reading From An Ethernet Device

Writing To An Ethernet Device

Handling Interrupts From An Ethernet Device

Ethernet Control Functions

A Minimal Internet Protocol Stack

Required Functionality

Simultaneous Conversations, Timeouts, And Processes

ARP Functions

Definition Of A Network Packet

The Network Input Process

Definition Of The UDP Table

UDP Functions

Internet Control Message Protocol

Dynamic Host Configuration Protocol

A Remote Disk Driver

The Disk Abstraction

Operations A Disk Driver Supports

Block Transfer And High-Level I/O Functions

A Remote Disk Paradigm

Semantics Of Disk Operations

Definition Of Driver Data Structures

Driver Initialization (rdsInit)

The Upper–Half Open Function (rdsOpen)

The Remote Communication Function (rdscomm)

The Upper–Half Write Function (rdsWrite)

The Upper–Half Read Function (rdsRead)

Flushing Pending Requests

The Upper–Half Control Function (rdsControl)

Allocating A Disk Buffer (rdsbufalloc)

The Upper–Half Close Function (rdsClose)

The Lower–Half Communication Process (rdsprocess)

File Systems

What Is A File System?

An Example Set Of File Operations

Design Of A Local File System

Data Structures For The Xinu File System

Implementation Of The Index Manager

Clearing An Index Block (lfibclear)

Retrieving An Index Block (lfibget)

Storing An Index Block (lfibput)

Allocating An Index Block From The Free List (lfiballoc)

Allocating A Data Block From The Free List (lfdballoc)

Using The Device-Independent I/O Functions For Files

File System Device Configuration And Function Names

The Local File System Open Function (lfsOpen)

Closing A File Pseudo-Device (lflClose)

Flushing Data To Disk (lfflush)

Bulk Transfer Functions For A File (lflWrite, lflRead)

Seeking To A New Position In the File (lflSeek)

Extracting One Byte From A File (lflGetc)

Changing One Byte In A File (lflPutc)

Loading An Index Block And A Data Block (lfsetup)

Master File System Device Initialization (lfsInit)

Pseudo-Device Initialization (lflInit)

File Truncation (lftruncate)

Initial File System Creation (lfscreate)

A Remote File Mechanism

Remote File Access

Remote File Semantics

Remote File Design And Messages

Remote File Server Communication

Sending A Basic Message

Network Byte Order

A Remote File System Using A Device Paradigm

Opening A Remote File

Checking The File Mode

Closing A Remote File

Reading From A Remote File

Writing To A Remote File

Seek On A Remote File

Character I/O On A Remote File

Remote File System Control Functions

Initializing The Remote File Data Structure

A Syntactic Namespace

Transparency And A Namespace Abstraction

Myriad Naming Schemes

Naming System Design Alternatives

A Syntactic Namespace

Patterns And Replacements

Prefix Patterns

Implementation Of A Namespace

Namespace Data Structures And Constants

Adding Mappings To The Namespace Prefix Table

Mapping Names With The Prefix Table

Opening A Named File

Namespace Initialization

Ordering Entries In The Prefix Table

Choosing A Logical Namespace

A Default Hierarchy And The Null Prefix

Additional Object Manipulation Functions

Advantages And Limits Of The Namespace Approach

Generalized Patterns

System Initialization

Bootstrap: Starting From Scratch

Operating System Initialization

Booting An Alternative Image On The E2100L

Xinu Initialization

System Startup

Transforming A Program Into A Process

Subsystem Initialization and Memory Marking

Self-initializing Modules

Self-initializing Modules in a Concurrent System

Self-initialization in the Presence Of Reboot

Initialization Using Accession Numbers

A Generalized Memory Marking Scheme

Data Declarations for the Memory Marking System

Implementation of Marking

Exception Handling

Terminology: Faults, Checks, Traps, and Exceptions

Vectored Exceptions and Maskable Interrupts

Types of Exceptions

Handling Exceptions

Exception Vector Initialization

Panic in the Face of Catastrophic Problems

Implementation of Panic

System Configuration

The Need For Multiple Configurations

Configuration In Xinu

Contents Of The Xinu Configuration File

Computation Of Minor Device Numbers

Steps In Configuring A Xinu System

An Example User Interface: The Xinu Shell

What Is A User Interface?

Commands And Design Principles

Design Decisions For A Simplified Shell

Shell Organization And Operation

The Definition Of Lexical Tokens

The Definition Of Command-Line Syntax

Implementation Of The Xinu Shell

Storage Of Tokens

Code For The Lexical Analyzer

The Heart Of The Command Interpreter

Command Name Lookup And Builtin Processing

Arguments Passed To Commands

Passing Arguments To A Non-Builtin Command

I/O Redirection

An Example Command Function (sleep)

Appendix 1: Porting an Operating System

Motivation: Evolving Hardware

Steps Taken When Porting An Operating System

Programming To Accommodate Change

Appendix 2: Xinu Design Notes


Xinu Design Notes

Xinu Implementation

Major Concepts And Implementation


Subject Categories

BISAC Subject Codes/Headings:
COMPUTERS / Operating Systems / General