Computer Systems

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. New & Key Features: - New high-order language -- The high-order language is changed from C++ to C. The C language is more common as a systems programming language and is more appropriate for a computer systems text. - New sidebars -- Each sidebar is a real-world example of the concepts described in that chapter. As most of the chapters describe the Pep/9 virtual machine, the sidebars for those chapters show corresponding implementations for the Intel x86 architecture. - New and expanded topics -- New and expanded topics include, QR codes, color displays, Unicode, UTF-32 and UTF-8 encoding, floating point underflow, big-endian and little-endian order, memory alignment issues, and expanded RISC design principles and MIPS coverage to contrast with the Pep/9 CISC design. - New virtual machine -- Pep/8, the virtual machine for the two previous editions, is now superseded by the new and improved Pep/9. Pep/9 retains the same eight addressing modes of Pep/8 but now includes memory-mapped I/O, an improved return-from-subroutine instruction, a new native compare-byte instruction, improved instruction mnemonics, and a new hexadecimal output trap instruction. - New software -- The Pep/9 system in the text is supported by two updated open source software applications, the assembler/simulator and the CPU simulator. Title Page......Page 2 Copyright Page......Page 3 Dedication......Page 5 Table of Contents......Page 6 Preface......Page 17 Level 7 Application......Page 30 1.1 Levels of Abstraction......Page 31 Abstraction in Art......Page 34 Abstraction in Documents......Page 35 Abstraction in Organizations......Page 37 Abstraction in Machines......Page 39 Abstraction in Computer Systems......Page 40 Central Processing Unit......Page 42 Main Memory......Page 44 Disk......Page 47 1.3 Software......Page 48 Operating Systems......Page 50 Software Analysis and Design......Page 51 Quantifying Space......Page 53 Quantifying Time......Page 57 Quick Response Codes......Page 59 Images......Page 65 1.5 Database Systems......Page 73 Queries......Page 74 Structure of the Language......Page 77 Chapter Summary......Page 78 Exercises......Page 79 Level 6 High-Order Language......Page 83 2. C......Page 84 The C Compiler......Page 85 Machine Independence......Page 86 The C Memory Model......Page 87 Global Variables and Assignment Statements......Page 88 Local Variables......Page 91 2.2 Flow of Control......Page 94 The If/Else Statement......Page 95 The Switch Statement......Page 96 The While Loop......Page 97 Arrays and the For Loop......Page 99 Void Functions and Call-by-Value Parameters......Page 101 Functions......Page 104 Call-by-Reference Parameters......Page 105 2.4 Recursion......Page 110 A Factorial Function......Page 111 Thinking Recursively......Page 115 Recursive Addition......Page 116 A Binomial Coefficient Function......Page 117 Reversing the Elements of an Array......Page 123 Towers of Hanoi......Page 124 Mutual Recursion......Page 127 The Cost of Recursion......Page 128 2.5 Dynamic Memory Allocation......Page 130 Pointers......Page 131 Structures......Page 133 Linked Data Structures......Page 134 Chapter Summary......Page 137 Exercises......Page 138 Problems......Page 139 Level 3 Instruction Set Architecture......Page 143 3.1 Unsigned Binary Representation......Page 144 Binary Storage......Page 145 Integers......Page 147 Base Conversions......Page 149 Unsigned Addition......Page 151 The Carry Bit......Page 152 3.2 Two’s Complement Binary Representation......Page 153 Two’s Complement Range......Page 156 Base Conversions......Page 158 The Number Line......Page 160 The Overflow Bit......Page 162 The Negative and Zero Bits......Page 163 Logical Operators......Page 165 Register Transfer Language......Page 166 Arithmetic Operators......Page 168 3.4 Hexadecimal and Character Representations......Page 170 Base Conversions......Page 171 ASCII Characters......Page 174 Unicode Characters......Page 178 3.5 Floating-Point Representation......Page 181 Binary Fractions......Page 182 Excess Representations......Page 184 The Hidden Bit......Page 186 Special Values......Page 188 The IEEE 754 Floating-Point Standard......Page 193 3.6 Models......Page 195 Chapter Summary......Page 197 Exercises......Page 198 Problems......Page 210 4. Computer Architecture......Page 214 Central Processing Unit (CPU)......Page 215 Main Memory......Page 216 Data and Control......Page 219 Instruction Format......Page 220 4.2 Direct Addressing......Page 224 The Load Word Instruction......Page 225 The Store Word Instruction......Page 226 The Add Instruction......Page 227 The Subtract Instruction......Page 228 The And and Or Instructions......Page 229 The Invert and Negate Instructions......Page 230 The Load Byte and Store Byte Instructions......Page 231 The Input and Output Devices......Page 233 Big Endian Versus Little Endian......Page 234 The von Neumann Execution Cycle......Page 236 A Character Output Program......Page 238 von Neumann Bugs......Page 242 A Character Input Program......Page 243 Converting Decimal to ASCII......Page 244 A Self-Modifying Program......Page 246 4.4 Programming at Level ISA3......Page 250 Read-Only Memory......Page 252 The Pep/9 Operating System......Page 253 Using the Pep/9 System......Page 255 Chapter Summary......Page 256 Exercises......Page 257 Problems......Page 259 Level 5 Assembly......Page 261 5.1 Assemblers......Page 262 Instruction Mnemonics......Page 263 The .ASCII and .END Pseudo-ops......Page 267 Assemblers......Page 269 The .BLOCK Pseudo-op......Page 270 The .WORD and .BYTE Pseudo-ops......Page 272 Using the Pep/9 Assembler......Page 273 5.2 Immediate Addressing and the Trap Instructions......Page 275 Immediate Addressing......Page 276 The DECI, DECO, and BR Instructions......Page 277 The STRO Instruction......Page 280 Interpreting Bit Patterns: The HEXO Instruction......Page 281 Disassemblers......Page 283 A Program with Symbols......Page 286 A von Neumann Illustration......Page 288 5.4 Translating from Level HOL6......Page 291 The Printf() Function......Page 292 Variables and Types......Page 294 Global Variables and Assignment Statements......Page 295 Type Compatibility......Page 300 Pep/9 Symbol Tracer......Page 301 The Shift and Rotate Instructions......Page 302 Constants and .EQUATE......Page 303 Placement of Instructions and Data......Page 307 Exercises......Page 308 Problems......Page 312 6.1 Stack Addressing and Local Variables......Page 315 Stack-Relative Addressing......Page 316 Accessing the Run-Time Stack......Page 317 Local Variables......Page 320 6.2 Branching Instructions and Flow of Control......Page 324 Translating the If Statement......Page 325 Optimizing Compilers......Page 327 Translating the If/Else Statement......Page 328 Translating the While Loop......Page 331 Translating the Do Loop......Page 333 Translating the For Loop......Page 335 Spaghetti Code......Page 337 The Structured Programming Theorem......Page 340 The Goto Controversy......Page 341 Translating a Function Call......Page 342 Translating Call-by-Value Parameters with Global Variables......Page 345 Translating Call-by-Value Parameters with Local Variables......Page 350 Translating Non-void Function Calls......Page 353 Translating Call-by-Reference Parameters with Global Variables......Page 356 Translating Call-by-Reference Parameters with Local Variables......Page 361 Translating Boolean Types......Page 365 Translating Global Arrays......Page 368 Translating Local Arrays......Page 372 Translating Arrays Passed as Parameters......Page 375 Translating the Switch Statement......Page 381 Translating Global Pointers......Page 387 Translating Local Pointers......Page 393 Translating Structures......Page 397 Translating Linked Data Structures......Page 403 Exercises......Page 408 Problems......Page 409 7. Language Translation Principles......Page 419 7.1 Languages, Grammars, and Parsing......Page 420 Languages......Page 421 Grammars......Page 422 A Grammar for C Identifiers......Page 423 A Grammar for Signed Integers......Page 425 A Context-Sensitive Grammar......Page 426 The Parsing Problem......Page 428 A Grammar for Expressions......Page 429 A C Subset Grammar......Page 432 Context Sensitivity of C......Page 437 An FSM to Parse an Identifier......Page 438 Nondeterministic FSMs......Page 440 Machines with Empty Transitions......Page 442 Multiple Token Recognizers......Page 445 Grammars Versus FSMs......Page 448 7.3 Implementing Finite-State Machines......Page 449 The Compilation Process......Page 450 A Table-Lookup Parser......Page 452 A Direct-Code Parser......Page 454 An Input Buffer Class......Page 457 A Multiple-Token Parser......Page 459 A Language Translator......Page 466 Chapter Summary......Page 486 Exercises......Page 487 Problems......Page 491 Level 4 Operating System......Page 496 8. Process Management......Page 497 The Pep/9 Operating System......Page 498 The Pep/9 Loader......Page 501 Program Termination......Page 503 The Trap Mechanism......Page 504 The RETTR Instruction......Page 505 The Trap Handlers......Page 506 Trap Addressing Mode Assertion......Page 509 Trap Operand Address Computation......Page 511 The No-Operation Trap Handlers......Page 515 The DECI Trap Handler......Page 516 The DECO Trap Handler......Page 524 The HEXO and STRO Trap Handlers and Operating System Vectors......Page 528 Asynchronous Interrupts......Page 531 Processes in the Operating System......Page 532 Multiprocessing......Page 534 A Concurrent Processing Program......Page 535 Critical Sections......Page 538 A First Attempt at Mutual Exclusion......Page 539 A Second Attempt at Mutual Exclusions......Page 540 Peterson’s Algorithm for Mutual Exclusion......Page 542 Semaphores......Page 544 8.4 Deadlocks......Page 546 Resource Allocation Graphs......Page 547 Deadlock Policy......Page 549 Exercises......Page 550 Problems......Page 557 9.1 Memory Allocation......Page 559 Uniprogramming......Page 560 Fixed-Partition Multiprogramming......Page 561 Logical Addresses......Page 562 Variable-Partition Multiprogramming......Page 564 Paging......Page 569 Large Program Behavior......Page 572 Virtual Memory......Page 573 Demand Paging......Page 574 Page-Replacement Algorithms......Page 575 9.3 File Management......Page 578 Disk Drives......Page 579 File Abstraction......Page 580 Allocation Techniques......Page 581 Error-Detecting Codes......Page 584 Code Requirements......Page 585 Single-Error-Correcting Codes......Page 588 9.5 RAID Storage Systems......Page 591 RAID Level 1: Mirrored......Page 592 RAID Levels 01 and 10: Striped and Mirrored......Page 593 RAID Level 3: Bit-Interleaved Parity......Page 596 RAID Level 4: Block-Interleaved Parity......Page 597 RAID Level 5: Block-Interleaved Distributed Parity......Page 598 Chapter Summary......Page 599 Exercises......Page 600 Level 1 Logic Gate......Page 603 10. Combinational Circuits......Page 604 10.1 Boolean Algebra and Logic Gates......Page 605 Truth Tables......Page 606 Boolean Algebra......Page 608 Boolean Algebra Theorems......Page 610 Proving Complements......Page 611 Logic Diagrams......Page 613 Alternate Representations......Page 616 Boolean Expressions and Logic Diagrams......Page 618 Truth Tables and Boolean Expressions......Page 620 Two-Level Circuits......Page 624 The Ubiquitous NAND......Page 627 Canonical Expressions......Page 629 Three-Variable Karnaugh Maps......Page 632 Four-Variable Karnaugh Maps......Page 638 Dual Karnaugh Maps......Page 643 Don’t-Care Conditions......Page 644 Viewpoints......Page 646 Multiplexer......Page 648 Binary Decoder......Page 649 Demultiplexer......Page 651 Adder......Page 652 Adder/Subtracter......Page 655 Arithmetic Logic Unit......Page 656 Abstraction at Level LG1......Page 665 Chapter Summary......Page 666 Exercises......Page 667 11.1 Latches and Clocked Flip-Flops......Page 677 The SR Latch......Page 678 The Clocked SR Flip-Flop......Page 681 The Master–Slave SR Flip-Flop......Page 683 The Basic Flip-Flops......Page 688 The JK Flip-Flop......Page 689 The D Flip-Flop......Page 693 The T Flip-Flop......Page 694 Excitation Tables......Page 695 11.2 Sequential Analysis and Design......Page 697 A Sequential Analysis Problem......Page 698 Sequential Design......Page 702 A Sequential Design Problem......Page 703 Registers......Page 707 Buses......Page 708 Memory Subsystems......Page 710 Address Decoding......Page 715 A Two-Port Register Bank......Page 721 Chapter Summary......Page 722 Exercises......Page 723 Level 2 Microcode......Page 729 The CPU Data Section......Page 730 The von Neumann Cycle......Page 735 The Store Byte Direct Instruction......Page 741 Bus Protocols......Page 742 The Store Word Direct Instruction......Page 743 The Add Immediate Instruction......Page 745 The Load Word Indirect Instruction......Page 746 The Arithmetic Shift Right Instruction......Page 750 The CPU Control Section......Page 751 The Data Bus Width and Memory Alignment......Page 754 Memory Alignment......Page 760 The Definition of an n-Bit Computer......Page 764 Cache Memories......Page 766 The System Performance Equation......Page 776 RISC Versus CISC......Page 777 The Register Set......Page 780 The Addressing Modes......Page 782 The Instruction Set......Page 786 MIPS Computer Organization......Page 792 Pipelining......Page 798 Simplifications in the Model......Page 809 The Big Picture......Page 810 Chapter Summary......Page 811 Exercises......Page 813 Problems......Page 816 Appendix......Page 820 Solutions to Selected Exercises......Page 832 Index......Page 853 Provides a clear, detailed, step-by-step introduction to the central concepts in computer organization, assembly language, and computer architecture while aligning with the ACM/IEEE CS2013 guidelines for Systems Fundamentals. It urges students to explore the many dimensions of computer systems through a top-down approach to the 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. -- Back cover