Operating System Design The Xinu Approach, Second Edition

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.

Introduction and OverviewOperating SystemsApproach Used In The TextA Hierarchical DesignThe Xinu Operating SystemWhat An Operating System Is NotAn Operating System Viewed From The OutsideRemainder Of The TextConcurrent Execution and Operating System ServicesProgramming Models For Multiple ActivitiesOperating System ServicesConcurrent Processing Concepts And TerminologyDistinction Between Sequential And Concurrent ProgramsMultiple Processes Sharing A Single Piece Of CodeProcess Exit And Process TerminationShared Memory, Race Conditions, And SynchronizationSemaphores And Mutual ExclusionType Names Used In XinuOperating System Debugging With Kputc And KprintfAn Overview of the Hardware and Run-Time EnvironmentPhysical And Logical Organizations Of The E2100LProcessor Organization And RegistersBus Operation: The Fetch-Store ParadigmDirect Memory AccessThe Bus Address SpaceContents Of Kernel Segments KSEG0 and KSEG1Bus Startup Static ConfigurationCalling Conventions And The Run-Time StackInterrupts And Interrupt ProcessingException ProcessingTimer HardwareSerial CommunicationPolled vs. Interrupt-Driven I/OMemory Cache And KSEG1Storage LayoutMemory ProtectionList and Queue ManipulationA Unified Structure For Linked Lists Of ProcessesA Compact List Data StructureImplementation Of The Queue Data StructureInline Queue Manipulation FunctionsBasic Functions To Extract A Process From A ListFIFO Queue ManipulationManipulation Of Priority QueuesList InitializationScheduling and Context SwitchingThe Process TableProcess StatesReady And Current StatesA Scheduling PolicyImplementation Of SchedulingImplementation Of Context SwitchingState Saved In MemoryContext Switch On A MIPS ProcessorAn Address At Which To Restart A ProcessConcurrent Execution And A Null ProcessMaking A Process Ready And The Scheduling InvariantDeferred ReschedulingOther Process Scheduling AlgorithmsMore Process ManagementProcess Suspension And ResumptionSelf-Suspension And Information HidingThe Concept Of A System CallInterrupt Control With Disable And RestoreA System Call TemplateSystem Call Return Values SYSERR And OKImplementation Of SuspendSuspending The Current ProcessSuspend Return ValueProcess Termination And Process ExitProcess CreationOther Process Manager FunctionsCoordination of Concurrent ProcessesThe Need For SynchronizationA Conceptual View Of Counting Semaphores Avoidance Of Busy Waiting Semaphore Policy And Process Selection The Waiting StateSemaphore Data StructuresThe Wait System CallThe Signal System CallStatic And Dynamic Semaphore AllocationExample Implementation Of Dynamic SemaphoresSemaphore DeletionSemaphore ResetCoordination Across Parallel Processors (Multicore)Message PassingTwo Types Of Message Passing ServicesLimits On Resources Used By MessagesMessage Passing Functions And State TransitionsImplementation Of SendImplementation Of ReceiveImplementation Of Non-Blocking Message ReceptionBasic Memory ManagementTypes Of MemoryDefinition Of A Heavyweight ProcessMemory Management In A Small Embedded SystemProgram Segments And Regions Of MemoryDynamic Memory Allocation In An Embedded SystemDesign Of The Low-Level Memory ManagerAllocation Strategy And Memory PersistenceKeeping Track Of Free MemoryImplementation Of Low-Level Memory ManagementAllocating Heap StorageAllocating Stack StorageReleasing Heap And Stack StorageHigh-Level Memory Management and Virtual MemoryPartitioned Space AllocationBuffer PoolsAllocating A BufferReturning Buffers To The Buffer PoolCreating A Buffer PoolInitializing The Buffer Pool TableVirtual Memory And Memory MultiplexingReal And Virtual Address SpacesHardware For Demand PagingAddress Translation With A Page TableMetadata In A Page Table EntryDemand Paging And Design QuestionsPage Replacement And Global ClockHigh-Level Message PassingInter-Process Communication PortsThe Implementation Of PortsPort Table InitializationPort CreationSending A Message To A PortReceiving A Message From A PortPort Deletion And ResetInterrupt ProcessingThe Advantage Of InterruptsInterrupt DispatchingVectored InterruptsAssignment Of Interrupt Vector NumbersInterrupt HardwareIRQ Limits And Interrupt MultiplexingInterrupt Software And DispatchingThe Lowest Level Of The Interrupt DispatcherThe High-Level Interrupt DispatcherDisabling InterruptsConstraints On Functions That Interrupt Code InvokesThe Need To Reschedule During An InterruptRescheduling During An InterruptReal-Time Clock ManagementTimed EventsReal-Time Clocks And Timer HardwareHandling Real-Time Clock InterruptsDelay And PreemptionEmulating A Real-Time Clock With A TimerImplementation Of PreemptionEfficient Management Of Delay With A Delta ListDelta List ImplementationPutting A Process To SleepTimed Message ReceptionAwakening Sleeping ProcessesClock Interrupt ProcessingClock InitializationInterval Timer ManagementDevice-Independent Input and OutputConceptual Organization Of I/O And Device DriversInterface And Driver AbstractionsAn Example I/O InterfaceThe Open-Read-Write-Close ParadigmBindings For I/O Operations And Device NamesDevice Names In XinuThe Concept Of A Device Switch TableMultiple Copies Of A Device And Shared DriversThe Implementation Of High-Level I/O OperationsOther High-Level I/O FunctionsOpen, Close, And Reference CountingNull And Error Entries In DevtabInitialization Of The I/O SystemAn Example Device DriverThe Tty AbstractionOrganization Of A Tty Device DriverRequest Queues And BuffersSynchronization Of Upper Half And Lower HalfHardware Buffers And Driver DesignTty Control Block And Data DeclarationsMinor Device NumbersUpper–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 ControlDMA Devices and Drivers (Ethernet)Direct Memory Access And BuffersMultiple Buffers And RingsAn Example Ethernet Driver Using DMADevice Hardware Definitions And ConstantsRings And Buffers In MemoryDefinitions Of An Ethernet Control BlockDevice And Driver InitializationAllocating An Input BufferReading From An Ethernet DeviceWriting To An Ethernet DeviceHandling Interrupts From An Ethernet DeviceEthernet Control FunctionsA Minimal Internet Protocol StackRequired FunctionalitySimultaneous Conversations, Timeouts, And ProcessesARP FunctionsDefinition Of A Network PacketThe Network Input ProcessDefinition Of The UDP TableUDP FunctionsInternet Control Message ProtocolDynamic Host Configuration ProtocolA Remote Disk DriverThe Disk AbstractionOperations A Disk Driver SupportsBlock Transfer And High-Level I/O FunctionsA Remote Disk ParadigmSemantics Of Disk OperationsDefinition Of Driver Data StructuresDriver 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 RequestsThe Upper–Half Control Function (rdsControl)Allocating A Disk Buffer (rdsbufalloc)The Upper–Half Close Function (rdsClose)The Lower–Half Communication Process (rdsprocess)File SystemsWhat Is A File System?An Example Set Of File OperationsDesign Of A Local File SystemData Structures For The Xinu File SystemImplementation Of The Index ManagerClearing 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 FilesFile System Device Configuration And Function NamesThe 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)Ch

Comer, Douglas; Comer, Douglas