book

Operating System Design, 3rd Edition

Name: Operating System Design, 3rd Edition
Author: Douglas Comer
ISBN: 9781040345764

by Douglas Comer

May 2025

Intermediate to advanced

573 pages

14h 38m

English

Chapman and Hall/CRC

Read now

Unlock full access

Cover Page
Half-Title Page
Title Page
Copyright Page
Dedication Page
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 Summary
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 Summary

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.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.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 Hardware Architecture Vs. Operating System Interface3.20 Perspective3.21 Hardware References
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 Summary
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.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 Summary
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 A Hardware Mechanism For System Calls6.15 Summary
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 Summary
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 Summary
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 Summary
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 Multi-Level Page Tables On 64-Bit Computers10.13 Metadata In A Page Table Entry10.14 Demand Paging And Design Questions10.15 Page Replacement And Global Clock10.16 Perspective10.17 Summary
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 Summary
Chapter 12 Interrupt Processing
12.1 Introduction12.2 The Advantage Of Interrupts12.3 Interrupt Processing12.4 Vectored Interrupts12.5 Integration Of Interrupts And Exceptions12.6 ARM Exception Vectors Containing Code12.7 Assignment Of Device Interrupt Vector Numbers12.8 Interrupt Dispatching12.9 The Structure Of Interrupt Software12.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 Summary
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 Summary
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 Null And Error Entries In Devtab14.12 Initialization Of The I/O System14.13 Perspective14.14 Summary
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 Tty Output Interrupt Processing (ttyhandle_out)15.18 Tty Input Processing (ttyhandle_in)15.19 Tty Control Block Initialization (ttyinit)15.20 Device Driver Control (ttycontrol)15.21 Perspective15.22 Summary
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 Definition Of An Ethernet Control Block16.8 Device And Driver Initialization16.9 Reading From And Writing To An Ethernet Device16.10 Handling Interrupts From An Ethernet Device16.11 Ethernet Control Functions16.12 Perspective16.13 Summary
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 The Network Input Process17.7 Functions For The Internet Protocol (IP)17.8 Functions For The User Datagram Protocol (UDP)17.9 Functions For the Internet Control Message Protocol (ICMP)17.10 Dynamic Host Configuration Protocol (DHCP)17.11 Perspective17.12 Summary
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 I/O Functions18.5 A Remote Disk Paradigm18.6 The Important Concept Of Block Caching18.7 Last-Write Semantics For Disk Operations18.8 Using A Serial Queue To Guarantee Request Ordering18.9 Definition Of Driver Data Structures And Messages18.10 Remote Disk Read, Write, And Sync Operations18.11 Coordinating With The Communication Process18.12 Communication With The Remote Server18.13 The Lower–half Communication Process (rdsprocess)18.14 Driver Initialization And Disk Open18.15 Perspective18.16 Summary
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 Index Block Operations19.7 Allocating Index And Data Blocks19.8 Using The Device-Independent I/O Functions For Files19.9 File System Device Configuration And Function Names19.10 The Local File System Open Function (lfsopen)19.11 Closing A File Pseudo-Device (lflclose)19.12 Bulk Transfer Functions For A File (lflwrite, lflread)19.13 Flushing Data To Disk (lfflush)19.14 Seeking To A New Position In the File (lflseek)19.15 Extracting And Storing One Byte In A File19.16 Loading An Index Block And A Data Block (lfsetup)19.17 File System Device Initialization19.18 File Truncation (lftruncate)19.19 Formatting A Disk For An Initial File System19.20 Perspective19.21 Summary
Chapter 20 A Remote File System
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 Closing A Remote File (rflclose)20.11 Reading And Writing A Remote File (rflread, rflwrite)20.12 Seeking On A Remote File (rflseek)20.13 Single Byte I/O On A Remote File (rflgetc, rflputc)20.14 Remote File System Control Functions (rfscontrol)20.15 Initializing The Remote File System (rfsinit, rflinit)20.16 Perspective20.17 Summary
Chapter 21 A Syntactic Namespace
21.1 Introduction21.2 Transparency And A Namespace Abstraction21.3 Myriad Naming Schemes21.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 Summary
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 Summary
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 Summary
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 Summary
Chapter 25 System Configuration
25.1 Introduction25.2 The Need For Multiple Configurations25.3 Configuration In Xinu25.4 Contents Of The Xinu Configuration File25.5 Computation Of Minor Device Numbers25.6 Steps In Configuring A Xinu System25.7 Perspective25.8 Summary
Chapter 26 A Pipe Mechanism
26.1 Introduction26.2 The Bounded Buffer Concept26.3 Pipes As Devices26.4 The Xinu Pipe Mechanism26.5 Pipe Devices And Device Types26.6 Pipe Definitions26.7 State Transitions For A Pipe Pseudo Device26.8 Synchronization Of Sending And Receiving Processes26.9 Initialization Of A Pipe Pseudo Device26.10 Opening A Pipe Device26.11 Extracting A Byte From A Pipe26.12 Depositing A Byte In A Pipe26.13 Reading Multiple Bytes From A Pipe26.14 Writing Multiple Bytes To A Pipe26.15 Closing A Pipe26.16 Summary
Chapter 27 An Example User Interface: The Xinu Shell
27.1 Introduction27.2 What Is A User Interface?27.3 Commands And Design Principles27.4 Design Decisions For A Simplified Shell27.5 Shell Organization And Operation27.6 The Definition Of Lexical Tokens27.7 The Definition Of Command-Line Syntax27.8 Implementation Of The Xinu Shell27.9 Storage Of Tokens27.10 Code For The Lexical Analyzer27.11 Steps The Shell Takes27.12 Arguments Passed To Commands27.13 Storing Arguments For A Command Process27.14 I/O Redirection In Shell Commands27.15 Example Shell Command Functions (Echo And Sleep)27.16 Perspective27.17 Summary
Chapter 28 Multicore Systems
28.1 Introduction28.2 The Move To Multicore Hardware28.3 Multicore Hardware28.4 Multicore Cache Coherence Hardware28.5 Mutual Exclusion On A Multicore System28.6 Mutual Exclusion With Hardware Locks And Busy Waiting28.7 Cache Coherence, Locks In Memory, And Test-And-Set28.8 Multicore Operating System Design28.9 A Simplistic Scheduling Invariant For Multiple Cores28.10 Context Switching And Changing Cores28.11 Multicore Scheduling Using Thread Affinity28.12 Simultaneous Multithreading (SMT)28.13 Modifying Device Drivers For A Multicore Processor28.14 Cross-Core Notifications28.15 Multicore Interrupt Processing28.16 Summary
Chapter 29 Operating Systems Everywhere
29.1 Introduction29.2 Embedded Systems29.3 The Internet of Things (IoT)29.4 Mobile Systems29.5 Unexpected Uses Of Operating Systems29.6 Operating Systems In Network Equipment29.7 Operating Systems In The Edge/Fog/Cloud Hierarchy29.8 Hypervisors, Virtual I/O Devices, And Containers29.9 Summary
Index

Content preview from Operating System Design, 3rd 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 of processes is especially important.

This chapter introduces a set of functions that form the backbone of a linked list manipulation system. The functions represent a unified approach — a single data structure and a single set of nodes used by all levels of the operating system to maintain lists of processes. We will see that the data structure includes functions to create a new ...

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: 9781040345764

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Operating System Design, 3rd 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.