Computer Systems

Dr. Umakishore Ramachandran received his Ph.D. in Computer Science from the University of Wisconsin, Madison in 1986 under the direction of Marvin Solomon. Since then he has been with Georgia Tech (home of the yellow jackets), where he is currently a Professor in the Core Computing Division in the College of Computing. His research interests are in the area of architectural design, programming, and analysis of parallel and distributed systems. At Georgia Tech, he has been involved in the design and evaluation of several large experimental systems including Clouds, Beehive, and Stampede (joint with Compaq Cambridge Research Lab), and studying their scalability from an applications perspective. Currently, in the ubiquitous presence project, he is investigating software and hardware mechanisms for ubiquitous distributed computing for an environment comprised of distributed sensors, embedded data concentrators, and backend clusters. He received a Presidential Young Investigator (PYI) Award from the National Science Foundation (NSF) in 1990, the Georgia Tech Doctoral Thesis Advisor award in 1993, the College of Computing Outstanding Senior Research Faculty award in 1996, the College of Computing Dean's Award in 2003, and the College of Computing William "Gus'' Baird Teaching Award in 2004.William D. "Bill" Leahy, Jr. is currently working as a lecturer at Georgia Tech teaching introductory Computer Science. Bill earned his MS in Computer Science, from Georgia Institute of Technology, his MS in Ceramic Engineering, from Virginia Polytechnic Institute and a BS in Ceramic Engineering, from Virginia Tech. Visit Bill's web page for more information about his education and experience.

• Preface ......................................................................................... iWhy a New Book on Computer Systems? ................................................................................................. iThe structure of the book ......................................................................................................................... iiWhere Does This Textbook Fit into the Continuum of CS Curriculum? ................................................... iiiSupplementary Material for Teaching an Integrated Course in Systems ................................................. vExample project ideas included in the supplementary material ............................................................. viChapter 1 Introduction.......................................................... 1-11.1 What is Inside a Box? ....................................................................................................................... 1-11.2 Levels of Abstraction in a Computer System ................................................................................... 1-21.3 The Role of the Operating System ................................................................................................... 1-51.4 What is happening inside the box? .................................................................................................. 1-71.4.1 Launching an application on the computer ............................................................................... 1-91.5 Evolution of Computer Hardware .................................................................................................... 1-91.6 Evolution of Operating Systems ..................................................................................................... 1-111.7 Roadmap of the rest of the book ................................................................................................... 1-121.8 Review Questions ........................................................................................................................... 1-13Chapter 2 Processor Architecture ........................................ 2-12.1 What is involved in processor design? ............................................................................................. 2-22.2 How do we design an instruction set? ............................................................................................. 2-22.3 A Common High-Level Language Feature Set .................................................................................. 2-32.4 Expressions and Assignment Statements ........................................................................................ 2-42.4.1 Where to keep the operands? .................................................................................................. 2-42.4.2 How do we specify a memory address in an instruction? ........................................................ 2-92.4.3 How wide should each operand be? ....................................................................................... 2-102.4.4 Endianness .............................................................................................................................. 2-122.4.5 Packing of operands and Alignment of word operands.......................................................... 2-152.5 High-level data abstractions .......................................................................................................... 2-172.5.1 Structures ............................................................................................................................... 2-172.5.2 Arrays ..................................................................................................................................... 2-182.6 Conditional statements and loops ................................................................................................. 2-202.6.1 If-then-else statement ............................................................................................................ 2-202.6.2 Switch statement .................................................................................................................... 2-222.6.3 Loop statement ....................................................................................................................... 2-242.7 Checkpoint .................................................................................................................................... 2-242.8 Compiling Function calls ................................................................................................................ 2-242.8.1 State of the Caller ................................................................................................................... 2-252.8.2 Remaining chores with procedure calling ............................................................................... 2-282.8.3 Software Convention .............................................................................................................. 2-302.8.4 Activation Record .................................................................................................................... 2-362.8.5 Recursion ............................................................................................................................... 2-372.8.6 Frame Pointer ......................................................................................................................... 2-372.9 Instruction-Set Architecture Choices ............................................................................................. 2-402.9.1 Additional Instructions ............................................................................................................ 2-402.9.2 Additional addressing modes .................................................................................................. 2-412.9.3 Architecture styles .................................................................................................................. 2-412.9.4 Instruction Format .................................................................................................................. 2-422.10 LC-2200 Instruction Set ................................................................................................................ 2-452.10.1 Instruction Format ................................................................................................................ 2-452.10.2 LC-2200 Register Set ............................................................................................................. 2-482.11 Issues influencing processor design ............................................................................................. 2-482.11.1 Instruction-set ....................................................................................................................... 2-482.11.2 Influence of applications on instruction-set design .............................................................. 2-502.11.3 Other issues driving processor design .................................................................................. 2-512.12 Summary ..................................................................................................................................... 2-522.13 Review Questions ......................................................................................................................... 2-53Chapter 3 Processor Implementation .................................. 3-13.1 Architecture versus Implementation ............................................................................................... 3-13.2 What is involved in Processor Implementation? ............................................................................. 3-23.3 Key hardware concepts .................................................................................................................... 3-33.3.1 Circuits ..................................................................................................................................... 3-33.3.2 Hardware resources of the datapath ........................................................................................ 3-33.3.3 Edge Triggered Logic ................................................................................................................. 3-53.3.4 Connecting the datapath elements .......................................................................................... 3-73.3.5 Towards bus-based Design ..................................................................................................... 3-103.3.6 Finite State Machine (FSM) ..................................................................................................... 3-133.4 Datapath Design ............................................................................................................................. 3-153.4.1 ISA and datapath width ........................................................................................................... 3-173.4.2 Width of the Clock Pulse ......................................................................................................... 3-183.4.3 Checkpoint .............................................................................................................................. 3-183.5 Control Unit Design ........................................................................................................................ 3-183.5.1 ROM plus state register .......................................................................................................... 3-193.5.2 FETCH macro state .................................................................................................................. 3-233.5.3 DECODE macro state ............................................................................................................... 3-253.5.4 EXECUTE macro state: ADD instruction (part of R-Type) ........................................................ 3-263.5.5 EXECUTE macro state: NAND instruction (part of R-Type) ..................................................... 3-283.5.6 EXECUTE macro state: JALR instruction (part of J-Type) ........................................................ 3-283.5.7 EXECUTE macro state: LW instruction (part of I-Type) ........................................................... 3-293.5.8 EXECUTE macro state: SW and ADDI instructions (part of I-Type) ......................................... 3-303.5.9 EXECUTE macro state: BEQ instruction (part of I-Type) ......................................................... 3-313.5.10 Engineering a conditional branch in the microprogram ....................................................... 3-323.5.11 DECODE macro state revisited .............................................................................................. 3-343.6 Alternative Style of Control Unit Design ........................................................................................ 3-353.6.1 Microprogrammed Control ..................................................................................................... 3-353.6.2 Hardwired control ................................................................................................................... 3-363.6.3 Choosing between the two control design styles ................................................................... 3-373.7 Summary ....................................................................................................................................... 3-383.8 Historical Perspective ..................................................................................................................... 3-383.9 Review Questions ........................................................................................................................... 3-41Chapter 4 Interrupts, Traps and Exceptions ...................... 4-14.1 Discontinuities in program execution .............................................................................................. 4-24.2 Dealing with program discontinuities .............................................................................................. 4-44.3 Architectural enhancements to handle program discontinuities .................................................... 4-74.3.1 Modifications to FSM ................................................................................................................ 4-84.3.2 A simple interrupt handler ........................................................................................................ 4-94.3.3 Handling cascaded interrupts ................................................................................................. 4-104.3.4 Returning from the handler .................................................................................................... 4-134.3.5 Checkpoint .............................................................................................................................. 4-144.4 Hardware details for handling program discontinuities ................................................................ 4-144.4.1 Datapath details for interrupts ............................................................................................... 4-144.4.2 Details of receiving the address of the handler ...................................................................... 4-164.4.3 Stack for saving/restoring ....................................................................................................... 4-184.5 Putting it all together ..................................................................................................................... 4-204.5.1 Summary of Architectural/hardware enhancements ............................................................. 4-204.5.2 Interrupt mechanism at work ................................................................................................. 4-204.6 Summary ....................................................................................................................................... 4-234.7 Review Questions ........................................................................................................................... 4-25Chapter 5 Processor Performance and Rudiments of Pipelined Processor Design ........................... 5-15.1 Space and Time Metrics ................................................................................................................... 5-15.2 Instruction Frequency ...................................................................................................................... 5-45.3 Benchmarks ..................................................................................................................................... 5-55.4 Increasing the Processor Performance ............................................................................................ 5-95.5 Speedup ........................................................................................................................................ 5-105.6 Increasing the Throughput of the Processor ................................................................................. 5-145.7 Introduction to Pipelining .............................................................................................................. 5-145.8 Towards an instruction processing assembly line ......................................................................... 5-155.9 Problems with a simple-minded instruction pipeline .................................................................... 5-175.10 Fixing the problems with the instruction pipeline ....................................................................... 5-185.11 Datapath elements for the instruction pipeline .......................................................................... 5-205.12 Pipeline-conscious architecture and implementation ................................................................. 5-225.12.1 Anatomy of an instruction passage through the pipeline .................................................... 5-235.12.2 Design of the Pipeline Registers ............................................................................................ 5-265.12.3 Implementation of the stages ............................................................................................... 5-275.13 Hazards ........................................................................................................................................ 5-275.13.1 Structural hazard ................................................................................................................... 5-285.13.2 Data Hazard ........................................................................................................................... 5-305.13.3 Control Hazard ...................................................................................................................... 5-415.13.4 Summary of Hazards ............................................................................................................. 5-515.14 Dealing with program discontinuities in a pipelined processor .................................................. 5-525.15 Advanced topics in processor design ........................................................................................... 5-555.15.1 Instruction Level Parallelism ................................................................................................. 5-555.15.2 Deeper pipelines ................................................................................................................... 5-565.15.3 Revisiting program discontinuities in the presence of out-of-order processing .................. 5-595.15.4 Managing shared resources .................................................................................................. 5-605.15.5 Power Consumption ............................................................................................................. 5-625.15.6 Multi-core Processor Design ................................................................................................. 5-635.15.7 Intel Core Microarchitecture: An example pipeline ............................................................. 5-645.16 Summary ..................................................................................................................................... 5-675.17 Historical Perspective ................................................................................................................... 5-675.18 Review Questions ......................................................................................................................... 5-68Chapter 6 Processor Scheduling ........................................... 6-16.1 Introduction .................................................................................................................................... 6-16.2 Programs and Processes .................................................................................................................. 6-26.3 Scheduling Environments ................................................................................................................. 6-76.4 Scheduling Basics ............................................................................................................................. 6-96.5 Performance Metrics ..................................................................................................................... 6-126.6 Non-preemptive Scheduling Algorithms ........................................................................................ 6-156.6.1 First-Come First-Served (FCFS) ................................................................................................ 6-156.6.2 Shortest Job First (SJF) ............................................................................................................ 6-196.6.3 Priority .................................................................................................................................... 6-216.7 Preemptive Scheduling Algorithms ................................................................................................ 6-236.7.1 Round Robin Scheduler ........................................................................................................... 6-266.8 Combining Priority and Preemption .............................................................................................. 6-316.9 Meta Schedulers ............................................................................................................................ 6-316.10 Evaluation ................................................................................................................................... 6-326.11 Impact of Scheduling on Processor Architecture ......................................................................... 6-346.12 Summary and a Look ahead ......................................................................................................... 6-366.13 Linux Scheduler – A case study .................................................................................................... 6-366.14 Historical Perspective ................................................................................................................... 6-396.15 Review Questions ......................................................................................................................... 6-41Chapter 7 Memory Management Techniques ..................... 7-17.1 Functionalities provided by a memory manager ............................................................................. 7-17.2 Simple Schemes for Memory Management .................................................................................... 7-47.3 Memory Allocation Schemes ........................................................................................................... 7-87.3.1 Fixed Size Partitions .................................................................................................................. 7-97.3.2 Variable Size Partitions ........................................................................................................... 7-107.3.3 Compaction ............................................................................................................................. 7-137.4 Paged Virtual Memory ................................................................................................................... 7-147.4.1 Page Table ............................................................................................................................... 7-177.4.2 Hardware for Paging ............................................................................................................... 7-197.4.3 Page Table Set up .................................................................................................................... 7-207.4.4 Relative sizes of virtual and physical memories ..................................................................... 7-207.5 Segmented Virtual Memory ........................................................................................................... 7-217.5.1 Hardware for Segmentation ................................................................................................... 7-267.6 Paging versus Segmentation .......................................................................................................... 7-277.6.1 Interpreting the CPU generated address ................................................................................ 7-297.7 Summary ....................................................................................................................................... 7-307.8 Historical Perspective ..................................................................................................................... 7-327.8.1 MULTICS ................................................................................................................................. 7-337.8.2 Intel’s Memory Architecture ................................................................................................... 7-357.9 Review Questions ........................................................................................................................... 7-36Chapter 8 Details of Page-based Memory Management .... 8-18.1 Demand Paging ............................................................................................................................... 8-18.1.1 Hardware for demand paging ................................................................................................... 8-18.1.2 Page fault handler ..................................................................................................................... 8-28.1.3 Data structures for Demand-paged Memory Management ..................................................... 8-38.1.4 Anatomy of a Page Fault ........................................................................................................... 8-58.2 Interaction between the Process Scheduler and Memory Manager ............................................... 8-88.3 Page Replacement Policies .............................................................................................................. 8-98.3.1 Belady’s Min ............................................................................................................................ 8-108.3.2 Random Replacement ............................................................................................................. 8-108.3.3 First In First Out (FIFO) ............................................................................................................ 8-118.3.4 Least Recently Used (LRU) ...................................................................................................... 8-138.3.5 Second chance page replacement algorithm.......................................................................... 8-178.3.6 Review of page replacement algorithms ................................................................................ 8-208.4 Optimizing Memory Management................................................................................................. 8-228.4.1 Pool of free page frames ......................................................................................................... 8-228.4.2 Thrashing ................................................................................................................................ 8-238.4.3 Working set ............................................................................................................................. 8-258.4.4 Controlling thrashing .............................................................................................................. 8-268.5 Other considerations ..................................................................................................................... 8-288.6 Translation Lookaside Buffer (TLB) ................................................................................................ 8-288.6.1 Address Translation with TLB .................................................................................................. 8-298.7 Advanced topics in memory management .................................................................................... 8-318.7.1 Multi-level page tables ............................................................................................................ 8-318.7.2 Access rights as part of the page table entry .......................................................................... 8-348.7.3 Inverted page tables ............................................................................................................... 8-348.8 Summary ....................................................................................................................................... 8-348.9 Review Questions ........................................................................................................................... 8-35Chapter 9 Memory Hierarchy .............................................. 9-19.1 The Concept of a Cache ................................................................................................................... 9-29.2 Principle of Locality .......................................................................................................................... 9-39.3 Basic terminologies .......................................................................................................................... 9-49.4 Multilevel Memory Hierarchy .......................................................................................................... 9-59.5 Cache organization ........................................................................................................................... 9-89.6 Direct-mapped cache organization .................................................................................................. 9-99.6.1 Cache Lookup .......................................................................................................................... 9-119.6.2 Fields of a Cache Entry ............................................................................................................ 9-139.6.3 Hardware for direct mapped cache ........................................................................................ 9-149.7 Repercussion on pipelined processor design ................................................................................. 9-169.8 Cache read/write algorithms ......................................................................................................... 9-179.8.1 Read access to the cache from the CPU ................................................................................. 9-189.8.2 Write access to the cache from the CPU ................................................................................ 9-199.9 Dealing with cache misses in the processor pipeline .................................................................... 9-229.9.1 Effect of memory stalls due to cache misses on pipeline performance ................................. 9-239.10 Exploiting spatial locality to improve cache performance ........................................................... 9-259.10.1 Performance implications of increased blocksize ................................................................. 9-309.11 Flexible placement ....................................................................................................................... 9-319.11.1 Fully associative cache .......................................................................................................... 9-329.11.2 Set associative cache ............................................................................................................ 9-349.11.3 Extremes of set associativity ................................................................................................. 9-379.12 Instruction and Data caches ......................................................................................................... 9-399.13 Reducing miss penalty ................................................................................................................. 9-409.14 Cache replacement policy ............................................................................................................ 9-419.15 Recapping Types of Misses .......................................................................................................... 9-439.16 Integrating TLB and Caches .......................................................................................................... 9-469.17 Cache controller ........................................................................................................................... 9-489.18 Virtually indexed physically tagged cache ................................................................................... 9-499.19 Recap of Cache Design Considerations ........................................................................................ 9-529.20 Main memory design considerations ........................................................................................... 9-529.20.1 Simple main memory ............................................................................................................ 9-539.20.2 Main memory and bus to match cache block size ................................................................ 9-549.20.3 Interleaved memory ............................................................................................................. 9-559.21 Elements of a modern main memory systems ............................................................................ 9-569.21.1 Page mode DRAM ................................................................................................................. 9-619.22 Performance implications of memory hierarchy ......................................................................... 9-629.23 Summary ..................................................................................................................................... 9-639.24 Memory hierarchy of modern processors – An example ............................................................ 9-659.25 Review Questions ......................................................................................................................... 9-66Chapter 10 Input/Output and Stable Storage ................... 10-110.1 Communication between the CPU and the I/O devices .............................................................. 10-110.1.1 Device controller ................................................................................................................... 10-210.1.2 Memory Mapped I/O ............................................................................................................ 10-310.2 Programmed I/O .......................................................................................................................... 10-510.3 DMA ............................................................................................................................................ 10-610.4 Buses ........................................................................................................................................... 10-910.5 I/O Processor .............................................................................................................................. 10-1010.6 Device Driver .............................................................................................................................. 10-1110.6.1 An Example ......................................................................................................................... 10-1210.7 Peripheral Devices ..................................................................................................................... 10-1510.8 Disk Storage ............................................................................................................................... 10-1710.8.1 Saga of Disk Technology ...................................................................................................... 10-2410.9 Disk Scheduling Algorithms ........................................................................................................ 10-2710.9.1 First-Come First Served ....................................................................................................... 10-3010.9.2 Shortest Seek Time First ..................................................................................................... 10-3010.9.3 Scan (elevator algorithm) .................................................................................................... 10-3110.9.4 C-Scan (Circular Scan) ......................................................................................................... 10-3210.9.5 Look and C-Look .................................................................................................................. 10-3310.9.6 Disk Scheduling Summary ................................................................................................... 10-3310.9.7 Comparison of the Algorithms ............................................................................................ 10-3410.10 Solid State Drive ....................................................................................................................... 10-3610.11 Evolution of I/O Buses and Device Drivers .............................................................................. 10-3810.11.1 Dynamic Loading of Device Drivers................................................................................... 10-3910.11.2 Putting it all Together ....................................................................................................... 10-3910.12 Summary ................................................................................................................................. 10-4210.13 Review Questions ..................................................................................................................... 10-42Chapter 11 File System ........................................................ 11-111.1 Attributes .................................................................................................................................... 11-211.2 Design Choices in implementing a File System on a Disk Subsystem .......................................... 11-811.2.1 Contiguous Allocation ........................................................................................................... 11-911.2.2 Contiguous Allocation with Overflow Area ......................................................................... 11-1211.2.3 Linked Allocation ................................................................................................................. 11-1211.2.4 File Allocation Table (FAT) .................................................................................................. 11-1311.2.5 Indexed Allocation .............................................................................................................. 11-1511.2.6 Multilevel Indexed Allocation ............................................................................................. 11-1711.2.7 Hybrid Indexed Allocation ................................................................................................... 11-1811.2.8 Comparison of the allocation strategies ............................................................................. 11-2111.3 Putting it all together ................................................................................................................. 11-2211.3.1 i-node ................................................................................................................................. 11-2811.4 Components of the File System ................................................................................................. 11-2911.4.1 Anatomy of creating and writing files ................................................................................. 11-3011.5 Interaction among the various subsystems ............................................................................... 11-3111.6 Layout of the file system on the physical media........................................................................ 11-3411.6.1 In memory data structures ................................................................................................. 11-3711.7 Dealing with System Crashes ..................................................................................................... 11-3811.8 File systems for other physical media ........................................................................................ 11-3911.9 A summary of modern file systems ........................................................................................... 11-3911.9.1 Linux ................................................................................................................................... 11-3911.9.2 Microsoft Windows ............................................................................................................. 11-4511.10 Summary ................................................................................................................................. 11-4711.11 Review Questions ..................................................................................................................... 11-48Chapter 12 Multithreaded Programming and Multiprocessors ............................. 12-112.1 Why Multithreading? ................................................................................................................... 12-112.2 Programming support for threads ............................................................................................... 12-312.2.1 Thread creation and termination .......................................................................................... 12-312.2.2 Communication among threads ........................................................................................... 12-612.2.3 Read-write conflict, Race condition, and Non-determinism ................................................ 12-712.2.4 Synchronization among threads ......................................................................................... 12-1212.2.5 Internal representation of data types provided by the threads library .............................. 12-1912.2.6 Simple programming examples .......................................................................................... 12-2012.2.7 Deadlocks and livelocks ...................................................................................................... 12-2512.2.8 Condition variables ............................................................................................................. 12-2712.2.9 A complete solution for the video processing example ..................................................... 12-3012.2.10 Rechecking the predicate .................................................................................................. 12-3312.3 Summary of thread function calls and threaded programming concepts ................................. 12-3612.4 Points to remember in programming with threads ................................................................... 12-3812.5 Using threads as software structuring abstraction .................................................................... 12-3912.6 POSIX pthreads library calls summary ....................................................................................... 12-4012.7 OS support for threads ............................................................................................................... 12-4212.7.1 User level threads ............................................................................................................... 12-4512.7.2 Kernel level threads ............................................................................................................ 12-4712.7.3 Solaris threads: An example of kernel level threads .......................................................... 12-4912.7.4 Threads and libraries........................................................................................................... 12-5012.8 Hardware support for multithreading in a uniprocessor ........................................................... 12-5112.8.1 Thread creation, termination, and communication among threads .................................. 12-5112.8.2 Inter-thread synchronization .............................................................................................. 12-5112.8.3 An atomic test-and-set instruction ..................................................................................... 12-5212.8.4 Lock algorithm with test-and-set instruction...................................................................... 12-5412.9 Multiprocessors ......................................................................................................................... 12-5512.9.1 Page tables .......................................................................................................................... 12-5612.9.2 Memory hierarchy .............................................................................................................. 12-5612.9.3 Ensuring atomicity .............................................................................................................. 12-5912.10 Advanced Topics ...................................................................................................................... 12-5912.10.1 OS topics ........................................................................................................................... 12-6012.10.2 Architecture topics ............................................................................................................ 12-7612.10.3 The Road Ahead: Multi- and Many-core Architectures .................................................... 12-8712.11 Summary ................................................................................................................................. 12-8912.12 Historical Perspective ............................................................................................................... 12-9012.13 Review Questions ..................................................................................................................... 12-92Chapter 13 Fundamentals of Networking and Network Protocols ................................. 13-113.1 Preliminaries ............................................................................................................................... 13-113.2 Basic Terminologies ..................................................................................................................... 13-213.3 Networking Software ................................................................................................................... 13-613.4 Protocol Stack .............................................................................................................................. 13-813.4.1 Internet Protocol Stack ......................................................................................................... 13-913.4.2 OSI Model ............................................................................................................................ 13-1213.4.3 Practical issues with layering .............................................................................................. 13-1313.5 Application Layer ....................................................................................................................... 13-1413.6 Transport Layer .......................................................................................................................... 13-1513.6.1 Stop and wait protocols ...................................................................................................... 13-1713.6.2 Pipelined protocols ............................................................................................................. 13-2013.6.3 Reliable Pipelined Protocol ................................................................................................. 13-2213.6.4 Dealing with transmission errors ........................................................................................ 13-2813.6.5 Transport protocols on the Internet ................................................................................... 13-2813.6.6 Transport Layer Summary ................................................................................................... 13-3213.7 Network Layer ............................................................................................................................ 13-3213.7.1 Routing Algorithms ............................................................................................................. 13-3313.7.2 Internet Addressing ............................................................................................................ 13-4013.7.3 Network Service Model....................................................................................................... 13-4313.7.4 Network Routing Vs. Forwarding ........................................................................................ 13-4713.7.5 Network Layer Summary .................................................................................................... 13-4813.8 Link Layer and Local Area Networks .......................................................................................... 13-5013.8.1 Ethernet .............................................................................................................................. 13-5013.8.2 CSMA/CD ............................................................................................................................. 13-5113.8.3 IEEE 802.3 ............................................................................................................................ 13-5313.8.4 Wireless LAN and IEEE 802.11 ............................................................................................ 13-5413.8.5 Token Ring ........................................................................................................................... 13-5513.8.6 Other link layer protocols ................................................................................................... 13-5713.9 Networking Hardware ................................................................................................................ 13-5813.10 Relationship between the Layers of the Protocol Stack .......................................................... 13-6313.11 Data structures for packet transmission .................................................................................. 13-6313.11.1 TCP/IP Header ................................................................................................................... 13-6513.12 Message transmission time ..................................................................................................... 13-6613.13 Summary of Protocol Layer Functionalities ............................................................................. 13-7213.14 Networking Software and the Operating System .................................................................... 13-7313.14.1 Socket Library .................................................................................................................... 13-7313.14.2 Implementation of the Protocol Stack in the Operating System ...................................... 13-7513.14.3 Network Device Driver ...................................................................................................... 13-7613.15 Network Programming using Unix Sockets .............................................................................. 13-7713.16 Network Services and Higher Level Protocols ......................................................................... 13-8513.17 Summary ................................................................................................................................. 13-8613.18 Historical Perspective ............................................................................................................... 13-8713.18.1 From Telephony to Computer Networking ....................................................................... 13-8713.18.2 Evolution of the Internet .................................................................................................. 13-9013.18.3 PC and the arrival of LAN .................................................................................................. 13-9113.18.4 Evolution of LAN ............................................................................................................... 13-9113.19 Review Questions ..................................................................................................................... 13-94Chapter 14 Epilogue: A Look Back at the Journey .......... 14-114.1 Processor Design .......................................................................................................................... 14-114.2 Process ........................................................................................................................................ 14-114.3 Virtual Memory System and Memory Management ................................................................... 14-214.4 Memory Hierarchy ....................................................................................................................... 14-214.5 Parallel System ............................................................................................................................. 14-314.6 Input/Output Systems .................................................................................................................. 14-314.7 Persistent Storage ........................................................................................................................ 14-314.8 Network ...................................................................................................................................... 14-414.9 Concluding Remarks ..................................................................................................................... 14-4Appendix A Network Programming with Unix Sockets ... A-1A.1 The problem ................................................................................................................................... A-1A.2 Source files provided ...................................................................................................................... A-1A.3 Makefile ......................................................................................................................................... A-1A.4 Common header file ....................................................................................................................... A-3A.5 Client source code .......................................................................................................................... A-3A.6 Server source code ......................................................................................................................... A-7A.7 Instantiating the client/server programs ...................................................................................... A-12