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

Published by Pearson (July 30, 2010) © 2011

  • Umakishore Ramachandran
  • William D. Leahy, Jr.
Products list

Details

  • A print text

This product is expected to ship within 3-6 business days for US and 5-10 business days for Canadian customers.

In the early days of computing, hardware and software systems were designed separately. Today, as multicore systems predominate, this separation is becoming impractical.

Computer Systems examines the key elements of all computer systems using an integrated approach that treats hardware and software as part of the same, larger system. Students gain important insights into the interplay between hardware and software and leave the course with a better understanding of a modern computer system

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 .................................................

Need help? Get in touch