Memory ManagementMemory Managementldots Memory Managementldots Dynamic Memory ManagementRun-Time Memory OrganizationRun-Time Memory Organizationldots Storage AllocationStorage Allocationldots Global Variables -- MIPSGlobal Variables -- Allocation by NameGlobal Variables -- Allocation in BlockGlobal Variables -- Allocation on StackStorage Allocationldots Readings and References520 —Spring 2008 — 4CSc 520Principles of ProgrammingLanguages4 : Memory Management — IntroductionChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 4Memory ManagementIn a language such as C or Pascal, there are threeways to allocate memory:1. Static allocation. Global variables are allocated atcompile time, by reserving2. Stack allocation. The stack is used to storeactivation records, which holds procedure call chainsand local variables.3. Dynamic allocation. The user can create newmemory at will, by calling a new or (in unix) mallocprocedure.The compiler and run-time system divide the availableaddress space (memory) into three sections, one foreach type of allocation:[2]520 —Spring 2008 — 4Memory Management...1. The static section is generated by the compiler andcannot be extended at run-time. Called theuninitialized data section in unix’s a.out.2. The stack. The stack grows and shrinks duringexecution, according to the depth of the call chain.Infinite recursion often leads to stack overflow. Largeparameters can also result in the program runningout of stack space.3. The heap. When the program makes a request formore dynamic memory (by calling malloc, forexample), a suitable chunk of memory is allocatedon the heap.[3]520 —Spring 2008 — 4Memory Management...Static allocation – GlobalvariablesStack allocation – Procedurecall chains, Local variables.Dynamic allocation – NEW,malloc, On the heap.Heap(Global Variables)Initialized Data(strings,reals...)Program CodeStackUninitialized Data[4]520 —Spring 2008 — 4Dynamic Memory ManagementThe run-time system linked in with the generated codeshould contain routines for allocation/deallocation ofdynamic memory.Pascal, C, C++, Modula-2 Explicit deallocation of dynamicmemory only. I.e. the programmer is required to keeptrack of all allocated memory and when it’s safe to freeit.Eiffel Implicit deallocation only. Dynamic memory which isno longer used is recycled by the garbage collector.Ada Implicit or explicit deallocation (implementationdefined).Modula-3 Implicit and explicit deallocation (programmer’schoice).[5]520 —Spring 2008 — 4Run-Time Memory OrganizationLow ⇒ HeapAddresses ⇓...⇑StackStatic DataHigh Initialized DataAddresses ⇒ Text Segment[6]520 —Spring 2008 — 4Run-Time Memory Organization...This is a common organization of memory on Unixsystems.The Text Segment holds the code (instructions) of theprogram. The Initialized Data segment holdsstrings, etc, that don’t change. Static Data holdsglobal variables. The Stack holds procedure activationrecords and the Heap dynamic data.[7]520 —Spring 2008 — 4Storage AllocationGlobal Variables are stored in the Static Data area.Strings (such as "Bart!") are stored in the InitializedData section.Dynamic Variables are stored on the Heap:PROCEDURE P ();VAR X : POINTER TO CHAR;BEGINNEW(X);END P[8]520 —Spring 2008 — 4Storage Allocation...Own Variables are stored in the Static Data area. An Ownvariable can only be referenced from within theprocedure in which it is declared. It retains its valuebetween procedure calls.PROCEDURE P (X : INTEGER);OWN W : INTEGER;VAR L : INTEGER;BEGIN W := W + X; END P[9]520 —Spring 2008 — 4Global Variables – MIPSHow do we allocate space for and access globalvariables? We’ll examine three ways.Running Example:PROGRAM P;VAR X : INTEGER; (* 4 bytes. *)VAR C : CHAR; (* 1 byte. *)VAR R : REAL; (* 4 bytes. *)END.[10]520 —Spring 2008 — 4Global Variables – Allocation by NameAllocate each global variable individually in the datasection. Prepend an underscore to each variable toavoid conflict with reserved words.Remember that every variable has to be aligned on anaddress that is a multiple of its size..dataX: .space 4C: .space 1.align 2 # 4 byte boundary.R: .space 4.textmain: lw $2, X[11]520 —Spring 2008 — 4Global Variables – Allocation in BlockAllocate one block of static data (called Data, forexample), holding all global variables. Refer toindividual variables by offsets from Data..dataData: .space 48.textmain: lw $2, Data+0 # Xlb $3, Data+4 # Cl.s $f4, Data+8 # R[12]520 —Spring 2008 — 4Global Variables – Allocation on StackAllocate global variables on the bottom of the stack.Refer to variables through the Global Pointer $gp, whichis set to point to the beginning of the stack.main: subu $sp,$sp,48move $gp,$splw $2, 0($gp) # Xlb $3, 4($gp) # Cl.s $f4, 8($gp) # RX: .space 4 Each access lw $2, X takes 2 cycles.Data: .space 48 Each access lw $2, Data+32takes 2 cycles.subu $sp,$sp,48 1 cycle to access the first 64K globalvariables.[13]520 —Spring 2008 — 4Storage Allocation...Local Variables: stored on the run-time stack.Actual parameters: stored on the stack or in special argumentregisters.Languages that allow recursion cannot store local variables in theStatic Data section. The reason is that every Procedure Activationneeds its own set of local variables.For every new procedure activation, a new set of local variables iscreated on the run-time stack. The data stored for a procedureactivation is called an Activation Record.Each Activation Record (or (Procedure) Call Frame) holds the localvariables and actual parameters of a particular procedure activation.[14]520 —Spring 2008 — 4Readings and ReferencesRead Scott, pp.
View Full Document
Unlocking...