پیکان کوشیل

For Computer Organization and Architecture and Computer Systems courses in CS and EE and ECE departments. Developed out of an introductory course at Carnegie Mellon University, this text explains the important and enduring concepts underlying all computer systems, and shows the concrete ways that these ideas affect the correctness, performance, and utility of application programs. The text's concrete and hands-on approach will help students understand what is going on "under the hood" of a computer system. Few students studying computer science or computer engineering will ever have the opportunity to build a computer system. On the other hand, most students will be required to use and program computers on a near daily basis. 'Computer Systems' introduces the important and enduring concepts that underlie application programs. Front Cover 1 Dedication 6 Contents 8 Preface 20 About the Authors 36 Chapter 1: A Tour of Computer Systems 38 1.1: Information Is Bits + Context 40 1.2: Programs Are Translated by Other Programs into Different Forms 41 1.3: It Pays to Understand How Compilation Systems Work 43 1.4: Processors Read and Interpret Instructions Stored in Memory 44 1.4.1: Hardware Organization of a System 45 1.4.2: Running the hello Program 47 1.5: Caches Matter 48 1.6: Storage Devices Form a Hierarchy 51 1.7: The Operating System Manages the Hardware 51 1.7.1: Processes 52 1.7.2: Threads 54 1.7.3: Virtual Memory 55 1.7.4: Files 56 1.8: Systems Communicate with Other Systems Using Networks 56 1.9: Important Themes 59 1.9.1: Amdahl’s Law 59 1.9.2: Concurrency and Parallelism 61 1.9.3: The Importance of Abstractions in Computer Systems 63 1.10: Summary 64 Bibliographic Notes 65 Solutions to Practice Problems 65 Part I: Program Structure and Execution 66 Chapter 2: Representing and Manipulating Information 68 2.1: Information Storage 71 2.1.1: Hexadecimal Notation 73 2.1.2: Data Sizes 76 2.1.3: Addressing and Byte Ordering 79 2.1.4: Representing Strings 86 2.1.5: Representing Code 86 2.1.6: Introduction to Boolean Algebra 87 2.1.7: Bit-Level Operations in C 91 2.1.8: Logical Operations in C 93 2.1.9: Shift Operations in C 94 2.2: Integer Representations 96 2.2.1: Integral Data Types 97 2.2.2: Unsigned Encodings 99 2.2.3: Two’s-Complement Encodings 101 2.2.4: Conversions between Signed and Unsigned 107 2.2.5: Signed versus Unsigned in C 111 2.2.6: Expanding the Bit Representation of a Number 113 2.2.7: Truncating Numbers 118 2.2.8: Advice on Signed versus Unsigned 120 2.3: Integer Arithmetic 121 2.3.1: Unsigned Addition 121 2.3.2: Two’s-Complement Addition 127 2.3.3: Two’s-Complement Negation 132 2.3.4: Unsigned Multiplication 133 2.3.5: Two’s-Complement Multiplication 134 2.3.6: Multiplying by Constant 138 2.3.7: Dividing by Powers of 2 140 2.3.8: Final Thoughts on Integer Arithmetic 144 2.4: Floating Point 145 2.4.1: Fractional Binary Numbers 146 2.4.2: IEEE Floating-Point Representation 149 2.4.3: Example Numbers 152 2.4.4: Rounding 157 2.4.5: Floating-Point Operations 159 2.4.6: Floating Point in C 161 2.5: Summary 163 Bibliographic Notes 164 Homework Problems 165 Solutions to Practice Problems 180 Chapter 3: Machine-Level Representation of Program 200 3.1: A Historical Perspective 203 3.2: Program Encodings 206 3.2.1: Machine-Level Code 207 3.2.2: Code Examples 209 3.2.3: Notes on Formatting 212 3.3: Data Formats 214 3.4: Accessing Information 216 3.4.1: Operand Specifiers 217 3.4.2: Data Movement Instructions 219 3.4.3: Data Movement Example 223 3.4.4: Pushing and Popping Stack Data 226 3.5: Arithmetic and Logical Operations 228 3.5.1: Load Effective Address 228 3.5.2: Unary and Binary Operations 231 3.5.3: Shift Operations 231 3.5.4: Discussion 233 3.5.5: Special Arithmetic Operations 234 3.6: Control 237 3.6.1: Condition Codes 238 3.6.2: Accessing the Condition Codes 239 3.6.3: Jump Instructions 242 3.6.4: Jump Instruction Encodings 244 3.6.5: Implementing Conditional Branches with Conditional Control 246 3.6.6: Implementing Conditional Branches with Conditional Moves 251 3.6.7: Loop 257 3.6.8: Switch Statements 269 3.7: Procedures 275 3.7.1: The Run-Time Stack 276 3.7.2: Control Transfer 278 3.7.3: Data Transfer 282 3.7.4: Local Storage on the Stack 285 3.7.5: Local Storage in Registers 286 3.7.6: Recursive Procedures 290 3.8: Array Allocation and Access 292 3.8.1: Basic Principles 292 3.8.2: Pointer Arithmetic 294 3.8.3: Nested Arrays 295 3.8.4: Fixed-Size Arrays 297 3.8.5: Variable-Size Arrays 299 3.9: Heterogeneous Data Structure 302 3.9.1: Structures 302 3.9.2: Unions 306 3.9.3: Data Alignment 310 3.10: Combining Control and Data in Machine-Level Programs 313 3.10.1: Understanding Pointers 314 3.10.2: Life in the RealWorld: Using the GDB Debugger 316 3.10.3: Out-of-Bounds Memory References and Buffer Overflow 316 3.10.4: Thwarting Buffer Overflow Attacks 321 3.10.5: Supporting Variable-Size Stack Frames 327 3.11: Floating-Point Code 330 3.11.1: Floating-Point Movement and Conversion Operations 333 3.11.2: Floating-Point Code in Procedures 338 3.11.3: Floating-Point Arithmetic Operations 339 3.11.4: Defining and Using Floating-Point Constants 341 3.11.5: Using Bitwise Operations in Floating-Point Code 342 3.11.6: Floating-Point Comparison Operations 343 3.11.7: Observations about Floating-Point Code 346 3.12: Summary 346 Bibliographic Notes 347 Homework Problems 348 Solutions to Practice Problems 362 Chapter 4: Processor Architecture 388 4.1: The Y86-64 Instruction Set Architecture 392 4.1.1: Programmer-Visible State 392 4.1.2: Y86-64 Instructions 393 4.1.3: Instruction Encoding 395 4.1.4: Y86-64 Exceptions 400 4.1.5: Y86-64 Programs 401 4.1.6: Some Y86-64 Instruction Details 407 4.2: Logic Design and the Hardware Control Language HCL 409 4.2.1: Logic Gates 410 4.2.2: Combinational Circuits and HCL Boolean Expressions 411 4.2.3: Word-Level Combinational Circuits and HCL Integer Expressions 413 4.2.4: Set Membership 417 4.2.5: Memory and Clocking 418 4.3: Sequential Y86-64 Implementations 421 4.3.1: Organizing Processing into Stages 421 4.3.2: SEQ Hardware Structure 433 4.3.3: SEQ Timing 437 4.3.4: SEQ Stage Implementations 441 4.4: General Principles of Pipelining 449 4.4.1: Computational Pipelines 449 4.4.2: A Detailed Look at Pipeline Operation 451 4.4.3: Limitations of Pipelining 453 4.4.4: Pipelining a System with Feedback 456 4.5: Pipelined Y86-64 Implementations 458 4.5.1: SEQ+: Rearranging the Computation Stages 458 4.5.2: Inserting Pipeline Registers 459 4.5.3: Rearranging and Relabeling Signals 463 4.5.4: Next PC Prediction 464 4.5.5: Pipeline Hazards 466 4.5.6: Exception Handling 481 4.5.7: PIPE Stage Implementations 484 4.5.8: Pipeline Control Logic 492 4.5.9: Performance Analysis 501 4.5.10: Unfinished Business 505 4.6: Summary 507 4.6.1: Y86-64 Simulators 509 Bibliographic Notes 510 Homework Problems 510 Solutions to Practice Problems 517 Chapter 5: Optimizing Program Performance 532 5.1: Capabilities and Limitations of Optimizing Compilers 535 5.2: Expressing Program Performance 539 5.3: Program Example 541 5.4: Eliminating Loop Inefficiencies 545 5.5: Reducing Procedure Calls 549 5.6: Eliminating Unneeded Memory References 551 5.7: Understanding Modern Processors 554 5.7.1: Overall Operation 555 5.7.2: Functional Unit Performance 560 5.7.3: An Abstract Model of Processor Operation 562 5.8: Loop Unrolling 568 5.9: Enhancing Parallelism 573 5.9.1: Multiple Accumulators 573 5.9.2: Reassociation Transformation 578 5.10: Summary of Results for Optimizing Combining Code 584 5.11: Some Limiting Factors 585 5.11.1: Register Spilling 585 5.11.2: Branch Prediction and Misprediction Penalties 586 5.12: Understanding Memory Performance 590 5.12.1: Load Performance 591 5.12.2: Store Performance 592 5.13: Life in the Real World: Performance Improvement Techniques 598 5.14: Identifying and Eliminating Performance Bottlenecks 599 5.14.1: Program Profiling 599 5.14.2: Using a Profiler to Guide Optimization 602 5.15: Summary 605 Bibliographic Notes 606 Homework Problems 607 Solutions to Practice Problems 610 Chapter 6: The Memory Hierarchy 616 6.1: Storage Technologie 618 6.1.1: Random Access Memory 618 6.1.2: Disk Storage 626 6.1.3: Solid State Disks 637 6.1.4: Storage Technology Trends 639 6.2: Locality 641 6.2.1: Locality of References to Program Data 643 6.2.2: Locality of Instruction Fetches 644 6.2.3: Summary of Locality 645 6.3: The Memory Hierarchy 646 6.3.1: Caching in the Memory Hierarchy 647 6.3.2: Summary of Memory Hierarchy Concepts 651 6.4: Cache Memories 651 6.4.1: Generic Cache Memory Organization 652 6.4.2: Direct-Mapped Caches 654 6.4.3: Set Associative Caches 661 6.4.4: Fully Associative Caches 663 6.4.5: Issues with Writes 667 6.4.6: Anatomy of a Real Cache Hierarchy 668 6.4.7: Performance Impact of Cache Parameters 668 6.5: Writing Cache-Friendly Code 670 6.6: Putting It Together: The Impact of Caches on Program Performance 676 6.6.1: The Memory Mountain 676 6.6.2: Rearranging Loops to Increase Spatial Locality 680 6.6.3: Exploiting Locality in Your Programs 684 6.7: Summary 685 Bibliographic Notes 685 Homework Problems 686 Solutions to Practice Problems 697 Part II: Running Programs on a System 704 Chapter 7: Linking 706 7.1: Compiler Drivers 708 7.2: Static Linking 709 7.3: Object Files 710 7.4: Relocatable Object Files 711 7.5: Symbols and Symbol Tables 712 7.6: Symbol Resolution 716 7.6.1: How Linkers Resolve Duplicate Symbol Names 717 7.6.2: Linking with Static Libraries 721 7.6.3: How Linkers Use Static Libraries to Resolve References 725 7.7: Relocation 726 7.7.1: Relocation Entries 727 7.7.2: Relocating Symbol References 728 7.8: Executable Object Files 732 7.9: Loading Executable Object Files 734 7.10: Dynamic Linking with Shared Libraries 735 7.11: Loading and Linking Shared Libraries from Applications 738 7.12: Position-Independent Code (PIC) 741 7.13: Library Interpositioning 744 7.13.1: Compile-Time Interpositioning 745 7.13.2: Link-Time Interpositioning 745 7.13.3: Run-Time Interpositioning 747 7.14: Tools for Manipulating Object Files 750 7.15: Summary 750 Bibliographic Notes 751 Homework Problems 751 Solutions to Practice Problems 754 Chapter 8: Exceptional Control Flow 758 8.1: Exceptions 760 8.1.1: Exception Handling 761 8.1.2: Classes of Exceptions 763 8.1.3: Exceptions in Linux/x86-64 Systems 766 8.2: Processes 769 8.2.1: Logical Control Flow 769 8.2.2: Concurrent Flows 770 8.2.3: Private Address Space 771 8.2.4: User and Kernel Modes 771 8.2.5: Context Switches 773 8.3: System Call Error Handling 774 8.4: Process Control 775 8.4.1: Obtaining Process IDs 776 8.4.2: Creating and Terminating Processes 776 8.4.3: Reaping Child Processes 780 8.4.4: Putting Processes to Sleep 786 8.4.5: Loading and Running Programs 787 8.4.6: Using fork and execve to Run Programs 790 8.5: Signals 793 8.5.1: Signal Terminology 795 8.5.2: Sending Signals 796 8.5.3: Receiving Signals 799 8.5.4: Blocking and Unblocking Signals 801 8.5.5: Writing Signal Handlers 803 8.5.6: Synchronizing Flows to Avoid Nasty Concurrency Bugs 813 8.5.7: ExplicitlyWaiting for Signals 815 8.6: Nonlocal Jumps 818 8.7: Tools for Manipulating Processes 823 8.8: Summary 824 Bibliographic Notes 824 Homework Problems 825 Solutions to Practice Problems 832 Chapter 9: Virtual Memory 838 9.1: Physical and Virtual Addressing 840 9.2: Address Spaces 841 9.3: VM as a Tool for Caching 842 9.3.1: DRAM Cache Organization 843 9.3.2: Page Tables 843 9.3.3: Page Hits 845 9.3.4: Page Faults 845 9.3.5: Allocating Pages 847 9.3.6: Locality to the Rescue Again 847 9.4: VM as a Tool for Memory Management 848 9.5: VM as a Tool for Memory Protection 849 9.6: Address Translation 850 9.6.1: Integrating Caches and VM 854 9.6.2: Speeding Up Address Translation with a TLB 854 9.6.3: Multi-Level Page Tables 856 9.6.4: Putting It Together: End-to-End Address Translation 858 9.7: Case Study: The Intel Core i7/Linux Memory System 862 9.7.1: Core i7 Address Translation 863 9.7.2: Linux Virtual Memory System 865 9.8: Memory Mapping 870 9.8.1: Shared Objects Revisited 870 9.8.2: The fork Function Revisited 873 9.8.3: The execve Function Revisited 873 9.8.4: User-Level Memory Mapping with the mmap Function 874 9.9: Dynamic Memory Allocation 876 9.9.1: The malloc and free Functions 877 9.9.2: Why Dynamic Memory Allocation? 880 9.9.3: Allocator Requirements and Goals 881 9.9.4: Fragmentation 883 9.9.5: Implementation Issues 883 9.9.6: Implicit Free Lists 884 9.9.7: Placing Allocated Blocks 886 9.9.8: Splitting Free Blocks 886 9.9.9: Getting Additional Heap Memory 887 9.9.10: Coalescing Free Blocks 887 9.9.11: Coalescing with Boundary Tags 888 9.9.12: Putting It Together: Implementing a Simple Allocator 891 9.9.13: Explicit Free Lists 899 9.9.14: Segregated Free Lists 900 9.10: Garbage Collection 902 9.10.1: Garbage Collector Basics 903 9.10.2: Mark&Sweep Garbage Collectors 904 9.10.3: Conservative Mark&Sweep for C Programs 906 9.11: Common Memory-Related Bugs in C Programs 907 9.11.1: Dereferencing Bad Pointers 907 9.11.2: Reading Uninitialized Memory 908 9.11.3: Allowing Stack Buffer Overflows 908 9.11.4: Assuming That Pointers and the Objects They Point to Are the Same Size 909 9.11.5: Making Off-by-One Errors 909 9.11.6: Referencing a Pointer Instead of the Object It Points To 910 9.11.7: Misunderstanding Pointer Arithmetic 910 9.11.8: Referencing Nonexistent Variables 911 9.11.9: Referencing Data in Free Heap Blocks 911 9.11.10: Introducing Memory Leaks 912 9.12: Summary 912 Bibliographic Notes 913 Homework Problems 913 Solutions to Practice Problems 917 Part III: Interaction and Communication between Programs 924 Chapter 10: System-Level I/O 926 10.1: Unix I/O 927 10.2: Files 928 10.3: Opening and Closing Files 930 10.4: Reading and Writing Files 932 10.5: Robust Reading and Writing with the Rio Package 934 10.5.1: Rio Unbuffered Input and Output Functions 934 10.5.2: Rio Buffered Input Functions 935 10.6: Reading File Metadata 940 10.7: Reading Directory Contents 942 10.8: Sharing Files 943 10.9: I/O Redirection 946 10.10: Standard I/O 948 10.11: Putting It Together: Which I/O Functions Should I Use? 948 10.12: Summary 950 Bibliographic Notes 951 Homework Problems 951 Solutions to Practice Problems 952 Chapter 11: Network Programming 954 11.1: The Client-Server Programming Model 955 11.2: Networks 956 11.3: The Global IP Internet 961 11.3.1: IP Addresses 962 11.3.2: Internet Domain Names 964 11.3.3: Internet Connections 966 11.4: The Sockets Interface 969 11.4.1: Socket Address Structures 970 11.4.2: The socket Function 971 11.4.3: The connect Function 971 11.4.4: The bind Function 972 11.4.5: The listen Function 972 11.4.6: The accept Function 973 11.4.7: Host and Service Conversion 974 11.4.8: Helper Functions for the Sockets Interface 979 11.4.9: Example Echo Client and Server 981 11.5: Web Servers 985 11.5.1: Web Basics 985 11.5.2: Web Content 986 11.5.3: HTTP Transactions 987 11.5.4: Serving Dynamic Content 990 11.6: Putting It Together: The Tiny Web Server 993 11.7: Summary 1001 Bibliographic Notes 1002 Homework Problems 1002 Solutions to Practice Problems 1003 Chapter 12: Concurrent Programming 1008 12.1: Concurrent Programming with Processes 1010 12.1.1: A Concurrent Server Based on Processes 1011 12.1.2: Pros and Cons of Processes 1012 12.2: Concurrent Programming with I/O Multiplexing 1014 12.2.1: A Concurrent Event-Driven Server Based on I/O Multiplexing 1017 12.2.2: Pros and Cons of I/O Multiplexing 1022 12.3: Concurrent Programming with Threads 1022 12.3.1: Thread Execution Model 1023 12.3.2: Posix Threads 1024 12.3.3: Creating Threads 1025 12.3.4: Terminating Threads 1025 12.3.5: Reaping Terminated Threads 1026 12.3.6: Detaching Threads 1026 12.3.7: Initializing Threads 1027 12.3.8: A Concurrent Server Based on Threads 1028 12.4: Shared Variables in Threaded Programs 1029 12.4.1: Threads Memory Model 1030 12.4.2: Mapping Variables to Memory 1031 12.4.3: Shared Variables 1032 12.5: Synchronizing Threads with Semaphores 1032 12.5.1: Progress Graphs 1036 12.5.2: Semaphores 1038 12.5.3: Using Semaphores for Mutual Exclusion 1039 12.5.4: Using Semaphores to Schedule Shared Resources 1041 12.5.5: Putting It Together: A Concurrent Server Based on Prethreading 1045 12.6: Using Threads for Parallelism 1050 12.7: Other Concurrency Issues 1057 12.7.1: Thread Safety 1057 12.7.2: Reentrancy 1060 12.7.3: Using Existing Library Functions in Threaded Programs 1061 12.7.4: Races 1062 12.7.5: Deadlocks 1064 12.8: Summary 1067 Bibliographic Notes 1067 Homework Problems 1068 Solutions to Practice Problems 1073 Appendix A: Error Handling 1078 A.1: Error Handling in Unix Systems 1079 A.2: Error-Handling Wrappers 1080 References 1084 Index 1090 Back Cover 1122 For courses in Computer Science and Programming Computer systems: A Programmer's Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer's perspective, this book strives to teach students how understanding basic elements of computer systems and executing real practice can lead them to create better programs. Spanning across computer science themes such as hardware architecture, the operating system, and systems software, the Third Edition serves as a comprehensive introduction to programming. This book strives to create programmers who understand all elements of computer systems and will be able to engage in any application of the field--from fixing faulty software, to writing more capable programs, to avoiding common flaws. It lays the groundwork for students to delve into more intensive topics such as computer architecture, embedded systems, and cybersecurity. This book focuses on systems that execute an x86-64 machine code, and recommends that students have access to a Linux system for this course. Students should have basic familiarity with C or C++. MasteringEngineering(R) not included. Students, if MasteringEngineering is a recommended/mandatory component of the course, please ask your instructor for the correct ISBN and course ID. MasteringEngineering should only be purchased when required by an instructor. Instructors, contact your Pearson representative for more information. MasteringEngineering is an online homework, tutorial, and assessment product designed to personalize learning and improve results. With a wide range of interactive, engaging, and assignable activities, students are encouraged to actively learn and retain tough course concepts For courses in Computer Science and Programming Computer systems: A Programmer's Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer's perspective, this book strives to teach students how understanding basic elements of computer systems and executing real practice can lead them to create better programs. Spanning across computer science themes such as hardware architecture, the operating system, and systems software, the 3rd Edition serves as a comprehensive introduction to programming. This book strives to create programmers who understand all elements of computer systems and will be able to engage in any application of the field--from fixing faulty software, to writing more capable programs, to avoiding common flaws. It lays the groundwork for students to delve into more intensive topics such as computer architecture, embedded systems, and cybersecurity. This book focuses on systems that execute an x86-64 machine code, and recommends that students have access to a Linux system for this course. Students should have basic familiarity with C or C++. The full text downloaded to your computer With eBooks you can: search for key concepts, words and phrases make highlights and notes as you study share your notes with friends eBooks are downloaded to your computer and accessible either offline through the Bookshelf (available as a free download), available online and also via the iPad and Android apps. Upon purchase, you'll gain instant access to this eBook. Time limit The eBooks products do not have an expiry date. You will continue to access your digital ebook products whilst you have your Bookshelf installed.