You are previewing Computer Systems, 5th Edition.
O'Reilly logo
Computer Systems, 5th Edition

Book Description

Computer Systems, Fifth Edition provides a clear, detailed, step-by-step introduction to the central concepts in computer organization, assembly language, and computer architecture. It urges students to explore the many dimensions of computer systems through a top-down approach to levels of abstraction. By examining how the different levels of abstraction relate to one another, the text helps students look at computer systems and their components as a unified concept.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication
  5. Table of Contents
      1. 1.1 Levels of Abstraction
        1. Abstraction in Art
        2. Abstraction in Documents
        3. Abstraction in Organizations
        4. Abstraction in Machines
        5. Abstraction in Computer Systems
      2. 1.2 Hardware
        1. Central Processing Unit
        2. Main Memory
        3. Disk
      3. 1.3 Software
        1. Operating Systems
        2. Software Analysis and Design
      4. 1.4 Digital Information
        1. Quantifying Space
        2. Quantifying Time
        3. Quick Response Codes
        4. Images
      5. 1.5 Database Systems
        1. Relations
        2. Queries
        3. Structure of the Language
      6. Chapter Summary
      7. Exercises
      1. 2.1 Variables
        1. The C Compiler
        2. Machine Independence
        3. The C Memory Model
        4. Global Variables and Assignment Statements
        5. Local Variables
      2. 2.2 Flow of Control
        1. The If/Else Statement
        2. The Switch Statement
        3. The While Loop
        4. The Do Loop
        5. Arrays and the For Loop
      3. 2.3 Functions
        1. Void Functions and Call-by-Value Parameters
        2. Functions
        3. Call-by-Reference Parameters
      4. 2.4 Recursion
        1. A Factorial Function
        2. Thinking Recursively
        3. Recursive Addition
        4. A Binomial Coefficient Function
        5. Reversing the Elements of an Array
        6. Towers of Hanoi
        7. Mutual Recursion
        8. The Cost of Recursion
      5. 2.5 Dynamic Memory Allocation
        1. Pointers
        2. Structures
        3. Linked Data Structures
      6. Chapter Summary
      7. Exercises
      8. Problems
      1. 3.1 Unsigned Binary Representation
        1. Binary Storage
        2. Integers
        3. Base Conversions
        4. Range for Unsigned Integers
        5. Unsigned Addition
        6. The Carry Bit
      2. 3.2 Two’s Complement Binary Representation
        1. Two’s Complement Range
        2. Base Conversions
        3. The Number Line
        4. The Overflow Bit
        5. The Negative and Zero Bits
      3. 3.3 Operations in Binary
        1. Logical Operators
        2. Register Transfer Language
        3. Arithmetic Operators
        4. Rotate Operators
      4. 3.4 Hexadecimal and Character Representations
        1. Hexadecimal
        2. Base Conversions
        3. ASCII Characters
        4. Unicode Characters
      5. 3.5 Floating-Point Representation
        1. Binary Fractions
        2. Excess Representations
        3. The Hidden Bit
        4. Special Values
        5. The IEEE 754 Floating-Point Standard
      6. 3.6 Models
      7. Chapter Summary
      8. Exercises
      9. Problems
      1. 4.1 Hardware
        1. Central Processing Unit (CPU)
        2. Main Memory
        3. Input/Output Devices
        4. Data and Control
        5. Instruction Format
      2. 4.2 Direct Addressing
        1. The Stop Instruction
        2. The Load Word Instruction
        3. The Store Word Instruction
        4. The Add Instruction
        5. The Subtract Instruction
        6. The And and Or Instructions
        7. The Invert and Negate Instructions
        8. The Load Byte and Store Byte Instructions
        9. The Input and Output Devices
        10. Big Endian Versus Little Endian
      3. 4.3 von Neumann Machines
        1. The von Neumann Execution Cycle
        2. A Character Output Program
        3. von Neumann Bugs
        4. A Character Input Program
        5. Converting Decimal to ASCII
        6. A Self-Modifying Program
      4. 4.4 Programming at Level ISA3
        1. Read-Only Memory
        2. The Pep/9 Operating System
        3. Using the Pep/9 System
      5. Chapter Summary
      6. Exercises
      7. Problems
      1. 5.1 Assemblers
        1. Instruction Mnemonics
        2. Pseudo-Operations
        3. The .ASCII and .END Pseudo-ops
        4. Assemblers
        5. The .BLOCK Pseudo-op
        6. The .WORD and .BYTE Pseudo-ops
        7. Using the Pep/9 Assembler
        8. Cross Assemblers
      2. 5.2 Immediate Addressing and the Trap Instructions
        1. Immediate Addressing
        2. The DECI, DECO, and BR Instructions
        3. The STRO Instruction
        4. Interpreting Bit Patterns: The HEXO Instruction
        5. Disassemblers
      3. 5.3 Symbols
        1. A Program with Symbols
        2. A von Neumann Illustration
      4. 5.4 Translating from Level HOL6
        1. The Printf() Function
        2. Variables and Types
        3. Global Variables and Assignment Statements
        4. Type Compatibility
        5. Pep/9 Symbol Tracer
        6. The Shift and Rotate Instructions
        7. Constants and .EQUATE
        8. Placement of Instructions and Data
      5. Chapter Summary
      6. Exercises
      7. Problems
      1. 6.1 Stack Addressing and Local Variables
        1. Stack-Relative Addressing
        2. Accessing the Run-Time Stack
        3. Local Variables
      2. 6.2 Branching Instructions and Flow of Control
        1. Translating the If Statement
        2. Optimizing Compilers
        3. Translating the If/Else Statement
        4. Translating the While Loop
        5. Translating the Do Loop
        6. Translating the For Loop
        7. Spaghetti Code
        8. Flow of Control in Early Languages
        9. The Structured Programming Theorem
        10. The Goto Controversy
      3. 6.3 Function Calls and Parameters
        1. Translating a Function Call
        2. Translating Call-by-Value Parameters with Global Variables
        3. Translating Call-by-Value Parameters with Local Variables
        4. Translating Non-void Function Calls
        5. Translating Call-by-Reference Parameters with Global Variables
        6. Translating Call-by-Reference Parameters with Local Variables
        7. Translating Boolean Types
      4. 6.4 Indexed Addressing and Arrays
        1. Translating Global Arrays
        2. Translating Local Arrays
        3. Translating Arrays Passed as Parameters
        4. Translating the Switch Statement
      5. 6.5 Dynamic Memory Allocation
        1. Translating Global Pointers
        2. Translating Local Pointers
        3. Translating Structures
        4. Translating Linked Data Structures
      6. Chapter Summary
      7. Exercises
      8. Problems
      1. 7.1 Languages, Grammars, and Parsing
        1. Concatenation
        2. Languages
        3. Grammars
        4. A Grammar for C Identifiers
        5. A Grammar for Signed Integers
        6. A Context-Sensitive Grammar
        7. The Parsing Problem
        8. A Grammar for Expressions
        9. A C Subset Grammar
        10. Context Sensitivity of C
      2. 7.2 Finite-State Machines
        1. An FSM to Parse an Identifier
        2. Simplified FSMs
        3. Nondeterministic FSMs
        4. Machines with Empty Transitions
        5. Multiple Token Recognizers
        6. Grammars Versus FSMs
      3. 7.3 Implementing Finite-State Machines
        1. The Compilation Process
        2. A Table-Lookup Parser
        3. A Direct-Code Parser
        4. An Input Buffer Class
        5. A Multiple-Token Parser
      4. 7.4 Code Generation
        1. A Language Translator
        2. Parser Characteristics
      5. Chapter Summary
      6. Exercises
      7. Problems
      1. 8.1 Loaders
        1. The Pep/9 Operating System
        2. The Pep/9 Loader
        3. Program Termination
      2. 8.2 Traps
        1. The Trap Mechanism
        2. The RETTR Instruction
        3. The Trap Handlers
        4. Trap Addressing Mode Assertion
        5. Trap Operand Address Computation
        6. The No-Operation Trap Handlers
        7. The DECI Trap Handler
        8. The DECO Trap Handler
        9. The HEXO and STRO Trap Handlers and Operating System Vectors
      3. 8.3 Concurrent Processes
        1. Asynchronous Interrupts
        2. Processes in the Operating System
        3. Multiprocessing
        4. A Concurrent Processing Program
        5. Critical Sections
        6. A First Attempt at Mutual Exclusion
        7. A Second Attempt at Mutual Exclusions
        8. Peterson’s Algorithm for Mutual Exclusion
        9. Semaphores
        10. Critical Sections with Semaphores
      4. 8.4 Deadlocks
        1. Resource Allocation Graphs
        2. Deadlock Policy
      5. Chapter Summary
      6. Exercises
      7. Problems
      1. 9.1 Memory Allocation
        1. Uniprogramming
        2. Fixed-Partition Multiprogramming
        3. Logical Addresses
        4. Variable-Partition Multiprogramming
        5. Paging
      2. 9.2 Virtual Memory
        1. Large Program Behavior
        2. Virtual Memory
        3. Demand Paging
        4. Page Replacement
        5. Page-Replacement Algorithms
      3. 9.3 File Management
        1. Disk Drives
        2. File Abstraction
        3. Allocation Techniques
      4. 9.4 Error-Detecting and Error-Correcting Codes
        1. Error-Detecting Codes
        2. Code Requirements
        3. Single-Error-Correcting Codes
      5. 9.5 RAID Storage Systems
        1. RAID Level 0: Nonredundant Striped
        2. RAID Level 1: Mirrored
        3. RAID Levels 01 and 10: Striped and Mirrored
        4. RAID Level 2: Memory-Style ECC
        5. RAID Level 3: Bit-Interleaved Parity
        6. RAID Level 4: Block-Interleaved Parity
        7. RAID Level 5: Block-Interleaved Distributed Parity
      6. Chapter Summary
      7. Exercises
      1. 10.1 Boolean Algebra and Logic Gates
        1. Combinational Circuits
        2. Truth Tables
        3. Boolean Algebra
        4. Boolean Algebra Theorems
        5. Proving Complements
        6. Logic Diagrams
        7. Alternate Representations
      2. 10.2 Combinational Analysis
        1. Boolean Expressions and Logic Diagrams
        2. Truth Tables and Boolean Expressions
        3. Two-Level Circuits
        4. The Ubiquitous NAND
      3. 10.3 Combinational Design
        1. Canonical Expressions
        2. Three-Variable Karnaugh Maps
        3. Four-Variable Karnaugh Maps
        4. Dual Karnaugh Maps
        5. Don’t-Care Conditions
      4. 10.4 Combinational Devices
        1. Viewpoints
        2. Multiplexer
        3. Binary Decoder
        4. Demultiplexer
        5. Adder
        6. Adder/Subtracter
        7. Arithmetic Logic Unit
        8. Abstraction at Level LG1
      5. Chapter Summary
      6. Exercises
      1. 11.1 Latches and Clocked Flip-Flops
        1. The SR Latch
        2. The Clocked SR Flip-Flop
        3. The Master–Slave SR Flip-Flop
        4. The Basic Flip-Flops
        5. The JK Flip-Flop
        6. The D Flip-Flop
        7. The T Flip-Flop
        8. Excitation Tables
      2. 11.2 Sequential Analysis and Design
        1. A Sequential Analysis Problem
        2. Preset and Clear
        3. Sequential Design
        4. A Sequential Design Problem
      3. 11.3 Computer Subsystems
        1. Registers
        2. Buses
        3. Memory Subsystems
        4. Address Decoding
        5. A Two-Port Register Bank
      4. Chapter Summary
      5. Exercises
      1. 12.1 Constructing a Level-ISA3 Machine
        1. The CPU Data Section
        2. The von Neumann Cycle
        3. The Store Byte Direct Instruction
        4. Bus Protocols
        5. The Store Word Direct Instruction
        6. The Add Immediate Instruction
        7. The Load Word Indirect Instruction
        8. The Arithmetic Shift Right Instruction
        9. The CPU Control Section
      2. 12.2 Performance
        1. The Data Bus Width and Memory Alignment
        2. Memory Alignment
        3. The Definition of an n-Bit Computer
        4. Cache Memories
        5. The System Performance Equation
        6. RISC Versus CISC
      3. 12.3 The MIPS Machine
        1. The Register Set
        2. The Addressing Modes
        3. The Instruction Set
        4. MIPS Computer Organization
        5. Pipelining
      4. 12.4 Conclusion
        1. Simplifications in the Model
        2. The Big Picture
      5. Chapter Summary
      6. Exercises
      7. Problems