计算机系统 集成方法 英文版PDF电子书下载

Chapter 1 Introduction 1

1.1 What Is Inside a Box? 2

1.2 Levels of Abstraction in a Computer System 2

1.3 The Role of the Operating System 5

1.4 What Is Happening Inside the Box? 8

1.4.1 Launching an Application on the Computer 10

1.5 Evolution of Computer Hardware 11

1.6 Evolution of Operating Systems 13

1.7 Roadmap of the Rest of the Book 14

Exercises 14

Bibliographic Notes and Further Reading 15

Chapter 2 Processor Architecture 18

2.1 What Is Involved in Processor Design? 19

2.2 How Do We Design an Instruction Set? 20

2.3 A Common High-Level Language Feature Set 21

2.4 Expressions and Assignment Statements 21

2.4.1 Where To Keep the Operands? 22

2.4.2 How Do We Specify a Memory Address in an Instruction? 26

2.4.3 How Wide Should Each Operand Be? 27

2.4.4 Endianness 30

2.4.5 Packing of Operands and Alignment of Word Operands 32

2.5 High-Level Data Abstractions 35

2.5.1 Structures 35

2.5.2 Arrays 35

2.6 Conditional Statements and Loops 37

2.6.1 If-Then-Else Statement 38

2.6.2 Switch Statement 40

2.6.3 Loop Statement 41

2.7 Checkpoint 42

2.8 Compiling Function Calls 42

2.8.1 State of the Caller 43

2.8.2 Remaining Chores with Procedure Calling 46

2.8.3 Software Convention 47

2.8.4 Activation Record 54

2.8.5 Recursion 54

2.8.6 Frame Pointer 55

2.9 Instruction-Set Architectural Choices 58

2.9.1 Additional Instructions 58

2.9.2 Additional Addressing Modes 58

2.9.3 Architecture Styles 59

2.9.4 Instruction Format 59

2.10 LC-2200 Instruction Set 62

2.10.1 Instruction Format 63

2.10.2 LC-2200 Register Set 65

2.11 Issues Influencing Processor Design 66

2.11.1 Instruction Set 66

2.11.2 Influence of Applications on Instruction Set Design 67

2.11.3 Other Issues Driving Processor Design 68

Summary 70

Exercises 70

Bibliographic Notes and Further Reading 74

Chapter 3 Processor Implementation 76

3.1 Architecture versus Implementation 76

3.2 What Is Involved in Processor Implementation? 77

3.3 Key Hardware Concepts 78

3.3.1 Circuits 78

3.3.2 Hardware Resources of the Datapath 79

3.3.3 Edge-Triggered Logic 80

3.3.4 Connecting the Datapath Elements 82

3.3.5 Toward Bus-Based Design 86

3.3.6 Finite State Machine(FSM) 89

3.4 Datapath Design 91

3.4.1 ISA and Datapath Width 93

3.4.2 Width of the Clock Pulse 94

3.4.3 Checkpoint 95

3.5 Control Unit Design 95

3.5.1 ROM Plus State Register 96

3.5.2 FETCH Macro State 99

3.5.3 DECODE Macro State 102

3.5.4 EXECUTE Macro State:ADD Instruction(Part of R-Type) 103

3.5.5 EXECUTE Macro State:NAND Instruction(Part of R-Type) 106

3.5.6 EXECUTE Macro State:JALR Instruction(Part of J-Type) 106

3.5.7 EXECUTE Macro State:LW Instruction(Part of I-Type) 108

3.5.8 EXECUTE Macro State:SW and ADDI Instructions(Part of I-Type) 111

3.5.9 EXECUTE Macro State:BEQ Instruction(Part of I-Type) 112

3.5.10 Engineering a Conditional Branch in the Microprogram 116

3.5.11 DECODE Macro State Revisited 116

3.6 Alternative Style of Control Unit Design 119

3.6.1 Microprogrammed Control 119

3.6.2 Hardwired Control 119

3.6.3 Choosing Between the Two Control Design Styles 121

Summary 122

Historical Perspective 122

Exercises 124

Bibliographic Notes and Further Reading 128

Chapter 4 Interrupts,Traps,and Exceptions 129

4.1 Discontinuities in Program Execution 130

4.2 Dealing with Program Discontinuities 132

4.3 Architectural Enhancements to Handle Program Discontinuities 135

4.3.1 Modifications to FSM 136

4.3.2 A Simple Interrupt Handler 137

4.3.3 Handling Cascaded Interrupts 138

4.3.4 Returning from the Handler 141

4.3.5 Checkpoint 143

4.4 Hardware Details for Handling Program Discontinuities 143

4.4.1 Datapath Details for Interrupts 143

4.4.2 Details of Receiving the Address of the Handler 146

4.4.3 Stack for Saving/Restoring 147

4.5 Putting It All Together 149

4.5.1 Summary of Architectural/Hardware Enhancements 149

4.5.2 Interrupt Mechanism at Work 150

Summary 152

Exercises 154

Bibliographic Notes and Further Reading 155

Chapter 5 Processor Performance and Pipelined Processor Design 156

5.1 Space and Time Metrics 156

5.2 Instruction Frequency 160

5.3 Benchmarks 161

5.4 Increasing the Processor Performance 165

5.5 Speedup 167

5.6 Increasing the Throughput of the Processor 171

5.7 Introduction to Pipelining 171

5.8 Toward an Instruction-Processing Assembly Line 172

5.9 Problems with a Simple-Minded Instruction Pipeline 175

5.10 Fixing the Problems with the Instruction Pipeline 176

5.11 Datapath Elements for the Instruction Pipeline 178

5.12 Pipeline-Conscious Architecture and Implementation 180

5.12.1 Anatomy of an Instruction Passage Through the Pipeline 181

5.12.2 Design of the Pipeline Registers 184

5.12.3 Implementation of the Stages 185

5.13 Hazards 185

5.13.1 Structural Hazard 186

5.13.2 Data Hazard 187

5.13.3 Control Hazard 200

5.13.4 Summary of Hazards 209

5.14 Dealing with Program Discontinuities in a Pipelined Processor 211

5.15 Advanced Topics in Processor Design 214

5.15.1 Instruction-Level Parallelism 214

5.15.2 Deeper Pipelines 215

5.15.3 Revisiting Program Discontinuities in the Presence of Out-Of-Order Processing 218

5.15.4 Managing Shared Resources 219

5.15.5 Power Consumption 221

5.15.6 Multicore Processor Design 221

5.15.7 Intel Core Microarchitecture:An Example Pipeline 222

Summary 225

Historical Perspective 225

Exercises 226

Bibliographic Notes and Further Reading 231

Chapter 6 Processor Scheduling 233

6.1 Introduction 233

6.2 Programs and Processes 235

6.3 Scheduling Environments 239

6.4 Scheduling Basics 242

6.5 Performance Metrics 245

6.6 Nonpreemptive Scheduling Algorithms 247

6.6.1 First-Come First-Served(FCFS) 247

6.6.2 Shortest Job First(SJF) 252

6.6.3 Priority 255

6.7 Preemptive Scheduling Algorithms 256

6.7.1 Round Robin Scheduler 259

6.8 Combining Priority and Preemption 264

6.9 Meta-Schedulers 264

6.10 Evaluation 265

6.11 Impact of Scheduling on Processor Architecture 267

Summary and a Look Ahead 268

Linux Scheduler—A Case Study 270

Historical Perspective 273

Exercises 275

Bibliographic Notes and Further Reading 276

Chapter 7 Memory Management Techniques 277

7.1 Functionalities Provided by a Memory Manager 278

7.2 Simple Schemes for Memory Management 280

7.3 Memory Allocation Schemes 285

7.3.1 Fixed-Size Partitions 286

7.3.2 Variable-Size Partitions 287

7.3.3 Compaction 289

7.4 Paged Virtual Memory 290

7.4.1 Page Table 293

7.4.2 Hardware for Paging 295

7.4.3 Page Table Setup 296

7.4.4 Relative Sizes of Virtual and Physical Memories 296

7.5 Segmented Virtual Memory 297

7.5.1 Hardware for Segmentation 303

7.6 Paging versus Segmentation 303

7.6.1 Interpreting the CPU-Generated Address 306

Summary 308

Historical Perspective 309

MULTICS 311

Intel's Memory Architecture 312

Exercises 314

Bibliographic Notes and Further Reading 315

Chapter 8 Details of Page-Based Memory Management 316

8.1 Demand Paging 316

8.1.1 Hardware for Demand Paging 317

8.1.2 Page Fault Handler 318

8.1.3 Data Structures for Demand-Paged Memory Management 318

8.1.4 Anatomy of a Page Fault 320

8.2 Interaction Between the Process Scheduler and Memory Manager 324

8.3 Page Replacement Policies 326

8.3.1 Belady's Min 326

8.3.2 Random Replacement 327

8.3.3 First In First Out(FIFO) 327

8.3.4 Least Recently Used(LRU) 329

8.3.5 Second Chance Page Replacement Algorithm 333

8.3.6 Review of Page Replacement Algorithms 336

8.4 Optimizing Memory Management 336

8.4.1 Pool of Free Page Frames 336

8.4.2 Thrashing 338

8.4.3 Working Set 340

8.4.4 Controlling Thrashing 341

8.5 Other Considerations 343

8.6 Translation Lookaside Buffer(TLB) 343

8.6.1 Address Translation with TLB 344

8.7 Advanced Topics in Memory Management 346

8.7.1 Multi-Level Page Tables 346

8.7.2 Access Rights As Part of the Page Table Entry 348

8.7.3 Inverted Page Tables 349

Summary 349

Exercises 350

Bibliographic Notes and Further Reading 352

Chapter 9 Memory Hierarchy 353

9.1 The Concept of a Cache 354

9.2 Principle of Locality 355

9.3 Basic Terminologies 355

9.4 Multilevel Memory Hierarchy 357

9.5 Cache Organization 360

9.6 Direct-Mapped Cache Organization 360

9.6.1 Cache Lookup 363

9.6.2 Fields of a Cache Entry 365

9.6.3 Hardware for a Direct-Mapped Cache 366

9.7 Repercussion on Pipelined Processor Design 369

9.8 Cache Read/Write Algorithms 370

9.8.1 Read Access to the Cache from the CPU 370

9.8.2 Write Access to the Cache from the CPU 370

9.9 Dealing with Cache Misses in the Processor Pipeline 375

9.9.1 Effect of Memory Stalls Due to Cache Misses on Pipeline Performance 376

9.10 Exploiting Spatial Locality to Improve Cache Performance 377

9.10.1 Performance Implications of Increased Block Size 383

9.11 Flexible Placement 384

9.11.1 Fully Associative Cache 385

9.11.2 Set Associative Cache 387

9.11.3 Extremes of Set Associativity 387

9.12 Instruction and Data Caches 392

9.13 Reducing Miss Penalty 393

9.14 Cache Replacement Policy 394

9.15 Recapping Types of Misses 396

9.16 Integrating TLB and Caches 399

9.17 Cache Controller 400

9.18 Virtually Indexed Physically Tagged Cache 401

9.19 Recap of Cache Design Considerations 404

9.20 Main Memory Design Considerations 405

9.20.1 Simple Main Memory 405

9.20.2 Main Memory and Bus to Match Cache Block Size 406

9.20.3 Interleaved Memory 407

9.21 Elements of Modern Main Memory Systems 408

9.21.1 Page Mode DRAM 413

9.22 Performance Implications of Memory Hierarchy 415

Summary 416

Memory Hierarchy of Modern Processors—An Example 418

Exercises 419

Bibliographic Notes and Further Reading 422

Chapter 10 Input/Output and Stable Storage 423

10.1 Communication Between the CPU and the I/O Devices 423

10.1.1 Device Controller 424

10.1.2 Memory Mapped I/O 425

10.2 Programmed I/O 427

10.3 DMA 429

10.4 Buses 432

10.5 I/O Processor 433

10.6 Device Driver 434

10.6.1 An Example 436

10.7 Peripheral Devices 438

10.8 Disk Storage 440

10.8.1 The Saga of Disk Technology 448

10.9 Disk Scheduling Algorithms 451

10.9.1 First-Come-First-Served(FCFS) 453

10.9.2 Shortest SeekTime First(SSTF) 453

10.9.3 SCAN(Elevator Algorithm) 453

10.9.4 C-SCAN(Circular Scan) 455

10.9.5 LOOK and C-LOOK 455

10.9.6 Disk Scheduling Summary 457

10.9.7 Comparison of the Algorithms 458

10.10 Solid State Drive 459

10.11 Evolution of I/O Buses and Device Drivers 461

10.11.1 Dynamic Loading of Device Drivers 463

10.11.2 Putting it All Together 463

Summary 466

Exercises 466

Bibliographic Notes and Further Reading 468

Chapter 11 File System 469

11.1 Attributes 469

11.2 Design Choices in Implementing a File System on a Disk Subsystem 476

11.2.1 Contiguous Allocation 477

11.2.2 Contiguous Allocation with Overflow Area 480

11.2.3 Linked Allocation 480

11.2.4 File Allocation Table(FAT) 481

11.2.5 Indexed Allocation 483

11.2.6 Multilevel Indexed Allocation 485

11.2.7 Hybrid Indexed Allocation 486

11.2.8 Comparison of the Allocation Strategies 490

11.3 Putting It All Together 491

11.3.1 i-node 497

11.4 Components of the File System 498

11.4.1 Anatomy of Creating and Writing Files 499

11.5 Interaction Among the Various Subsystems 500

11.6 Layout of the File System on the Physical Media 503

11.6.1 In Memory Data Structures 507

11.7 Dealing with System Crashes 508

11.8 File Systems for Other Physical Media 508

11.9 A Glimpse of Modern File Systems 509

11.9.1 Linux 509

11.9.2 Microsoft Windows 515

Summary 517

Exercises 518

Bibliographic Notes and Further Reading 520

Chapter 12 Multithreaded Programming and Multiprocessors 521

12.1 Why Multithreading? 522

12.2 Programming Support for Threads 523

12.2.1 Thread Creation and Termination 523

12.2.2 Communication Among Threads 526

12.2.3 Read-Write Conflict,Race Condition,and Nondeterminism 528

12.2.4 Synchronization Among Threads 533

12.2.5 Internal Representation of Data Types Provided by the Threads Library 540

12.2.6 Simple Programming Examples 541

12.2.7 Deadlocks and Livelocks 546

12.2.8 Condition Variables 548

12.2.9 A Complete Solution for the Video Processing Example 553

12.2.10 Discussion of the Solution 554

12.2.11 Rechecking the Predicate 556

12.3 Summary of Thread Function Calls and Threaded Programming Concepts 559

12.4 Points to Remember in Programming with Threads 561

12.5 Using Threads as Software Structuring Abstraction 561

12.6 POSIX pthreads Library Calls Summary 562

12.7 OS Support for Threads 565

12.7.1 User Level Threads 567

12.7.2 Kernel-Level Threads 570

12.7.3 Solaris Threads:An Example of Kernel-Level Threads 572

12.7.4 Threads and Libraries 573

12.8 Hardware Support for Multithreading in a Uniprocessor 574

12.8.1 Thread Creation,Termination,and Communication Among Threads 574

12.8.2 Inter-Thread Synchronization 575

12.8.3 An Atomic Test-and-Set Instruction 575

12.8.4 Lock Algorithm with Test-and-Set Instruction 577

12.9 Multiprocessors 578

12.9.1 Page Tables 579

12.9.2 Memory Hierarchy 580

12.9.3 Ensuring Atomicity 582

12.10 Advanced Topics 583

12.10.1 OS Topics 583

12.10.2 Architecture Topics 596

12.10.3 The Road Ahead:Multicore and Many-Core Architectures 610

Summary 612

Historical Perspective 612

Exercises 614

Bibliographic Notes and Further Reading 617

Chapter 13 Fundamentals of Networking and Network Protocols 620

13.1 Preliminaries 620

13.2 Basic Terminologies 621

13.3 Networking Software 626

13.4 Protocol Stack 628

13.4.1 Internet Protocol Stack 628

13.4.2 OSI Model 631

13.4.3 Practical Issues with Layering 632

13.5 Application Layer 632

13.6 Transport Layer 634

13.6.1 Stop-and-Wait Protocols 636

13.6.2 Pipelined Protocols 640

13.6.3 Reliable Pipelined Protocol 642

13.6.4 Dealing with Transmission Errors 647

13.6.5 Transport Protocols on the Internet 648

13.6.6 Transport Layer Summary 651

13.7 Network Layer 652

13.7.1 Routing Algorithms 653

13.7.2 Internet Addressing 658

13.7.3 Network Service Model 663

13.7.4 Network Routing versus Forwarding 668

13.7.5 Network Layer Summary 668

13.8 Link Layer and Local Area Networks 670

13.8.1 Ethernet 670

13.8.2 CSMA/CD 671

13.8.3 IEEE 802.3 673

13.8.4 Wireless LAN and IEEE 802.11 674

13.8.5 Token Ring 675

13.8.6 Other Link-Layer Protocols 676

13.9 Networking Hardware 678

13.10 Relationship Between the Layers of the Protocol Stack 683

13.11 Data Structures for Packet Transmission 685

13.11.1 TCP/IP Header 687

13.12 Message Transmission Time 688

13.13 Summary of Protocol-Layer Functionalities 694

13.14 Networking Software and the Operating System 695

13.14.1 Socket Library 695

13.14.2 Implementation of the Protocol Stack in the Operating System 697

13.14.3 Network Device Driver 697

13.15 Network Programming Using UNIX Sockets 699

13.16 Network Services and Higher-Level Protocols 706

Summary 708

Historical Perspective 709

From Telephony to Computer Networking 709

Evolution of the Internet 712

PC and the Arrival of LAN 713

Evolution of LAN 713

Exercises 715

Bibliographic Notes and Further Reading 718

Chapter 14 Epilogue:A Look Back at the Journey 720

14.1 Processor Design 720

14.2 Process 720

14.3 Virtual Memory System and Memory Management 721

14.4 Memory Hierarchy 722

14.5 ParallelSystem 722

14.6 Input/Output Systems 722

14.7 Persistent Storage 723

14.8 Network 723

Concluding Remarks 723

Appendix:Network Programming with UNIX Sockets 724

Bibliography 736