Operating System Design : The Xinu Approach, Second Edition book cover
2nd Edition

Operating System Design
The Xinu Approach, Second Edition

ISBN 9781498712439
Published February 18, 2015 by Chapman and Hall/CRC
701 Pages - 65 Color Illustrations

SAVE ~ $23.00
was $115.00
USD $92.00

Prices & shipping based on shipping country

Book Description

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.

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


View More


"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

Support Material


  • Instructor Resources

    To gain access to the instructor resources for this title, please visit the Instructor Resources Download Hub.

    You will be prompted to fill out a regist