book

Operating System Design, 2nd Edition

Name: Operating System Design, 2nd Edition
Author: Douglas Comer
ISBN: 9781003803768

by Douglas Comer

February 2015

Intermediate to advanced

701 pages

15h 1m

English

Chapman and Hall/CRC

Read now

Unlock full access

Cover Page
Half Title Page
Title Page
Copyright Page
Dedication
Contents
Preface
About the Author
Chapter 1 Introduction And Overview
1.1 Operating Systems1.2 Approach Used In The Text1.3 A Hierarchical Design1.4 The Xinu Operating System1.5 What An Operating System Is Not1.6 An Operating System Viewed From The Outside1.7 Remainder of the Text1.8 Perspective1.9 SummaryExercises
Chapter 2 Concurrent Execution And Operating System Services
2.1 Introduction2.2 Programming Models For Multiple Activities2.3 Operating System Services2.4 Concurrent Processing Concepts And Terminology2.5 Distinction Between Sequential And Concurrent Programs2.6 Multiple Processes Sharing A Single Piece of Code2.7 Process Exit And Process Termination2.8 Shared Memory, Race Conditions, And Synchronization2.9 Semaphores And Mutual Exclusion2.10 Type Names Used In Xinu2.11 Operating System Debugging With Kputc And Kprintf2.12 Perspective2.13 SummaryExercises

Chapter 3 An Overview Of The Hardware And Runtime Environment
3.1 Introduction3.2 Physical And Logical Organizations of A Platform3.3 Instruction Sets3.4 General-purpose Registers3.4 .1Galileo (Intel)3.4 .2BeagleBone Black (ARM)3.5 I/O Buses And The Fetch-Store Paradigm3.6 Direct Memory Access3.7 The Bus Address Space3.8 Bus Startup And Configuration3.9 Calling Conventions And The Runtime Stack3.9.1 Galileo (Intel)3.9.2 BeagleBone Black (ARM)3.10 Interrupts And Interrupt Processing3.11 Vectored Interrupts3.12 Exception Vectors And Exception Processing3.13 Clock Hardware3.14 Serial Communication3.15 Polled vs. Interrupt-driven I/O3.16 Storage Layout3.17 Memory Protection3.18 Hardware Details And A System On Chip Architecture3.19 Perspective3.20 Hardware ReferencesExercises
Chapter 4 List And Queue Manipulation
4.1 Introduction4.2 A Unified Structure for Linked Lists of Processes4.3 A Compact List Data Structure4.4 Implementation of the Queue Data Structure4.5 Inline Queue Manipulation Functions4.6 Basic Functions To Extract A Process From A List4.7 FIFO Queue Manipulation4.8 Manipulation of Priority Queues4.9 List Initialization4.10 Perspective4.11 SummaryExercises
Chapter 5 Scheduling And Context Switching
5.1 Introduction5.2 The Process Table5.3 Process States5.4 Ready And Current States5.5 A Scheduling Policy5.6 Implementation Of Scheduling5.7 Deferred Rescheduling5.8 Implementation Of Context Switching5.9 State Saved In Memory5.10 Context Switch Operation5.10.1 Galileo (Intel)5.10.2 BeagleBone Black (ARM)5.11 An Address At Which To Restart A Process5.12 Concurrent Execution And A Null Process5.13 Making A Process Ready And The Scheduling Invariant5.14 Other Process Scheduling Algorithms5.15 Perspective5.16 SummaryExercises
Chapter 6 More Process Management
6.1 Introduction6.2 Process Suspension And Resumption6.3 Self–suspension And Information Hiding6.4 The Concept Of A System Call6.5 Interrupt Control With Disable And Restore6.6 A System Call Template6.7 System Call Return Values SYSERR And OK6.8 Implementation of Suspend6.9 Suspending The Current Process6.10 The Value Returned By Suspend6.11 Process Termination And Process Exit6.12 Process Creation6.13 Other Process Manager Functions6.14 SummaryExercises
Chapter 7 Coordination Of Concurrent Processes
7.1 Introduction7.2 The Need for Synchronization7.3 A Conceptual View of Counting Semaphores7.4 Avoidance of Busy Waiting7.5 Semaphore Policy And Process Selection7.6 The Waiting State7.7 Semaphore Data Structures7.8 The Wait System Call7.9 The Signal System Call7.10 Static And Dynamic Semaphore Allocation7.11 Example Implementation of Dynamic Semaphores7.12 Semaphore Deletion7.13 Semaphore Reset7.14 Coordination Across Parallel Processors (Multicore)7.15 Perspective7.16 SummaryExercises
Chapter 8 Message Passing
8.1 Introduction8.2 Two Types of Message Passing Services8.3 Limits On Resources Used By Messages8.4 Message Passing Functions And State Transitions8.5 Implementation of Send8.6 Implementation of Receive8.7 Implementation Of Non-Blocking Message Reception8.8 Perspective8.9 SummaryExercises
Chapter 9 Basic Memory Management
9.1 Introduction9.2 Types of Memory9.3 Definition of A Heavyweight Process9.4 Memory Management In Our Example System9.5 Program Segments And Regions of Memory9.6 Dynamic Memory Allocation9.7 Design Of The Low–level Memory Manager9.8 Allocation Strategy And Memory Persistence9.9 Keeping Track of Free Memory9.10 Implementation Of Low–level Memory Management9.11 Data Structure Definitions Used With Free Memory9.12 Allocating Heap Storage9.13 Allocating Stack Storage9.14 Releasing Heap And Stack Storage9.15 Perspective9.16 SummaryExercises
Chapter 10 High-level Memory Management And Virtual Memory
10.1 Introduction10.2 Partitioned Space Allocation10.3 Buffer Pools10.4 Allocating A Buffer10.5 Returning Buffers To the Buffer Pool10.6 Creating A Buffer Pool10.7 Initializing the Buffer Pool Table10.8 Virtual Memory And Memory Multiplexing10.9 Real And Virtual Address Spaces10.10 Hardware for Demand Paging10.11 Address Translation With A Page Table10.12 Metadata In A Page Table Entry10.13 Demand Paging And Design Questions10.14 Page Replacement And Global Clock10.15 Perspective10.16 SummaryExercises
Chapter 11 High-level Message Passing
11.1 Introduction11.2 Inter–process Communication Ports11.3 The Implementation of Ports11.4 Port Table Initialization11.5 Port Creation11.6 Sending A Message To A Port11.7 Receiving A Message From A Port11.8 Port Deletion And Reset11.9 Perspective11.10 SummaryExercises
Chapter 12 Interrupt Processing
12.1 Introduction12.2 The Advantage of Interrupts12.3 Interrupt Processing12.4 Vectored Interrupts12.5 Integration of Interrupts and Exceptions12.5.1 Galileo (Intel)12.5.2 BeagleBone Black (ARM)12.6 ARM Exception Vectors Using Code12.7 Assignment Of Device Interrupt Vector Numbers12.8 Interrupt Dispatching12.9 The Structure Of Interrupt Software12.9.1 Galileo (Intel)12.9.2 BeagleBone Black (ARM)12.10 Disabling Interrupts12.11 Constraints On Functions That Interrupt Code Invokes12.12 The Need To Reschedule During An Interrupt12.13 Rescheduling During An Interrupt12.14 Perspective12.15 SummaryExercises
Chapter 13 Real-time Clock Management
13.1 Introduction13.2 Timed Events13.3 Real-time Clocks And Timer Hardware13.4 Handling Real-time Clock Interrupts13.5 Delay And Preemption13.6 Implementation Of Preemption13.7 Efficient Management of Delay With A Delta List13.8 Delta List Implementation13.9 Putting A Process To Sleep13.10 Timed Message Reception13.11 Awakening Sleeping Processes13.12 Clock Interrupt Processing13.13 Clock Initialization13.14 Perspective13.15 SummaryExercises
Chapter 14 Device–independent Input and Output
14.1 Introduction14.2 Conceptual Organization of I/O and Device Drivers14.3 Interface and Driver Abstractions14.4 An Example I/O Interface14.5 The Open-Read-Write-Close Paradigm14.6 Bindings For I/O Operations And Device Names14.7 Device Names In Xinu14.8 The Concept Of A Device Switch Table14.9 Multiple Copies Of A Device And Shared Drivers14.10 The Implementation Of High–level I/O Operations14.11 Other High–level I/O Functions14.12 Open, Close, And Reference Counting14.13 Null And Error Entries In Devtab14.14 Initialization Of The I/O System14.15 Perspective14.16 SummaryExercises
Chapter 15 An Example Device Driver
15.1 Introduction15.2 Serial Communication Using UART Hardware15.3 The Tty Abstraction15.4 Organization Of A Tty Device Driver15.5 Request Queues And Buffers15.6 Synchronization Of Upper Half And Lower Half15.7 UART Hardware FIFOs And Driver Design15.8 The Concept Of A Control Block15.9 Tty Control Block And Data Declarations15.10 Minor Device Numbers15.11 Upper–half Tty Character Input (ttygetc)15.12 Upper–half Tty Read Function (ttyread)15.13 Upper–half Tty Character Output (ttyputc)15.14 Starting Output (ttykickout)15.15 Upper–half Tty Multiple Character Output (ttywrite)15.16 Lower–half Tty Driver Function (ttyhandler)15.17 Output Interrupt Processing (ttyhandle_out)15.18 Tty Input Processing (ttyhandle_in)15.18.1 Raw Mode Processing15.18.2 Cbreak Mode Processing15.18.3 Cooked Mode Processing15.19 Tty Control Block Initialization (ttyinit)15.20 Device Driver Control (ttycontrol)15.21 Perspective15.22 SummaryExercises
Chapter 16 DMA Devices And Drivers (Ethernet)
16.1 Introduction16.2 Direct Memory Access And Buffers16.3 Multiple Buffers And Rings16.4 An Example Ethernet Driver Using DMA16.5 Device Hardware Definitions and Constants16.6 Rings And Buffers In Memory16.7 Definitions Of An Ethernet Control Block16.8 Device And Driver Initialization16.9 Reading From An Ethernet Device16.10 Writing To An Ethernet Device16.11 Handling Interrupts From An Ethernet Device16.12 Ethernet Control Functions16.13 Perspective16.14 SummaryExercises
Chapter 17 A Minimal Internet Protocol Stack
17.1 Introduction17.2 Required Functionality17.3 Simultaneous Conversations, Timeouts, And Processes17.4 A Consequence Of The Design17.5 ARP Functions17.6 Definition Of A Network Packet17.7 The Network Input Process17.8 Definitions For IP17.9 IP Functions17.10 Definition Of The UDP Table17.11 UDP Functions17.12 Internet Control Message Protocol17.13 Dynamic Host Configuration Protocol17.14 Perspective17.15 SummaryExercises
Chapter 18 A Remote Disk Driver
18.1 Introduction18.2 The Disk Abstraction18.3 Operations A Disk Driver Supports18.4 Block Transfer And High-level VO Functions18.5 A Remote Disk Paradigm18.6 The Important Concept Of Caching18.7 Semantics Of Disk Operations18.8 Definition Of Driver Data Structures18.9 Driver Initialization (rdsinit)18.10 The Upper-half Open Function (rdsopen)18.11 The Remote Communication Function (rdscomm)18.12 The Upper-half Write Function (rdswrite)18.13 The Upper-half Read Function (rdsread)18.14 Flushing Pending Requests18.15 The Upper-half Control Function (rdscontrol)18.16 Allocating A Disk Buffer (rdsbufalloc)18.17 The Upper-half Close Function (rdsclose)18.18 The Lower-half Communication Process (rdsprocess)18.19 Perspective18.20 SummaryExercises
Chapter 19 File Systems
19.1 What Is A File System?19.2 An Example Set Of File Operations19.3 Design Of A Local File System19.4 Data Structures For The Xinu File System19.5 Implementation Of The Index Manager19.6 Clearing An Index Block (Ifibclear)19.7 Retrieving An Index Block (lfibget)19.8 Storing An Index Block (lfibput)19.9 Allocating An Index Block From The Free List (lfiballoc)19.10 Allocating A Data Block From The Free List (lfdballoc)19.11 Using The Device-Independent I/O Functions For Files19.12 File System Device Configuration And Function Names19.13 The Local File System Open Function (lfsopen)19.14 Closing A File Pseudo-Device (lflclose)19.15 Flushing Data To Disk (lfflush)19.16 Bulk Transfer Functions For A File (lflwrite, lflread)19.17 Seeking To A New Position In the File (lflseek)19.18 Extracting One Byte From A File (lflgetc)19.19 Changing One Byte In A File (lflputc)19.20 Loading An Index Block And A Data Block (lfsetup)19.21 Master File System Device Initialization (lfsinit)19.22 Pseudo-Device Initialization (lflinit)19.23 File Truncation (lftruncate)19.24 Initial File System Creation (lfscreate)19.25 Perspective19.26 SummaryExercises
Chapter Chapter 20 A Remote File Mechanism
20.1 Introduction20.2 Remote File Access20.3 Remote File Semantics20.4 Remote File Design And Messages20.5 Remote File Server Communication (rfscomm)20.6 Sending A Basic Message (rfsndmsg)20.7 Network Byte Order20.8 A Remote File System Using A Device Paradigm20.9 Opening A Remote File (rfsopen)20.10 Checking The File Mode (rfsgetmode)20.11 Closing A Remote File (rflclose)20.12 Reading From A Remote File (rflread)20.13 Writing To A Remote File (rflwrite)20.14 Seeking On A Remote File (rflseek)20.15 Character I/O On A Remote File (rflgetc, rflputc)20.16 Remote File System Control Functions (rfscontrol)20.17 Initializing The Remote File System (rfsinit, rflinit)20.18 Perspective20.19 SummaryExercises
Chapter Chapter 21 A Syntactic Namespace
21.1 Introduction21.2 Transparency And A Namespace Abstraction21.3 Myriad Naming Schemes21.3.1 Ms-Dos21.3.2 Unix21.3.3 V System21.3.4 Ibis21.4 Naming System Design Alternatives21.5 Thinking About Names Syntactically21.6 Patterns And Replacements21.7 Prefix Patterns21.8 Implementation Of A Namespace21.9 Namespace Data Structures And Constants21.10 Adding Mappings To The Namespace Prefix Table21.11 Mapping Names With The Prefix Table21.12 Opening A Named File21.13 Namespace Initialization21.14 Ordering Entries In The Prefix Table21.15 Choosing A Logical Namespace21.16 A Default Hierarchy And The Null Prefix21.17 Additional Object Manipulation Functions21.18 Advantages And Limits Of The Namespace Approach21.19 Generalized Patterns21.20 Perspective21.21 SummaryExercises
Chapter 22 System Initialization
22.1 Introduction22.2 Bootstrap: Starting From Scratch22.3 An Example Of Booting Over A Network22.4 Operating System Initialization22.5 Xinu Initialization22.6 Xinu System Startup22.7 Transforming A Program Into A Process22.8 Perspective22.9 SummaryExercises
Chapter 23 Subsystem Initialization And Memory Marking
23.1 Introduction23.2 Self-initializing Modules23.3 Self-initializing Modules In A Concurrent System23.4 Self-initialization In The Presence Of Reboot23.5 Initialization Using Accession Numbers23.6 A Generalized Memory Marking Scheme23.7 Data Declarations For The Memory Marking System23.8 Implementation Of Marking23.9 Perspective23.10 SummaryExercises
Chapter 24 Exception Handling
24.1 Introduction24.2 Terminology: Faults, Checks, Traps, And Exceptions24.3 Vectored Exceptions And Maskable Interrupts24.4 Types Of Exceptions24.5 Handling Exceptions24.6 Exception Vector Initialization24.7 Panic In The Face Of Catastrophic Problems24.8 Implementation Of Panic24.9 Perspective24.10 SummaryExercises
Chapter 25 System Configuration
25.1 Introduction25.2 The Need For Multiple Configurations25.3 Configuration In Xinu25.4 Contents Of The Xinu Configuration File25.4.1 Section 1: Type Declarations25.4.2 Section 2: Device Specifications25.4.3 Symbolic Constants25.5 Computation Of Minor Device Numbers25.6 Steps In Configuring A Xinu System25.7 Perspective25.8 SummaryExercises
Chapter 26 An Example User Interface: The Xinu Shell
26.1 Introduction26.2 What Is A User Interface?26.3 Commands And Design Principles26.4 Design Decisions For A Simplified Shell26.5 Shell Organization And Operation26.6 The Definition Of Lexical Tokens26.7 The Definition Of Command-Line Syntax26.8 Implementation Of The Xinu Shell26.9 Storage Of Tokens26.10 Code For The Lexical Analyzer26.11 The Heart Of The Command Interpreter26.12 Command Name Lookup And Builtin Processing26.13 Arguments Passed To Commands26.14 Passing Arguments To A Non-builtin Command26.15 I/O Redirection26.16 An Example Command Function (sleep)26.17 Perspective26.18 SummaryExercises
Chapter Appendix 1: Porting An Operating System
A1.1 IntroductionA1.2 Motivation: Evolving HardwareA1.3 Steps Taken When Porting An Operating SystemA1.3.1 Learning About The HardwareA1.3.2 Build Cross-Development ToolsA1.3.3 Learn The Compiler's Calling ConventionsA1.3.4 Build A Bootstrap MechanismA1.3.5 Devise A Basic Polled Output FunctionA1.3.6 Load And Run A Sequential ProgramA1.3.7 Port And Test The Basic Memory ManagerA1.3.8 Port The Context Switch And Process Creation FunctionsA1.3.9 Port And Test The Remaining Process Manager FunctionsA1.3.10 Build An Interrupt DispatcherA1.3.11 Port And Test The Real-Time Clock FunctionsA1.3.12 Port And Test A Tty DriverA1.3.13 Port Or Create Drivers For An Ethernet And Other DevicesA1.3.14 Port The Network Stack, Including Internet ProtocolsA1.3.15 Port The Remote Disk And RAM Disk ModulesA1.3.16 Port The Local And Remote File System ModulesA1.3.17 Port The Xinu Shell And Other ApplicationsA1.4 Programming To Accommodate ChangeA1.5 Summary
Chapter Appendix 2: Xinu Design Notes
A2.1 IntroductionA2.2 OverviewA2.3 Xinu CharacteristicsA2.4 Xinu ImplementationA2.5 Major Concepts And Implementation
Index

Content preview from Operating System Design, 2nd Edition

4 List And Queue Manipulation

As some day it may happen that a victim must be found, I’ve got a little list ....

— W. S. Gilbert

4.1 Introduction

Linked list processing is fundamental in operating systems, and pervades each component. Linked structures enable a system to manage sets of objects efficiently without searching or copying. As we will see, managing lists ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781498712439

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Operating System Design, 2nd Edition

by Douglas Comer

4 List And Queue Manipulation

4.1 Introduction

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.