Computer Systems
A Programmer’s Perspective
1
(Beta Draft)
Randal E. Bryant
David R. O’Hallaron
November 16, 2001
1
Copyright
c
2001, R. E. Bryant, D. R. O’Hallaron. All rights reserved.
2
Contents
Preface i
1 Introduction 1
1.1 InformationisBitsinContext ................................. 2
1.2 ProgramsareTranslatedbyOtherProgramsintoDifferentForms............... 3
1.3 ItPaystoUnderstandHowCompilationSystemsWork.................... 4
1.4 Processors Read and Interpret Instructions Stored in Memory ................. 5
1.4.1 HardwareOrganizationofaSystem .......................... 5
1.4.2 Running the hello Program ............................. 8
1.5 CachesMatter.......................................... 9
1.6 StorageDevicesFormaHierarchy............................... 10
1.7 TheOperatingSystemManagestheHardware......................... 11
1.7.1 Processes . ....................................... 13
1.7.2 Threads......................................... 14
1.7.3 Virtual Memory . . . .................................. 14
1.7.4 Files........................................... 15
1.8 SystemsCommunicateWithOtherSystemsUsingNetworks ................. 16
1.9 Summary ............................................ 18
I Program Structure and Execution 19
2 Representing and Manipulating Information 21
2.1 InformationStorage....................................... 22
2.1.1 HexadecimalNotation ................................. 23
2.1.2 Words.......................................... 25
3
4
CONTENTS
2.1.3 DataSizes........................................ 25
2.1.4 Addressing and Byte Ordering . ............................ 26
2.1.5 Representing Strings .................................. 33
2.1.6 Representing Code . .................................. 33
2.1.7 BooleanAlgebrasandRings.............................. 34
2.1.8 Bit-Level Operations in C . . . ............................ 37
2.1.9 LogicalOperationsinC ................................ 39
2.1.10 ShiftOperationsinC.................................. 40
2.2 Integer Representations . . . .................................. 41
2.2.1 IntegralDataTypes................................... 41
2.2.2 UnsignedandTwo’sComplementEncodings ..................... 41
2.2.3 ConversionsBetweenSignedandUnsigned...................... 45
2.2.4 Signedvs.UnsignedinC................................ 47
2.2.5 Expanding the Bit Representation of a Number . . . ................. 49
2.2.6 TruncatingNumbers .................................. 51
2.2.7 AdviceonSignedvs.Unsigned ............................ 52
2.3 Integer Arithmetic . ....................................... 53
2.3.1 Unsigned Addition . .................................. 53
2.3.2 Two’s Complement Addition . . ............................ 56
2.3.3 Two’sComplementNegation.............................. 60
2.3.4 Unsigned Multiplication ................................ 61
2.3.5 Two’s Complement Multiplication ........................... 62
2.3.6 Multiplying by Powers of Two . ............................ 63
2.3.7 DividingbyPowersofTwo .............................. 64
2.4 FloatingPoint.......................................... 66
2.4.1 FractionalBinaryNumbers............................... 67
2.4.2 IEEE Floating-Point Representation . . . ....................... 69
2.4.3 ExampleNumbers ................................... 71
2.4.4 Rounding . ....................................... 74
2.4.5 Floating-PointOperations ............................... 76
2.4.6 FloatingPointinC................................... 77
2.5 Summary ............................................ 79
CONTENTS
5
3 Machine-Level Representation of C Programs 89
3.1 AHistoricalPerspective .................................... 90
3.2 ProgramEncodings....................................... 92
3.2.1 Machine-LevelCode.................................. 93
3.2.2 CodeExamples..................................... 94
3.2.3 A Note on Formatting ................................. 97
3.3 DataFormats .......................................... 98
3.4 Accessing Information . . . .................................. 99
3.4.1 OperandSpecifiers...................................100
3.4.2 DataMovementInstructions..............................102
3.4.3 DataMovementExample................................103
3.5 Arithmetic and Logical Operations . . . ............................105
3.5.1 LoadEffectiveAddress.................................106
3.5.2 UnaryandBinaryOperations .............................106
3.5.3 ShiftOperations ....................................107
3.5.4 Discussion .......................................108
3.5.5 Special Arithmetic Operations . ............................109
3.6 Control .............................................110
3.6.1 Condition Codes . . ..................................110
3.6.2 Accessing the Condition Codes ............................111
3.6.3 JumpInstructionsandtheirEncodings.........................114
3.6.4 TranslatingConditionalBranches ...........................117
3.6.5 Loops . . . .......................................119
3.6.6 SwitchStatements ...................................128
3.7 Procedures............................................132
3.7.1 StackFrameStructure .................................132
3.7.2 Transferring Control ..................................134
3.7.3 RegisterUsageConventions ..............................135
3.7.4 ProcedureExample...................................137
3.7.5 RecursiveProcedures..................................140
3.8 Array Allocation and Access ..................................142
3.8.1 BasicPrinciples.....................................143
3.8.2 Pointer Arithmetic . ..................................144
