4.4BSD操作系統(tǒng)設(shè)計與實現(xiàn)：英文版

Part 1　Overview　1
Chapter 1　History and Goals　3
1.1　History of the UNIX System　3
·Origins　3
·Research UNIX　4
·AT&T UNIX System Ⅲ and System V　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
2.5　Memory Management　29
·BSD Memory-Management Design Decisions　29
·Memory Management Inside the Kernel　31
2.6　I/O System　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
·Reference　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
·Return from the Kernel　53
3.2　System Calls　53
·Result Handing　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
3.6　Timing Services　63
·Real Time　63
·Adjustment of the Time　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
3.9　System-Operation Services　71
·Accounting　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
4.3　Context Switching　87
·Process State　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
·Working-Set Model　121
·Swapping　121
·Advantages of Virtual Memory　122
·Hardware Requirements for Virtual Memory　122
5.2　Overview of the 4.4 BSD Virtual-Memory System　123
5.3　Kernel 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
·Objects to Pages　137
5.5　Shared Memory　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
5.8　Process Manipulation of Its Address Space　151
·Change of Process Size　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 of the pmap 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
·Device Drivers　195
·I/O Queuing　195
·Interrupt Handing　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 of a 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 Filesytems　241
7.1　Hierarchical Filesystem Management　241
7.2　Structure of an Inode　243
·Inode Management　245
7.3　Naming　247
·Directories　247
·Finding of Names in Directories　249
·Pathname Translation　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
8.2　The Berkeley Fast Filesystem　269
·Organization of 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-Structure 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 Handing　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 Group, 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 Disciplines　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
12.2　Socket-to-Protocol Interface　405
·Protocol User-Request Routine　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
·Out-of-Band Data　430
·Address Resolution Protocol　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
·Timers　459
·Estimation of Round-Trip Time　460
·Connection Establishment　461
·Connection Shutdown　463
13.6　TCP Input 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
14.2　Bootstrapping　492
·The Boot Program　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
14.6　User-Level Initialization　505
·/sbin/init　505
·/etc/rc　505
·/usr/libexec/getty　506
·/usr/bin/login　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