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