Topic 3 Run Time Environment Memory Model Activation Record Call Convention Storage Allocation Runtime Stack and Heap Garbage Collection 2 29 2008 1 ABET Outcome Understand the software conventions necessary to support various source languages including data representation storage allocation for the various storage classes of variables visibility rules call sequence entry exit and return Ability to apply the knowledge of run time support system to trace the program execution 2 29 2008 course cpeg421 08s Topic 3 ppt 2 Reading List Slides Dragon book chapter 7 Muchnick s book Chapter 5 Other readings as assigned in class or homeworks 2 29 2008 course cpeg421 08s Topic 3 ppt 3 What Does Runtime Environment Do The execution environment provided by the system software services The runtime environment dictates how executable code is loaded into memory where data is stored and how routines call other routines and system software routines 2 29 2008 course cpeg421 08s Topic 3 ppt 4 Jobs of Runtime Environment Issues Software conventions such as data layout and allocation Mechanism to access variables Procedure calling Interface to OS libraries I O devices etc Names versus data objects Same name can refer to different data objects during execution the runtime environment provides the mapping Procedure activations Each time a procedure is called a new activation of that procedure occurs within an environment who call it where it was called from What declarations are active at call site Recursion a new activation of same procedure can start before an early activation has ended 2 29 2008 course cpeg421 08s Topic 3 ppt 5 Runtime Environment Architecture Instruction Set Architecture ISA Data Types Register Usage Convention Memory System Addressing Model the organization of data in registers and memory Operating system Memory organization and management Stack Usage Convention Special Register Initialization Compiler Data layout Activation Record Calling convention 2 29 2008 course cpeg421 08s Topic 3 ppt 6 Related Topics Memory Model Memory Layout Register usage Procedure calling convention Runtime Stack and Heap 2 29 2008 course cpeg421 08s Topic 3 ppt 7 MIPS Architecture Overview Processor Features Full 32 bit operation efficient pipelining on chip TLB Translation Lookaside Buffer for virtual to physical memory mapping cache control coprocessor interface Registers 32 general 32 bit registers a 32 bit Program Counter ISA Instruction Set Architecture Each instruction is 32 bits long three instruction formats intermediate Itype jump J type and register R type Memory Management System Physical memory addressing range of 4 Gbytes 32 bits The virtual address space is divided into 2 Gbytes for users and 2 Gbytes for the kernel Addressing Model Defines a 64 bit doubleword a 32 bit word a 16 bit halfword and an 8 bit byte Byte addressing The byte ordering can be configured in either Bigendian or Little endian format 2 29 2008 course cpeg421 08s Topic 3 ppt 8 MIPS Register Usage Convention Mnemonic Name Register Number Conventional Use 0 zero Permanently 0 1 at Assembler Temporary reserved 2 3 v0 v1 Value returned by a subroutine 4 7 a0 a3 Arguments to a subroutine 8 15 t0 t7 Temporary not preserved across a function call 16 23 s0 s7 Saved registers preserved across a function call 24 25 t8 t9 Temporary 26 27 k0 k1 Kernel reserved for OS 28 gp Global Pointer 29 sp Stack Pointer 30 fp Frame Pointer 31 ra Return Address Automatically used in some instructions 2 29 2008 course cpeg421 08s Topic 3 ppt 9 Memory Model Modern computer systems nearly always use virtual memory The purpose of virtual memory is to make it appear as if a program has the full address space available So the programming model has the full address space User memory space Virtual memory OS memory space Physical memory 2 29 2008 course cpeg421 08s Topic 3 ppt 10 Why Virtual Memory Why Virtual Memory Limited physical memory size 64MB to 2GB Unlimited virtual memory size Each process may have 4GB Many processes in the system 2 29 2008 course cpeg421 08s Topic 3 ppt 11 Virtual Memory Physical Memory Physical memory and virtual memory broke into fixed size pages Each physical page holds a virtual page may come from different processes Only the active pages of each process reside in physical memory physical memory works as cache of virtual memory disk Other pages stay on disk 2 29 2008 course cpeg421 08s Topic 3 ppt 12 Mapping Virtual Memory to Physical Memory Physical Memory Process 1 VM Page 0 OS U1 P0 U2 P0 Page 1 OS U1 P1 U2 P1 Page 2 U1 P0 U1 P2 U2 P2 Page 3 U2 P3 U1 P3 U2 P3 Page 4 U1 P3 U1 P4 U2 P4 Page 5 U1 P7 U1 P5 U2 P5 Page 6 U1 P6 U1 P6 U2 P6 Page 7 U2 P1 U1 P7 U2 P7 Process 2 VM On Disk 2 29 2008 course cpeg421 08s Topic 3 ppt 13 Virtual Memory Layout Virtual address Stack High Reserved for kernel Stack segment Heap BSS Global Data Dynamic data Static data Data segment Data Text segment Text VM Layout User View 2 29 2008 Reserved Low VM Layout OS View course cpeg421 08s Topic 3 ppt 14 Procedure Activation A procedure is activated when it is called 2 29 2008 course cpeg421 08s Topic 3 ppt 15 Activation Lifetime Lifetime of an activation of procedure P is the sequence between first and last steps in execution of procedure body including time spend executing any procedures called from P Structure program languages allow only nested procedure lifetimes Allows use of stack to define runtime environment Can show relations in procedure activation tree 2 29 2008 course cpeg421 08s Topic 3 ppt 16 Activation Tree A data structure that represents the activations during the running of an entire program Assumption Each execution of a procedure starts at the beginning of the procedure body and eventually returns control to the point immediately following the place where the procedure was called 2 29 2008 course cpeg421 08s Topic 3 ppt 17 Activation Tree Con t Features of activation tree Each node is a procedure activation each edge represents opening an activation while the parent activation is still open The root node is the main program activation Flow of control in procedure calls corresponds to a preorder depth first traversal of the activation tree Flow of control in procedure returns corresponds to a postorder traversal of the activation tree A node A is to the left of node B in the tree means the lifetime of A occurs before the lifetime of B We can use a control stack to keep track of live procedure activations 2 29 2008 course