Operating System Design: The Xinu Approach, Linksys Version

About the Book

Operating System Design: The Xinu Approach, Linksys Version provides a comprehensive introduction to Operating System Design, using Xinu, a small, elegant operating system that serves as an example and a pattern for system design. The book focuses the discussion of operating systems on the microkernel operating system facilities used in embedded systems. Rather than introduce a new course to teach the important topics of embedded systems programming, this textbook takes the approach of integrating more embedded processing into existing operating systems courses. Designed for advanced undergraduate or graduate courses, the book prepares students for the increased demand for operating system expertise in industry. Highlights Explains how each operating system abstraction can be built and shows how the abstractions can be organized into an elegant, efficient design Considers each level of the system individually, beginning with the raw hardware and ending with a working operating system Covers every part of the system, so a reader will see how an entire system fits together, not merely how one or two parts interact Provides source code for all pieces described in the text, leaving no mystery about any part of the implementation -- a reader can obtain a copy of the system to examine, modify, instrument, measure, extend, or transport to another architecture Demonstrates how each piece of an operating system fits into the design, in order to prepare the reader to understand alternative design choices Beginning with the underlying machine and proceeding step by step through the design and implementation of an actual system, Operating System Design: The Xinu Approach, Linksys Version guides readers through the construction of a traditional process-based operating system using practical, straightforward primitives. It reviews the major system components and imposes a hierarchical design paradigm that organizes the components in an orderly and understandable manner. All of the code in the book is designed to run on the Linksys router, because it is small, inexpensive, and easily accessible to students. Software and instructions for building a lab that allows students to experiment are available on the author's website: www.xinu.cs.purdue.edu

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

Exception Handling
Exceptions, Traps, And Illegal Interrupts
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: Porting An Operating System
Motivation: Evolving Hardware
Steps Taken When Porting An Operating System
Programming To Accommodate Change

Appendix: Xinu Design Notes
Overview
Xinu Design Notes
Xinu Implementation
Major Concepts And Implementation

Index

About the Author :
Professor Comer is an internationally recognized expert on computer networking and the TCP/IP protocols. He has been working with TCP/IP and the Internet since the late 1970s. Dr. Comer established his reputation as a principal investigator on several early Internet research projects. He served as chairman of the CSNET technical committee, chairman of the DARPA Distributed Systems Architecture Board, and was a member of the Internet Activities Board (the group of researchers who built the Internet.). Dr. Comer has created courses on operating systems, computer networks, the Internet, and TCP/IP protocols for a variety of audiences, including in-depth courses for engineers and less technical courses for others; he continues to teach at various industries and networking conferences around the world. In addition, Dr. Comer consults for private industry on the design of systems, networks, and networking equipment. Professor Comer is well-known for his series of ground breaking textbooks on operating systems, computer networks, and the Internet. His books have been translated into sixteen languages, and are widely used in both industry and academia. Dr. Comer's three-volume series Internetworking With TCP/IP is often cited as an authoritative reference for the Internet protocols. More significantly, his texts have been used by fifteen of the top sixteen Computer Science Departments listed in the U.S. News and World Report ranking. Dr. Comer's research is experimental. He and his students design and implement working prototypes of large, complex systems. They measure the performance of the resulting prototypes and assess tradeoffs. The operating system and protocol software that have resulted from his research have been used by industry in a variety of products. For twenty years, Professor Comer served as editor-in-chief of the research journal Software--Practice and Experience, published by John Wiley & Sons. He is a Fellow of the ACM and the recipient of numerous teaching awards.

Review :
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, Ecole Polytechnique de Montreal