4.4BSD操作系统设计与实现 英文版PDF电子书下载

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