计算机系统概论（英文影印版）（第2版）

Exercises
2 Bits. Data Types. and Operations
2.1 Bits and Data Types
2.1.1 The Bit as the Unit of Information
2.1.2 Data Types
2.2 integer Data Types
2.2.1 Unsigned integers
2.2.2 Signed Integers
2.3 2's Complement integers
2.4 Binary-Decimal Conversion
2.4.1 Binary to Decimal Conversion
2.4.2 Decimal to Binary Conversion
2.5 Operations on Bits--Part I: Arithmetic
2.5.1 Addition and Subtraction
2.5.2 Sign-Extension
2.5.3 Overflow
2.6 Operations on Bits--Part II: Logical Operations
2.6.1 The AND Function
2.6.2 The OR Function
2.6.3 The NOT Function
2.6.4 The Exclusive-OR Function
2.7 Other Representations
2.7.1 The Bit Vector
2.7.2 Floating Point Data Type
2.7.3 ASCII Codes
2.7.4 Hexadecimal Notation
Exercises
3 Digital Logic Structures
3.1 The Transistor
3.2 Logic Gates
3.2.1 The NOT Gate (inverter)
3.2.2 OR and NOR Gates
3.2.3 AND and NAND Gates
3.2.4 DeMorgan's Law
3.2.5 Larger Gates
3.3 Combinational Logic Circuits
3.3.1 Decoder
3.3.2 Mux
3.3.3 Full Adder
3.3.4 The Programmable Logic Array (PLA)
3.3.5 Logical Completeness
3.4 Basic Storage Elements
3.4.1 The R-S Latch
3.4.2 The Gated D Latch
3.4.3 A Register
3.5 The Concept of Memory
3.5.1 Address Space
3.5.2 Addressability
3.5.3 A 22-by-3-Bit Memory
3.6 Sequential Logic Circuits
3.6.1 A Simple Example: The Combination Lock
3.6.2 The Concept of State
3.6.3 Finite State Machines
3.6.4 An Example: The Complete Implementation of a Finite State Machine
3.7 The Data Path of the LC-3
Exercises
4 The von Neumann Model
4.1 Basic Components
4.1.1 Memory
4.1.2 Processing Unit
4.1.3 Input and Output
4.1.4 Control Unit
4.2 The LC-3: An Example von Neumann Machine
4.3 instruction Processing
4.3.1 The Instruction
4.3.2 The Instruction Cycle
4.4 Changing the Sequence of Execution
4.4.1 Control of the Instruction Cycle
4.5 Stopping the Computer
Exercises
5 The LC-3
5.1 The ISA: Overview
5.1.1 Memory Organization
5.1.2 Registers
5.1.3 The instruction Set
5.1.4 Opcodes
5.1.5 Data Types
5.1.6 Addressing Modes
5.1.7 Condition Cqdes
5.2 Operate Instructions
5.3 Data Movement Instructions
5.3.1 PC-Relative Mode
5.3.2 indirect Mode
5.3.3 Base+offset Mode
5.3.4 Immediate Mode
5.3.5 An Example
5.4 Control Instructions
5.4.1 Conditional Branches
5.4.2 An Example
5.4.3 Two Methods for Loop Control
5.4.4 Example: Adding a Column of Numbers Using a Sentinel
5.4.5 The JMP Instruction
5.4.6 The TRAP Instruction
5.5 Another Example: Counting Occurrences of a Character
5.6 The Data Path Revisited
5.6.1 Basic Components of the Data Path
5.6.2 The Instruction Cycle
Exercises
6 Programming
6.1 Problem Solving
6.1.1 Systematic Decomposition
6.1.2 The Three Constructs: Sequential. Conditional. Iterative
6.1.3 LC-3 Control Instructions to Implement the Three Constructs
6.1.4 The Character Count Example from Chapter 5. Revisited
6.2 Debugging
6.2.1 Debugging Operations
6.2.2 Examples: Use of the interactive Debugger
Exercises
7 Assembly Language
7.1 Assembly Language Programming—Moving Up a Level
7.2 An Assembly Language Program
7.2.1 Instructions
7.2.2 Pseudo-ops (Assembler Directives)
7.2.3 Example: The Character Count Example of Section 5.5. Revisited
7.3 The Assembly Process
7.3.1 Introduction
7.3.2 A Two-Pass Process
7.3.3 The First Pass: Creating the Symbol Table
7.3.4 The Second Pass: Generating the Machine Language Program
7.4 Beyond the Assembly of a Single Assembly Language Program
7.4.1 The Executable Image
7.4.2 More than One Object File
Exercises
8 I/O
8.1 I/O Basics
8.1.1 Device Registers
8.1.2 Memory-Mapped I/O versus Special Input/Output Instructions
8.1.3 Asynchronous versus Synchronous
8.1.4 Interrupt-Driven versus Polling
8.2 Input from the Keyboard
8.2.1 Basic Input Registers (the KBDR and the KBSR)
8.2.2 The Basic Input Service Routine
8.2.3 Implementation of Memory-Mapped Input
8.3 Output to the Monitor
8.3.1 Basic Output Registers (the DDR and the DSR)
8.3.2 The Basic Output Service Routine
8.3.3 Implementation of Memory-Mapped Output
8.3.4 Example: Keyboard Echo
8.4 A More Sophisticated Input Routine
8.5 Interrupt-Driven I/O
8.5.1 What Is Interrupt-Driven I/O?
8.5.2 Why Have Interrupt-Driven I/O? 210
8.5.3 Generation of the Interrupt Signal
8.6 Implementation of Memory-Mapped I/O. Revisited
Exercises
9 TRAP Routines and Subroutines
9.1 LC-3 TRAP Routines
9.1.1 Introduction
9.1.2 The TRAP Mechanism
9.1.3 The TRAP Instruction
9.1.4 The Complete Mechanism
9.1.5 TRAP Routines for Handling I/O
9.1.6 TRAP Routine for Halting the Computer
9.1.7 Saving and Restoring Registers
9.2 Subroutines
9.2.1 The Call/Return Mechanism
9.2.2 The JSR(R) Instruction
9.2.3 The TRAP Routine for Character Input. Revisited
9.2.4 PUTS: Writing a Character String to the Monitor
9.2.5 Library Routines
Exercises
10 And. Finally... The Stack
10.1 The Stack: Its Basic Structure
10.1.1 The Stack--An Abstract Data Type
10.1.2 Two Example Implementations
10.1.3 Implementation in Memory
10.1.4 The Complete Picture
10.2 Interrupt-Driven I/O (Part 2)
10.2.1 Initiate and Service the Interrupt
10.2.2 Return from the Interrupt
10.2.3 An Example
10.3 Arithmetic Using a Stack
10.3.1 The Stack as TemporaryStorage
10.3.2 An Example
10.3.3 OpAdd. OpMult. and OpNeg
10.4 Data Type Conversion
10.4.1 Example: The Bogus Program: 2+3=e
10.4.2 ASCII to Binary
10.4.3 Binaryto ASCII
10.5 Our Final Example: The Calculator
Exercises..
11 Introduction to Programming in C
11.1 Our Objective
11.2 Bridging the Gap
11.3 Translating High-Level Language Programs
11.3.1 Interpretation
11.3.2 Compilation
11.3.3 Pros and Cons
11.4 The C Programming Language
11.4.1 The C Compiler
11.5 A Simple Example
11.5.1 The Function main
11.5.2 Formatting. Comments. and Style
11.5.3 The C Preprocessor
11.5.4 Input and Output
11.6 Summary
Exercises
12 Variables and Operators
12.1 Introduction
12.2 Variables
12.2.1 Three Basic Data Types: int. char. double
12.2.2 Choosing Identifiers
12.2.3 Scope: Local versus Global
12.2.4 More Examples
12.3 Operators
12.3.1 Expressions and Statements
12.3.2 The Assignment Operator
12.3.3 Arithmetic Operators
12.3.4 Order of Evaluation
12.3.5 Bitwise Operators
12.3.6 Relational Operators
12.3.7 Logical Operators
12.3.8 Increment/Decrement Operators
12.3.9 Expressions with Multiple Operators
12.4 Problem Solving Using Operators
12.5 Tying it All Together
12.5.1 Symbol Table
12.5.2 Allocating Space for Variables
12.5.3 A Comprehensive Example
12.6 Additional Topics
12.6.1 Variations of the Three Basic Types
12.6.2 Literals. Constants. and Symbolic Values
12.6.3 Storage Class
12.6.4 Additional C Operators
12.7 Summary
Exercises
13 Control Structures
13.1 Introduction
13.2 Conditional Constructs
13.2.1 The if Statement
13.2.2 The if-else Statement
13.3 Iteration Constructs
13.3.1 The while Statement
13.3.2 The for Statement
13.3.3 The do-while Statement
13.4 Problem Solving Using Control Structures
13.4.1 Problem 1: Approximating the Value of π
13.4.2 Problem 2: Finding Prime Numbers Less than 100
13.4.3 Problem 3: Analyzingan E-mail Address
13.5 Additional C Control Structures
13.5.1 The switch Statement
13.5.2 The break and continue Statements
13.5.3 An Example: Simple Calculator
13.6 Summary
Exercises
14 Functions
14.1 Introduction
14.2 Functions in C
14.2.1 A Function with a Parameter
14.2.2 Example: Area of a Ring
14.3 Implementing Functions in C
14.3.1 Run-Time Stack
14.3.2 Getting It All to Work
14.3.3 Tying It All Together
14.4 Problem Solving Using Functions
14.4.1 Problem 1: Case Conversion
14.4.2 Problem 2: Pythagorean Triples
14.5 Summary
Exercises
15 Testing and Debugging
15.1 Introduction
15.2 Types of Errors
15.2.1 Syntactic Errors
15.2.2 Semantic Errors
15.2.3 Algorithmic Errors
15.3 Testing
15.3.1 Black-Box Testing
15.3.2 White-Box Testing
15.4 Debugging
15.4.1 Ad Hoc Techniques
15.4.2 Source-Level Debuggers
15.5 Programming for Correctness
15.5.1 Nailing Down the Specification
15.5.2 Modular Design
15.5.3 Defensive Programming
15.6 Summary
Exercises
16 Pointers and Arrays
16.1 Introduction
16.2 Pointers
16.2.1 Declaring Pointer Variables
16.2.2 Pointer Operators
16.2.3 Passing a Reference Using Pointers
16.2.4 Null Pointers
16.2.5 Demystifying the Syntax
16.2.6 An Example Problem involving Pointers
16.3 Arrays
16.3.1 Declaring and Using Arrays
16.3.2 Examples Using Arrays
16.3.3 Arrays as Parameters
16.3.4 Strings in C
16.3.5 The Relationship Between Arrays and Pointers in C
16.3.6 Problem Solving: Insertion Sort
16.3.7 Common Pitfalls with Arrays in C
16.4 Summary
Exercises
17 Recursion
17.1 Introduction
17.2 What Is Recursion?
17.3 Recursion versus Iteration
17.4 Towers of Hanoi
17.5 Fibonacci Numbers
17.6 Binary Search
17.7 Integer to ASCII
17.8 Summary
Exercises
18 I／O in C
18.1 Introduction
18.2 The C Standard Library
18.3 I/O. One Character at a Time
18.3.1 I/O Streams
18.3.2 putchar
18.3.3 getchar
18.3.4 Buffered UO
18.4 Formatted I/O
18.4.1 printf
18.4.2 scanf
18.4.3 Variable Argument Lists
18.5 I/O from Files
18.6 Summary
Exercises
19 Data Structures
19.1 Introduction
19.2 Structures
19.2.1 typedef
19.2.2 Implementing Structures in C
19.3 Arrays of Structures
19.4 Dynamic Memory Allocation
19.4.1 Dynamically Sized Arrays
19.5 Linked Lists
19.5.1 An Example
19.6 Summary
Exercises
A The LC-3 ISA
A.1 Overview
A.2 Notation
A.3 The Instruction Set
A.4 Interrupt and Exception Processing
A.4.1 Interrupts
A.4.2 Exceptions
B From LC-3 to x86
B.1 LC-3 Features and Corresponding x86 Features
B.1.1 instruction Set
B.1.2 Memory
B.1.3 Internal State
B.2 The Format and Specification of x86 instructions
B.2.1 Prefix
B.2.2 Opcode
B.2.3 ModR/M Byte
B.2.4 SiB Byte
B.2.5 Displacement
8.2.6 Immediate
B.3 An Example
C The Microarchitecture of the LC-3
C.1 Overview
C.2 The State Machine
C.3 The Data Path
C.4 The Control Structure
C.5 Memory-Mapped 1/0
C.6 interrupt and Exception Control
C.6.1 initiating an Interrupt
C.6.2 Returning from an interrupt. RTI
C.6.3 The illegal Opcode Exception
C.7 Control Store
D The C Programming Language
D.1 Overview
D.2 C Conventions
D.2.1 Source Files
D.2.2 Header Files
D.2.3 Comments
D.2.4 Literals
D.2.5 Formatting
D.2.6 Keywords
D.3 Types
D.3.1 Basic Data Types
D.3.2 Type Qualifiers
D.3.3 Storage Class
D.3.4 Derived Types
D.3.5 typedef
D.4 Declarations
D.4.1 Variable Declarations
D.4.2 Function Declarations
D.5 Operators
D.5.1 Assignment Operators
D.5.2 Arithmetic Operators
D.5.3 Bit-wise Operators
D.5.4 Logical Operators
D.5.5 Relational Operators
D.5.6 increment/Decrement Operators
D.5.7 Conditional Expression
D.5.8 Pointer. Array. and Structure Operators
D.5.9 sizeof
D.5.10 Order of Evaluation
D.5.11 Type Conversions
D.6 Expressions and Statements
D.6.1 Expressions
D.6.2 Statements
D.7 Control
D.7.1 If
D.7.2 If-else
D.7.3 Switch
D.7.4 While
D.7.5 For
D.7.6 Do-while
D.7.7 Break
D.7.8 continue
D.7.9 return
D.8 The C Preprocessor
D.8.1 Macro substitution
D.8.2 File inclusion
D.9 Some Standard Library Functions
D.9.1 I／O Functions
D.C.2 String Functions
D.9.3 Math Functions
D.9.4 Utility Functions
E Useful Tables
E.1 Commonly Used Numerical Prefixes
E.2 Standard ASCii codes
E.3 Powers of 2
F Solutions to Selected Exercises...

.　　The book has been used to delve deeply into computer implementation in the sophomore year. The semester is spent in Chapters 1 through I0, sometimes culminating in a thorough study of Appendix C, which provides the complete microarchitecture of a microprogrammed LC-3. We note, however, that some very important ideas in computer architecture are not covered here, most notably cache memory, pipelining, and virtual memory. We agree that these topics are very important to the education of a computer scientist or computer engineer, but we feel these topics are better suited to a senior course in computer architecture and design. This book is not intended for that purpose.
　　Acknowledgments
　　Our book continues to benefit greatly from important contributions of many, many people. We particularly want to acknowledge Brian Hartman and Matt Starolis.
　　Brian Hartman continues to be a very important part of this work, both for the great positive energy he brings to the table and for his technical expertise. He is now out of school more than three years and remains committed to the concept. He took the course the first year it was offered at Michigan (Winter term, 1996), TAed it several times as an undergraduate student, and wrote the first LC-2 simulator for Windows while he was working on his master's degree. He recently upgraded the Windows simulator to incorporate the new LC-3.
　　Matt Starolis took the freshman course at UT two years ago and TAed it as a junior last fall. He, too, has been very important to us getting out this second edition. He has been both critic of our writing and helpful designer of many of the figures, He also updated the tutorials for the simulators, which was necessary in order to incorporate the new characteristics of the LC-3. When something needed to be done, Matt volunteered to do it. His enthusiasm for the course and the book has been a pleasure.
　　With more than 100 adopters now, we regularly get enthusiastic e-mail with suggestions from professors from all over the world. Although we realize we have undoubtedly forgotten some, we would at least like to thank Professors Vijay Pai, Rice; Richard Johnson, Western New Mexico; Tore Larsen, Tromso; Greg Byrd, NC State; Walid Najjar, UC Riverside; Sean Joyee, Heidelberg College; James Boettler, South Carolina State; Steven Zeltmann, Arkansas; Mike McGregor, Alberta; David Lilja, Minnesota; Eric Thompson, Colorado, Denver; and Brad Hutchings, Brigham Young.
　　Between the two of us, we have taught the course four more times since the first edition came out, and that has produced a new enthusiastic group of believers, both TAs and students. Kathy Buckheit, Mustafa Erwa, Joseph Grzywacz, Chandresh Jain, Kevin Major, Onur Mutlu, Moinuddin Qureshi, Kapil Sachdeva, Russell Schreiber, Paroma Sen, Santhosh Srinath, Kameswar Subramaniam, David Thompson, Francis Tseng, Brian Ward, and Kevin Woley have all served as TAs and have demonstrated a commitment to helping students learn that can only be described as wonderful. Linda Bigelow, Matt Starolis, and Lester Guillory all took the course as freshmen, and two years later they were among the most enthusiastic TAs the course has known.
　　Ashley Wise developed the Linux version of the LC-3 simulator. Ajay Ladsaria ported the LCC compiler to generate LC-3 code. Gregory Muthler and Francesco Spadini enthusiastically provided critical feedback on drafts of the chapters in the second half.
　　Kathy Buckheit wrote introductory tutorials to help students use the LC-2 simulator because she felt it was necessary.
　　Several other faculty members at The University of Texas have used the book and shared their insights with us: Tony Ambler, Craig Chase, Mario Gonzalez, and Earl Swartzlander in ECE, and Doug Burger, Chris Edmundson, and Steve Keckler in CS. We thank them.
　　We continue to celebrate the commitment displayed by our editors, Betsy Jones and Michelle Flomenhoft.
　　As was the case with the first edition, our book has benefited from extensive reviews provided by faculty members from many universities. We thank Robert Crisp, Arkansas; Allen Tannenbaum, Georgia Tech; Nickolas Jovanovic, Arkansas-Little Rock; Dean Brock, North Carolina-Asheville; Amar Raheja, Cai State-Pomona; Dayton Clark, Brooklyn College; William Yurcik, lllinois State; Jose Delgado-Frias, Washington State; Peter Drexel, Plymouth State; Mahmoud Manzoul, Jackson State; Dan Connors, Colorado; Massoud Ghyam, Southern Cal; John Gray, UMass-Dartmouth; John Hamilton, Auburn; Alan Rosenthal, Toronto; and Ron Taylor, Wright State.
　　Finally, there are those who have contributed in many different and often unique ways. Without listing their individual contributions, we simply list them and say thank you. Amanda, Bryan, and Carissa Hwu, Mateo Valero, Rich Belgard, Janak Patel, Matthew Frank, Milena Milenkovic, Lila Rhoades, Bruce Shriver, Steve Lumetta, and Brian Evans. Sanjay would like to thank Ann Young for all her love and support.
　　AFinalNord
　　It is worth repeating our final words from the preface to the first edition: We are mindful that the current version of this book will always be a work in progress, and we welcome your comments on any aspect of it. You can reach us by e-mail at patt@ece.utexas.edu and sjp@crhc.uiuc.edu. We hope you will. ...
　　Yale N. Patt
　　San jay J. Patel
　　May, 2003