《计算机组成与系统结构》课程参考教材：Computer Systems_A Programmer's Perspective-Pearson（THIRD EDITION，2015）

Preface xxi code/intro/hello.c #include <stdio.h> 飞 3 int main() k 5 printf("hello,world\n"); 6 return 0; code/intro/hello.c Figure 1 A typical code example. immediately to test your understanding.Solutions to the practice problems are at the end of each chapter.As you read,try to solve each problem on your own and then check the solution to make sure you are on the right track.Each chapter is followed by a set of homework problems of varying difficulty.Your instructor has the solutions to the homework problems in an instructor's manual.For each homework problem,we show a rating of the amount of effort we feelit will require: Should require just a few minutes.Little or no programming required. Might require up to 20 minutes.Often involves writing and testing some code.(Many of these are derived from problems we have given on exams.) Requires a significant effort,perhaps 1-2 hours.Generally involves writ. ing and testing a significant amount of code.. ◆◆◆◆A lab assignment,requiring up to 10 hours of effort. Each code example in the text was formatted directly,without any manual intervention,from a C program compiled with Gcc and tested on a Linux'system. Ofcourse,your system may have a different version of Gcc,or a different'compiler altogether,so your compiler might generate different machine code;but the overall behavior should be the same.All of the source code available from the CS:APP Web page ("CS:APP"being our shorthand for the book's title)at csapp .cs.cmu.edu.In the text,the filenarhes of the source programs are documnented in horizontal bars that sutround the formatted code.For example,the program in Figure 1 can be found in the file hello.c in directory code/intro/.We encourage you to try running the example programs on your system as you encounter them. To avoid having a.book that is overwhelming,both imbulk and in content,we have:created a'number of.Web asides containing material that.supplements the main presentation of the book.These asides are referenced within the book with a notation'of the form CHAR:TOP,where CHAP is a short encoding of the chapter sub- ject,and Topis,a short code fonthe topic that is covered.For example,Web Aside DATA:BOOL contains supplementary material on-Boolean algebra for the presenta- tion on data representations in Chapter 2,while Web Aside ARCH:VLOG contains

--~· ~· ------'----------~-'---'code!intro/hello.c 1' #include <st!dio.h> 2 3 int main() 4 { 5 printf("hello, world\n"); 6 return O; 7 } -------------~---------- code/introlhel/o.c Figure 1 A typical code exqmple. immeC!iately to test your understanding. Solutions t6 the practice problems are at the end of each chapter. As you read, try to solve each problem on your own and then check the solution to make sure you are on the rigll.t track. Each chapter is fallowed by a s6t of homework problems of varying difficulty. Your instructor has the solutiohs to \he h6mework p1ob!ems in an instructor's manual. For each homew9rk problem, we show a rating 6f the amount of effort we feel it will require: ' ' + Should require just a few min~t~s. Little or no programming required. ~ • ~ • .1 • ~,t MighVygui,re up, to 20 mip.utes. Often il)volves Wfili.i;ig.and ,t,esting some code. (Many of these,arq'flerived from pn1blems.we ha,ve given on exams.) +++ Requires a sjgnificant;,effort1 perhaps1-2 hours. Generally in\lolves writ￾ing and testing a significant amount of code .. ++++ A lab assignment, requiring up to 10 hours of effort. Each eode example in the te;t was formatted directly, Without any manual intervention, from a C program compile<i":ith clC<; and' tested on a Lin ID:· system. of"course, your system may have a different version of ace, or a different compiler • ' ' '<} altogether, so your compiler might generate different \fiachme code; but the overall behavior should be the same. All bf the.source code!i§' available from the CS:APP Web page ("CS:APP" being our shorthahd fot 146 book's title) at csapp .cs.cmu.edu. In the text, the filenarlies 6f the so'urce progrAhts are docuinented in horizont111 bars that sutround the formatted code. For example; the program in Figure' I can be found in the file hello. c in directory code"f intro/. We encourage yoli1o try rurming the example programs on your system as you encounter them. To avoid.having a.book that is overwhelming, both irrbulk and in content, we have:cre'ated•a'number of.w.rb asides containing matetial that.supplements the main presentatioh of1ha boolo.,These asides are referenced!Within the book with a notation'of the form CHAE:TOP, where CHAP is ashoi;~ encoding of the chapter sub- ·iect, and TOPds.a shott-cocje·fonthe topic-that is covered.·For example, Web Aside DATK.BOOL contains supplementary material on·Booleanalgebra for the presenta￾tion on data representations in Chapter 2, while Web Aside ARCH:VLOG contains Preface ,xxi

xxii Preface material describing processor designs using the Verilog hardware description lan- guage,supplementing the presentation of processor design in Chapter 4.All of these Web asides are available from the CS:APP Web page. Book Overview The CS:APP book consists of 12 chapters designed to capture the core ideas in computer systems.Here is an overview. Chapter 1:A Tour of Computer Systems.This chapter introduces the major ideas and themes in computer systems by tracing the life cycle of a simple"hello, world”program. Chapter 2:Representing and Manipulating Information.We cover computer arith- metic,emphasizing the properties of unsigned and two's-complement num- ber representations that affect programmers.We consider how numbers are represented and therefore what range of values can be encoded for a given word size.We consider the effect of casting between signed and unsigned numbers.We cover the mathematical properties of arithmetic op- erations.Novice programmers are often surprised to learn that the(two's- complement)sum or product of two positive numbers can be negative.On the other hand,two's-complement arithmetic satisfies many of the algebraic properties of integer arithmetic,and hence a compiler can safely transform multiplication by a constant into a sequence of shifts and adds.We use the bit-level operations of C to demonstrate the principles and applications of Boolean algebra.We cover the IEEE floating-point format in terms of how it represents values and the mathematical properties of floating-point oper- ations. Having a solid understanding of computer arithmetic is critical to writ- ing reliable programs.For example,programmers and compilers cannot re- place the expression (x<y)with(x-y <0),due to the possibility of overflow. They cannot even replace it with the expression (-y <-x),due to the asym- metric range of negative and positive numbers in the two's-complement representation.Arithmetic overflow is a common source of programming errors and security vulnerabilities,yet few other books cover the properties of computer arithmetic from a programmer's perspective. Chapter 3:Machine-Level Representation of Programs.We teach you how to read the x86-64 machine code generated by a C compiler.We cover the ba- sic instruction patterns generated for different control constructs,such as conditionals,loops,and switch statements.We cover the implementation of procedures,including stack allocation,register usage conventions,and parameter passing.We cover the way different data structures such as struc- tures,unions,and arrays are allocated and accessed.We cover the instruc- tions that implement both integer and floating-point arithmetic.We also use the machine-level view of programs as a way to understand common code security vulnerabilities,such as buffer overflow,and steps that the pro-

xxii Preface I,, I material describing processor designs using the Verilog hardware description lan￾guage, supplementing the presentation of processor design in Chapter 4. All of these Web asides are available from the CS:APP Web page. Book Overview The CS:APP book consists of 12 chapters designed to capture the core ideas in computer systems. Here is an overview. Chapter 1: A Tour of Computer Systems. This chapter introduces the major ideas and themes in computer systems by tracing the life cycle of a simple "hello, world" program. Chapter 2: Representing and Manipulating Information. We cover computer arith￾metic, emphasizing the properties of unsigned and two's-complement num￾ber representations that affect programmers. We consider how numbers are represented and therefore what range of values can be encoded for a given word size. We consider the effect of casting between signed and unsigned numbers. We cover the mathematical properties of arithmetic op￾erations. Novice programmers are often surprised to learn that the (two's￾complement) sum or product of two positive numbers can be negative. On the other hand, two's-complement arithmetic satisfies many of the algebraic properties of integer arithmetic, and hence a compiler can safely transform multiplication by a constant into a sequence of shifts and adds. We use the bit-level operations of C to demonstrate the principles and applications of Boolean algebra. We cover the IEEE floating-point format in terms of how it represents values and the mathematical properties of floating-point oper￾ations. Having a solid understanding of computer arithmetic is critical to writ￾ing reliable programs. For ex~ple, programmers and compilers cannot re￾place the expression (x<y) with (x-y < O), due to the possibility of overflow. They cannot even replace it with the expression (-y < -x), due to the asym￾metric range of negative and positive numbers in the two's-complement representation. Arithmetic overflow is a common source of programming errors and security vulnerabilities, yet few other books cover the properties of computer arithmetic from a programmer's perspective. Chapter 3: Machine-Level Representation of Programs. We teach you how to read the x86-64 machine code generated by a C compiler. We cover the ba￾sic instruction patterns generated for different control constructs, such as conditionals, loops, and switch statements. We cover the implementation of procedures, including stack allocation, register usage convention~, and parameter passing. We cover the way different data structures such as struc￾tures, unions, and arrays are allocated and accessed. We cover the instruc￾tions that implement both integer and floating-point arithmetic. We also use the machine-level view of programs as a way to understand common code se~urity vulnerabilities, such as buffer overflow, and steps that the pro-

Preface xxili AsideWhat is,an aside? 度深T:”公空龙客到年“女 You will encounter asides ofthis form'throughoutthe.text Asides parenithetical remarks that give you some additional insight into the current-topic,Asides servea number of purposes.Some are little -history lessons.For example,where did C Linux and the Internet come from?Other asides are meant toclarify ideas that students often find confusing For example whatis the difference between a cache lifie,set,and block?Other asides give real-world examples,such as how a floating-point error crashed a French Focket or the geometric and operational patameters of a commercial disk drive.Finally,some asides are just fun'stuff.For example;whatsisa"hoinky A 4de,生。好。心 药 grammer,the compiler,and the operating system can take to reduce these threats.Learning the concepts in this chapter helps you become a better programmer,because you will understand how programs are represented on a machine.One certain benefit is that you will develop a thorough and concrete understanding of pointers. Chapter 4:Processor Architecture.This chapter covers basic combinational and sequential logic elements,and then shows how these elements can be com- bined in a datapath that executes a simplified subset of the x86-64 instruction set called "Y86-64."We begin with the design of a single-cycle datapath This design is conceptually very simple,but it would not be very fast.We then introduce pipelining,where the different steps required to process an instruction are implemented as separate stages.At any given.time,each stage can work on a different instruction.Our five:stage processor pipeline is much more realistic.The control logic for the processor designs is described using a simple hardware description language called HCL.Hardware de- signs written in HCL can be compiled and linked into simulators provided with the textbook,and they can be used to generate Verilog descriptions suitable for synthesis into working hardware. Chapter 5:Optimizing Program Performance.This chapter introduces a number of techniques for improving code performance,with the idea being that pro- grammers learn to write their Ccode in such,a way that a compiler can then generate efficient machine code.We start with transformations that reduce the work to be done by a program and hence should be standard practice when writing any program for any machine.We then progress to trans- formations that enhance the degree of instruction-level parallelism in the generated machine code,thereby improving their performance on modern superscalar"processors.To motivate these transformations,we introduce a simple operational model of how modern out-of-order processors work, and show how to measure the potential performance of a program in terms of the critical paths through a graphical representation of a program.You will be surprised how much you can speed up a program by simple transfor- mations of the C code

grammer, the compiler, and the operating system can take to reduce these threats. Learning the concepts in this chapter helps you become a better programmer, because you will understand how programs are represented on a machine. One certain benefit is that you·will develop a thorough and concrete understanding of pointers. Chapter 4: Processor Architecture. This chapter covers basic combinational and sequential logic elements, and then shows how these elements, can be com￾bined in a data path that executes a simplified subset of the x86-64 instruction set called "Y86-64." We begin with the design of a single-cycle datapath. This design is conceptually very simple, but it would not be very fast. We then introduce pipelining, where the different steps required to process an instruction are implemented as separate stages. At any given.time, each stage can work on a different instruction. Ol!r five,stage processor pipeline is much more realistic. The control logic for the processor designs is described using a simple hardware description language called HCL. Hardware de￾signs written in HCL can be compiled and linked into· simulators provided with the textbook, and they can be used to generate Verilog descriptions suitable for synthesis into working hardware. Chapter 5: Qptimizing fro gram Performance. This chapter introduces a number of techniques for improving code performance, with the idea being that pro￾grammers leafll to write their C code in such.a way that a compiler can then generate efficient maGhine, code. We start wiih transformations that reduce the work to be dope qy ,a program and,Q7ncl' ~hould be standar,d practice when writing any program for any machine. We then progress to trans￾formations that enhance the degree of instruction-le~el parallelism in the generated machine code, thereby improving their performance on modern "superscalar" processors. To motivate these transformations, we introduce a simple operational model of how modern out-of-order processors work, and show how to measure the potential performance of a program in terms of the critical paths through a graphical representation of a program. You will be surprised how much you can speed up a program by simple transfor￾mations of the C code. Preface xxiii

xxiv Preface Chapter 6:The Memory Hierarchy.The memory system is one of the most visible parts of a computer system to application programmers.To this point,you have relied on a conceptual model of the memory system as a linear array with uniform access times.In practice,a memory system is a hierarchy of storage devices with different capacities,costs,and access times.We cover the different types of RAM and ROM memories and the geometry and organization of magnetic-disk and.solid state drives.We describe how these storage devices are arranged in a hierarchy.We show how this hierarchy is made possible by locality of reference.We make these ideas concrete by introducing a unique view of a memory system as a"memory mountain" with ridges of temporal locality and slopes of spatial locality.Finally,we show you how to improve the performance of application programs by improving their temporal and spatial locality. Chapter 7:Linking.This chapter covers both static and dynamic linking,including the ideas of relocatable and executable object files,symbol resolution,re- location,static libraries,shared object libraries,position-independent code, and library interpositioning.Linking is not covered in most systems texts, but we cover it for two reasons.First,some of the most confusing errors that programmers can encounter are related to glitches during linking,especially for large software packages.Second,the object files produced by linkers are tied to concepts such as loading,virtual memory,and memory mapping. Chapter 8:Exceptional Control Flow.In this part of the presentation,we step beyond the single-program model by introducing the general concept of exceptional control flow (i.e.,changes in control flow that are outside the normal branches and procedure calls).We cover examples of exceptional control flow that exist at alllevels of the system,from low-level hardware ex- ceptions and interrupts,to context switches between concurrent processes, to abrupt changes in control flow caused by the receipt of Linux signals,to the nonlocal jumps in C that break the stack discipline. This is the part of the book where we introduce the fundamental idea of a process,an abstraction of an executing program.You will learn how processes work and how they can be created and manipulated from appli- cation programs.We show how application programmers can make use of multiple processes via Linux system calls.When you finish this chapter,you will be able to write a simple Linux shell with job control.It is also your first introduction to the nondeterministic behavior that arises with concurrent program execution. Chapter 9:Virtual Memory.Our presentation of the virtual memory system seeks to give some understanding of how it works and its characteristics.We want you to know how it is that the different simultaneous processes can each use an identical range of addresses,sharing some pages but having individual copies of others.We also cover issues involved in managing and manip- ulating virtual memory.In particular,we cover the operation of storage allocators such as the standard-library malloc and free operations.Cov-

xxiv Preface i 11 t ,,, Chapter 6: The Memory Hierarchy. The memory system is one of the most visible parts of a computer system to application programmers. To this point, you have relied on a conceptual model of the memory system as a linear array with uniform access times. In practice, a memory system is a hierarchy of storage devices with different capacities, costs, and access times. We cover the different types of RAM and ROM memories and the geometry and organization of magnetic-disk and.solid state drives. We describe how these storage devices are arranged in a hierarchy. We show how this hierarchy is made possible by locality of reference. We make these ideas concrete by introducing a unique view of a memory system as a "memory mountain" with ridges of temporal locality and slopes of spatial locality. Finally, we show you how to improve the performance of application programs by improving their temporal and spatial locality. Chapter Z· Linking. This chapter covers both static and dynamic linking, including the ideas of relocatable and executable object files, symbol resolution, re￾location, static libraries, shared object libraries, position-independent code, and library interpositioning. Linking is not covered in most systems texts, but we cover it for two reasons. First, some of the most confusing errors that programmers can enc9unter are related to glitches during linking, especially for large software packages. Second, the object files produced by linkers are tied to concepts such as loading, virtual memory, and memory mapping. I Chapter 8: Exceptional Control Flow. In this part of the presentation, we step beyond the single-program model by introducing the general concept of exceptional control flow (i.e., changes in control flow that are outside the normal branches and procedure calls). We cover examples of exceptional control flow that exist at all levels of the system, from low-level hardware ex￾ceptions and interrupts, to context switches between concurrent processes, to abrupt changes in control flow caused by the receipt of Linux signals, to the nonlocal jumps in C that break the stack discipline. This is the part of the book where we introduce the fundamental idea of a process, an abstraction of an executing program. You will learn how processes work and how they can l:le created and manipulated from appli￾cation programs. We show how application programmers can make use of multiple processes via Linux system calls. When you finish this chapter, you will be able to write a simple Linux shell with job control. It is also your first introduction to the nondeterministic behavior that arises with concurrent program execution. Chapter 9: Virtual Memory. Our presentation of the virtual memory system seeks to give some understanding of how it works and its characteristics. We want you to know how it is that the different simultaneous processes can each use an identical range of addresses, sharing some pages but having individual copies of others. We also cover issues involved in managing and manip￾ulating virtual memory. In particular, we cover the operation of storage allocators such as the standard-library malloc and free operations. Cov-

Preface xxv ering this material serves several purposes.It reinforces the concept that the virtual memory space is just an array of bytes that the program can subdivide into different storage units.It helps you understand the effects of programs containing memory referencing errors such as storage leaks and invalid pointer references.Finally,many application programmers write their own storage allocators optimized toward the needs and characteris- tics of the application.This chapter,more than any other,demonstrates the benefit of covering both the hardware and the software aspects'of computer systems in a unified way.Traditional computer architecture and operating systems texts present only part of the virtual memory story. Chapter 10:System-Level 1/O.We cover the basic concepts of Unix I/O such as files and descriptors.We describe how files are shared,how I/O redirection works,and how to access file metadata.We also develop a robust buffered I/O package that deals correctly with a curious behavior known as.short counts,where the library function reads only part of the input data.We cover the C standard I/O library and its relationship to Linux I/O,focusing on limitations of standard I/O that make it unsuitable for network program- ming.In general,the topics covered in this'chapter are building blocks for the next two chapters on network and concurrent programming. Chapter 11,Network Programming.Networks are interesting I/O devices to pro- gram,tying together many of the ideas that we study earlier in the text,such as processes,signals,byte ordering,memory mapping,and dynamic storage allocation.Network prograims also provide a compelling context for con- currency,which is the topie of the next chapter.This chapter is a thin slice through network programming that'gets you to the point where you can write'a simple Web server.We cover the client-server model that underlies all network applications.We present a programmer's view of the Internet and show how to write Internet clients and servers using the sockets inter- face.Finally,we introduce HTTP and develop a simple iterative Web server. Chapter 12:Concurrent Programming.This chapter introduces concurrent pro- gramming using Internet'server design as the runifing motivational'example. We compare and contrast the three basic mechanisms for writing concur- rent programsprocesses,I/O multiplexing,and threads-and show how to use them to build concurrent Internet servers.We cover basic principles of synchronization,using P and V semaphore operations,thread safety and reentrancy,race conditions,and deadlocks.Writing concurrent code is es- sential for most server applications.We also describe the use of thread-level programming to express parallelism in,an application program,enabling faster execution on multi-core processors.Getting all of the'cores working on a single computational problem requires a.careful coordination of the concurrent threads,both for correctness and to achieve high performance

ering this material serves several purposes. It reinforces the concept that the virtual memory spac~ is just an array of bytes that the program can subdivide info different storage units. It helps you understand thy effects of programs containing memory referencing errors such as storage leaks an'a invalid pointer references. Ffnaliy;many a~plication programmers write 'their own' storage allocators optimized toward the needs and characteris￾tics of the application. This chapter, more than any other, dem8nstrates the benefit of covering lioth the'hardw'are and the foftware aspec:ts'bf computer systems in a unified way. Traditional computer architecture and operating systems texts present only part of the virtual memory story. Chapter 10: System-Level 110. We cover the basic concepts of Unix I/O such as files and descriptors. We describe how files are shared, how I/O redirection works, and how to access file metadata. We also develop a robust buffered I/O package that deals coqect)y with a curious behavior known as. s/iort counts, where the library function reads only parb of the iµput data. We cover the C standard I/O lib~ary and its relationship to Linux I/O, focusing on limitations of standard I/O that make it unsuitable fbr'network program￾ming. In .general, the topics covered in this'chapter are-building blocks for 'the next two c)lapters on network and concurrent programming . .... t ~ • ' Chapter JJ; Network Programming. Networks are interesting I/O clevices to pro￾gram, tying together many of the ideas that we study earlier in'the text, such as processes, signals, byte ordering, memory mapping, and dynamic storage allocation. Net)V6fk programs also provide a -compelling context for con￾currerlc~, which is the topic of the next chapfe'r. 'This chapter' is· a thin slice through network programmin'_g that' gets you to the' pbilli wbere you can w'rite'a simple Web server. We cover tlie client-server model that underlies all network applications. We preselit a programmer's view of the Internet and show how to write Internet clients 'ahll servers using the sockets inter￾face. Finally, we introduce HTTP and develop a simple iterative Web server. Chapter 12: Concurrent Programming. This cha'pt'er iniroduces concurrent pro￾gramming using Internet'sei:ver design as the tunifing motivational·example. We compare and contrast the three basic mechanisms for writing concur￾rent programs-;;P,rocesses'II/O multiplexing, al\d thread,s-al).d sh9w how to use them to build concurrent Intyrn~t servers. We cover basic principles of synchr0nization,usipg P and y semaphore opera,tions,,thrp,ad safety and , ,. reyntrancy, race condition~, and deadloc,ks. Writing concur,rent code is es￾sential for mo~t server appl1cations. We also nescribe the use of thread-level IJ I ror"l'Jit I { '} programming to express parallelism in.an applicatiop.,.pro!f~m, enabling faster execution on multi-core processors. Getting all of the cores working on a single computational P.roblem requires a. careful coordination of the concurrent threads, both fo; correctness and to achieve high performance. Preface xxv