Welcome to “Algorithms and the Beauty of Programming” ↑ pay attention to us!
This article was first published on the wechat official account “Beauty of Algorithms and Programming”. Welcome to follow and learn more about this series of blogs in time.
This book is a book we highly recommend, written very very good, if the English foundation is better, you can directly read the original English.
The book is called “a treasure trove of priceless resources worth more than their weight in gold”;
This book has been used as a textbook by computer science majors at more than 80 leading universities in the United States and the world.
Low starting point, wide coverage, suitable for junior and senior undergraduates; A good programmer must understand the underlying operations, architecture, and operating systems, and this book is a good place to start.
If you are in school, and if you have completed composition principles and architecture, it is highly recommended that you read this book. This is a really good book, and I have no reason not to applaud this book. It would be great if computer students could follow this book as a textbook. Read this book you will have a fundamental understanding of computer principles, assembly language and C language. This book is so well written! Concepts that I did not understand in many places are clearly and accurately explained in this book. Each concept is simple but gets to the point. The classic of the classics. Anyone who writes code should buy one.
A particularly good book, especially for college students. The whole knowledge system is very perfect, related elaboration is also from shallow to deep, fine!
The book, CS:APP for short, is aimed at computer scientists, computer engineers, and anyone who wants to write better programs by learning the inner workings of computer systems.
Our goal is to explain the essential concepts of all computer systems and show you how these concepts really affect the correctness, performance, and usefulness of your applications. Other systems books are written from a builder’s point of view, describing how to implement hardware or system software, including operating systems, compilers, and network interfaces. This book is written from a programmer’s point of view, showing how application programmers can use their knowledge of systems to write better programs. Of course, learning what a computer system should do is a good starting point for learning how to build one, so this book is also a valuable introduction for anyone who wishes to continue learning about the hardware and software implementation of a system. Most systems books also tend to focus on one aspect of the system, such as hardware architecture, operating system, compiler, or network.
This book covers all of these aspects from a programmer’s point of view. If you research and grasp the concepts in this book, you will begin to become one of the few “awesome people” who know how things work and how to fix things when they go wrong. Your programs will be able to take better advantage of the capabilities offered by the operating system and system software, operate correctly for a variety of operating conditions and runtime parameters, run faster, and avoid bugs that make your programs vulnerable to cyber attacks. At the same time, be prepared to delve deeper into such advanced topics as compilers, computer architecture, operating systems, embedded systems, network interconnection, and network security.
The following is the table of contents:
preface
About the author
Chapter 1 Computer System Roaming 1
1.1 Information is bits + context 1
1.2 Programs translated into different formats by other programs 3
1.3 It is helpful to know how a compilation system works
1.4 The processor reads and interprets instructions stored in memory 5
1.4.1 Hardware Composition 5
1.4.2 Running hello program 7
1.5 Caching is critical 9
1.6 Storage Device Hierarchy 9
1.7 OS Management Hardware 10
1.7.1 process 11
1.7.2 thread 12
1.7.3 Virtual Memory 12
14 1.7.4 file
1.8 Network Communication between systems 14
1.9 Important Themes 16
1.9.1 Amdahl’s law 16
1.9.2 Concurrency and Parallelism 17
1.9.3 The importance of abstraction in computer systems 19
1.10 summary 20
20 Refs
Answer to exercise 20
The first part
Program structure and execution
Chapter 2 Representation and Processing of information
2.1 Information Storage 24
2.1.1 Hex notation 25
2.1.2 Word data size 27
2.1.3 Addressing and byte order 29
2.1.4 indicates the character string 34
2.1.5 indicates code 34
2.1.6 Introduction to Boolean algebra 35
2.1.7 Bit-level operations in C language 37
2.1.8 Logical Operations in C language 39
2.1.9 Shift operation in C language 40
2.2 The integer indicates 41
2.2.1 Integer Data type 42
2.2.2 Coding of unsigned numbers 43
2.2.3 Complement code 44
2.2.4 Conversion between signed and unsigned numbers 49
2.2.5 Signed and unsigned Numbers in C 52
2.2.6 Extend a number of bits to represent 54
2.2.7 Truncate the number 56
2.2.8 Recommendations on signed and unsigned Numbers 58
2.3 Integer Operation 60
2.3.1 Unsigned addition 60
2.3.2 Complement addition 62
2.3.3 Non-66 of complement
2.3.4 Unsigned multiplication 67
2.3.5 Complement multiplication 67
2.3.6 times the constant 70
2.3.7 divided by a power of 2 71
2.3.8 Final thoughts on integer operation 74
2.4 Floating point 75
2.4.1 Binary decimal 76
2.4.2IEEE Floating point 78
2.4.3 Numerical Example 79
2.4.4 rounding, 83
2.4.5 Floating point operation 85
2.4.6 Floating point 86 in C
2.5 summary of 87
Ref. 88
Homework 88
Answer to exercise 97
Chapter 3 the machine-level representation of the program is 109
3.1 Historical Viewpoint 110
3.2 Program code 113
3.2.1 Machine level code 113
3.2.2 Code Example 114
3.2.3 Note 117 on format
3.3 Data Format 119
3.4 Accessing Information 119
3.4.1 Operand indicator 121
3.4.2 Data transmission instruction 122
3.4.3 Data Transfer Example 125
3.4.4 Pushing and ejecting stack data 127
3.5 Arithmetic and Logical operations 128
3.5.1 Loading valid Address 129
3.5.2 Unitary and binary operations 130
3.5.3 Shift Operation 131
3.5.4 discussed 131
3.5.5 Special arithmetic operation 133
3.6 control of 135
3.6.1 Condition Code 135
3.6.2 Access Condition code 136
3.6.3 Jump instruction 138
3.6.4 Coding of jump instruction 139
3.6.5 Conditional branching with Conditional control… 141
3.6.6 Conditional branching with conditional delivery… 145
3.6.7 circular 149
3.6.8 switch statement 159
3.7 the process of 164
3.7.1 Run time stack 164
3.7.2 Transfer control 165
3.7.3 Data Transfer 168
3.7.4 Local store 170 on the stack
3.7.5 Local storage space in register 172
3.7.6 Recursive process 174
3.8 Array allocation and Access 176
3.8.1 Basic Principles 176
3.8.2 Pointer Operations 177
3.8.3 Nested array 178
3.8.4 Fixed-length array 179
3.8.5 Variable Length Array 181
3.9 Heterogeneous Data Structure 183
3.9.1 structure 183
3.9.2 joint 186
3.9.3 Align Data 189
3.10 Combine control and data in machine-level programs 192
3.10.1 Understanding Pointer 192
3.10.2 Application: Use the GDB debugger 193
3.10.3 Memory out-of-bounds references and buffer overflows 194
3.10.4 Defending against Buffer Overflow Attacks 198
Support variable length stack frame 201
Floating point code 204
3.11.1 Floating point transfer and conversion operation 205
Floating point code 209 in procedure 3.11.2
3.11.3 Floating point operation 210
3.11.4 Define and use the floating point constant 212
3.11.5 Use bit-level operation 212 in floating point code
3.11.6 Floating point comparison operation 213
3.11.7 Observations on floating point code 215
3.12 summary of 216
Ref. 216
Homework 216
The answer to the exercise is 226
Chapter 4 Processor Architecture 243
4.1Y86-64 Instruction set architecture 245
4.1.1 State visible to programmers 245
4.1.2 Y86 245-64 instructions
4.1.3 Instruction code 246
4.1.4 Y86 abnormal – 64, 250
4.1.5 Y86-64 program, 251
4.1.6 Details of some y86-64 instructions 255
4.2 Logic design and hardware control language HCL256
4.2.1 Logical gate 257
4.2.2 Combinative circuits and HCL Boolean expressions 257
4.2.3 Word level combined circuit and HCL integer expression 258
4.2.4 Set Relations 261
4.2.5 Memory and Clock 262
4.3 The sequence of Y86-64 realizes 264
4.3.1 Organize the processing into stage 264
4.3.2SEQ Hardware structure 272
4.3.3 Timing sequence of SEQ 274
4.3.4 Implementation of SEQ stage 277
4.4 General principles of assembly line
4.4.1 Calculation flow line 282
4.4.2 Detailed Description of assembly line Operation
4.4.3 Limitations of assembly line 284
4.4.4 Pipeline system with feedback 287
4.5Y86-64 pipeline achieves 288
4.5.1SEQ+ : Reschedule phase 288
4.5.2 Insert pipeline register 289
4.5.3 Rearrange the signal and label 292
4.5.4 Predicting the next PC293
4.5.5 Assembly Line Adventure 295
4.5.6 Exception Handling 306
4.5.7 Implementation of various stages of PIPE 308
4.5.8 Assembly line control logic 314
4.5.9 Performance Analysis 322
4.5.10 Unfinished Work 323
4.6 summary of 325
Ref. 326
Homework 327
The answer to exercise 331
Chapter 5 Optimize program performance
5.1 Capabilities and limitations of optimizing the compiler 342
5.2 indicates the program performance 345
5.3 Program Example 347
5.4 Eliminate cycle inefficiency 350
5.5 Reduced procedure calls by 353
5.6 Eliminating unnecessary memory references 354
5.7 Understanding the Modern processor 357
5.7.1 Overall Operation 357
5.7.2 Performance of functional units 361
5.7.3 Abstract model of processor operation 362
5.8 Loop Expansion 366
5.9 Improve parallelism
5.9.1 Multiple cumulative variables 370
5.9.2 Recombine transform 373
5.10 Result summary of optimized merging code 377
5.11 Some limiting factors
5.11.1 Register Overflow 378
5.11.2 Branch prediction and prediction error penalty 379
5.12 Understanding Memory Performance 382
5.12.1 Loading Performance 382
5.12.2 Storage Performance 383
5.13 Application: Performance improvement technology
5.14 Confirming and removing performance Bottlenecks 388
5.14.1 Program analysis 388
5.14.2 Use profilers to guide optimization 390
5.15 summary of 392
Refs. 393
Homework 393
The answer to the exercise is 395
Chapter 6 Memory Hierarchy
6.1 Storage Technology 399
6.1.1 Random Access Memory 400
6.1.2 Disk Storage 406
6.1.3 SOLID-state drive 414
6.1.4 Storage Technology Trends 415
6.2 Locality 418
6.2.1 Locality of program data references
6.2.2 Locality of fetch instruction 419
6.2.3 Local Summary 420
6.3 Storage Hierarchy 421
6.3.1 Caches in the memory hierarchy 422
6.3.2 Summary of storage hierarchy concepts
6.4 Cache memory 425
6.4.1 General cache storage organization Structure 425
6.4.2 Directly mapping cache 427
6.4.3 Group Association Cache 433
6.4.4 Full associative cache 434
6.4.5 Questions about writing 437
6.4.6 Anatomy of a real cache hierarchy
6.4.7 Performance Impact of cache parameters 439
6.5 Write cache-friendly code 440
6.6 Synthesis: The impact of caching on program performance
6.6.1 Memory Hill 444
6.6.2 Rearrange the cycles to improve spatial locality 447
6.6.3 Use locality 450 in the program
6.7 summary of 450
Refs. 451
Homework 451
The answer to exercise is 459
The second part
Run the program on the system
Chapter 7 link 464
7.1 Compiler driver 465
7.2 Static Link 466
7.3 Object File 466
7.4 You can relocate object file 467
7.5 Symbols and symbol table 468
7.6 Symbol Analysis 470
7.6.1 How does the linker resolve the multi-defined global symbol 471
7.6.2 Link with static library 475
7.6.3 How does the linker use static libraries to resolve reference 477
7.7 Relocating 478
7.7.1 Relocate entry 479
7.7.2 Reposition symbol reference 479
7.8 Executable object file 483
7.9 Loading the Executable Object File 484
7.10 Dynamically Linked Shared Library 485
7.11 Loading and linking shared library 487 from Applications
7.12 Position-independent code 489
7.13 Piling mechanism of warehouse 492
7.13.1 Piling at compile time
7.13.2 Piling when linking 492
7.13.3 Piling in operation 494
7.14 Tools for processing object files 496
7.15 summary of 496
Refs. 497
Homework 497
The answer to the exercise is 499
Chapter 8 Abnormal Control Flow 501
8.1 abnormal 502
8.1.1 Exception Handling 503
8.1.2 Exception Category 504
8.1.3 Exceptions In Linux/x86-64 505
8.2 process 508
8.2.1 Logical Control Flow 508
8.2.2 Concurrent streams 509
8.2.3 Private address space 509
8.2.4 User Mode and Kernel Mode 510
8.2.5 Context Switch 511
8.3 System Call Error Handling 512
8.4 Process Control 513
8.4.1 Obtaining the PROCESS ID513
8.4.2 Creating and Stopping Process 513
8.4.3 Reclaim subprocess 516
8.4.4 Hibernating processes 521
8.4.5 Load and run program 521
8.4.6 Run program 524 with fork and execve
8.5 signal of 526
8.5.1 Signal Term 527
8.5.2 Sending signals 528
8.5.3 Receiving Signal 531
8.5.4 Blocking and unblocking signals 532
8.5.5 Write signal processing program 533
8.5.6 Synchronize streams to avoid nasty concurrency errors 540
8.5.7 Waiting explicitly for a signal 543
8.6 Non-Local Forward 546
8.7 Tools for Operating processes 550
8.8 summary of 550
Bibliography 550
Homework 550
The answer to the exercise is 556
Chapter 9 Virtual memory 559
9.1 Physical and Virtual addressing 560
9.2 Address Space 560
9.3 Virtual memory as a caching tool 561
9.3.1DRAM Cache organization 562
9.3.2 page table 562
Page 9.3.3 hit 563
9.3.4 missing page 564
9.3.5 Assign Page 565
Again, locality saves us 565
9.4 Virtual Memory as a Tool for Memory management
9.5 Virtual Memory as a Tool for memory protection
9.6 Address translation 567
9.6.1 Combining Cache and Virtual memory 570
9.6.2 Accelerating address translation with TLB 570
9.6.3 Multi-level page table 571
9.6.4 Synthesis: End-to-end address translation 573
9.7 Case study: Intel Core I7 /Linux Memory system 576
9.7.1Core I7 address translation 576
9.7.2Linux Virtual Memory System 580
9.8 Memory Mapping 582
9.8.1 View Shared Object 583
Fork function 584
Execve function 584
9.8.4 User-level Memory Mapping using the Mmap function 585
9.9 Dynamic Memory Allocation 587
9.9.1 Malloc and free function 587
9.9.2 Why use dynamic memory allocation 589
9.9.3 Requirements and objectives of the dispenser 590
9.9.4 pieces 591
9.9.5 Implement Question 592
Implicitly free linked list 592
9.9.7 Placing the allocated block 593
9.9.8 Splitting free Blocks 594
9.9.9 Obtaining additional heap memory 594
9.9.10 Merging free Block 594
9.9.11 Merge with boundary markers 595
9.9.12 Synthesis: Implement a simple allocator 597
9.9.13 Explicit free list 603
9.9.14 Separated free linked list 604
9.10 Garbage collection 605
9.10.1 Garbage Collector Basics 606
9.10.2Mark&Sweep garbage collector 607
9.10.3c program of conservative Mark&Sweep608
9.11 Common memory related error 609 in C programs
9.11.1 Indirectly referencing bad pointer 609
9.11.2 Reading Uninitialized Memory 609
9.11.3 Allow stack buffer overflow 610
9.11.4 Assume that Pointers and the objects they point to are 610 of the same size
9.11.5 Causing dislocation error 611
9.11.6 refers to a pointer rather than the object to which it points, 611
9.11.7 Misread Pointer operation 611
9.11.8 Reference to non-existent variable 612
9.11.9 Referencing data from a free heap block 612
9.11.10 Memory Leakage 613
9.12 summary of 613
Ref. 613
Homework 614
The answer to exercise is 617
The third part
Interaction and communication between programs
Chapter 10 System level I/O62210.1Unix I/O622
10.2 file 623
10.3 Opening and Closing File 624
10.4 Reading and Writing Files 625
10.5 Read and write 626 robustly with the RIO package
10.5.1RIO’s unbuffered I/O function 627
10.5.2RIO’s buffered input function 627
10.6 Reading Metadata from a File 632
10.7 Reading Contents of a Directory 633
10.8 Sharing a File 634
10.9I/O Redirection 637
10.10 standard I/O638
10.11 Synthesis: Which I/O Functions should I Use? 638
10.12 summary of 640
Refs. 640
Homework 640
The answer to exercise is 641
Chapter 11 Network programming 642
11.1 Client server programming model 642
11.2 network of 643
11.3 Global IP Internet 646
11.3.1 IP address 647
11.3.2 Internet domain 649
11.3.3 Internet Connection 651
11.4 Socket interface 652
11.4.1 Socket address structure 653
654 11.4.2 socket function
654 11.4.3 connect function
11.4.4 bind function 654
655 11.4.5 listen function
11.4.6 the accept function is 655
11.4.7 Switching between Hosts and Services 656
11.4.8 Auxiliary functions of socket interface 660
11.4.9 Echo Client and Server 662
11.5Web Server 665
11.5.1 Web base 665
11.5.2 666 Web content
11.5.3 HTTP transaction. 667
11.5.4 Service Dynamic Content 669
11.6 Integration: TINY Web Server 671
11.7 summary of 678
Bibliography 678
Homework 678
The answer to exercise is 679
Chapter 12 Concurrent programming 681
12.1 Process-based concurrent programming 682
12.2 Concurrent programming based on I/O Multiplexing 684
12.3 Concurrent programming based on threads 691
12.4 Shared variable 696 in multithreaded programs
12.5 Synchronizing threads with semaphores 698
12.6 Using threads to improve parallelism 710
12.7 Other Concurrent Problems 716
12.8 summary of 722
Ref. 723
Homework 723
Answer to exercise 726
Appendix A Error Handling 729
733 refs
Follow the wechat official account, reply “CSapp” and you will get the HD ebook.
\
More interesting articles:
Where2go team
Wechat: The beauty of algorithms and programming
Long press to identify the QR code to follow us!
Tips: Click on the lower right corner of the page “Write a message” to comment, looking forward to your participation! Looking forward to your forwarding!