Part 1 Overview 1
Chapter 1 History and Goals 3
1.1 History ofthe UNIX System 3
Origins 3
Research UNIX 4
AT＆T UNIX System Ⅲ and System Ⅴ 7
Other Organizations 8
Berkeley Software Distributions 8
UNIX in the World 10
1.2 BSD and Other Systems 10
The Influence of the User Community 11
1.3 Design Goals of 4BSD 12
4.2BSD Design Goals 13
4.3BSD Design Goals 14
4.4BSD Design Goals 15
1.4 Release Engineering 16
References 17
Chapter 2 Design Overview of 4.4BSD 21
2.1 4.4BSD Facilities and the Kernel 21
The Kernel 22
2.2 Kernel Organization 23
2.3 Kernel Services 25
2.4 Process Management 26
Signals 27
Process Groups and Sessions 28
BSD Memory-Management Design Decisions 29
2.5 Memory Management 29
Memory Management Inside the Kernel 31
2.6 I/OSystem 31
Descriptors and I/O 32
Descriptor Management 33
Devices 34
Socket IPC 35
Scatter/Gather I/O 35
Multiple Filesystem Support 36
2.7 Filesystems 36
2.8 Filestores 40
2.9 Network Filesystem 41
2.10 Terminals 42
2.11 Interprocess Communication 43
2.12 Network Communication 44
2.13 Network Implementation 44
2.14 System Operation 45
Exercises 45
References 46
Chapter 3 Kernel Services 49
3.1 Kernel Organization 49
System Processes 49
System Entry 50
Run-Time Organization 50
Entry to the Kernel 52
3.2 System Calls 53
Return from the Kernel 53
Result Handling 54
Returning from a System Call 54
3.3 Traps and Interrupts 55
Traps 55
I/O Device Interrupts 55
Software Interrupts 56
3.4 Clock Interrupts 57
Statistics and Process Scheduling 58
Timeouts 58
3.5 Memory-Management Services 60
Adjustment of the Time 63
RealTime 63
3.6 Timing Services 63
External Representation 64
Interval Time 64
3.7 User,Group,and Other Identifiers 65
Host Identifiers 67
Process Groups and Sessions 68
3.8 Resource Services 68
Process Priorities 69
Resource Utilization 69
Resource Limits 70
Filesystem Quotas 70
Accounting 71
3.9 System-Operation Services 71
Exercises 72
References 73
Part 2 Processes 75
Chapter 4 Process Management 77
4.1 Introduction to Process Management 77
Multiprogramming 78
Scheduling 79
4.2 Process State 80
The Process Structure 81
The User Structure 85
Process State 87
4.3 Context Switching 87
Low-Level Context Switching 88
Voluntary Context Switching 88
Synchronization 91
4.4 Process Scheduling 92
Calculations of Process Priority 93
Process-Priority Routines 95
Process Run Queues and Context Switching 96
4.5 Process Creation 98
4.6 Process Termination 99
4.7 Signals 100
Comparison with POSIX Signals 103
Posting of a Signal 104
Delivering a Signal 106
4.8 Process Groups and Sessions 107
Sessions 109
Job Control 110
4.9 Process Debugging 112
Exercises 114
References 116
Chapter 5 Memory Management 117
5.1 Terminology 117
Processes and Memory 118
Paging 119
Replacement Algorithms 120
Swapping 121
Working-Set Model 121
Advantages of Virtual Memory 122
Hardware Requirements for Virtual Memory 122
5.2 Overview of the 4.4BSD Virtual-Memory System 123
5.3 Kemel Memory Management 126
Kernel Maps and Submaps 127
Kernel Address-Space Allocation 128
Kernel Malloc 129
5.4 Per-Process Resources 132
4.4BSD Process Virtual-Address Space 132
Page-Fault Dispatch 134
Mapping to Objects 134
Objects 136
5.5 Shared Memory 137
Objects to Pages 137
Mmap Model 139
Shared Mapping 141
Private Mapping 142
Collapsing of Shadow Chains 144
Private Snapshots 145
5.6 Creation of a New Process 146
Reserving Kernel Resources 147
Duplication of the User Address Space 148
Creation of a New Process Without Copying 149
5.7 Execution of a File 150
Change of Process Size 151
5.8 Process Manipulation of Its Address Space 151
File Mapping 152
Change of Protection 154
5.9 Termination of a Process 154
5.10 The Pager Interface 156
Vnode Pager 157
Device Pager 159
Swap Pager 160
5.11 Paging 162
5.12 Page Replacement 166
Paging Parameters 168
The Pageout Daemon 169
Swapping 171
The Swap-In Process 172
5.13 Portability 173
The Role ofthepmap Module 176
Initialization and Startup 179
Mapping Allocation and Deallocation 181
Change of Access and Wiring Attributes for Mappings 184
Management of Page-Usage Information 185
Initialization of Physical Pages 186
Management of Internal Data Structures 186
Exercises 187
References 188
Part 3 I/O System 191
Chapter 6 I/O System Overview 193
6.1 I/O Mapping from User to Device 193
I/O Queueing 195
Device Drivers 195
Interrupt Handling 196
6.2 Block Devices 196
Entry Points for Block-Device Drivers 197
Sorting of Disk I/O Requests 198
Disk Labels 199
6.3 Character Devices 200
Raw Devices and Physical I/O 201
Character-Oriented Devices 202
Entry Points for Character-Device Drivers 203
6.4 Descriptor Management and Services 205
Open File Entries 205
Management of Descriptors 207
File-Descriptor Locking 209
Multiplexing I/O on Descriptors 211
Implementation of Select 213
Movement of Data Inside the Kernel 216
6.5 The Virtual-Filesystem Interface 218
Contents ofa Vnode 219
Vnode Operations 220
Pathname Translation 222
Exported Filesystem Services 222
6.6 Filesystem-Independent Services 223
The Name Cache 225
Buffer Management 226
Implementation of Buffer Management 229
6.7 Stackable Filesystems 231
Simple Filesystem Layers 234
The Union Mount Filesystem 235
Other Filesystems 237
Exercises 238
References 240
Chapter 7 Local Filesysterms 241
7.1 Hierarchical Filesystem Management 241
7.2 Structure of an Inode 243
Inode Management 245
7.3 Naming 247
Directories 247
Pathname Translation 249
Finding of Names in Directories 249
Links 251
7.4 Quotas 253
7.5 File Locking 257
7.6 Other Filesystem Semantics 262
Large File Sizes 262
File Flags 263
Exercises 264
References 264
Chapter 8 Local Filestores 265
8.1 Overview of the Filestore 265
Organization of the Berkeley Fast Filesystem 269
8.2 The Berkeley Fast Filesystem 269
Optimization of Storage Utilization 271
Reading and Writing to a File 273
Filesystem Parameterization 275
Layout Policies 276
Allocation Mechanisms 277
Block Clustering 281
Synchronous Operations 284
8.3 The Log-Structured Filesystem 285
Organization of the Log-Structured Filesystem 286
Index File 288
Reading of the Log 290
Writing to the Log 291
Block Accounting 292
The Buffer Cache 294
Directory Operations 295
Creation of a File 296
Reading and Writing to a File 297
Filesystem Cleaning 297
Filesystem Parameterization 300
Filesystem-Crash Recovery 300
8.4 The Memory-Based Filesystem 302
Organization of the Memory-Based Filesystem 303
Filesystem Performance 305
Future Work 305
Exercises 306
References 307
Chapter 9 The Network Filesystem 311
9.1 History and Overview 311
9.2 NFS Structure and Operation 314
The NFS Protocol 316
The 4.4BSD NFS Implementation 318
Client-Server Interactions 321
RPC Transport Issues 322
Security Issues 324
9.3 Techniques for Improving Performance 325
Leases 328
Crash Recovery 332
Exercises 333
References 334
Chapter 10 Terminal Handling 337
10.1 Terminal-Processing Modes 338
10.2 Line Disciplines 339
10.3 User Interface 340
10.4 The tty Structure 342
10.5 Process Groups,Sessions,and Terminal Control 343
10.6 C-lists 344
10.7 RS-232 and Modem Control 346
10.8 Terminal Operations 347
Open 347
Output Line Discipline 347
Output Top Half 349
Output Bottom Half 350
Input Bottom Half 351
Input Top Half 352
The stop Routine 353
The ioctl Routine 353
Modem Transitions 354
Closing of Terminal Devices 355
10.9 Other Line Disciplines 355
Serial Line IP Discipline 356
Graphics Tablet Discipline 356
Exercises 357
References 357
Part 4 Interprocess Communication 359
Chapter 11 Interprocess Communication 361
11.1 Interprocess-Communication Model 362
Use of Sockets 364
11.2 Implementation Structure and Overview 368
11.3 Memory Management 369
Mbufs 369
Storage-Management Algorithms 372
Mbuf Utility Routines 373
11.4 Data Structures 374
Communication Domains 375
Sockets 376
Socket Addresses 378
11.5 Connection Setup 380
11.6 Data Transfer 382
Transmitting Data 383
Receiving Data 385
Passing Access Rights 388
Passing Access Rights in the Local Domain 389
11.7 Socket Shutdown 390
Exercises 391
References 393
Chapter 12 Network Communication 395
12.1 Internal Structure 396
Data Flow 397
Communication Protocols 398
Network Interfaces 400
Protocol User-Request Routine 405
12.2 Socket-to-Protocol Interface 405
Internal Requests 409
Protocol Control-Output Routine 409
12.3 Protocol-Protocol Interface 410
pr_output 411
pr_input 411
pr_ctlinput 411
12.4 Interface between Protocol and Network Interface 412
Packet Transmission 412
Packet Reception 413
12.5 Routing 416
Kernel Routing Tables 417
Routing Lookup 420
Routing Redirects 423
Routing-Table Interface 424
User-Level Routing Policies 425
User-Level Routing Interface:Routing Socket 425
12.6 Buffering and Congestion Control 426
Protocol Buffering Policies 427
Queue Limiting 427
12.7 Raw Sockets 428
Control Blocks 428
Input Processing 429
Output Processing 429
12.8 Additional Network-Subsystem Topics 429
Address Resolution Protocol 430
Out-of-Band Data 430
Exercises 432
References 433
Chapter 13 Network Protocols 435
13.1 Internet Network Protocols 436
Internet Addresses 437
Subnets 438
Broadcast Addresses 441
Internet Multicast 441
Internet Ports and Associations 442
Protocol Control Blocks 442
13.2 User Datagram Protocol(UDP) 443
Initialization 443
Output 444
Input 445
Control Operations 446
13.3 Internet Protocol(IP) 446
Output 447
Input 448
Forwarding 449
13.4 Transmission Control Protocol(TCP) 451
TCP Connection States 453
Sequence Variables 456
13.5 TCP Algorithms 457
Timers 459
Estimation of Round-Trip Time 460
Connection Establishment 461
Connection Shutdown 463
13.6 TCP Input Processing 464
13.7 TCP Output Processing 468
Sending of Data 468
Avoidance of the Silly-Window Syndrome 469
Avoidance of Small Packets 470
Delayed Acknowledgments and Window Updates 471
Retransmit State 472
Slow Start 472
Source-Quench Processing 474
Buffer and Window Sizing 474
Avoidance of Congestion with Slow Start 475
Fast Retransmission 476
13.8 Internet Control Message Protocol(ICMP) 477
13.9 OSI Implementation Issues 478
13.10 Summary of Networking and Interprocess Communication 480
Creation of a Communication Channel 481
Sending and Receiving of Data 482
Termination of Data Transmission or Reception 483
Exercises 484
References 486
Part 5 System Operation 489
Chapter 14 System Startup 491
14.1 Overview 491
The boot Program 492
14.2 Bootstrapping 492
14.3 Kernel Initialization 493
Assembly-Language Startup 494
Machine-Dependent Initialization 495
Message Buffer 495
System Data Structures 496
14.4 Autoconfiguration 496
Device Probing 498
Device Attachment 499
New Autoconfiguration Data Structures 499
New Autoconfiguration Functions 501
Device Naming 501
14.5 Machine-Independent Initialization 502
/etc/rc 505
14.6 User-Level Initialization 505
/sbin/init 505
/usr/libexec/getty 506
/usr/bin/Iogin 506
14.7 System-Startup Topics 507
Kernel Configuration 507
System Shutdown and Autoreboot 507
System Debugging 508
Passage of Information To and From the Kernel 509
Exercises 511
References 511
Glossary 513
Index 551