Table of Contents: Macintosh version of Operating System Design


Preface

Foreword To The First Edition

Chapter 1 Introduction and Overview

1.1 Operating Systems 1
1.2 Our Approach 2
1.3 What An Operating System Is Not 3
1.4 An Operating System Viewed From The Outside 4
1.4.1 The Xinu Small Machine Environment 4
1.4.2 Xinu Services 4
1.4.3 Concurrent Processing 6
1.4.4 The Distinction Between Programs And Processes 6
1.4.5 Process Exit 11
1.4.6 Shared Memory 12
1.4.7 Synchronization 13
1.4.8 Mutual Exclusion 15
1.5 An Operating System Viewed From The Inside 16
1.6 Summary 18
For Further Study 19
Exercises 19

Chapter 2 An Overview of the Machine and Run-Time Environment

2.1 The Machine 21
2.1.1 Physical Organization Of The Macintosh 22
2.1.2 Logical Organization Of The Macintosh 23
2.1.3 Registers In The MC68000 24
2.1.4 The Address Space 24
2.1.5 Processor Status Register 27
2.1.6 Vectored Interrupts 28
2.1.7 Exceptional Conditions 30
2.2 Bit-Mapped Screen Display 30
2.3 Windows 31
2.4 The Mouse Interface 32
2.5 Interrupts and Events 32
2.6 Disk Storage Organization 33
2.6.1 Disk Interface And Control Hardware 34
2.6.2 The Pieces Of Disk Hardware 35
2.7 The C Run-Time Environment 35
2.8 Summary 37
For Further Study 38
Exercises 38

Chapter 3 List and Queue Manipulation

3.1 Linked Lists Of Processes 41
3.2 Implementation Of The Q Structure 43
3.2.1 In-Line Q Functions 45
3.2.2 FIFO Queue Manipulation 45
3.3 Priority Queue Manipulation 47
3.4 List Initialization 49
3.5 Summary 51
For Further Study 51
Exercises 51

Chapter 4 Scheduling and Context Switching

4.1 The Process Table 53
4.2 Process States 56
4.3 Selecting A Ready Process 56
4.4 The Null Process 61
4.5 Making A Process Ready 61
4.6 Summary 63
For Further Study 63
Exercises 63

Chapter 5 More Process Management

5.1 Process Suspension And Resumption 65
5.1.1 Implementation Of Resume 66
5.1.2 The Return Values SYSERR And OK 68
5.2 System Calls 68
5.2.1 Implementation of Suspend 68
5.2.2 Suspending The Current Process 69
5.3 Process Termination 70
5.4 Kernel Declarations 72
5.5 Process Creation 74
5.6 Utility Procedures 77
5.7 Summary 80
For Further Study 80
Exercises 80

Chapter 6 Process Coordination

6.1 Low-Level Coordination Techniques 84
6.2 Implementation Of High-Level Coordination Primitives 84
6.2.1 Semaphore Data Structures 85
6.3 Semaphore Creation and Deletion 89
6.4 Summary 92
For Further Study 92
Exercises 92

Chapter 7 Memory Management

7.1 Memory Management On The Macintosh 96
7.2 Dynamic Memory Requirements In Xinu 96
7.3 Low-Level Memory Management Procedures 97
7.4 The Location Of Allocated Storage 98
7.5 The Implementation Of Xinu Memory Management 98
7.5.1 Allocating Heap Storage 99
7.5.2 Allocating Stack Storage 101
7.5.3 Releasing Storage 102
7.6 Summary 104
For Further Study 104
Exercises 105

Chapter 8 Interrupt Processing

8.1 Dispatching Interrupts 107
8.2 Interrupt Dispatchers 108
8.3 The Rules For Interrupt Processing 111
8.4 Rescheduling While Processing An Interrupt 112
8.5 Macintosh Interrupts And Hardware Events 113
8.6 Summary 114
For Further Study 114
Exercises 115

Chapter 9 Real-Time Clock Management

9.1 The Real-Time Clock Mechanism 117
9.2 Optimization Of Clock Interrupt Processing 118
9.3 The Use Of A Real-Time Clock 119
9.4 Delta List Processing 120
9.5 Putting A Process To Sleep 121
9.6 Delays Measured In Seconds 124
9.7 Awakening Sleeping Processes 125
9.8 Removing An Entry From The Clock Queue 126
9.9 Deferred Clock Processing 127
9.9.1 Procedures For Changing To And From Deferred Mode 127
9.10 Clock Interrupt Dispatching 129
9.11 Clock Initialization 131
9.12 Summary 133
For Further Study 133
Exercises 133

Chapter 10 Message Passing

10.1 Illustration Of Message Passing Using Xinu 136
10.2 Implementation Of Send 138
10.3 Implementation Of Receive 139
10.4 Summary 143
For Further Study 143
Exercises 143

Chapter 11 Process-Based Hardware Event Handling

11.1 Introduction 145
11.2 A Process To Handle Firmware Events 146
11.3 Mutual Exclusion In Event Handling 151
11.4 Invocation Of Eventd 152
11.5 Summary 153
For Further Study 153
Exercises 153

Chapter 12 Device Independent Input and Output

12.1 Properties Of The Input And Output Interface 156
12.2 Abstract Operations 156
12.3 Binding Abstract Operations To Real Devices 157
12.4 Binding I/O Calls To Device Drivers At Run-Time 157
12.5 The Implementation Of High-Level I/O Operations 161
12.6 Opening And Closing Devices 166
12.7 Null And Error Entries In Devtab 167
12.8 Initialization Of The I/O System 168
12.9 Summary 174
For Further Study 175
Exercises 175

Chapter 13 An Example Device Driver

13.1 The Device Type Con 177
13.2 Upper And Lower Halves Of The Device Driver 179
13.3 Synchronization Of The Upper And Lower Halves 180
13.4 Control Block And Buffer Declarations 180
13.5 Upper-Half Con Input Routines 184
13.6 Upper-Half Con Output Routines 188
13.7 Upper-Half Utility Routines 191
13.8 Lower-Half Con Driver Routine 193
13.9 Cooked Mode And Cbreak Mode Processing 198
13.10 Console Control Block Initialization 198
13.11 Device Driver Control 200
13.12 Opening The Console Device 202
13.13 Summary 203
For Further Study 203
Exercises 203

Chapter 14 Window Management Using Devices

14.1 Introduction 205
14.2 The Macintosh Window Paradigm 206
14.3 A Text Window Model 206
14.4 Windows As Devices 207
14.5 The Pseudo-Device Concept 207
14.6 The Master Window Pseudo-Device 207
14.7 Window Pseudo-Device 208
14.8 Window Device Control 214
14.9 Closing A Window Pseudo-Device 226
14.10 Initializing A Window Pseudo-Device 228
14.11 Window Master Pseudo-Device 229
14.12 Driver Configuration 237
14.13 Summary 237
For Further Study 238
Exercises 238

Chapter 15 System Initialization

15.1 Starting From Scratch 239
15.2 Booting Xinu 240
15.3 Operating System Startup 241
15.4 Initializing System Data Structures 241
15.5 Transforming The Program Into A Process 246
15.6 Macintosh-Dependent Initialization 246
15.7 Summary 253
For Further Study 253
Exercises 253

Chapter 16 High-Level Memory Management and Message Passing

16.1 Self-Initializing Modules 256
16.1.1 Specifying Initialization 256
16.1.2 Automatic Initialization 256
16.2 Memory Marking 257
16.3 Implementation Of Memory Marking 257
16.4 Partitioned Space Allocation 259
16.5 Buffer Pools 260
16.6 Returning Buffers To The Buffer Pool 263
16.7 Creating A Buffer Pool 264
16.8 Initializing The Buffer Pool Table 265
16.9 Communication Ports 266
16.10 The Implementation Of Ports 267
16.11 Other Operations On Ports 275
16.12 Summary 279
For Further Study 279
Exercises 279

Chapter 17 A Disk Driver

17.1 Operations Supplied By The Disk Driver 281
17.2 The List Of Pending Disk Requests 282
17.3 Enqueuing Disk Requests 284
17.4 Optimizing the Request Queue 287
17.5 The Block Copy Utility 289
17.6 Starting A Disk Operation 289
17.7 Driver Initialization 292
17.8 The Upper-Half Disk Read Routine 293
17.9 The Upper-Half Disk Output Routine 295
17.10 Implementation Of The Upper-Half Output Routine 297
17.11 The Lower-Half Of The Disk Driver 298
17.12 Flushing Pending Requests 299
17.13 Disk Ejection 302
17.14 Summary 303
For Further Study 304
Exercises 304

Chapter 18 File Systems

18.1 What Is A File System? 305
18.2 Layers Of The File System 306
18.3 Semantics Of File Manipulation 307
18.4 Disk And File Servers 308
18.5 Local File System Interface 308
18.6 Data Structures For The File System 309
18.7 The Directory Layer 310
18.8 A Macintosh File System Interface 311
18.9 Using The Device Switch Table For Files 311
18.10 Establishing A Pseudo-Device 313
18.10.1 The Pseudo-Device Seek Routine 317
18.10.2 The Pseudo-Device Read Routine 318
18.10.3 The Pseudo-Device Write Routine 319
18.10.4 The Pseudo-Device Getc Routine 320
18.10.5 The Pseudo-Device Putc Routine 320
18.10.6 The Pseudo-Device Close Routine 321
18.10.7 The Pseudo-Device Control Routine 322
18.10.8 The Pseudo-Device Initialization Routine 325
18.10.9 Lower-Half Routine For The Pseudo-Device 326
18.10.10 Firmware File Manipulation Interface 327
18.11 Summary 329
For Further Study 329
Exercises 330

Chapter 19 A Syntactic Namespace

19.1 Introduction 331
19.2 The Problem With File Names 332
19.2.1 MS-DOS 332
19.2.2 UNIX 332
19.2.3 V System 332
19.2.4 Newcastle Connection 333
19.2.5 IBIS 333
19.2.6 TILDE 333
19.3 Naming System Design Alternatives 333
19.4 A Syntactic Namespace 334
19.5 Patterns And Replacements 334
19.6 Prefix Patterns 334
19.7 Implementation Of A Simple Syntactic Namespace 335
19.7.1 The Pseudo-Device NAMESPACE 335
19.7.2 Definitions Of Data Structures And Constants 335
19.7.3 Adding Mappings To The Prefix Table 336
19.7.4 Removing A Name Mapping 338
19.7.5 Mapping Names With The Prefix Table 339
19.7.6 Iterative Resolution Of Recursive Mappings 341
19.7.7 Opening A Named File 342
19.7.8 Namespace Initialization 342
19.8 Choosing Initial Prefix Mappings 344
19.8.1 Default Hierarchy And The Null Prefix 344
19.8.2 A Common Name Syntax 345
19.9 Additional File Manipulation Commands 346
19.9.1 Removing A File 346
19.9.2 Renaming A File 347
19.9.3 Testing File Accessibility 348
19.10 Advantages Of The Namespace Approach 349
19.11 The Limits Of Fixed Prefix Patterns 350
19.12 Generalized Patterns 350
19.13 Configuring The Namespace Pseudo-Device 351
19.14 Summary 351
For Further Study 352
Exercises 352

Chapter 20 User Interface Design

20.1 Introduction 355
20.2 What Is A User Interface? 355
20.3 The Definition Of Goodness 356
20.4 What We Seek 356
20.5 Interface Hardware 357
20.5.1 Keyboard Input Hardware 357
20.5.2 Display Hardware 358
20.5.3 Pointing Device 359
20.6 The Two-Tier Interface Model 359
20.7 Syntactic Flexibility 360
20.8 Semantic Features And Issues 361
20.8.1 Command Set 361
20.8.2 Design Principles 361
20.8.3 Concurrent Processing 362
20.8.4 Interprocess Communication 362
20.8.5 I/O And File Specification 363
20.8.6 Response To Requests 363
20.9 Syntactic Features And Issues 363
20.9.1 Lexical Conventions And Quoting 364
20.9.2 Command History And Editing 364
20.9.3 Abbreviations And Command Aliases 364
20.9.4 Command Name Expansion 365
20.9.5 Typed Vs. Untyped Arguments 365
20.9.6 Programming Language Constructs 366
20.9.7 Windows 366
20.10 Modifying The Syntactic Interface 368
20.10.1 Parameterization Vs. Extensibility 368
20.10.2 Multiple Syntactic Interfaces 369
20.11 Summary 369
For Further Study 370
Exercises 370

Chapter 21 An Example User Interface: The Xinu Shell

21.1 Introduction 371
21.2 The Assumed Interface Hardware 371
21.3 A Basic Design Decision 372
21.4 Overview Of Shell Organization And Operation 372
21.4.1 Input Form 372
21.5 Imperative Vs. Interrogative Interaction Form 372
21.5.1 Processes Vs. Procedures 373
21.5.2 File Name Independence 373
21.6 Command Syntax 373
21.6.1 The Definition Of Lexical Tokens 373
21.6.2 Lexical Details and Quoting 374
21.6.3 The Definition Of Command-Line Syntax 375
21.7 Shell Semantics 376
21.8 Implementation Of The Example Shell 377
21.8.1 Shell Definitions 377
21.8.2 Declaration Of Commands 379
21.8.3 Dividing The Command Line Into Tokens 381
21.8.4 The Heart Of The Command Interpreter 384
21.8.5 Command Lookup And Invocation Of Builtins 389
21.8.6 I/O Redirection 390
21.8.7 Passing Arguments To The Command Process 391
21.8.8 Starting A Command In Background 394
21.8.9 Foreground And Background Processing 395
21.8.10 Moving A Command To Background 396
21.8.11 User Login 397
21.9 Summary 399
For Further Study 399
Exercises 400

Chapter 22 An Example Set Of Shell Commands

22.1 Introduction 403
22.2 Command And Procedure Names 403
22.2.1 Choosing Command Names 403
22.2.2 Choosing Procedure Names 404
22.3 Types Of Commands 404
22.4 Command Implementation 405
22.5 General Information Commands 405
22.5.1 Time And Date Command 405
22.5.2 Help Command 409
22.6 System Information Commands 410
22.6.1 Bpool Command 410
22.6.2 Devs Command 411
22.6.3 Mem Command 412
22.6.4 Ps Command 415
22.6.5 Who Command 417
22.7 Computational Commands 419
22.7.1 Cat Command 419
22.7.2 Close Command 421
22.7.3 Cp Command 422
22.7.4 Echo Command 423
22.7.5 Exit And Logout Commands 424
22.7.6 Kill Command 425
22.7.7 Mount Command 426
22.7.8 Mv Command 428
22.7.9 Rm Command 429
22.7.10 Shutdown Command 430
22.7.11 Sleep Command 431
22.7.12 Unmount Command 432
22.8 Summary 433
For Further Study 433
Exercises 433

Chapter 23 Exception Handling and Support Routines

23.1 Exceptions, Traps, And Illegal Interrupts 437
23.2 Interrupt Vector Initialization 438
23.3 Implementation Of Panic 441
23.4 Formatted Output 451
23.4.1 Printf And Fprintf 459
23.4.2 Kprintf 460
23.5 Summary 463
For Further Study 463
Exercises 463

Chapter 24 System Configuration

24.1 The Need For Multiple Configurations 465
24.2 Static vs. Dynamic Configuration 466
24.3 The Details Of Configuration In Xinu 466
24.3.1 Input To Config 470
24.3.2 Computation Of Minor Device Numbers 471
24.4 Configuring A Xinu System 472
24.4.1 Counting Devices 472
24.5 System Calls And Procedures 473
24.6 Summary 474
For Further Study 474
Exercises 474
Xinu Shell Commands 489
System Calls 521
Library Procedures 577
Device Descriptions 598

Index



Return to list of Comer's OS books



Return to Comer's homepage