cnai contents

Table of Contents For

Xinu

2nd Edition

Preface xix

About The Author xxiii

Chapter 1 Introduction And Overview 1

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

Chapter 2 Concurrent Execution And Operating System Services 13

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

Chapter 3 An Overview Of The Hardware And Runtime Environment 33

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

Chapter 4 List And Queue Manipulation 51

4.1	Introduction 51
4.2	A Unified Structure For Linked Lists Of Processes 52
4.3	A Compact List Data Structure 53
4.4	Implementation Of The Queue Data Structure 55
4.5	Inline Queue Manipulation Functions 56
4.6	Basic Functions To Extract A Process From A List 57
4.7	FIFO Queue Manipulation 59
4.8	Manipulation Of Priority Queues 62
4.9	List Initialization 64
4.10	Perspective 65
4.11	Summary 66
	Exercises 66

Chapter 5 Scheduling And Context Switching 69

5.1	Introduction 69
5.2	The Process Table 70
5.3	Process States 73
5.4	Ready And Current States 74
5.5	A Scheduling Policy 74
5.6	Implementation Of Scheduling 75
5.7	Deferred Rescheduling 79
5.8	Implementation Of Context Switching 79
5.9	State Saved In Memory 80
5.10	Context Switch Operation 81
	5.10.1	Galileo (Intel) 82
	5.10.2	BeagleBone Black (ARM) 83
5.11	An Address At Which To Restart A Process 85
5.12	Concurrent Execution And A Null Process 86
5.13	Making A Process Ready And The Scheduling Invariant 87
5.14	Other Process Scheduling Algorithms 88
5.15	Perspective 89
5.16	Summary 89
	Exercises 89

Chapter 6 More Process Management 93

6.1	Introduction 93
6.2	Process Suspension And Resumption 93
6.3	Self\-suspension And Information Hiding 94
6.4	The Concept Of A System Call 95
6.5	Interrupt Control With Disable And Restore 97
6.6	A System Call Template 98
6.7	System Call Return Values SYSERR And OK 99
6.8	Implementation Of Suspend 99
6.9	Suspending The Current Process 101
6.10	The Value Returned By Suspend 101
6.11	Process Termination And Process Exit 102
6.12	Process Creation 105
6.13	Other Process Manager Functions 109
6.14	Summary 111
	Exercises 112

Chapter 7 Coordination Of Concurrent Processes 115

7.1	Introduction 115
7.2	The Need For Synchronization 115
7.3	A Conceptual View Of Counting Semaphores 117
7.4	Avoidance Of Busy Waiting 117
7.5	Semaphore Policy And Process Selection 118
7.6	The Waiting State 119
7.7	Semaphore Data Structures 120
7.8	The Wait System Call 121
7.9	The Signal System Call 122
7.10	Static And Dynamic Semaphore Allocation 123
7.11	Example Implementation Of Dynamic Semaphores 124
7.12	Semaphore Deletion 125
7.13	Semaphore Reset 127
7.14	Coordination Across Parallel Processors (Multicore) 128
7.15	Perspective 129
7.16	Summary 129
	Exercises 130

Chapter 8 Message Passing 133

8.1	Introduction 133
8.2	Two Types Of Message Passing Services 133
8.3	Limits On Resources Used By Messages 134
8.4	Message Passing Functions And State Transitions 135
8.5	Implementation Of Send 136
8.6	Implementation Of Receive 138
8.7	Implementation Of Non-Blocking Message Reception 139
8.8	Perspective 139
8.9	Summary 140
	Exercises 140

Chapter 9 Basic Memory Management 143

9.1	Introduction 143
9.2	Types Of Memory 143
9.3	Definition Of A Heavyweight Process 144
9.4	Memory Management In Our Example System 145
9.5	Program Segments And Regions Of Memory 146
9.6	Dynamic Memory Allocation 147
9.7	Design Of The Low\-level Memory Manager 148
9.8	Allocation Strategy And Memory Persistence 149
9.9	Keeping Track Of Free Memory 149
9.10	Implementation Of Low\-level Memory Management 150
9.11	Data Structure Definitions Used With Free Memory 151
9.12	Allocating Heap Storage 152
9.13	Allocating Stack Storage 155
9.14	Releasing Heap And Stack Storage 157
9.15	Perspective 160
9.16	Summary 160
	Exercises 160

Chapter 10 High-level Memory Management and Virtual Memory 163

10.1	Introduction 163
10.2	Partitioned Space Allocation 164
10.3	Buffer Pools 164
10.4	Allocating A Buffer 166
10.5	Returning Buffers To The Buffer Pool 167
10.6	Creating A Buffer Pool 169
10.7	Initializing The Buffer Pool Table 171
10.8	Virtual Memory And Memory Multiplexing 172
10.9	Real And Virtual Address Spaces 173
10.10	Hardware For Demand Paging 174
10.11	Address Translation With A Page Table 175
10.12	Metadata In A Page Table Entry 176
10.13	Demand Paging And Design Questions 177
10.14	Page Replacement And Global Clock 178
10.15	Perspective 179
10.16	Summary 179
	Exercises 180

Chapter 11 High-level Message Passing 183

11.1	Introduction 183
11.2	Inter\-process Communication Ports 183
11.3	The Implementation Of Ports 184
11.4	Port Table Initialization 185
11.5	Port Creation 187
11.6	Sending A Message To A Port 188
11.7	Receiving A Message From A Port 190
11.8	Port Deletion And Reset 192
11.9	Perspective 195
11.10	Summary 195
	Exercises 195

Chapter 12 Interrupt Processing 199

12.1	Introduction 199
12.2	The Advantage Of Interrupts 200
12.3	Interrupt Processing 200
12.4	Vectored Interrupts 201
12.5	Integration Of Interrupts And Exceptions 202
	12.5.1	Galileo (Intel) 202
	12.5.2	BeagleBone Black (ARM) 202
12.6	ARM Exception Vectors Using Code 203
12.7	Assignment Of Device Interrupt Vector Numbers 207
12.8	Interrupt Dispatching 208
12.9	The Structure Of Interrupt Software 209
	12.9.1	Galileo (Intel) 209
	12.9.2	BeagleBone Black (ARM) 210
12.10	Disabling Interrupts 211
12.11	Constraints On Functions That Interrupt Code Invokes 213
12.12	The Need To Reschedule During An Interrupt 213
12.13	Rescheduling During An Interrupt 214
12.14	Perspective 215
12.15	Summary 216
	Exercises 216

Chapter 13 Real-time Clock Management 219

13.1	Introduction 219
13.2	Timed Events 220
13.3	Real-time Clocks And Timer Hardware 220
13.4	Handling Real-time Clock Interrupts 221
13.5	Delay And Preemption 222
13.6	Implementation Of Preemption 223
13.7	Efficient Management Of Delay With A Delta List 224
13.8	Delta List Implementation 225
13.9	Putting A Process To Sleep 227
13.10	Timed Message Reception 230
13.11	Awakening Sleeping Processes 234
13.12	Clock Interrupt Processing 235
13.13	Clock Initialization 237
13.14	Perspective 240
13.15	Summary 241
	Exercises 241

Chapter 14 Device\-independent Input And Output 245

14.1	Introduction 245
14.2	Conceptual Organization Of I\^/\^O And Device Drivers 246
14.3	Interface And Driver Abstractions 247
14.4	An Example I\^/\^O Interface 248
14.5	The Open-Read-Write-Close Paradigm 249
14.6	Bindings For I\^/\^O Operations And Device Names 250
14.7	Device Names In Xinu 251
14.8	The Concept Of A Device Switch Table 251
14.9	Multiple Copies Of A Device And Shared Drivers 252
14.10	The Implementation Of High\-level I\^/\^O Operations 255
14.11	Other High\-level I\^/\^O Functions 257
14.12	Open, Close, And Reference Counting 261
14.13	Null And Error Entries In Devtab 263
14.14	Initialization Of The I\^/\^O System 264
14.15	Perspective 267
14.16	Summary 268
	Exercises 268

Chapter 15 An Example Device Driver 271

15.1	Introduction 271
15.2	Serial Communication Using UART Hardware 271
15.3	The Tty Abstraction 272
15.4	Organization Of A Tty Device Driver 273
15.5	Request Queues And Buffers 274
15.6	Synchronization Of Upper Half And Lower Half 275
15.7	UART Hardware FIFOs And Driver Design 276
15.8	The Concept Of A Control Block 277
15.9	Tty Control Block And Data Declarations 277
15.10	Minor Device Numbers 280
15.11	Upper\-half Tty Character Input (ttygetc) 281
15.12	Upper\-half Tty Read Function (ttyread) 282
15.13	Upper\-half Tty Character Output (ttyputc) 284
15.14	Starting Output (ttykickout) 285
15.15	Upper\-half Tty Multiple Character Output (ttywrite) 286
15.16	Lower\-half Tty Driver Function (ttyhandler) 287
15.17	Output Interrupt Processing (ttyhandle_out) 290
15.18	Tty Input Processing (ttyhandle_in) 292
	15.18.1	Raw Mode Processing 298
	15.18.2	Cbreak Mode Processing 298
	15.18.3	Cooked Mode Processing 298
15.19	Tty Control Block Initialization (ttyinit) 299
15.20	Device Driver Control (ttycontrol) 301
15.21	Perspective 303
15.22	Summary 304
	Exercises 304

Chapter 16 DMA Devices And Drivers (Ethernet) 307

16.1	Introduction 307
16.2	Direct Memory Access And Buffers 307
16.3	Multiple Buffers And Rings 308
16.4	An Example Ethernet Driver Using DMA 309
16.5	Device Hardware Definitions And Constants 310
16.6	Rings And Buffers In Memory 313
16.7	Definitions Of An Ethernet Control Block 315
16.8	Device And Driver Initialization 318
16.9	Reading From An Ethernet Device 325
16.10	Writing To An Ethernet Device 329
16.11	Handling Interrupts From An Ethernet Device 331
16.12	Ethernet Control Functions 334
16.13	Perspective 335
16.14	Summary 336
	Exercises 336

Chapter 17 A Minimal Internet Protocol Stack 339

17.1	Introduction 339
17.2	Required Functionality 340
17.3	Simultaneous Conversations, Timeouts, And Processes 341
17.4	A Consequence Of the Design 341
17.5	ARP Functions 342
17.6	Definition Of A Network Packet 353
17.7	The Network Input Process 355
17.8	Definitions For IP 359
17.9	IP functions 359
17.10	Definition Of The UDP Table 370
17.11	UDP Functions 371
17.12	Internet Control Message Protocol 385
17.13	Dynamic Host Configuration Protocol 386
17.14	Perspective 394
17.15	Summary 395
	Exercises 395

Chapter 18 A Remote Disk Driver 399

18.1	Introduction 399
18.2	The Disk Abstraction 399
18.3	Operations A Disk Driver Supports 400
18.4	Block Transfer And High\-level I\^/\^O Functions 400
18.5	A Remote Disk Paradigm 401
18.6	The Important Concept Of Caching 402
18.7	Semantics Of Disk Operations 403
18.8	Definition Of Driver Data Structures 403
18.9	Driver Initialization (rdsinit) 409
18.10	The Upper\-half Open Function (rdsopen) 412
18.11	The Remote Communication Function (rdscomm) 414
18.12	The Upper\-half Write Function (rdswrite) 417
18.13	The Upper\-half Read Function (rdsread) 420
18.14	Flushing Pending Requests 424
18.15	The Upper\-half Control Function (rdscontrol) 424
18.16	Allocating A Disk Buffer (rdsbufalloc) 427
18.17	The Upper\-half Close Function (rdsclose) 429
18.18	The Lower\-half Communication Process (rdsprocess) 430
18.19	Perspective 435
18.20	Summary 436
	Exercises 436

Chapter 19 File Systems 439

19.1	What Is A File System? 439
19.2	An Example Set Of File Operations 440
19.3	Design Of A Local File System 441
19.4	Data Structures For The Xinu File System 441
19.5	Implementation Of The Index Manager 442
19.6	Clearing An Index Block (lfibclear) 447
19.7	Retrieving An Index Block (lfibget) 448
19.8	Storing An Index Block (lfibput) 449
19.9	Allocating An Index Block From The Free List (lfiballoc) 451
19.10	Allocating A Data Block From The Free List (lfdballoc) 452
19.11	Using The Device-Independent I\^/\^O Functions For Files 454
19.12	File System Device Configuration And Function Names 454
19.13	The Local File System Open Function (lfsopen) 455
19.14	Closing A File Pseudo-Device (lflclose) 463
19.15	Flushing Data To Disk (lfflush) 463
19.16	Bulk Transfer Functions For A File (lflwrite, lflread) 466
19.17	Seeking To A New Position In the File (lflseek) 468
19.18	Extracting One Byte From A File (lflgetc) 469
19.19	Changing One Byte In A File (lflputc) 470
19.20	Loading An Index Block And A Data Block (lfsetup) 472
19.21	Master File System Device Initialization (lfsinit) 476
19.22	Pseudo-Device Initialization (lflinit) 477
19.23	File Truncation (lftruncate) 479
19.24	Initial File System Creation (lfscreate) 481
19.25	Perspective 483
19.26	Summary 484
	Exercises 484

Chapter 20 A Remote File Mechanism 487

20.1	Introduction 487
20.2	Remote File Access 487
20.3	Remote File Semantics 488
20.4	Remote File Design And Messages 488
20.5	Remote File Server Communication (rfscomm) 496
20.6	Sending A Basic Message (rfsndmsg) 498
20.7	Network Byte Order 500
20.8	A Remote File System Using A Device Paradigm 500
20.9	Opening A Remote File (rfsopen) 502
20.10	Checking The File Mode (rfsgetmode) 505
20.11	Closing A Remote File (rflclose) 506
20.12	Reading From A Remote File (rflread) 507
20.13	Writing To A Remote File (rflwrite) 510
20.14	Seeking On A Remote File (rflseek) 513
20.15	Character I\^/\^O On A Remote File (rflgetc, rflputc) 514
20.16	Remote File System Control Functions (rfscontrol) 515
20.17	Initializing The Remote File System (rfsinit, rflinit) 519
20.18	Perspective 521
20.19	Summary 521
	Exercises 522

Chapter 21 A Syntactic Namespace 525

21.1	Introduction 525
21.2	Transparency And A Namespace Abstraction 525
21.3	Myriad Naming Schemes 526
	21.3.1	MS-DOS 527
	21.3.2	Unix 527
	21.3.3	V System 527
	21.3.4	IBIS 527
21.4	Naming System Design Alternatives 528
21.5	Thinking About Names Syntactically 528
21.6	Patterns And Replacements 529
21.7	Prefix Patterns 529
21.8	Implementation Of A Namespace 530
21.9	Namespace Data Structures And Constants 530
21.10	Adding Mappings To The Namespace Prefix Table 531
21.11	Mapping Names With The Prefix Table 533
21.12	Opening A Named File 537
21.13	Namespace Initialization 538
21.14	Ordering Entries In The Prefix Table 540
21.15	Choosing A Logical Namespace 541
21.16	A Default Hierarchy And The Null Prefix 542
21.17	Additional Object Manipulation Functions 542
21.18	Advantages And Limits Of The Namespace Approach 544
21.19	Generalized Patterns 544
21.20	Perspective 545
21.21	Summary 546
	Exercises 546

Chapter 22 System Initialization 549

22.1	Introduction 549
22.2	Bootstrap: Starting From Scratch 549
22.3	An Example OF Booting Over A Network 550
22.4	Operating System Initialization 551
22.5	Xinu Initialization 552
22.6	Xinu System Startup 555
22.7	Transforming A Program Into A Process 559
22.8	Perspective 560
22.9	Summary 560
	Exercises 561

Chapter 23 Subsystem Initialization And Memory Marking 563

23.1	Introduction 563
23.2	Self-initializing Modules 564
23.3	Self-initializing Modules In A Concurrent System 565
23.4	Self-initialization In The Presence Of Reboot 567
23.5	Initialization Using Accession Numbers 567
23.6	A Generalized Memory Marking Scheme 569
23.7	Data Declarations For The Memory Marking System 570
23.8	Implementation Of Marking 572
23.9	Perspective 573
23.10	Summary 573
	Exercises 574

Chapter 24 Exception Handling 577

24.1	Introduction 577
24.2	Terminology: Faults, Checks, Traps, And Exceptions 577
24.3	Vectored Exceptions And Maskable Interrupts 578
24.4	Types Of Exceptions 578
24.5	Handling Exceptions 579
24.6	Exception Vector Initialization 580
24.7	Panic In The Face Of Catastrophic Problems 580
24.8	Implementation Of Panic 581
24.9	Perspective 581
24.10	Summary 582
	Exercises 582

Chapter 25 System Configuration 585

25.1	Introduction 585
25.2	The Need For Multiple Configurations 585
25.3	Configuration In Xinu 587
25.4	Contents Of The Xinu Configuration File 587
	25.4.1	Section 1: Type Declarations 587
	25.4.2	Section 2: Device Specifications 588
	25.4.3	Symbolic Constants 589
25.5	Computation Of Minor Device Numbers 590
25.6	Steps In Configuring A Xinu System 590
25.7	Perspective 591
25.8	Summary 591
	Exercises 592

Chapter 26 An Example User Interface: The Xinu Shell 595

26.1	Introduction 595
26.2	What Is A User Interface? 596
26.3	Commands And Design Principles 596
26.4	Design Decisions For A Simplified Shell 597
26.5	Shell Organization And Operation 597
26.6	The Definition Of Lexical Tokens 598
26.7	The Definition Of Command-Line Syntax 599
26.8	Implementation Of The Xinu Shell 599
26.9	Storage Of Tokens 602
26.10	Code For The Lexical Analyzer 603
26.11	The Heart Of The Command Interpreter 607
26.12	Command Name Lookup And Builtin Processing 615
26.13	Arguments Passed To Commands 615
26.14	Passing Arguments To A Non-builtin Command 617
26.15	I\^/\^O Redirection 620
26.16	An Example Command Function (sleep) 621
26.17	Perspective 623
26.18	Summary 624
	Exercises 624

Appendix 1 Porting An Operating System 627

A1.1	Introduction 627
A1.2	Motivation: Evolving Hardware 628
A1.3	Steps Taken When Porting An Operating System 628
	A1.3.1	Learning About The Hardware 630
	A1.3.2	Build Cross-Development Tools 630
	A1.3.3	Learn The Compiler's Calling Conventions 630
	A1.3.4	Build A Bootstrap Mechanism 631
	A1.3.5	Devise A Basic Polled Output Function 631
	A1.3.6	Load And Run A Sequential Program 631
	A1.3.7	Port And Test The Basic Memory Manager 632
	A1.3.8	Port The Context Switch And Process Creation Functions 632
	A1.3.9	Port And Test The Remaining Process Manager Functions 632
	A1.3.10	Build An Interrupt Dispatcher 633
	A1.3.11	Port And Test The Real-Time Clock Functions 633
	A1.3.12	Port And Test A Tty Driver 633
	A1.3.13	Port Or Create Drivers For An Ethernet And Other Devices 633
	A1.3.14	Port The Network Stack, Including Internet Protocols 634
	A1.3.15	Port The Remote Disk And RAM Disk Modules 634
	A1.3.16	Port The Local And Remote File System Modules 634
	A1.3.17	Port The Xinu Shell And Other Applications 634
A1.4	Programming To Accommodate Change 634
A1.5	Summary 636

Appendix 2 Xinu Design Notes 637

A2.1	Introduction 637
A2.2	Overview 637
A2.3	Xinu Characteristics 638
A2.4	Xinu Implementation 639
A2.5	Major Concepts And Implementation 641

Table of Contents For Xinu 2nd Edition

Preface xix

About The Author xxiii

Chapter 1 Introduction And Overview 1

Chapter 2 Concurrent Execution And Operating System Services 13

Chapter 3 An Overview Of The Hardware And Runtime Environment 33

Chapter 4 List And Queue Manipulation 51

Chapter 5 Scheduling And Context Switching 69

Chapter 6 More Process Management 93

Chapter 7 Coordination Of Concurrent Processes 115

Chapter 8 Message Passing 133

Chapter 9 Basic Memory Management 143

Chapter 10 High-level Memory Management and Virtual Memory 163

Chapter 11 High-level Message Passing 183

Chapter 12 Interrupt Processing 199

Chapter 13 Real-time Clock Management 219

Chapter 14 Device\-independent Input And Output 245

Chapter 15 An Example Device Driver 271

Chapter 16 DMA Devices And Drivers (Ethernet) 307

Chapter 17 A Minimal Internet Protocol Stack 339

Chapter 18 A Remote Disk Driver 399

Chapter 19 File Systems 439

Chapter 20 A Remote File Mechanism 487

Chapter 21 A Syntactic Namespace 525

Chapter 22 System Initialization 549

Chapter 23 Subsystem Initialization And Memory Marking 563

Chapter 24 Exception Handling 577

Chapter 25 System Configuration 585

Chapter 26 An Example User Interface: The Xinu Shell 595

Appendix 1 Porting An Operating System 627

Appendix 2 Xinu Design Notes 637

Index 643

Table of Contents For

Xinu

2nd Edition