xinu-book-linksys-version

Table of Contents For

Operating Systems Design: The Xinu Approach (Linksys Version)

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 8
1.9	Summary 9
	Exercises 9

Chapter 2 Concurrent Execution And Operating System Services 11

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

Chapter 3 An Overview Of The Hardware and Run-Time Environment 31

3.1	Introduction 31
3.2	Physical And Logical Organizations Of The E2100L 32
3.3	Processor Organization And Registers 33
3.4	Bus Operation: The Fetch-Store Paradigm 34
3.5	Direct Memory Access 34
3.6	The Bus Address Space 35
3.7	Contents Of Kernel Segments KSEG0 and KSEG1 36
3.8	Bus Startup Static Configuration 37
3.9	Calling Conventions And The Run-Time Stack 38
3.10	Interrupts And Interrupt Processing 40
3.11	Exception Processing 41
3.12	Timer Hardware 42
3.13	Serial Communication 42
3.14	Polled vs. Interrupt-Driven I/O 43
3.15	Memory Cache And KSEG1 43
3.16	Storage Layout 44
3.17	Memory Protection 45
3.18	Perspective 45
	Exercises 45

Chapter 4 List and Queue Manipulation 49

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

Chapter 5 Scheduling and Context Switching 67

5.1	Introduction 67
5.2	The Process Table 68
5.3	Process States 71
5.4	Ready And Current States 72
5.5	A Scheduling Policy 72
5.6	Implementation Of Scheduling 73
5.7	Implementation Of Context Switching 76
5.8	State Saved In Memory 76
5.9	Context Switch On A MIPS Processor 77
5.10	An Address At Which To Restart A Process 80
5.11	Concurrent Execution And A Null Process 81
5.12	Making A Process Ready And The Scheduling Invariant 82
5.13	Deferred Rescheduling 83
5.14	Other Process Scheduling Algorithms 85
5.15	Perspective 86
5.16	Summary 86
	Exercises 87

Chapter 6 More Process Management 89

6.1	Introduction 89
6.2	Process Suspension And Resumption 89
6.3	Self-Suspension And Information Hiding 90
6.4	The Concept Of A System Call 91
6.5	Interrupt Control With Disable And Restore 93
6.6	A System Call Template 94
6.7	System Call Return Values SYSERR And OK 95
6.8	Implementation Of Suspend 95
6.9	Suspending The Current Process 97
6.10	Suspend Return Value 97
6.11	Process Termination And Process Exit 98
6.12	Process Creation 101
6.13	Other Process Manager Functions 106
6.14	Summary 108
	Exercises 108

Chapter 7 Coordination Of Concurrent Processes 111

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

Chapter 8 Message Passing 129

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

Chapter 9 Basic Memory Management 139

9.1	Introduction 139
9.2	Types Of Memory 139
9.3	Definition Of A Heavyweight Process 140
9.4	Memory Management In A Small Embedded System 141
9.5	Program Segments And Regions Of Memory 142
9.6	Dynamic Memory Allocation In An Embedded System 143
9.7	Design Of The Low-Level Memory Manager 144
9.8	Allocation Strategy And Memory Persistence 144
9.9	Keeping Track Of Free Memory 145
9.10	Implementation Of Low-Level Memory Management 146
9.11	Allocating Heap Storage 148
9.12	Allocating Stack Storage 151
9.13	Releasing Heap And Stack Storage 153
9.14	Perspective 156
9.15	Summary 156
	Exercises 157

Chapter 10 High-Level Memory Management and Virtual Memory 159

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

Chapter 11 High-Level Message Passing 179

11.1	Introduction 179
11.2	Inter-Process Communication Ports 179
11.3	The Implementation Of Ports 180
11.4	Port Table Initialization 181
11.5	Port Creation 183
11.6	Sending A Message To A Port 184
11.7	Receiving A Message From A Port 186
11.8	Port Deletion And Reset 188
11.9	Perspective 191
11.10	Summary 191
	Exercises 191

Chapter 12 Interrupt Processing 195

12.1	Introduction 195
12.2	The Advantage Of Interrupts 196
12.3	Interrupt Dispatching 196
12.4	Vectored Interrupts 197
12.5	Assignment Of Interrupt Vector Numbers 197
12.6	Interrupt Hardware 198
12.7	IRQ Limits And Interrupt Multiplexing 199
12.8	Interrupt Software And Dispatching 199
12.9	The Lowest Level Of The Interrupt Dispatcher 202
12.10	The High-Level Interrupt Dispatcher 204
12.11	Disabling Interrupts 208
12.12	Constraints On Functions That Interrupt Code Invokes 208
12.13	The Need To Reschedule During An Interrupt 209
12.14	Rescheduling During An Interrupt 210
12.15	Perspective 211
12.16	Summary 211
	Exercises 212

Chapter 13 Real-Time Clock Management 215

13.1	Introduction 215
13.2	Timed Events 216
13.3	Real-Time Clocks And Timer Hardware 216
13.4	Handling Real-Time Clock Interrupts 217
13.5	Delay And Preemption 218
13.6	Emulating A Real-Time Clock With A Timer 219
13.7	Implementation Of Preemption 219
13.8	Efficient Management Of Delay With A Delta List 220
13.9	Delta List Implementation 221
13.10	Putting A Process To Sleep 223
13.11	Timed Message Reception 226
13.12	Awakening Sleeping Processes 230
13.13	Clock Interrupt Processing 231
13.14	Clock Initialization 232
13.15	Interval Timer Management 233
13.16	Perspective 235
13.17	Summary 235
	Exercises 235

Chapter 14 Device\-Independent Input and Output 239

14.1	Introduction 239
14.2	Conceptual Organization Of I/O And Device Drivers 240
14.3	Interface And Driver Abstractions 241
14.4	An Example I/O Interface 242
14.5	The Open-Read-Write-Close Paradigm 243
14.6	Bindings For I/O Operations And Device Names 244
14.7	Device Names In Xinu 245
14.8	The Concept Of A Device Switch Table 245
14.9	Multiple Copies Of A Device And Shared Drivers 246
14.10	The Implementation Of High-Level I/O Operations 249
14.11	Other High-Level I/O Functions 251
14.12	Open, Close, And Reference Counting 255
14.13	Null And Error Entries In Devtab 257
14.14	Initialization Of The I/O System 258
14.15	Perspective 262
14.16	Summary 263
	Exercises 263

Chapter 15 An Example Device Driver 267

15.1	Introduction 267
15.2	The Tty Abstraction 267
15.3	Organization Of A Tty Device Driver 269
15.4	Request Queues And Buffers 270
15.5	Synchronization Of Upper Half And Lower Half 271
15.6	Hardware Buffers And Driver Design 272
15.7	Tty Control Block And Data Declarations 273
15.8	Minor Device Numbers 276
15.9	Upper\-Half Tty Character Input (ttyGetc) 277
15.10	Generalized Upper\-Half Tty Input (ttyRead) 278
15.11	Upper\-Half Tty Character Output (ttyPutc) 280
15.12	Starting Output (ttyKickOut) 281
15.13	Upper\-Half Tty Multiple Character Output (ttyWrite) 282
15.14	Lower\-Half Tty Driver Function (ttyInterrupt) 283
15.15	Output Interrupt Processing (ttyInter_out) 286
15.16	Tty Input Processing (ttyInter_in) 288
	15.16.1	Raw Mode Processing 294
	15.16.2	Cbreak Mode Processing 294
	15.16.3	Cooked Mode Processing 295
15.17	Tty Control Block Initialization (ttyInit) 295
15.18	Device Driver Control 297
15.19	Perspective 299
15.20	Summary 300
	Exercises 300

Chapter 16 DMA Devices And Drivers (Ethernet) 303

16.1	Introduction 303
16.2	Direct Memory Access And Buffers 303
16.3	Multiple Buffers And Rings 304
16.4	An Example Ethernet Driver Using DMA 305
16.5	Device Hardware Definitions And Constants 305
16.6	Rings And Buffers In Memory 309
16.7	Definitions Of An Ethernet Control Block 310
16.8	Device And Driver Initialization 313
16.9	Allocating An Input Buffer 318
16.10	Reading From An Ethernet Device 320
16.11	Writing To An Ethernet Device 322
16.12	Handling Interrupts From An Ethernet Device 324
16.13	Ethernet Control Functions 328
16.14	Perspective 330
16.15	Summary 330
	Exercises 331

Chapter 17 A Minimal Internet Protocol Stack 333

17.1	Introduction 333
17.2	Required Functionality 334
17.3	Simultaneous Conversations, Timeouts, And Processes 335
17.4	ARP Functions 336
17.5	Definition Of A Network Packet 346
17.6	The Network Input Process 347
17.7	Definition Of The UDP Table 351
17.8	UDP Functions 352
17.9	Internet Control Message Protocol 362
17.10	Dynamic Host Configuration Protocol 363
17.11	Perspective 368
17.12	Summary 368
	Exercises 369

Chapter 18 A Remote Disk Driver 371

18.1	Introduction 371
18.2	The Disk Abstraction 371
18.3	Operations A Disk Driver Supports 372
18.4	Block Transfer And High-Level I/O Functions 372
18.5	A Remote Disk Paradigm 373
18.6	Semantics Of Disk Operations 374
18.7	Definition Of Driver Data Structures 375
18.8	Driver Initialization (rdsInit) 381
18.9	The Upper\-Half Open Function (rdsOpen) 384
18.10	The Remote Communication Function (rdscomm) 386
18.11	The Upper\-Half Write Function (rdsWrite) 389
18.12	The Upper\-Half Read Function (rdsRead) 391
18.13	Flushing Pending Requests 395
18.14	The Upper\-Half Control Function (rdsControl) 396
18.15	Allocating A Disk Buffer (rdsbufalloc) 399
18.16	The Upper\-Half Close Function (rdsClose) 400
18.17	The Lower\-Half Communication Process (rdsprocess) 402
18.18	Perspective 407
18.19	Summary 407
	Exercises 408

Chapter 19 File Systems 411

19.1	What Is A File System? 411
19.2	An Example Set Of File Operations 412
19.3	Design Of A Local File System 413
19.4	Data Structures For The Xinu File System 413
19.5	Implementation Of The Index Manager 415
19.6	Clearing An Index Block (lfibclear) 420
19.7	Retrieving An Index Block (lfibget) 420
19.8	Storing An Index Block (lfibput) 421
19.9	Allocating An Index Block From The Free List (lfiballoc) 423
19.10	Allocating A Data Block From The Free List (lfdballoc) 424
19.11	Using The Device-Independent I/O Functions For Files 426
19.12	File System Device Configuration And Function Names 426
19.13	The Local File System Open Function (lfsOpen) 427
19.14	Closing A File Pseudo-Device (lflClose) 435
19.15	Flushing Data To Disk (lfflush) 436
19.16	Bulk Transfer Functions For A File (lflWrite, lflRead) 437
19.17	Seeking To A New Position In the File (lflSeek) 439
19.18	Extracting One Byte From A File (lflGetc) 440
19.19	Changing One Byte In A File (lflPutc) 442
19.20	Loading An Index Block And A Data Block (lfsetup) 443
19.21	Master File System Device Initialization (lfsInit) 447
19.22	Pseudo-Device Initialization (lflInit) 448
19.23	File Truncation (lftruncate) 449
19.24	Initial File System Creation (lfscreate) 452
19.25	Perspective 454
19.26	Summary 455
	Exercises 455

Chapter 20 A Remote File Mechanism 459

20.1	Introduction 459
20.2	Remote File Access 459
20.3	Remote File Semantics 460
20.4	Remote File Design And Messages 460
20.5	Remote File Server Communication 468
20.6	Sending A Basic Message 470
20.7	Network Byte Order 472
20.8	A Remote File System Using A Device Paradigm 472
20.9	Opening A Remote File 474
20.10	Checking The File Mode 477
20.11	Closing A Remote File 478
20.12	Reading From A Remote File 479
20.13	Writing To A Remote File 482
20.14	Seek On A Remote File 485
20.15	Character I/O On A Remote File 486
20.16	Remote File System Control Functions 487
20.17	Initializing The Remote File Data Structure 491
20.18	Perspective 493
20.19	Summary 493
	Exercises 493

Chapter 21 A Syntactic Namespace 497

21.1	Introduction 497
21.2	Transparency And A Namespace Abstraction 497
21.3	Myriad Naming Schemes 498
	21.3.1	MS-DOS 499
	21.3.2	UNIX 499
	21.3.3	V System 499
	21.3.4	IBIS 499
21.4	Naming System Design Alternatives 500
21.5	A Syntactic Namespace 500
21.6	Patterns And Replacements 501
21.7	Prefix Patterns 501
21.8	Implementation Of A Namespace 502
21.9	Namespace Data Structures And Constants 502
21.10	Adding Mappings To The Namespace Prefix Table 503
21.11	Mapping Names With The Prefix Table 505
21.12	Opening A Named File 509
21.13	Namespace Initialization 510
21.14	Ordering Entries In The Prefix Table 513
21.15	Choosing A Logical Namespace 514
21.16	A Default Hierarchy And The Null Prefix 515
21.17	Additional Object Manipulation Functions 515
21.18	Advantages And Limits Of The Namespace Approach 516
21.19	Generalized Patterns 517
21.20	Perspective 518
21.21	Summary 518
	Exercises 519

Chapter 22 System Initialization 521

22.1	Introduction 521
22.2	Bootstrap: Starting From Scratch 521
22.3	Operating System Initialization 522
22.4	Booting An Alternative Image On The E2100L 523
22.5	Xinu Initialization 524
22.6	System Startup 527
22.7	Transforming A Program Into A Process 531
22.8	Perspective 532
22.9	Summary 532
	Exercises 532

Chapter 23 Exception Handling 535

23.1	Introduction 535
23.2	Exceptions, Traps, And Illegal Interrupts 535
23.3	Implementation Of Panic 536
23.4	Perspective 537
23.5	Summary 538
	Exercises 538

Chapter 24 System Configuration 541

24.1	Introduction 541
24.2	The Need For Multiple Configurations 541
24.3	Configuration In Xinu 542
24.4	Contents Of The Xinu Configuration File 543
	24.4.1	Section 1: Type Declarations 543
	24.4.2	Section 2: Device Specifications 544
	24.4.3	Automatically Generated Symbolic Constants 545
24.5	Computation Of Minor Device Numbers 545
24.6	Steps In Configuring A Xinu System 546
24.7	Perspective 547
24.8	Summary 547
	Exercises 547

Chapter 25 An Example User Interface: The Xinu Shell 549

25.1	Introduction 549
25.2	What Is A User Interface? 550
25.3	Commands And Design Principles 550
25.4	Design Decisions For A Simplified Shell 551
25.5	Shell Organization And Operation 551
25.6	The Definition Of Lexical Tokens 552
25.7	The Definition Of Command-Line Syntax 552
25.8	Implementation Of The Xinu Shell 553
25.9	Storage Of Tokens 555
25.10	Code For The Lexical Analyzer 556
25.11	The Heart Of The Command Interpreter 561
25.12	Command Name Lookup And Builtin Processing 569
25.13	Arguments Passed To Commands 570
25.14	Passing Arguments To A Non-Builtin Command 571
25.15	I/O Redirection 575
25.16	An Example Command Function (sleep) 575
25.17	Perspective 577
25.18	Summary 578
	Exercises 578

Appendix 1 Porting An Operating System 580

A1.1	Introduction 580
A1.2	Motivation: Evolving Hardware 581
A1.3	Steps Taken When Porting An Operating System 581
	A1.3.1	Learning About The Hardware And Compile 583
	A1.3.2	Cross Development 583
	A1.3.3	Calling Conventions 583
	A1.3.4	Bootstrap Mechanisms 584
	A1.3.5	Polled Output 584
	A1.3.6	Sequential Program Execution 584
	A1.3.7	Basic Memory Management 585
	A1.3.8	Process Creation And Context Switch 585
	A1.3.9	Synchronization And Other Process Management Functions 585
	A1.3.10	Interrupt Dispatching And Real-Time Clock 586
	A1.3.11	Tty Device Driver 586
	A1.3.12	Other I/O Software And Device Drivers 586
	A1.3.13	File System 587
	A1.3.14	Protocol Software 587
	A1.3.15	Shell And Applications 587
A1.4	Programming To Accommodate Change 587
A1.5	Summary 589

Appendix 2 Xinu Design Notes 590

A2.1	Introduction 590
A2.2	Overview 590
A2.3	Xinu Design Notes 591
A2.4	Xinu Implementation 592
A2.5	Major Concepts And Implementation 593

Table of Contents For Operating Systems Design: The Xinu Approach (Linksys Version)

Preface xix

About The Author xxiii

Chapter 1 Introduction and Overview 1

Chapter 2 Concurrent Execution And Operating System Services 11

Chapter 3 An Overview Of The Hardware and Run-Time Environment 31

Chapter 4 List and Queue Manipulation 49

Chapter 5 Scheduling and Context Switching 67

Chapter 6 More Process Management 89

Chapter 7 Coordination Of Concurrent Processes 111

Chapter 8 Message Passing 129

Chapter 9 Basic Memory Management 139

Chapter 10 High-Level Memory Management and Virtual Memory 159

Chapter 11 High-Level Message Passing 179

Chapter 12 Interrupt Processing 195

Chapter 13 Real-Time Clock Management 215

Chapter 14 Device\-Independent Input and Output 239

Chapter 15 An Example Device Driver 267

Chapter 16 DMA Devices And Drivers (Ethernet) 303

Chapter 17 A Minimal Internet Protocol Stack 333

Chapter 18 A Remote Disk Driver 371

Chapter 19 File Systems 411

Chapter 20 A Remote File Mechanism 459

Chapter 21 A Syntactic Namespace 497

Chapter 22 System Initialization 521

Chapter 23 Exception Handling 535

Chapter 24 System Configuration 541

Chapter 25 An Example User Interface: The Xinu Shell 549

Appendix 1 Porting An Operating System 580

Appendix 2 Xinu Design Notes 590

Index 596

Table of Contents For

Operating Systems Design: The Xinu Approach (Linksys Version)