Computer Systems: An Integrated Approach to Architecture and Operating Systems, 1st edition

Preface ......................................................................................... i
Why a New Book on Computer Systems? ................................................................................................. i
The structure of the book ......................................................................................................................... ii
Where Does This Textbook Fit into the Continuum of CS Curriculum? ................................................... iii
Supplementary Material for Teaching an Integrated Course in Systems ................................................. v
Example project ideas included in the supplementary material ............................................................. vi

Chapter 1 Introduction.......................................................... 1-1
1.1 What is Inside a Box? ....................................................................................................................... 1-1
1.2 Levels of Abstraction in a Computer System ................................................................................... 1-2
1.3 The Role of the Operating System ................................................................................................... 1-5
1.4 What is happening inside the box? .................................................................................................. 1-7
1.4.1 Launching an application on the computer ............................................................................... 1-9
1.5 Evolution of Computer Hardware .................................................................................................... 1-9
1.6 Evolution of Operating Systems ..................................................................................................... 1-11
1.7 Roadmap of the rest of the book ................................................................................................... 1-12
1.8 Review Questions ........................................................................................................................... 1-13

Chapter 2 Processor Architecture ........................................ 2-1
2.1 What is involved in processor design? ............................................................................................. 2-2
2.2 How do we design an instruction set? ............................................................................................. 2-2
2.3 A Common High-Level Language Feature Set .................................................................................. 2-3
2.4 Expressions and Assignment Statements ........................................................................................ 2-4
2.4.1 Where to keep the operands? .................................................................................................. 2-4
2.4.2 How do we specify a memory address in an instruction? ........................................................ 2-9
2.4.3 How wide should each operand be? ....................................................................................... 2-10
2.4.4 Endianness .............................................................................................................................. 2-12
2.4.5 Packing of operands and Alignment of word operands.......................................................... 2-15
2.5 High-level data abstractions .......................................................................................................... 2-17
2.5.1 Structures ............................................................................................................................... 2-17
2.5.2 Arrays ..................................................................................................................................... 2-18
2.6 Conditional statements and loops ................................................................................................. 2-20
2.6.1 If-then-else statement ............................................................................................................ 2-20
2.6.2 Switch statement .................................................................................................................... 2-22
2.6.3 Loop statement ....................................................................................................................... 2-24
2.7 Checkpoint .................................................................................................................................... 2-24
2.8 Compiling Function calls ................................................................................................................ 2-24
2.8.1 State of the Caller ................................................................................................................... 2-25
2.8.2 Remaining chores with procedure calling ............................................................................... 2-28
2.8.3 Software Convention .............................................................................................................. 2-30
2.8.4 Activation Record .................................................................................................................... 2-36
2.8.5 Recursion ............................................................................................................................... 2-37
2.8.6 Frame Pointer ......................................................................................................................... 2-37
2.9 Instruction-Set Architecture Choices ............................................................................................. 2-40
2.9.1 Additional Instructions ............................................................................................................ 2-40
2.9.2 Additional addressing modes .................................................................................................. 2-41
2.9.3 Architecture styles .................................................................................................................. 2-41
2.9.4 Instruction Format .................................................................................................................. 2-42
2.10 LC-2200 Instruction Set ................................................................................................................ 2-45
2.10.1 Instruction Format ................................................................................................................ 2-45
2.10.2 LC-2200 Register Set ............................................................................................................. 2-48
2.11 Issues influencing processor design ............................................................................................. 2-48
2.11.1 Instruction-set ....................................................................................................................... 2-48
2.11.2 Influence of applications on instruction-set design .............................................................. 2-50
2.11.3 Other issues driving processor design .................................................................................. 2-51
2.12 Summary ..................................................................................................................................... 2-52
2.13 Review Questions ......................................................................................................................... 2-53

Chapter 3 Processor Implementation .................................. 3-1
3.1 Architecture versus Implementation ............................................................................................... 3-1
3.2 What is involved in Processor Implementation? ............................................................................. 3-2
3.3 Key hardware concepts .................................................................................................................... 3-3
3.3.1 Circuits ..................................................................................................................................... 3-3
3.3.2 Hardware resources of the datapath ........................................................................................ 3-3
3.3.3 Edge Triggered Logic ................................................................................................................. 3-5
3.3.4 Connecting the datapath elements .......................................................................................... 3-7
3.3.5 Towards bus-based Design ..................................................................................................... 3-10
3.3.6 Finite State Machine (FSM) ..................................................................................................... 3-13
3.4 Datapath Design ............................................................................................................................. 3-15
3.4.1 ISA and datapath width ........................................................................................................... 3-17
3.4.2 Width of the Clock Pulse ......................................................................................................... 3-18
3.4.3 Checkpoint .............................................................................................................................. 3-18
3.5 Control Unit Design ........................................................................................................................ 3-18
3.5.1 ROM plus state register .......................................................................................................... 3-19
3.5.2 FETCH macro state .................................................................................................................. 3-23
3.5.3 DECODE macro state ............................................................................................................... 3-25
3.5.4 EXECUTE macro state: ADD instruction (part of R-Type) ........................................................ 3-26
3.5.5 EXECUTE macro state: NAND instruction (part of R-Type) ..................................................... 3-28
3.5.6 EXECUTE macro state: JALR instruction (part of J-Type) ........................................................ 3-28
3.5.7 EXECUTE macro state: LW instruction (part of I-Type) ........................................................... 3-29
3.5.8 EXECUTE macro state: SW and ADDI instructions (part of I-Type) ......................................... 3-30
3.5.9 EXECUTE macro state: BEQ instruction (part of I-Type) ......................................................... 3-31
3.5.10 Engineering a conditional branch in the microprogram ....................................................... 3-32
3.5.11 DECODE macro state revisited .............................................................................................. 3-34
3.6 Alternative Style of Control Unit Design ........................................................................................ 3-35
3.6.1 Microprogrammed Control ..................................................................................................... 3-35
3.6.2 Hardwired control ................................................................................................................... 3-36
3.6.3 Choosing between the two control design styles ................................................................... 3-37
3.7 Summary ....................................................................................................................................... 3-38
3.8 Historical Perspective ..................................................................................................................... 3-38
3.9 Review Questions ........................................................................................................................... 3-41

Chapter 4 Interrupts, Traps and Exceptions ...................... 4-1
4.1 Discontinuities in program execution .............................................................................................. 4-2
4.2 Dealing with program discontinuities .............................................................................................. 4-4
4.3 Architectural enhancements to handle program discontinuities .................................................... 4-7
4.3.1 Modifications to FSM ................................................................................................................ 4-8
4.3.2 A simple interrupt handler ........................................................................................................ 4-9
4.3.3 Handling cascaded interrupts ................................................................................................. 4-10
4.3.4 Returning from the handler .................................................................................................... 4-13
4.3.5 Checkpoint .............................................................................................................................. 4-14
4.4 Hardware details for handling program discontinuities ................................................................ 4-14
4.4.1 Datapath details for interrupts ............................................................................................... 4-14
4.4.2 Details of receiving the address of the handler ...................................................................... 4-16
4.4.3 Stack for saving/restoring ....................................................................................................... 4-18
4.5 Putting it all together ..................................................................................................................... 4-20
4.5.1 Summary of Architectural/hardware enhancements ............................................................. 4-20
4.5.2 Interrupt mechanism at work ................................................................................................. 4-20
4.6 Summary ....................................................................................................................................... 4-23
4.7 Review Questions ........................................................................................................................... 4-25

Chapter 5 Processor Performance and Rudiments of Pipelined Processor Design ........................... 5-1
5.1 Space and Time Metrics ................................................................................................................... 5-1
5.2 Instruction Frequency ...................................................................................................................... 5-4
5.3 Benchmarks ..................................................................................................................................... 5-5
5.4 Increasing the Processor Performance ............................................................................................ 5-9
5.5 Speedup ........................................................................................................................................ 5-10
5.6 Increasing the Throughput of the Processor ................................................................................. 5-14
5.7 Introduction to Pipelining .............................................................................................................. 5-14
5.8 Towards an instruction processing assembly line ......................................................................... 5-15
5.9 Problems with a simple-minded instruction pipeline .................................................................... 5-17
5.10 Fixing the problems with the instruction pipeline ....................................................................... 5-18
5.11 Datapath elements for the instruction pipeline .......................................................................... 5-20
5.12 Pipeline-conscious architecture and implementation ................................................................. 5-22
5.12.1 Anatomy of an instruction passage through the pipeline .................................................... 5-23
5.12.2 Design of the Pipeline Registers ............................................................................................ 5-26
5.12.3 Implementation of the stages ............................................................................................... 5-27
5.13 Hazards ........................................................................................................................................ 5-27
5.13.1 Structural hazard ................................................................................................................... 5-28
5.13.2 Data Hazard ........................................................................................................................... 5-30
5.13.3 Control Hazard ...................................................................................................................... 5-41
5.13.4 Summary of Hazards ............................................................................................................. 5-51
5.14 Dealing with program discontinuities in a pipelined processor .................................................. 5-52
5.15 Advanced topics in processor design ........................................................................................... 5-55
5.15.1 Instruction Level Parallelism ................................................................................................. 5-55
5.15.2 Deeper pipelines ................................................................................................................... 5-56
5.15.3 Revisiting program discontinuities in the presence of out-of-order processing .................. 5-59
5.15.4 Managing shared resources .................................................................................................. 5-60
5.15.5 Power Consumption ............................................................................................................. 5-62
5.15.6 Multi-core Processor Design ................................................................................................. 5-63
5.15.7 Intel Core Microarchitecture: An example pipeline ............................................................. 5-64
5.16 Summary ..................................................................................................................................... 5-67
5.17 Historical Perspective ................................................................................................................... 5-67
5.18 Review Questions ......................................................................................................................... 5-68

Chapter 6 Processor Scheduling ........................................... 6-1
6.1 Introduction .................................................................................................................................... 6-1
6.2 Programs and Processes .................................................................................................................. 6-2
6.3 Scheduling Environments ................................................................................................................. 6-7
6.4 Scheduling Basics ............................................................................................................................. 6-9
6.5 Performance Metrics ..................................................................................................................... 6-12
6.6 Non-preemptive Scheduling Algorithms ........................................................................................ 6-15
6.6.1 First-Come First-Served (FCFS) ................................................................................................ 6-15
6.6.2 Shortest Job First (SJF) ............................................................................................................ 6-19
6.6.3 Priority .................................................................................................................................... 6-21
6.7 Preemptive Scheduling Algorithms ................................................................................................ 6-23
6.7.1 Round Robin Scheduler ........................................................................................................... 6-26
6.8 Combining Priority and Preemption .............................................................................................. 6-31
6.9 Meta Schedulers ............................................................................................................................ 6-31
6.10 Evaluation ................................................................................................................................... 6-32
6.11 Impact of Scheduling on Processor Architecture ......................................................................... 6-34
6.12 Summary and a Look ahead ......................................................................................................... 6-36
6.13 Linux Scheduler – A case study .................................................................................................... 6-36
6.14 Historical Perspective ................................................................................................................... 6-39
6.15 Review Questions ......................................................................................................................... 6-41

Chapter 7 Memory Management Techniques ..................... 7-1
7.1 Functionalities provided by a memory manager ............................................................................. 7-1
7.2 Simple Schemes for Memory Management .................................................................................... 7-4
7.3 Memory Allocation Schemes ........................................................................................................... 7-8
7.3.1 Fixed Size Partitions .................................................................................................................. 7-9
7.3.2 Variable Size Partitions ........................................................................................................... 7-10
7.3.3 Compaction ............................................................................................................................. 7-13
7.4 Paged Virtual Memory ................................................................................................................... 7-14
7.4.1 Page Table ............................................................................................................................... 7-17
7.4.2 Hardware for Paging ............................................................................................................... 7-19
7.4.3 Page Table Set up .................................................................................................................... 7-20
7.4.4 Relative sizes of virtual and physical memories ..................................................................... 7-20
7.5 Segmented Virtual Memory ........................................................................................................... 7-21
7.5.1 Hardware for Segmentation ................................................................................................... 7-26
7.6 Paging versus Segmentation .......................................................................................................... 7-27
7.6.1 Interpreting the CPU generated address ................................................................................ 7-29
7.7 Summary ....................................................................................................................................... 7-30
7.8 Historical Perspective ..................................................................................................................... 7-32
7.8.1 MULTICS ................................................................................................................................. 7-33
7.8.2 Intel's Memory Architecture ................................................................................................... 7-35
7.9 Review Questions ........................................................................................................................... 7-36

Chapter 8 Details of Page-based Memory Management .... 8-1
8.1 Demand Paging ............................................................................................................................... 8-1
8.1.1 Hardware for demand paging ................................................................................................... 8-1
8.1.2 Page fault handler ..................................................................................................................... 8-2
8.1.3 Data structures for Demand-paged Memory Management ..................................................... 8-3
8.1.4 Anatomy of a Page Fault ........................................................................................................... 8-5
8.2 Interaction between the Process Scheduler and Memory Manager ............................................... 8-8
8.3 Page Replacement Policies .............................................................................................................. 8-9
8.3.1 Belady's Min ............................................................................................................................ 8-10
8.3.2 Random Replacement ............................................................................................................. 8-10
8.3.3 First In First Out (FIFO) ............................................................................................................ 8-11
8.3.4 Least Recently Used (LRU) ...................................................................................................... 8-13
8.3.5 Second chance page replacement algorithm.......................................................................... 8-17
8.3.6 Review of page replacement algorithms ................................................................................ 8-20
8.4 Optimizing Memory Management................................................................................................. 8-22
8.4.1 Pool of free page frames ......................................................................................................... 8-22
8.4.2 Thrashing ................................................................................................................................ 8-23
8.4.3 Working set ............................................................................................................................. 8-25
8.4.4 Controlling thrashing .............................................................................................................. 8-26
8.5 Other considerations ..................................................................................................................... 8-28
8.6 Translation Lookaside Buffer (TLB) ................................................................................................ 8-28
8.6.1 Address Translation with TLB .................................................................................................. 8-29
8.7 Advanced topics in memory management .................................................................................... 8-31
8.7.1 Multi-level page tables ............................................................................................................ 8-31
8.7.2 Access rights as part of the page table entry .......................................................................... 8-34
8.7.3 Inverted page tables ............................................................................................................... 8-34
8.8 Summary ....................................................................................................................................... 8-34
8.9 Review Questions ........................................................................................................................... 8-35

Chapter 9 Memory Hierarchy .............................................. 9-1
9.1 The Concept of a Cache ................................................................................................................... 9-2
9.2 Principle of Locality .......................................................................................................................... 9-3
9.3 Basic terminologies .......................................................................................................................... 9-4
9.4 Multilevel Memory Hierarchy .......................................................................................................... 9-5
9.5 Cache organization ........................................................................................................................... 9-8
9.6 Direct-mapped cache organization .................................................................................................. 9-9
9.6.1 Cache Lookup .......................................................................................................................... 9-11
9.6.2 Fields of a Cache Entry ............................................................................................................ 9-13
9.6.3 Hardware for direct mapped cache ........................................................................................ 9-14
9.7 Repercussion on pipelined processor design ................................................................................. 9-16
9.8 Cache read/write algorithms ......................................................................................................... 9-17
9.8.1 Read access to the cache from the CPU ................................................................................. 9-18
9.8.2 Write access to the cache from the CPU ................................................................................ 9-19
9.9 Dealing with cache misses in the processor pipeline .................................................................... 9-22
9.9.1 Effect of memory stalls due to cache misses on pipeline performance ................................. 9-23
9.10 Exploiting spatial locality to improve cache performance ........................................................... 9-25
9.10.1 Performance implications of increased blocksize ................................................................. 9-30
9.11 Flexible placement ....................................................................................................................... 9-31
9.11.1 Fully associative cache .......................................................................................................... 9-32
9.11.2 Set associative cache ............................................................................................................ 9-34
9.11.3 Extremes of set associativity ................................................................................................. 9-37
9.12 Instruction and Data caches .................................................