編譯原理-全動(dòng)態(tài)內(nèi)存管理

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Compiler Theory Fall 2003 Jianhui Yue,*,Chapter 7,Dynamic Memory,Parameter Passing Mechanisms,Instructor Jianhui Yue,Software College SCU,compilerscu21cn,Limitations of Stack-Based Environment,If a reference to a local variable in a procedure can be returned to the caller, the result will be dangling reference.,When the procedure is exited, the activation record will be deallocated from the stack.,addr = dangle(),causes,addr,to point to an unsafe location.,Such program is erroneous in C.,(No compiler will give an error message),int *dangle(),int x;,return ,Limitations of Stack-Based Environment (cont),C prohibits local procedures.,Functional programming languages (LISP, ML),Functions must be able to be,locally defined,Passed as parameters,Returned as results.,Stack-based runtime environment is inadequate for these languages.,Fully Dynamic Environment,It can deallocate activation records only when all references to them have disappeared.,Activation records can be dynamically freed at arbitrary times during execution.,Fully dynamic environment is more complicated.,Tracking the references during execution.,Finding and deallocating inaccessible areas of memory at arbitrary times during execution (garbage collection).,Activation Records,The basic structure of an activation record remains the same:,Space for parameters and local variables.,Control and access links.,The exited activation record remains in memory, to be deallocated at some later time.,The entire additional complexity can be encapsulated in a memory manager that replaces the runtime stack operations with more general allocation and deallocation routines.,Object-Oriented Languages,OO languages require special mechanisms in the runtime environment to implement their added features:,Objects,Methods,Inheritance,Dynamic binding,OO languages vary in their requirements for the runtime environment:,C+ retains the stack-based environment of C, no automatic dynamic memory management,Smalltalk requires fully dynamic environment similar to LISP,Implementation of Objects,Keep a complete description of the class structure in memory during execution.,Maintain the inheritance by the superclass pointers.,Keep pointers to all methods.,Each object keeps:,Fields for instance variables,A pointer to its defining class,All methods (local and inherited) are found through it.,Instance variables have predictable offsets.,Methods do not. They are maintained in a symbol table structure with lookup capabilities.,Implementation of Objects (cont),An alternative approach is to compute a list of code pointers for methods of each class, and store this in (static) memory as a virtual function table.,It can be arranged so that each method has a predictable offset.,Each object contains a pointer to the appropriate,virtual function table,.,It is the method of choice for C+.,Example 7.8,class A, public:,double x, y;,void f();,virtual void g();,;,class B: public A, public:,double z;,void f();,virtual void h();,;,x,y,Virtual function table pointer,A:g,x,y,Virtual function table pointer,z,A:g,B:h,Object A,Object B,Heap,The data structure that handles pointer allocation and deallocation is called heap.,Heap is usually allocated as a linear block of memory in a way that it can grow, while interfering as little as possible with the stack.,Heap provides to operation,Allocate,Takes size parameter,Return a pointer to a block of memory of the correct size or null if none exists.,Free,Takes a pointer to an allocated block of memory,Marks it as being free,Must be able to find the size of the block.,Heap Implementation,Use circular linked list of free blocks.,Two drawbacks:,Free operation cannot tell whether its pointer is pointing at a block of memory that was previously allocated by,malloc,.,Need to,coalesce,blocks to the adjacent free blocks. The result is a free block of the maximal size.,This needs to be done to avoid the fragmentation.,Improved Heap Implementation,1 Tow improvements ( more robust , self-coalescing blocks ),Bookkeeping information : Header,(next : pointer to the next block in the list ,usedsize , freesize ),Free space pointer :memptr,( point to the block hold free space ),next,usedsize,freesize,used space,free space,header,malloc and free operation on heap,allocated header,free space,used,used,used,free,memptr,used,free,used,free,memptr,a,b,c,a : initialized b: 3 times malloc operations c free one block,memptr,malloc ( nbytes),Header *p ,*newp; unsigned nunits;,nunits= ( nbytes+sizeof(Header)-1)/sizeof(Header ) + 1;,/* initiate the first header */,/* search the list with the first fit , the p points to the first fit block */,newp=p+p->s.usedsized ;,newp ->used= nunits;,newp ->s.freesize=p->s.freesize-nunits;,newp->s.next=p->s.next;,p->s.freesize=0;,p->s.next=newp;,memptr=newp;,return (void *) (newp+1);,free ( void *ap ), Header *bp,*p,*prev;,bp= (Header *) ap 1;,/* search the list to find the block containing ap */,prev->s.freesize+=p->s.usedsize+p->s.freesize;,prev->s.next=p->s.next;,memptr=prev;,Automatic Management of Heap,The programmer uses the explicit management on the heap using manually malloc( ) and free( ).,In the fully dynamic runtime environment, the heap should be managed automatically.,malloc,can be automatically scheduled at each procedure call.,free,cannot be automatically scheduled on exit,Activation records must persist until all references to them have disappeared.,Mark and Sweep,The standard technique is,mark and sweep garbage collection,.,No memory is freed until the call to,malloc,fails.,Follow all pointer recursively and mark each block of storage reached.,Sweep linearly through the memory, return unmarked blocks to free memory.,Memory compaction by moving all the allocated space to one end of the heap,Drawbacks,Extra storage for marks,Delay in processing (minutes) due to multiple passes.,Parameter Passing Mechanisms,Parameters correspond the to locations in the activation record, which are filled with parameter values (arguments).,To the called procedure, a parameter represents a pure formal value. It serves to establish a location in the activation record, where the procedure can find the value of the parameter.,Common Parameter Passing Mechanisms,Pass by value,Pass by reference,Pass by value-result,Pass by name (delayed evaluation),Parameter Evaluation Order,In most situations, the order in which arguments are evaluated is unimportant. Any evaluation order will produce the same result.,It is not true in general.,f(+x, x),A standard evaluation order may be specified,By the language definition,By a compiler writer (different implementations),C compilers typically evaluate their arguments from right to left.,Pass by Value,This is the only parameter passing mechanism available in C.,The parameters in the body of the procedure are replaced by the values of the arguments.,In C, value parameters are viewed as initialized local variables.,Changes to them never cause any nonlocal changes.,void inc2(int x), +x; +x; /* incorrect */,void inc2(int* x), +x; +x; /* correct */,inc2(,Pass by Reference,Pass by reference passes the location of the variable, so that the parameter becomes an alias for the argument.,Any changes made to parameter occur to the argument as well.,This is the only parameter passing in FORTRAN77.,void inc2(int & x), +x; +x; /* correct */,inc2(y);,Pass by Reference (cont),The compiler must,Compute the address of the argument,Store it in the local activation record,Turn local accesses to a reference parameter into indirect accesses,No copy of the passed value is made.,This is significant when the parameter is a large structure.,Pass by Value-Result,Similar to pass by reference.,No actual alias is established,The value of the argument is copied and used in the procedure,On exit the final value of the parameter is copied back out to the location of the argument.,This method is known as copy-in, copy-out or copy-restore.,void p(int x, int y), +x; +y;,main (), int a=1;,p(a,a);,return 0;,a,has value of,3,after,p,is called if pass by reference is used.,a,has value of,2,after,p,is called if pass by value-result is used.,Pass by Name,The idea is that the argument is not evaluated until its actual use in the called program.,The name of the argument replaces the name of the parameter it corresponds to.,int i;,int a10,void p(int x), +i; +x;,main(), i=1;,a1=1;,a2=2,p(ai);,return 0; ,a2,is set to 3,a1,is unchanged,Pass by Name (cont),Pass by name was offered in,Algol60, but become unpopular.,It can give surprising and counterintuitive results in the presence of the side effects.,It is difficult to implement,Each argument must be turned into the procedure,It is inefficient,A variation on this mechanism called,lazy evaluation,become popular in purely functional languages,(Miranda, Haskell),Homework,7.11, 7.15,