eca contents

Table of Contents For

Operating System Design --

The Xinu Approach

Preface xx

About the Author xxiii

Chapter 1 Introduction And Overview 3

1.1	Operating Systems 3
1.2	Approach Used In The Text 4
1.3	A Hierarchical Design 5
1.4	The Xinu Operating System 7
1.5	What An Operating System Is Not 8
1.6	An Operating System Viewed From The Outside 9
1.7	Remainder Of The Text 10
1.8	Perspective 11
1.9	Summary 11
	Exercises 12

Chapter 2 Concurrent Execution And Operating System Services 15

2.1	Introduction 15
2.2	Programming Models For Multiple Activities 16
2.3	Operating System Services 17
2.4	Concurrent Processing Concepts And Terminology 17
2.5	Distinction Between Sequential And Concurrent Programs 19
2.6	Multiple Processes Sharing A Single Piece Of Code 21
2.7	Process Exit And Process Termination 23
2.8	Shared Memory, Race Conditions, And Synchronization 24
2.9	Semaphores And Mutual Exclusion 28
2.10	Type Names Used In Xinu 30
2.11	Operating System Debugging With Kputc And Kprintf 31
2.12	Perspective 32
2.13	Summary 32
	Exercises 33

Chapter 3 An Overview Of The Hardware And Runtime Environment 37

3.1	Introduction 37
3.2	Physical And Logical Organizations Of A Platform 38
3.3	Instruction Sets 38
3.4	General-purpose Registers 39
	3.4.1	Galileo (Intel) 40
	3.4.2	BeagleBone Black (ARM) 41
3.5	I\^/\^O Buses And The Fetch-Store Paradigm 41
3.6	Direct Memory Access 42
3.7	The Bus Address Space 42
3.8	Bus Startup And Configuration 43
3.9	Calling Conventions And The Runtime Stack 44
	3.9.1	Galileo (Intel) 45
	3.9.2	BeagleBone Black (ARM) 46
3.10	Interrupts And Interrupt Processing 47
3.11	Vectored Interrupts 48
3.12	Exception Vectors And Exception Processing 48
3.13	Clock Hardware 49
3.14	Serial Communication 49
3.15	Polled vs. Interrupt-driven I\^/\^O 49
3.16	Storage Layout 50
3.17	Memory Protection 51
3.18	Hardware Details And A System On Chip Architecture 51
3.19	Hardware Architecture Vs. Operating System Interface 52
3.20	Perspective 52
3.21	Hardware References 52
	Exercises 53

Chapter 4 List And Queue Manipulation 57

4.1	Introduction 57
4.2	A Unified Structure For Linked Lists Of Processes 58
4.3	A Compact List Data Structure 59
4.4	Implementation Of The Queue Data Structure 61
4.5	Inline Queue Manipulation Functions 62
4.6	Basic Functions To Extract A Process From A List 63
4.7	FIFO Queue Manipulation 65
4.8	Manipulation Of Priority Queues 68
4.9	List Initialization 70
4.10	Perspective 71
4.11	Summary 72
	Exercises 72

Chapter 5 Scheduling And Context Switching 77

5.1	Introduction 77
5.2	The Process Table 78
5.3	Process States 81
5.4	Ready And Current States 82
5.5	A Scheduling Policy 82
5.6	Implementation Of Scheduling 83
5.7	Deferred Rescheduling 87
5.8	Implementation Of Context Switching 88
5.9	State Saved In Memory 88
5.10	Context Switch Operation 89
	5.10.1	Galileo (Intel) 90
	5.10.2	BeagleBone Black (ARM) 91
5.11	An Address At Which To Restart A Process 93
5.12	Concurrent Execution And A Null Process 94
5.13	Making A Process Ready And The Scheduling Invariant 95
5.14	Other Process Scheduling Algorithms 96
5.15	Perspective 97
5.16	Summary 97
	Exercises 97

Chapter 6 More Process Management 101

6.1	Introduction 101
6.2	Process Suspension And Resumption 101
6.3	Self\-suspension And Information Hiding 102
6.4	The Concept Of A System Call 103
6.5	Interrupt Control With Disable And Restore 105
6.6	A System Call Template 106
6.7	System Call Return Values SYSERR And OK 106
6.8	Implementation Of Suspend 107
6.9	Suspending The Current Process 109
6.10	The Value Returned By Suspend 109
6.11	Process Termination And Process Exit 110
6.12	Process Creation 113
6.13	Other Process Manager Functions 117
6.14	A Hardware Mechanism For System Calls 119
6.15	Summary 120
	Exercises 120

Chapter 7 Coordination Of Concurrent Processes 125

7.1	Introduction 125
7.2	The Need For Synchronization 125
7.3	A Conceptual View Of Counting Semaphores 127
7.4	Avoidance Of Busy Waiting 127
7.5	Semaphore Policy And Process Selection 128
7.6	The Waiting State 129
7.7	Semaphore Data Structures 130
7.8	The Wait System Call 131
7.9	The Signal System Call 132
7.10	Static And Dynamic Semaphore Allocation 133
7.11	Example Implementation Of Dynamic Semaphores 134
7.12	Semaphore Deletion 135
7.13	Semaphore Reset 137
7.14	Coordination Across Parallel Processors (Multicore) 138
7.15	Perspective 139
7.16	Summary 139
	Exercises 140

Chapter 8 Message Passing 145

8.1	Introduction 145
8.2	Two Types Of Message Passing Services 145
8.3	Limits On Resources Used By Messages 146
8.4	Message Passing Functions And State Transitions 147
8.5	Implementation Of Send 148
8.6	Implementation Of Receive 150
8.7	Implementation Of Non-Blocking Message Reception 151
8.8	Perspective 151
8.9	Summary 152
	Exercises 152

Chapter 9 Basic Memory Management 155

9.1	Introduction 155
9.2	Types Of Memory 155
9.3	Definition Of A Heavyweight Process 156
9.4	Memory Management In Our Example System 157
9.5	Program Segments And Regions Of Memory 158
9.6	Dynamic Memory Allocation 159
9.7	Design Of The Low\-level Memory Manager 160
9.8	Allocation Strategy And Memory Persistence 161
9.9	Keeping Track Of Free Memory 161
9.10	Implementation Of Low\-level Memory Management 162
9.11	Data Structure Definitions Used With Free Memory 163
9.12	Allocating Heap Storage 164
9.13	Allocating Stack Storage 167
9.14	Releasing Heap And Stack Storage 169
9.15	Perspective 172
9.16	Summary 172
	Exercises 173

Chapter 10 High-level Memory Management and Virtual Memory 177

10.1	Introduction 177
10.2	Partitioned Space Allocation 178
10.3	Buffer Pools 178
10.4	Allocating A Buffer 180
10.5	Returning Buffers To The Buffer Pool 181
10.6	Creating A Buffer Pool 183
10.7	Initializing The Buffer Pool Table 185
10.8	Virtual Memory And Memory Multiplexing 186
10.9	Real And Virtual Address Spaces 187
10.10	Hardware For Demand Paging 188
10.11	Address Translation With A Page Table 189
10.12	Multi-Level Page Tables On 64-Bit Computers 190
10.13	Metadata In A Page Table Entry 191
10.14	Demand Paging And Design Questions 191
10.15	Page Replacement And Global Clock 192
10.16	Perspective 193
10.17	Summary 193
	Exercises 194

Chapter 11 High-level Message Passing 197

11.1	Introduction 197
11.2	Inter\-process Communication Ports 197
11.3	The Implementation Of Ports 198
11.4	Port Table Initialization 199
11.5	Port Creation 201
11.6	Sending A Message To A Port 202
11.7	Receiving A Message From A Port 204
11.8	Port Deletion And Reset 206
11.9	Perspective 209
11.10	Summary 209
	Exercises 209

Chapter 12 Interrupt Processing 213

12.1	Introduction 213
12.2	The Advantage Of Interrupts 214
12.3	Interrupt Processing 214
12.4	Vectored Interrupts 215
12.5	Integration Of Interrupts And Exceptions 216
	12.5.1	Galileo (Intel) 216
	12.5.2	BeagleBone Black (ARM) 216
12.6	ARM Exception Vectors Containing Code 217
12.7	Assignment Of Device Interrupt Vector Numbers 221
12.8	Interrupt Dispatching 222
12.9	The Structure Of Interrupt Software 223
	12.9.1	Galileo (Intel) 223
	12.9.2	BeagleBone Black (ARM) 224
12.10	Disabling Interrupts 225
12.11	Constraints On Functions That Interrupt Code Invokes 227
12.12	The Need To Reschedule During An Interrupt 227
12.13	Rescheduling During An Interrupt 228
12.14	Perspective 229
12.15	Summary 230
	Exercises 230

Chapter 13 Real-time Clock Management 235

13.1	Introduction 235
13.2	Timed Events 236
13.3	Real-time Clocks And Timer Hardware 236
13.4	Handling Real-time Clock Interrupts 237
13.5	Delay And Preemption 238
13.6	Implementation Of Preemption 239
13.7	Efficient Management Of Delay With A Delta List 240
13.8	Delta List Implementation 241
13.9	Putting A Process To Sleep 243
13.10	Timed Message Reception 246
13.11	Awakening Sleeping Processes 250
13.12	Clock Interrupt Processing 251
13.13	Clock Initialization 253
13.14	Perspective 256
13.15	Summary 257
	Exercises 257

Chapter 14 Device\-independent Input And Output 261

14.1	Introduction 261
14.2	Conceptual Organization Of I\^/\^O And Device Drivers 262
14.3	Interface And Driver Abstractions 263
14.4	An Example I\^/\^O Interface 264
14.5	The Open-Read-Write-Close Paradigm 265
14.6	Bindings For I\^/\^O Operations And Device Names 266
14.7	Device Names In Xinu 267
14.8	The Concept Of A Device Switch Table 267
14.9	Multiple Copies Of A Device And Shared Drivers 268
14.10	The Implementation Of High\-level I\^/\^O Operations 271
14.11	Null And Error Entries In Devtab 273
14.12	Initialization Of The I\^/\^O System 274
14.13	Perspective 275
14.14	Summary 275
	Exercises 276

Chapter 15 An Example Device Driver 279

15.1	Introduction 279
15.2	Serial Communication Using UART Hardware 279
15.3	The Tty Abstraction 280
15.4	Organization Of A Tty Device Driver 281
15.5	Request Queues And Buffers 282
15.6	Synchronization Of Upper Half And Lower Half 283
15.7	UART Hardware FIFOs And Driver Design 284
15.8	The Concept Of A Control Block 285
15.9	Tty Control Block And Data Declarations 285
15.10	Minor Device Numbers 288
15.11	Upper\-half Tty Character Input (ttygetc) 289
15.12	Upper\-half Tty Read Function (ttyread) 290
15.13	Upper\-half Tty Character Output (ttyputc) 292
15.14	Starting Output (ttykickout) 293
15.15	Upper\-half Tty Multiple Character Output (ttywrite) 294
15.16	Lower\-half Tty Driver Function (ttyhandler) 295
15.17	Tty Output Interrupt Processing (ttyhandle_out) 298
15.18	Tty Input Processing (ttyhandle_in) 300
	15.18.1	Raw Mode Processing 306
	15.18.2	Cbreak Mode Processing 306
	15.18.3	Cooked Mode Processing 307
15.19	Tty Control Block Initialization (ttyinit) 307
15.20	Device Driver Control (ttycontrol) 310
15.21	Perspective 312
15.22	Summary 312
	Exercises 313

Chapter 16 DMA Devices And Drivers (Ethernet) 317

16.1	Introduction 317
16.2	Direct Memory Access And Buffers 317
16.3	Multiple Buffers And Rings 318
16.4	An Example Ethernet Driver Using DMA 319
16.5	Device Hardware Definitions And Constants 320
16.6	Rings And Buffers In Memory 320
16.7	Definition Of An Ethernet Control Block 321
16.8	Device And Driver Initialization 322
16.9	Reading From And Writing To An Ethernet Device 322
16.10	Handling Interrupts From An Ethernet Device 323
16.11	Ethernet Control Functions 323
16.12	Perspective 324
16.13	Summary 324
	Exercises 325

Chapter 17 A Minimal Internet Protocol Stack 329

17.1	Introduction 329
17.2	Required Functionality 330
17.3	Simultaneous Conversations, Timeouts, And Processes 331
17.4	A Consequence Of The Design 331
17.5	ARP Functions 332
17.6	The Network Input Process 334
17.7	Functions For The Internet Protocol (IP) 335
17.8	Functions For The User Datagram Protocol (UDP) 335
17.9	Functions For the Internet Control Message Protocol (ICMP) 337
17.10	Dynamic Host Configuration Protocol (DHCP) 337
17.11	Perspective 338
17.12	Summary 339
	Exercises 339

Chapter 18 A Remote Disk Driver 343

18.1	Introduction 343
18.2	The Disk Abstraction 343
18.3	Operations A Disk Driver Supports 344
18.4	Block Transfer And High\-level I/O Functions 344
18.5	A Remote Disk Paradigm 345
18.6	The Important Concept Of Block Caching 346
18.7	Last-Write Semantics For Disk Operations 347
18.8	Using A Serial Queue To Guarantee Request Ordering 348
18.9	Definition Of Driver Data Structures And Messages 349
18.10	Remote Disk Read, Write, And Sync Operations 349
18.11	Coordinating With The Communication Process 350
18.12	Communication With The Remote Server 351
18.13	The Lower\-half Communication Process (rdsprocess) 351
18.14	Driver Initialization And Disk Open 352
18.15	Perspective 352
18.16	Summary 352
	Exercises 353

Chapter 19 File Systems 357

19.1	What Is A File System? 357
19.2	An Example Set Of File Operations 358
19.3	Design Of A Local File System 359
19.4	Data Structures For The Xinu File System 359
19.5	Implementation Of The Index Manager 360
19.6	Index Block Operations 362
19.7	Allocating Index And Data Blocks 362
19.8	Using The Device-Independent I\^/\^O Functions For Files 363
19.9	File System Device Configuration And Function Names 364
19.10	The Local File System Open Function (lfsopen) 365
19.11	Closing A File Pseudo-Device (lflclose) 367
19.12	Bulk Transfer Functions For A File (lflwrite, lflread) 367
19.13	Flushing Data To Disk (lfflush) 368
19.14	Seeking To A New Position In the File (lflseek) 368
19.15	Extracting And Storing One Byte In A File 368
19.16	Loading An Index Block And A Data Block (lfsetup) 369
19.17	File System Device Initialization 370
19.18	File Truncation (lftruncate) 370
19.19	Formatting A Disk For An Initial File System 371
19.20	Perspective 371
19.21	Summary 372
	Exercises 372

Chapter 20 A Remote File System 377

20.1	Introduction 377
20.2	Remote File Access 377
20.3	Remote File Semantics 378
20.4	Remote File Design And Messages 379
20.5	Remote File Server Communication (rfscomm) 379
20.6	Sending A Basic Message (rfsndmsg) 380
20.7	Network Byte Order 380
20.8	A Remote File System Using A Device Paradigm 381
20.9	Opening A Remote File (rfsopen) 382
20.10	Closing A Remote File (rflclose) 383
20.11	Reading And Writing A Remote File (rflread, rflwrite) 383
20.12	Seeking On A Remote File (rflseek) 383
20.13	Single Byte I\^/\^O On A Remote File (rflgetc, rflputc) 384
20.14	Remote File System Control Functions (rfscontrol) 384
20.15	Initializing The Remote File System (rfsinit, rflinit) 385
20.16	Perspective 385
20.17	Summary 386
	Exercises 386

Chapter 21 A Syntactic Namespace 389

21.1	Introduction 389
21.2	Transparency And A Namespace Abstraction 389
21.3	Myriad Naming Schemes 390
	21.3.1	MS-DOS 391
	21.3.2	Unix 391
	21.3.3	V System 391
	21.3.4	IBIS 391
21.4	Naming System Design Alternatives 392
21.5	Thinking About Names Syntactically 392
21.6	Patterns And Replacements 393
21.7	Prefix Patterns 393
21.8	Implementation Of A Namespace 394
21.9	Namespace Data Structures And Constants 394
21.10	Adding Mappings To The Namespace Prefix Table 395
21.11	Mapping Names With The Prefix Table 397
21.12	Opening A Named File 401
21.13	Namespace Initialization 402
21.14	Ordering Entries In The Prefix Table 405
21.15	Choosing A Logical Namespace 406
21.16	A Default Hierarchy And The Null Prefix 407
21.17	Additional Object Manipulation Functions 407
21.18	Advantages And Limits Of The Namespace Approach 408
21.19	Generalized Patterns 409
21.20	Perspective 410
21.21	Summary 410
	Exercises 411

Chapter 22 System Initialization 415

22.1	Introduction 415
22.2	Bootstrap: Starting From Scratch 415
22.3	An Example Of Booting Over A Network 416
22.4	Operating System Initialization 417
22.5	Xinu Initialization 418
22.6	Xinu System Startup 421
22.7	Transforming A Program Into A Process 427
22.8	Perspective 427
22.9	Summary 428
	Exercises 428

Chapter 23 Subsystem Initialization And Memory Marking 431

23.1	Introduction 431
23.2	Self-initializing Modules 432
23.3	Self-initializing Modules In A Concurrent System 433
23.4	Self-initialization In The Presence Of Reboot 435
23.5	Initialization Using Accession Numbers 435
23.6	A Generalized Memory Marking Scheme 437
23.7	Data Declarations For The Memory Marking System 438
23.8	Implementation Of Marking 439
23.9	Perspective 441
23.10	Summary 442
	Exercises 442

Chapter 24 Exception Handling 445

24.1	Introduction 445
24.2	Terminology: Faults, Checks, Traps, And Exceptions 445
24.3	Vectored Exceptions And Maskable Interrupts 446
24.4	Types Of Exceptions 446
24.5	Handling Exceptions 447
24.6	Exception Vector Initialization 448
24.7	Panic In The Face Of Catastrophic Problems 448
24.8	Implementation Of Panic 449
24.9	Perspective 449
24.10	Summary 450
	Exercises 450

Chapter 25 System Configuration 453

25.1	Introduction 453
25.2	The Need For Multiple Configurations 453
25.3	Configuration In Xinu 455
25.4	Contents Of The Xinu Configuration File 455
	25.4.1	Section 1: Type Declarations 455
	25.4.2	Section 2: Device Specifications 456
	25.4.3	Symbolic Constants 457
25.5	Computation Of Minor Device Numbers 458
25.6	Steps In Configuring A Xinu System 458
25.7	Perspective 459
25.8	Summary 459
	Exercises 460

Chapter 26 A Pipe Mechanism 463

26.1	Introduction 463
26.2	The Bounded Buffer Concept 463
26.3	Pipes As Devices 464
26.4	The Xinu Pipe Mechanism 464
26.5	Pipe Devices And Device Types 464
26.6	Pipe Definitions 465
26.7	State Transitions For A Pipe Pseudo Device 466
26.8	Synchronization Of Sending And Receiving Processes 466
26.9	Initialization Of A Pipe Pseudo Device 467
26.10	Opening A Pipe Device 468
26.11	Extracting A Byte From A Pipe 469
26.12	Depositing A Byte In A Pipe 471
26.13	Reading Multiple Bytes From A Pipe 472
26.14	Writing Multiple Bytes To A Pipe 473
26.15	Closing A Pipe 475
26.16	Summary 476
	Exercises 477

Chapter 27 An Example User Interface: The Xinu Shell 481

27.1	Introduction 481
27.2	What Is A User Interface? 482
27.3	Commands And Design Principles 482
27.4	Design Decisions For A Simplified Shell 483
27.5	Shell Organization And Operation 483
27.6	The Definition Of Lexical Tokens 484
27.7	The Definition Of Command-Line Syntax 485
27.8	Implementation Of The Xinu Shell 486
27.9	Storage Of Tokens 488
27.10	Code For The Lexical Analyzer 489
27.11	Steps The Shell Takes 493
27.12	Arguments Passed To Commands 505
27.13	Storing Arguments For A Command Process 506
27.14	I\^/\^O Redirection In Shell Commands 510
27.15	Example Shell Command Functions (Echo And Sleep) 511
27.16	Perspective 513
27.17	Summary 514
	Exercises 514

Chapter 28 Multicore Systems 519

28.1	Introduction 519
28.2	The Move To Multicore Hardware 519
28.3	Multicore Hardware 520
28.4	Multicore Cache Coherence Hardware 521
28.5	Mutual Exclusion On A Multicore System 522
28.6	Mutual Exclusion With Hardware Locks And Busy Waiting 522
28.7	Cache Coherence, Locks In Memory, And Test-And-Set 522
28.8	Multicore Operating System Design 523
28.9	A Simplistic Scheduling Invariant For Multiple Cores 525
28.10	Context Switching And Changing Cores 525
28.11	Multicore Scheduling Using Thread Affinity 525
28.12	Simultaneous Multithreading (SMT) 527
28.13	Modifying Device Drivers For A Multicore Processor 527
28.14	Cross-Core Notifications 528
28.15	Multicore Interrupt Processing 529
28.16	Summary 529
	Exercises 530

Chapter 29 Operating Systems Everywhere 533

29.1	Introduction 533
29.2	Embedded Systems 533
29.3	The Internet of Things (IoT) 534
29.4	Mobile Systems 534
29.5	Unexpected Uses Of Operating Systems 535
29.6	Operating Systems In Network Equipment 536
29.7	Operating Systems In The Edge/Fog/Cloud Hierarchy 536
29.8	Hypervisors, Virtual I/O Devices, And Containers 537
29.9	Summary 538

Table of Contents For Operating System Design -- The Xinu Approach

Preface xx

About the Author xxiii

Chapter 1 Introduction And Overview 3

Chapter 2 Concurrent Execution And Operating System Services 15

Chapter 3 An Overview Of The Hardware And Runtime Environment 37

Chapter 4 List And Queue Manipulation 57

Chapter 5 Scheduling And Context Switching 77

Chapter 6 More Process Management 101

Chapter 7 Coordination Of Concurrent Processes 125

Chapter 8 Message Passing 145

Chapter 9 Basic Memory Management 155

Chapter 10 High-level Memory Management and Virtual Memory 177

Chapter 11 High-level Message Passing 197

Chapter 12 Interrupt Processing 213

Chapter 13 Real-time Clock Management 235

Chapter 14 Device\-independent Input And Output 261

Chapter 15 An Example Device Driver 279

Chapter 16 DMA Devices And Drivers (Ethernet) 317

Chapter 17 A Minimal Internet Protocol Stack 329

Chapter 18 A Remote Disk Driver 343

Chapter 19 File Systems 357

Chapter 20 A Remote File System 377

Chapter 21 A Syntactic Namespace 389

Chapter 22 System Initialization 415

Chapter 23 Subsystem Initialization And Memory Marking 431

Chapter 24 Exception Handling 445

Chapter 25 System Configuration 453

Chapter 26 A Pipe Mechanism 463

Chapter 27 An Example User Interface: The Xinu Shell 481

Chapter 28 Multicore Systems 519

Chapter 29 Operating Systems Everywhere 533

Index 539

Table of Contents For

Operating System Design --

The Xinu Approach