Operating System Design: The Xinu Approach, Linksys Version

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)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 MechanismRemote File AccessRemote File SemanticsRemote File Design And MessagesRemote File Server CommunicationSending A Basic MessageNetwork Byte OrderA Remote File System Using A Device ParadigmOpening A Remote FileChecking The File ModeClosing A Remote FileReading From A Remote FileWriting To A Remote FileSeek On A Remote FileCharacter I/O On A Remote FileRemote File System Control FunctionsInitializing The Remote File Data StructureA Syntactic NamespaceTransparency And A Namespace AbstractionMyriad Naming SchemesNaming System Design AlternativesA Syntactic NamespacePatterns And ReplacementsPrefix PatternsImplementation Of A NamespaceNamespace Data Structures And ConstantsAdding Mappings To The Namespace Prefix TableMapping Names With The Prefix TableOpening A Named FileNamespace InitializationOrdering Entries In The Prefix TableChoosing A Logical NamespaceA Default Hierarchy And The Null PrefixAdditional Object Manipulation FunctionsAdvantages And Limits Of The Namespace ApproachGeneralized PatternsSystem InitializationBootstrap: Starting From ScratchOperating System InitializationBooting An Alternative Image.

On.

Front Cover -- Dedication -- Contents -- Preface -- About The Author -- Chapter 1: Introduction and Overview -- Chapter 2: Concurrent Execution and Operating System Services -- Chapter 3: An Overview of The Hardware and Run-Time Environment -- Chapter 4: List and Queue Manipulation -- Chapter 5: Scheduling and Context Switching -- Chapter 6: More Process Management -- Chapter 7: Coordination of Concurrent Processes -- Chapter 8: Message Passing -- Chapter 9: Basic Memory Management -- Chapter 10: High-Level Memory Management and Virtual Memory -- Chapter 11: High-Level Message Passing -- Chapter 12: Interrupt Processing -- Chapter 13: Real-Time Clock Management -- Chapter 14: Device-Independent Input and Output -- Chapter 15: An Example Device Driver -- Chapter 16: DMA Devices and Drivers (Ethernet) -- Chapter 17: A Minimal Internet Protocol Stack -- Chapter 18: A Remote Disk Driver -- Chapter 19: File Systems -- Chapter 20: A Remote File Mechanism -- Chapter 21: A Syntactic Namespace -- Chapter 22: System Initialization -- Chapter 23: Exception Handling -- Chapter 24: System Configuration -- Chapter 25: An Example User Interface: The Xinu Shell -- Appendix 1: Porting an Operating…