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