《編譯原理-全動(dòng)態(tài)內(nèi)存管理》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《編譯原理-全動(dòng)態(tài)內(nèi)存管理（27頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、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 E
2、nvironment,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 erron
3、eous 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
4、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.,Tra
5、cking 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.,
6、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 req
7、uire 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 require
8、s 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 de
9、fining 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 f
10、or 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
11、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 i
12、s 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 all
13、ocated 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,coal
14、esce,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 th
15、e 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 mal
16、loc 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;
17、,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.nex
18、t=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,c
19、annot 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 o
20、f 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 corr
21、espond 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 Param
22、eter 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,
23、 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
24、 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 pas
25、ses 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,Compu
26、te 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 al
27、ias 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
28、,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 c
29、orresponds 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,
編譯原理-全動(dòng)態(tài)內(nèi)存管理
