上海交通大学：《编译原理》教学资源_第六周讲义_Heap Management

Heap Management slide I

Heap Mana gement slide 1

Quote of the day "Manually managing blocks of memory in C is like juggling bars of soap in a prison shower: It's all fun and games until you forget about one of them.” Unknown slide2

Quote of the Day “Manually managing blocks of memory in C is lik j li b f i i h like juggling bars of soap in a prison shower: It's all fun and games until you forget about one ofh ” t em. - Unknown slide 2

Major Areas of Memory ●Static area Fixed size,fixed content,allocated at compile time ·Run-time stack Variable size,variable content(activation records) -Used for managing function calls and returns ·Heap Fixed size,variable content Dynamically allocated objects and data structures Examples:ML reference cells,malloc in C,new in Java slide 3

Major Areas of Memory • Static area – Fixed size, fixed content, allocated at compile time • Run-time stack – Variable size, variable content (activation records) – Used for managing function calls and returns • Heap – Fixed size variable content Fixed size, variable content – Dynamically allocated objects and data structures • Examples: ML reference cells, malloc in C, new in Java slide 3

Heap Storage Memory allocation under explicit programmatic control -C malloc,C++/Pascal Java/C#new operation. Memory allocation implicit in language constructs -Lisp,Scheme,Haskel,SML,..most functional languages Autoboxing/unboxing in Java 1.5 and C# Deallocation under explicit programmatic control -C,C++,Pascal Deallocation implicit Java,C#,Lisp,Scheme,Haskel,SML

Heap Storage • Memory allocation under explicit programmatic control – C malloc, C++ / Pascal / Java / C# new operation. • Memory allocation implicit in language constructs – Lisp, Scheme, Haskel, SML, … most functional languages – Autoboxing/unboxing in Java 1.5 and C# • Deallocation under explicit programmatic control – C, C++, Pascal • Deallocation implicit – Java, C#, Lisp, Scheme, Haskel, SML, …

Heap Storage Deallocation Explicit versus Implicit Deallocation In explicit memory management,the program must explicitly call an operation to release memory back to the memory management system. In implicit memory management,heap memory is reclaimed automatically by a "garbage collector". Examples: Implicit:Java,Scheme Explicit:Pascal and C To free heap memory a specific operation must be called. Pascal ==dispose C ==free C++==delete Implicit and Explicit:Ada Deallocation on leaving scope

Heap Storage Deallocation Explicit versus Implicit Deallocation In explicit memory management, the program must explicitly In explicit memory management, the program must explicitly call an operation to release memory back to the memory management system. In implicit memory management, heap memory is reclaimed automatically by a “garbage collector”. Examples: • Implicit: Java, Scheme • Explicit: Pascal and C Explicit: Pascal and C To free heap memory a specific operation must be called. Pascal ==> dispose C == > free C++ ==> delete • Implicit and Explicit: Ada Deallocation on leaving scope

Cells and Liveness Cell data item in the heap -Cells are"pointed to"by pointers held in registers,stack,global/static memory,or in other heap cells Roots:registers,stack locations,global/static variables A cell is live if its address is held in a root or held by another live cell in the heap slide 6

Cells and Liveness • Cell = data item in the heap – Cells are “pointed to” by pointers held in registers, stack, global/static memory, or in other heap cells • Roots: registers, stack locations, global/static variables • A cell is live if its address is held in a root or held by another live cell in the heap slide 6

Garbage 。 Garbage is a block of heap memory that cannot be accessed by the program An allocated block of heap memory does not have a reference to it (cell is no longer "live") -Another kind of memory error:a reference exists to a block of memory that is no longer allocated 。 Garbage collection(GC)-automatic management of dynamically allocated storage Reclaim unused heap blocks for later use by program slide7

Garbage • Garbage is a block of heap memory that cannot be accessed by the program – An allocated block of heap memory does not have a reference to it (cell is no longer An allocated block of heap memory does not have a reference to it (cell is no longer “live”) – Another kind of memory error: a reference exists to a block of memory that is no longer allocated • Garbage collection (GC) - automatic management of dynamically allocated storage allocated storage – Reclaim unused heap blocks for later use by program slide 7

Example of Garbage class node int value; p=new node(); node next; q new node(); q=p; delete p, node p,q, null q (a) (b) (c) slide 8

Example of Garbage class node { int value; node next; p = new node(); q = new node(); node next; } node p, q; q (); q = p; delete p; p, q; slide 8

OO Languages and heap allocation Objects are a lot like records and instance variables are a lot like fields. =The representation of objects is similar to that of a record. Methods are a lot like procedures. =>Implementation of methods is similar to routines. But...there are differences: Objects have methods as well as instance variables,records only have fields. The methods have to somehow know what object they are associated with (so that methods can access the object's instance variables)

OO Langg p ua es and heap allocation Objects are a lot like records and instance variables are a lot like fields. like fields. => The representation of objects is similar to that of a record. Methods are a lot like procedures. => Implementation of methods is similar to routines. But… there are differences: there are differences: Objects have methods as well as instance variables, records only have fields. Th th d h t h k h t bj t th The methods have to somehow know what object they are associated with (so that methods can access the object’s instance variables) instance variables)

Example:Representation of a simple Java object Example:a simple Java object(no inheritance) class Point int x,y; (1public Point(int x,int y){ this.x=x;this.y=y; (2public void move(int dx,int dy){ x=x+dx;y=y+dy; (3public float area (){... (4public float dist (Point other){

Example: Representation of a simple Java object Example: a simple Java object (no inheritance) class Point { class Point { int x,y; ( 1 )p y ublic Point(int x, int y) { this.x=x; this.y=y; } ( ) public void move(int dx, int dy) { x=x+dx; y=y+dy; (2) x=x+dx; y=y+dy; } public float area() { ...} public float dist(Point other) { ... } } (3) (4)