计算机系统概论 英文版 作者: [美] Yale N. Patt>>second editionintroduction toComputing systemsfrom bils and gates to c and beyYalen. pattThe University of texas at austinSanjay J. PatelUniversity of Illinois at Urbana-ChampaignVcaHigher EducationBoston Burr Ridge, IL Dubuque, IA Madison, W New York San Francisco StouIsBangkok Bogota Caracas Kuala Lumpur Lisbon London Madrid Mexico CityMilan Montreal New Delhi Santiagogapore Sydney Taipei TorontoTo the memory of my parentsAbraham Walter Patt a"H and Sarah Clara patt a"Hwho taught me to value learningeven before they taught me to ride a bicycleTo Mira and her grandparentsSharda patel and jeram patecontentsPreface xi2.4.1 Binary to Decimal Conversion 27Preface to the first edition xvii2.4.2 Decimal to Binary Conversion 282.5 Operations on Bits-Part I: Arithmetic 292.5.1 Addition and subtraction 292.5.2 Sign-Extension 301 Welcome Aboard 15.3 Overfow 311.1 What We Will Try to do 12.6 Operations on Bits -Part II: Logical1.2 How We will get there 2Operations 33Two Recurring Themes 32.6.1 The AND Function 331.3.1 The Notion of abstraction 32.6.2 the oR Function 341.3.2 Hardware versus Software 52.6.3,. The NoT Function 351. 4 A Computer system2.6.4 The Exclusive-OR Tunction 351.5 Two Very Important Ideas 92.7 Other Representations 361.6 Computers as Universal Computational2.7.1 The bit vector 36Devices 92.7Floating Point Data Type 371.7 How Do we get the electrons to do lhe2.7.3 ASCIi Codes 40Wark? 122.7. 4 Hexadecimal Notation 411.7.1 The Statement of the problem 13Exercises 431.7.2 The Algorithm 131.7.3 The Program 141.7. 4 The isa 1 41.7.5 The Microarchitecture 153 Digital Logic Structures 517. 6 The Logic Circuit I3.1 The Transistor 511.7.7 The Devices 163.2 Lagic Gates 531.7.8 Putting It Together 163.2.1 The not Gate(InverterExercises 173.2.2 oR and Nor Gates 543.2.3 AND and MAND Gates 563.2.4 DeMorgan's Law 582 Bits, Data Types, and3.2.5 Larger Gates 583.3 Combinational Logic Circuits 59Operations 213.3.1 Decoder 592.1 Bits and Data Types 213.3.2Mux602.1.1 the Bit as the unit of3.3.3 Full Adder 61Information 2I3.3.4 The Programmable Logic Array2.1.2 Data T ypes 22(PLA 632.2 Integer Data Types 233,3.5 Logical Completeness 642.2.1 Unsigned Integers 233. 4 Basic Storage Elements 642.2.2 Signed Integers 233.4.1 The R-s Latch 642.3 25 Complement Integers 253.4,The gated d latch 662.4 Binary-Decimal Conversion 273. 4.3 A Register 66Contents3.5 The Concept of Memory 675.4 Control Instructions 1303.5. 1 Address space 685. 4.1 Conditional Branches 1313.5.2 Addressability 685.4.2 An Example 1323.5.3 A 2-by-3-Bit Memory 685.4.3 TwO Methods for Loop Control 1353.6 Sequential Logic Circuits 705. 4.4 Examplc: Adding a Column of3.6. 1 A Simple Example: The combinationNumbers Using a Sentinel 135Lock 715.4.5 The jMP Instruction 1363.6.2 The Concept of state 725.4.6 The TRAP Instruction 1373.6.3 Finite State Machines 745.5 Another Example: Counting Occurrences of3.6.4 An Example: The compietea character 138Implementation of a5. 6 the data p ath revisited 141Finite State Machine 775.6.1 Basic Components of the data3.7 The Data Path of the lC-3 80Path 141Exercises 825.6.2 The Instruction Cycle 144Exercises 1454 The von neumann Model 974.1 Basic Components 976 Programming 1554.1.1 Memory 986.1 Problem Solving 1556.1.1 Systematic Decomposition 1554. 1.2 Processing Unit 996.1.2 The Three Constructs: Stia4.1.3 Input and Output 100Conditional Iterative 1564.1.4 Controf init 1006.1.3 LC-3 Control Instructions to4.2 The LC-3: An Example von NeumannImplement the ThreeMachine 1014.3 Instruction Processing 103Constructs 1576.1.4 The Character Count Example from4.3.1 The Instruction 103Chapter 5, Revisited 1584.3.2 The Instruction Cycle 1044.4 Changing the Sequence of Execution 1076.2 Debugging 1626.2.1 Debugging Operati1634.4.1 Control of the instruction6.2.2 Examples: Use of the InteractiveCycle 108Debugger 164Slopping the Computer 110Exercises 172Exercises 1117 Assembly Language 1775 The lc-3 1157.1 Assembly Language programming-5.1 The ISA: Overview 115Moving Up a Level 1775.1.1 Memory Organization 1167. 2 An Assembly Language Program 1785.1.2 Registers 1167.2.1 Instructions 1795.1.3 The Instruction Set 1177.2.2 Pseudo-ops(Assembler5.1.40 codes117Directives) 1825.1.5 Data Types 1187.2.3 Example: The Character Count5.1.6 Addressing Modes 118Example of section 5.55.1.7 Condition codes 120Revisited 1835.2 Operate Instructions 1207. 3 The Assembly process 1855.3 Data Movement instructions 1237.3.1 Introduction 1855.31 PC-Relative Mode 1247.3. 2 A Two-Pass Process 1855.3.2 Indirect Mode 1257.3.3 The First Pass: Creating the Symbol5.3. 3 Base+offset Mode 127Table 1865.3. 4 Immediate Mode 1287.3.4 The Second Pass: generating the5.3.5 An Example 129Machine Language Program 187Contents7.4 Beyond the Assembly of a Single Assembly9.1.5 TRAP Routines for Handl ingLanguage Program 188/02257.4.1 The Executable Image 1899.1.6 TRAP Routine for halt ing the7. 4.2 More than one object File 189Computer 225Exercises 1909.1.7 Saving and RestoringRegisters 2299.2 Subroutines 2308I01999.2.1 The CallfReturn Mechanism 2309.2.2 The jsr(R) Instruction 2328.1 i/0 Basics 1998. 1.1 Device Registers 1999.2.3 The traP Routine for characterIt revisited 2338.1.2 Memory-Mapped 1/0 versus SpecialInput/Output Instructions 2009.2.4 PUTS: Writing a Character String tothe Monitor 2358.1.3 Asynchronous versus9.2.5 Library Routines 235Synchronous 200Exercises 2408.1.4 Interrupt- Driven versus Poll ing 2028.2 Input frorn the Keyboard 2028.2.1 Basic Input Registers (the Kbr andthe kbsrd 20210 And, Finally.. The Stack 2518.2.2 The Basic Input service10.1 The Stack: Its Basic Structure 251Routine 20210.1.1 The Stack- An Abstract Data8.2, 3 Implementation of Memory-MappedType 251Input 20310.1.2 Two Example Implementations 2528. 3 Output to the monitor 20410.1.3 Implermeritation in Memory 2538.3.1 Basic Output Registers(the DDR and10.1.4 The complete Picture 257the dsr) 20410.2 Interrupt-Driven 1/0( Part 2)2588.3.2 The Basic Output service10.2.1 Initiate and service theRoutine 205Interrupt 2598.3.3 Implementat ion of Memory-Mapped10.2.2 Return from the Interrupt 261Output 20610.2.3 An Example 2628.3.4 Example: Keyboard Echo 20710.3 Arithmetic Using a Stack 2648.4 A More Sophisticated Input Routine 20710.3.1 The Stack as Temporary8.5 Interrupt-Driven 1/0 209Storage 2648.5.1 What Is Interrupt-Driven 170? 20910.3.2 An Example 2658.5.2 Why Have Interrupt-Driven10.3.3 OpAdd op mult, and opNeg 265/0?21010.4 Data Type Conversion 2728.5.3 Generation of the Interrupt10.4.1 Example: The Bogus ProgramSignal 2112+3=e2728.6 Implementation of Memory-Mapped 1/010.4.2 ASCII to Binary 273Revisited 21410.4.3 Binary to asciI 276Eⅹ excises21510.5 Our Final Example: The Calculator 278Exercises 2839 TRAP Routines andSubroutines 21911 Introduction to Programming9.1C-3TRAP Routines 219in C 2899.1.1 Introduction 21911.1 Our Objective 2899.1.2 The traP Mechan ism 22011.2 Bridging the Gap 2909.1.3 The trap instruction 22111.3 Translating High-Level Language9.1.4 The Complete Mechanism 222Programs 292Contents11.3.1 Interpretation 29213 Control Structures 34311.3.2 Compi lation 29313.1 Introduction 34311, 3.3 Pros and cons 29313.2 Conditional Constructs 34411. 4 The c Programming Language 29313.2.1 The if statement 34411.4.1 The C compiler 29513.2.2 I he if-eise statement 34711.5 A Simple example 29713.3 Iteration Constructs 35011.5.1 The function main 29713.3.1 The while Statement 35011.5.2 Formatting, Comments, and13.3.2 The for statement 353Style 29913.3.3 The do-while statement 35811.5. 3 The C Preprocessor 30013.4 Problem Solving Using Contro11.5.4 Input and output 301Structures 35911.6 Summary 30413.4.1 Problem 1: Approximating the valueExercises 305fr36013.4.2 Problem 2: Finding Prime NumbersLess than 100 36212 Variables and operators 30713.4.3 Problem 3: Analyzing an E-mailAddress 36612.1 Introduction 30713.5 Additional C Control Structures 36812.2 Variables 30813.5.1 The switch Statement 36812.2.1 Three Basic Data Types: int char13.5.2 The break and continuedouble 308Statements 37012.2.2 Choosing Identifiers 31012.2.3 Scope: Local versus Global 31113.5.3 An Example: Sim pCalculator 37012.2.4 More Examples 31312.3 Operators 31413.6 Summary 372Exercises 37212.3.1 Expressions and statements 31512.3.2 The Assignment Operator 31612.3.3 Arithmetic Operators 31712.3.4 Order of Evaluation 31814 Functions 37912.3.5 Bitwise Operators 31914.1 Introduction 37912.3.6 Relational Operators 32014.2 Functions in C 38012.3.7 Logical Operators 32214.2.1 A Function with a Parametcr 380123. 8 ncrement/ decrement14.2.2 Example: Area of a ring 384Operators 32214.3 Implementing Functions in C 38512.3.9 Expressions with Multiple14.3.1 Run-Time stack 385Operators 32414.3.2 Getting It all to Work 38812.4 Problem Solving Using Operators 32414.3.3 Tying It All Together 39312.5 T ying it All Together 32614.4 Problem Solving using Functions 39412.5.1 Symbol Table 32614.4.1 Problem l: Case Conversion 39512.5.2 Allocating Space for variables 32814.4.2 Problem 2: Pythagorean12, 5.3 A Comprehensive Example 331Triples 39712. Additional Topics 33212.6.1 variations of the three basic14.5 Summary 398ypes212.6.2 Literals, Constants and Symbolic∨aues33412.6.3 Storaye class 33515 Testing and debugging 40712.6.4 Additional C Operators 33615.1 Introduction 40712. 7 Summary 3 3715. 2 Types of er408Eⅹ excises33815.2.1 Syntactic Errors 409Contents05.2.2 Semantic Errors 40917.5 Fibonacci numbers 46415.2.3 Algorithmic Errors 41117.6 Binary Search 46815.3 Testing 41217.7 Integer to ascii 47115.3.1 Black-Box Testing 41217. 8 Summary 47315.3.2 White-Box Testing 413Exercises 47315.4 Debugging 41415.4, 1 Ad Hoc Techniques 4145.4.2 Source-Level Debuggers 41518I0inC48115.5 Programming for Correctness 41718.1 Introduction 48115.5.1 Nailing Downl the18.2 The C standard Library 481Specification 41718. 3 I0, One Character at a time 48215.5.2 Modular Design 41818.3.11/0 Streams48215.5.3 Defensive Programming 41818.3.2 putchar 48315.6 Summary 41918.3.3 getchar 483Exercises 42118.3. 4 Buffered 1/0 48318.4 Formatted 1/0 4858.4.1 printf 48516 Pointers and Arrays 4278. 4.2 canf 48716.1 Introduction 42718.4.3 Variable Argument16.2 Pointers 428Lists 48916.2.1 Declaring Pointer Variables 42918.5 1/0 from Files 49116.2.2 Pointer Operators 43018.6 Summary 49316.2.3 Passing a reference UsingExercises 494Pointers 43216.24 Null Pointers 43316.2.5 Demystifying the Syntax 43416.2.6 An Example problem Involving19 Data Structures 497Pointers 43419.1 Introduction 49716.3 Arrays 43619.2 structures 49816.3.1 Declaring and Using19.2.1 typedef 500Arrays 43619.2.2 Implementing Structures16.3.2 Examples Using Arrays 438inc 50116.3.3 Arrays as Parameters 44019.3 Arrays of Structures 50216.3.4 Strings in C 44119.4 Dynamic Memory Allacation 5043.5 The Relationship Between Arrays and19.4.1 Dynamically sized Arrays 506Pointers in c 44619.5 Linked Lists 50816.3.6 Problem Solving Insertion19.5.1 An EXample 510Sort 44619.6 Summary 51616.3.7 Common Pitfalls with arraysExercises 517nC44916.4 Summary 451Exercises 451a The LC-3 Isa 521A1 Overview 52117 Recursion 457A2 Notation 52317.1 Introduction 457A. 3 The instruction Set 52317.2 What Is Recursion? 458A4 Interrupt and Exception Processing 54317.3 Recursion versus iteration 459A.4.1 Interrupts 54317. 4 Towers of hanoi 460A 4.2 Exceptions 544ContentsB From LC-3 to x86 547D4 Declarations 595B. 1 LC-3 Features and Corresponding x86D, 4.1 Variable declarations 595Features 548D 4.2 Function Declarations 596B.1.1 Instruction set 548D5 Operators 596B.1.2 Memo53D.5.1 Assignment Operators 597B. 1. 3 Internal State 553D.5.2 Arithmetic Operators 597B.2 The Format and Specification of x86D 5.3 Bit-wise Operators 598Instructions 557D5.4 Logical Operators 598B 2.1 Prefix 558D.5.5 Relational Operators 599B 2.2 Opcode 559D5.6 Increment/ DecrementB.2.3 ModR/M Byte 559Operat ors 599B 2. 4 SIB Byte 560D.5.7 Conditional Expression 600B.2.5 Displacement 560D.5.8 Pointer, Array and StructureB.2.6 Immediate 5600perators 600B3 An Example 562D.5.9 sizeof 601D510 Order of evaluation 602D511 Type Conversions 602C The Microarchitecture of theD 6 Expressions and Statements 603D.6.1 Expressi603LC-3565D6.2 Statements 604C1 Overview 565D7 Control 604C. 2 The State Machine 567D.71Tf604c. 3 The data Path 569D.72工f-e1se605C. 4 The Control structure 569D.7.3 Switch 605C5 Memory-Mapped 1/0 57D7. While 606C6 Interrupt and Exception Control 576D.75For607C.6.1 Initiating an Interrupt 579D.7.6Do-whi1e60了C.6.2 Returning from an InterruptD, 7.7 Break 608RTI 581ntinue 608C.6. 3 The Illegal Opcode Exception 582D79 return 6097 Control store 583D. 8 The C PrepD 8.1 Macro substitution 609D 8.2F10D The c programmingD.9 Some Standard Library Functions 610D.9.1 1/0 Functions 611Language 585D.9.2 STring Functions 612D1 Overview 585D93 Math functions 6D2 C Conventions 585D 9.4 Utility Functions 613D.2.1 Source Files 585D 2.2 Header Fiies 585D 2.3 Comments 586D.2. 4 Literals 586E Useful Tables 615D.7.5 Formatting 588E1 Commonly Used Numerical Prefxes 615D 2.6 Keywords 588E2 Standard Asc]i codes 616D3 Types 589E3 Powers of 2 617D 3.1 Basic Data Types 589D.3.2 Type Qualifiers 590D.3.3 Storage class 591F Solutions to SelectedD.3. Derived Types 592D3.5 typedef 594Exercises 619