资源描述
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
展开阅读全文