Memory management rankly,it would be nice to forget about memory. Our programs would just create objects as they please.One after the other,unused objects would vanish into abysses,while those most needed would slowly move closer to the top,like meritorious employees of a large corporation who manage once in a while to catch the attention of a higher officer,and by making themselves indispensable to their immediate superiors will with a bit of luck,at the end of a busy career,be admitted into the inner circle. But it is not so.Memory is not infinite;it does not harmoniously organize itself into a continuous spectrum of storage layers with decreasing access speeds,to which objects would naturally distribute.We do need to fire our useless employees,even if we must call it early retirement imposed with regret because of the overall economic situation.This chapter examines who should be thus downsized,how,and by whom. 9.1 WHAT HAPPENS TO OBJECTS Object-oriented programs create objects.The previous chapter showed how useful it is to rely on dynamic creation to obtain flexible object structures,which automatically adapt to the needs of a system's execution in any particular case. Object creation We have seen the basic operation for allocating space to new objects.In its simplest form it appears as !x and its effect was defined as threefold:create a new object;attach it to the referencex;and initialize its fields A variant of the instruction calls an initialization procedure;and you can also create new objects through routines clone and deep clone.Since all these forms of allocation internally rely on basic creation instructions,we can restrict our attention to the form !!x without fear of losing generality We will now study the effect of such instructions on memory management
9 Memory management Frankly, it would be nice to forget about memory. Our programs would just create objects as they please. One after the other, unused objects would vanish into abysses, while those most needed would slowly move closer to the top, like meritorious employees of a large corporation who manage once in a while to catch the attention of a higher officer, and by making themselves indispensable to their immediate superiors will with a bit of luck, at the end of a busy career, be admitted into the inner circle. But it is not so. Memory is not infinite; it does not harmoniously organize itself into a continuous spectrum of storage layers with decreasing access speeds, to which objects would naturally distribute. We do need to fire our useless employees, even if we must call it early retirement imposed with regret because of the overall economic situation. This chapter examines who should be thus downsized, how, and by whom. 9.1 WHAT HAPPENS TO OBJECTS Object-oriented programs create objects. The previous chapter showed how useful it is to rely on dynamic creation to obtain flexible object structures, which automatically adapt to the needs of a system’s execution in any particular case. Object creation We have seen the basic operation for allocating space to new objects. In its simplest form it appears as !! x and its effect was defined as threefold: create a new object; attach it to the reference x; and initialize its fields. A variant of the instruction calls an initialization procedure; and you can also create new objects through routines clone and deep_clone. Since all these forms of allocation internally rely on basic creation instructions, we can restrict our attention to the form !! x without fear of losing generality. We will now study the effect of such instructions on memory management
280 MEMORY MANAGEMENT $9.1 Three modes of object management First it is useful to broaden the scope of the discussion.The form of object management used for object-oriented computation is only one of three commonly found modes:static, stack-based and free.The choice between these modes determines how an entity can become attached to an object. Recall that an entity is a name in the software text representing a run-time value,or a succession ofrun-time values.Such values are either objects or(possibly void)references to objects.Entities include attributes,formal routine arguments,local entities of routines and Result.The term attached describes associations between entities and objects:at some stage during execution,an entity x is attached to an object O if the value ofx is either O(for x of expanded type)or a reference to O(forx ofreference type).Ifx is attached to O,it is sometimes convenient to say also that O is attached to x.But whereas a reference is attached to at most one object,an object may be attached to two or more references; this is the problem of dynamic aliasing,discussed in the previous chapter. In the static mode,an entity may become attached to at most one run-time object during the entire execution of the software.This is the scheme promoted by languages such as Fortran,designed to allow an implementation technique which will allocate space for all objects(and attach them to the corresponding entities)once and for all,at program loading time or at the beginning of execution. The static mode Objects FIXED MEMORY AREA The static mode is simple and supports efficient implementation on the usual computer architectures.But it presents serious limitations: It precludes recursion,since a recursive routine must be permitted to have several incarnations active at once,each with its own incarnations of the routine's entities. It also precludes dynamically created data structures,since the compiler must be able to deduce the exact size of every data structure from the software text.Each array, for example,must be statically declared with its exact size.This seriously limits the modeling power of the language:it is impossible to handle structures that grow and shrink in response to run-time events,except by allocating the maximum possible space for each of them-a technique that wastes memory,and is rather dangerous since just one data structure may cause the whole system execution to fail if its size has been underestimated
280 MEMORY MANAGEMENT §9.1 Three modes of object management First it is useful to broaden the scope of the discussion. The form of object management used for object-oriented computation is only one of three commonly found modes: static, stack-based and free. The choice between these modes determines how an entity can become attached to an object. Recall that an entity is a name in the software text representing a run-time value, or a succession of run-time values. Such values are either objects or (possibly void) references to objects. Entities include attributes, formal routine arguments, local entities of routines and Result. The term attached describes associations between entities and objects: at some stage during execution, an entity x is attached to an object O if the value of x is either O (for x of expanded type) or a reference to O (for x of reference type). If x is attached to O, it is sometimes convenient to say also that O is attached to x. But whereas a reference is attached to at most one object, an object may be attached to two or more references; this is the problem of dynamic aliasing, discussed in the previous chapter. In the static mode, an entity may become attached to at most one run-time object during the entire execution of the software. This is the scheme promoted by languages such as Fortran, designed to allow an implementation technique which will allocate space for all objects (and attach them to the corresponding entities) once and for all, at program loading time or at the beginning of execution. The static mode is simple and supports efficient implementation on the usual computer architectures. But it presents serious limitations: • It precludes recursion, since a recursive routine must be permitted to have several incarnations active at once, each with its own incarnations of the routine’s entities. • It also precludes dynamically created data structures, since the compiler must be able to deduce the exact size of every data structure from the software text. Each array, for example, must be statically declared with its exact size. This seriously limits the modeling power of the language: it is impossible to handle structures that grow and shrink in response to run-time events, except by allocating the maximum possible space for each of them — a technique that wastes memory, and is rather dangerous since just one data structure may cause the whole system execution to fail if its size has been underestimated. The static mode FIXED MEMORY AREA Objects
$9.1 WHAT HAPPENS TO OBJECTS 281 The second scheme of object allocation is the stack-based mode.Here an entity may at run time become attached to several objects in succession,and the run-time mechanisms allocate and deallocate these objects in last-in,first-out order.When an object is deallocated,the corresponding entity becomes attached again to the object to which it was previously attached,if any. The stack- based mode Objects of block i+/ Memory allocated on entry to block i+/ Order of allocation Order of (on block entry) Objects of block i deallocation (on block exit) THE STACK Memory allocated on entry to block i Dynamic arrays can Stack-based object management was made popular by Algol 60 and is supported be created in C (often in conjunction with one or both of the other two modes)in most posterior through the malloc function,a mecha- programming languages.Stack-based allocation supports recursion and,if the language nism of the“fee” permits it,arrays whose bounds only become known at run time.In Pascal and C, kind,the mode stud- however,the mechanism only applies to variables of basic types and record types-not ied next,some Pas- to arrays as it did in Algol.In practice the data structures that developers would most often cal extensions support dynamic want to allocate in this fashion are precisely arrays.Even when it applies to arrays,stack- arrays. based allocation still does not support complex data structures in their full generality. To obtain such general data structures,we need the third and last scheme:the free mode,also called heap-based because of the way it is implemented.This is the fully dynamic mode in which objects are created dynamically through explicit requests.An entity may become successively attached to any number of objects;the pattern of object creations is usually not predictable at compile time.Objects may,furthermore,contain references to other objects. The free (heap- based)mode THE HEAP The free mode allows us to create the sophisticated dynamic data structures which we will need if,as discussed in the previous chapter,we are to take our software systems to their full modeling power
§9.1 WHAT HAPPENS TO OBJECTS 281 The second scheme of object allocation is the stack-based mode. Here an entity may at run time become attached to several objects in succession, and the run-time mechanisms allocate and deallocate these objects in last-in, first-out order. When an object is deallocated, the corresponding entity becomes attached again to the object to which it was previously attached, if any. Stack-based object management was made popular by Algol 60 and is supported (often in conjunction with one or both of the other two modes) in most posterior programming languages. Stack-based allocation supports recursion and, if the language permits it, arrays whose bounds only become known at run time. In Pascal and C, however, the mechanism only applies to variables of basic types and record types — not to arrays as it did in Algol. In practice the data structures that developers would most often want to allocate in this fashion are precisely arrays. Even when it applies to arrays, stackbased allocation still does not support complex data structures in their full generality. To obtain such general data structures, we need the third and last scheme: the free mode, also called heap-based because of the way it is implemented. This is the fully dynamic mode in which objects are created dynamically through explicit requests. An entity may become successively attached to any number of objects; the pattern of object creations is usually not predictable at compile time. Objects may, furthermore, contain references to other objects. The free mode allows us to create the sophisticated dynamic data structures which we will need if, as discussed in the previous chapter, we are to take our software systems to their full modeling power. The stackbased mode Objects of block i Memory allocated on entry to block i Memory allocated on entry to block i+1 Objects of block i+1 Order of allocation (on block entry) Order of (on block exit) THE STACK deallocation Dynamic arrays can be created in C through the malloc function, a mechanism of the “free” kind, the mode studied next; some Pascal extensions support dynamic arrays. The free (heapbased) mode THE HEAP
282 MEMORY MANAGEMENT $9.1 Using the free mode The free mode is clearly the most general,and is required for object-oriented computation. Many non-O-O languages use it too.In particular: Pascal uses the static mode for arrays,the stack-based mode for variables of type other than array or pointer,and the free mode for pointer variables.In the last case object creation is achieved by a call to a special creation procedure,new. C is similar to Pascal but in addition offers static non-array variables and free arrays. Dynamic allocation of pointer variables and arrays relies on a library function,malloc. PL/I supports all modes. Lisp systems have traditionally been highly dynamic,relying for the most part on the free mode.One of the most important Lisp operations,used repeatedly to construct lists,is CONS,which creates a two-field cell,ready to serve as a list element with the element's value in the first field and a pointer to the next element in the second field. Here CONS,rather than explicit creation instructions,will be the principal source of new objects Space reclamation in the three modes The ability to create objects dynamically,as in the stack-based and free modes,raises the question of what to do when an object becomes unused:is it possible to reclaim its memory space,so as to use it again for one or more new objects in later creation instructions? In the static mode,the problem does not exist:for every object,there is exactly one attached entity;execution needs to retain the object's space as long as the entity is active. So there is no possibility for reclamation in the proper sense.A related technique is, however,sometimes used.If you are convinced that the objects attached to two entities will never be needed at the same time,if these entities need not retain their values between successive uses,and if space efficiency is a critical problem,you can assign the same memory location to two or more entities-if you are really sure of what you are doing. This technique,known as overlay is still,appallingly enough,practiced manually. If used at all,overlay should clearly be handled by automatic software tools,as the potential for errors is too high when programmers control the process themselves.Once again a major problem is change:a decision to overlay two variables may be correct at a certain stage of the program's evolution,but an unexpected change may suddenly make it invalid.We will encounter similar problems below,in a more modern context,with garbage collection. With the stack-based mode,the objects attached to an entity may be allocated on a stack.Block-structured language make things particularly simple:object allocation occurs at the same time for all entities declared in a given block,allowing the use ofa single stack for a whole program.The scheme is elegant indeed,as it just involves two sets of concomitant events:
282 MEMORY MANAGEMENT §9.1 Using the free mode The free mode is clearly the most general, and is required for object-oriented computation. Many non-O-O languages use it too. In particular: • Pascal uses the static mode for arrays, the stack-based mode for variables of type other than array or pointer, and the free mode for pointer variables. In the last case object creation is achieved by a call to a special creation procedure, new. • C is similar to Pascal but in addition offers static non-array variables and free arrays. Dynamic allocation of pointer variables and arrays relies on a library function, malloc. • PL/I supports all modes. • Lisp systems have traditionally been highly dynamic, relying for the most part on the free mode. One of the most important Lisp operations, used repeatedly to construct lists, is CONS, which creates a two-field cell, ready to serve as a list element with the element’s value in the first field and a pointer to the next element in the second field. Here CONS, rather than explicit creation instructions, will be the principal source of new objects Space reclamation in the three modes The ability to create objects dynamically, as in the stack-based and free modes, raises the question of what to do when an object becomes unused: is it possible to reclaim its memory space, so as to use it again for one or more new objects in later creation instructions? In the static mode, the problem does not exist: for every object, there is exactly one attached entity; execution needs to retain the object’s space as long as the entity is active. So there is no possibility for reclamation in the proper sense. A related technique is, however, sometimes used. If you are convinced that the objects attached to two entities will never be needed at the same time, if these entities need not retain their values between successive uses, and if space efficiency is a critical problem, you can assign the same memory location to two or more entities — if you are really sure of what you are doing. This technique, known as overlay is still, appallingly enough, practiced manually. If used at all, overlay should clearly be handled by automatic software tools, as the potential for errors is too high when programmers control the process themselves. Once again a major problem is change: a decision to overlay two variables may be correct at a certain stage of the program’s evolution, but an unexpected change may suddenly make it invalid. We will encounter similar problems below, in a more modern context, with garbage collection. With the stack-based mode, the objects attached to an entity may be allocated on a stack. Block-structured language make things particularly simple: object allocation occurs at the same time for all entities declared in a given block, allowing the use of a single stack for a whole program. The scheme is elegant indeed, as it just involves two sets of concomitant events:
$9.1 WHAT HAPPENS TO OBJECTS 283 Allocation and Dynamic Property Static Property Implementation deallocation in (event at execution (location in the Technique a block- time) software text) structured Object allocation Block entry. Push objects (one for language each of the entities local to the block)onto stack. Object deallocation Block exit. Pop stack. The simplicity and efficiency of this implementation technique are part of the reason why block-structured languages have been so successful. With the free mode,things cease to be so simple.The problem comes from the very power of the mechanism:since the pattern ofobject creation is unknown at compile time, it is not possible to predict when a given object may become useless. Detachment Objects may indeed,in the free mode,become useless to the software at unpredictable times during execution,so that some mechanism(to be determined later in this discussion) may reclaim the memory they occupy. The reason is the presence in our execution mode ofoperations performing what may be called detachment-the reverse ofattachment.The previous chapter studied at length how entities can become attached to objects,but did not examine in any detail the consequences of detachments.Now is the time to correct this. Detachment only affects entities x of reference types.Ifx is of expanded type,the value ofx is an object O,and there is no way to detach x from O.Note,however,that ifx is an expanded attribute of some class,O represents a subobject of some bigger object BO; then BO,and with it O,may become unreachable for any of the reasons studied below. So for the rest of this chapter we may confine our attention to entities of reference types. Detachment 03 Attachments: Before After The principal causes of detachment are the following,assuming x and y,entities of reference type,were initially attached to objects Ol and O2.The figure illustrates cases DI and D2. DI.An assignment of the form x:=loid,orx:=v where y is void,detachesx from O1
§9.1 WHAT HAPPENS TO OBJECTS 283 The simplicity and efficiency of this implementation technique are part of the reason why block-structured languages have been so successful. With the free mode, things cease to be so simple. The problem comes from the very power of the mechanism: since the pattern of object creation is unknown at compile time, it is not possible to predict when a given object may become useless. Detachment Objects may indeed, in the free mode, become useless to the software at unpredictable times during execution, so that some mechanism (to be determined later in this discussion) may reclaim the memory they occupy. The reason is the presence in our execution mode of operations performing what may be called detachment — the reverse of attachment. The previous chapter studied at length how entities can become attached to objects, but did not examine in any detail the consequences of detachments. Now is the time to correct this. Detachment only affects entities x of reference types. If x is of expanded type, the value of x is an object O, and there is no way to detach x from O. Note, however, that if x is an expanded attribute of some class, O represents a subobject of some bigger object BO; then BO, and with it O, may become unreachable for any of the reasons studied below. So for the rest of this chapter we may confine our attention to entities of reference types. The principal causes of detachment are the following, assuming x and y, entities of reference type, were initially attached to objects O1 and O2. The figure illustrates cases D1 and D2. D1 • An assignment of the form x := Void, or x := v where v is void, detaches x from O1. Dynamic Property (event at execution time) Static Property (location in the software text) Implementation Technique Object allocation Block entry. Push objects (one for each of the entities local to the block) onto stack. Object deallocation Block exit. Pop stack. Allocation and deallocation in a blockstructured language Detachment O1 O2 x y z O3 Attachments: Before ✄ ✄ After
284 MEMORY MANAGEMENT $9.1 D2.An assignment of the formy:==,where=is attached to an object other than O2, detaches y from 02. D3.Termination of a routine detaches formal arguments from any attached objects. D4.A creation instruction !!x,attaches x to a newly created object,and hence detaches x if it was previously attached to an object O1. Case D3 corresponds to the rule given earlier that the semantics of an assignment a=b is exactly the same as that of initializing a formal argument a of a routine r at the time of a call t.(...,b....),where the position of b in the call corresponds to that of a in the declaration ofr. Unreachable objects Does detachment mean that the detached object-Ol or 02 on the preceding figure- becomes useless and hence that the runtime mechanisms can reclaim the memory space it occupies,then recycle it for other objects?That would be too easy!The entity for which an object was initially created may have lost all interest in it,but because of dynamic aliasing other references may still be attached to it.For example the last figure may have shown only a partial view of attachments;looking at a broader context might reveal that Ol and O2 are still reachable from other objects: Detachment is not always death 02 But this is still not the entire object structure.By getting even more context,we might now discover that O4 and O5 are themselves useless,so that in the absence of other references O1 and O2 are not needed after all. So the answer to the question"what objects can we reclaim?"must follow from a global analysis of the entire set of objects created so far.We can identify three kinds of object: C1.Objects directly attached to entities of the software text,known(from the language rules)to be needed
284 MEMORY MANAGEMENT §9.1 D2 • An assignment of the form y := z, where z is attached to an object other than O2, detaches y from O2. D3 • Termination of a routine detaches formal arguments from any attached objects. D4 • A creation instruction !! x, attaches x to a newly created object, and hence detaches x if it was previously attached to an object O1. Case D3 corresponds to the rule given earlier that the semantics of an assignment a := b is exactly the same as that of initializing a formal argument a of a routine r at the time of a call t ● r (…, b, …), where the position of b in the call corresponds to that of a in the declaration of r. Unreachable objects Does detachment mean that the detached object — O1 or O2 on the preceding figure — becomes useless and hence that the runtime mechanisms can reclaim the memory space it occupies, then recycle it for other objects? That would be too easy! The entity for which an object was initially created may have lost all interest in it, but because of dynamic aliasing other references may still be attached to it. For example the last figure may have shown only a partial view of attachments; looking at a broader context might reveal that O1 and O2 are still reachable from other objects: But this is still not the entire object structure. By getting even more context, we might now discover that O4 and O5 are themselves useless, so that in the absence of other references O1 and O2 are not needed after all. So the answer to the question “what objects can we reclaim?” must follow from a global analysis of the entire set of objects created so far. We can identify three kinds of object: C1 • Objects directly attached to entities of the software text, known (from the language rules) to be needed. Detachment is not always death O1 O2 x y z O3 ✄ ✄ O4 O5
$9.1 WHAT HAPPENS TO OBJECTS 285 C2.Dependents of objects of category C1.(Recall that the direct dependents of an object are those to which it has references;here we are considering both direct and indirect dependents.) C3.Objects which are in neither of the preceding two categories. The objects of category CI may be called the origins.Together with those of category C2,the origins make up the set of reachable objects.Those of category C3 are unreachable.They correspond to what was informally called "useless objects"above.A more lively if somewhat macabre terminology uses the term"dead objects"for C3,the origins and their dependents being then called "live objects".(Computing scientists, however,have not quite managed to reconcile their various metaphors,as the process of reclaiming dead objects,studied below,is called "garbage collection".) The term“root”is also used for“orig in'”.But here the latter is preferable because an O-O system also has a "root object"and a root class.The resulting ambiguity would not be too damaging since the root object,as seen below,is indeed one of the origins. The first step towards addressing the problem of memory management under the free mode is to separate the reachable objects from the unreachable ones.To identify reachable objects,we must start from the origins and repeatedly follow all references.So the first question is to identify the origins;the answer depends on the run-time structure defined by the underlying language. Reachable objects in classical approaches Because the unreachability problem is already present in the run-time structure of such classical approaches as Pascal,C and Ada,it is interesting to start with this case.(More accurately,this is interesting for the reader who is familiar with one of these approaches. If you are not in this category,you may prefer to skip this section and go directly to the next one,which moves right on to the run-time structure of O-O software.) The approaches quoted combine the stack-based and free modes of allocation.C and Ada also support the static mode,but to keep things simple we may ignore static allocation by viewing it as a special case of stack-based allocation:we treat static objects as if they were allocated once and for all,when execution starts,at the bottom of the stack.(This is indeed the way Pascal developers emulate static entities:they declare them in the outermost block.) Another common property of these approaches is that entities may denote pointers. To provide a better preparation for the object-oriented approach of this book,where instead of pointers we use references (a more abstract notion,as discussed in the previous chapter),let us pretend that the pointers in question are actually references.This means in particular that we disregard the weakly typed nature of pointers in C. With these assumptions and simplifications the origins,shown with thick borders on the following figure,are all the objects which are either allocated on the stack or attached to references allocated on the stack.The reachable objects (including the origins)appear in color,the unreachable objects in black
§9.1 WHAT HAPPENS TO OBJECTS 285 C2 • Dependents of objects of category C1. (Recall that the direct dependents of an object are those to which it has references; here we are considering both direct and indirect dependents.) C3 • Objects which are in neither of the preceding two categories. The objects of category C1 may be called the origins. Together with those of category C2, the origins make up the set of reachable objects. Those of category C3 are unreachable. They correspond to what was informally called “useless objects” above. A more lively if somewhat macabre terminology uses the term “dead objects” for C3, the origins and their dependents being then called “live objects”. (Computing scientists, however, have not quite managed to reconcile their various metaphors, as the process of reclaiming dead objects, studied below, is called “garbage collection”.) The term “root” is also used for “origin”. But here the latter is preferable because an O-O system also has a “root object” and a root class. The resulting ambiguity would not be too damaging since the root object, as seen below, is indeed one of the origins. The first step towards addressing the problem of memory management under the free mode is to separate the reachable objects from the unreachable ones. To identify reachable objects, we must start from the origins and repeatedly follow all references. So the first question is to identify the origins; the answer depends on the run-time structure defined by the underlying language. Reachable objects in classical approaches Because the unreachability problem is already present in the run-time structure of such classical approaches as Pascal, C and Ada, it is interesting to start with this case. (More accurately, this is interesting for the reader who is familiar with one of these approaches. If you are not in this category, you may prefer to skip this section and go directly to the next one, which moves right on to the run-time structure of O-O software.) The approaches quoted combine the stack-based and free modes of allocation. C and Ada also support the static mode, but to keep things simple we may ignore static allocation by viewing it as a special case of stack-based allocation: we treat static objects as if they were allocated once and for all, when execution starts, at the bottom of the stack. (This is indeed the way Pascal developers emulate static entities: they declare them in the outermost block.) Another common property of these approaches is that entities may denote pointers. To provide a better preparation for the object-oriented approach of this book, where instead of pointers we use references (a more abstract notion, as discussed in the previous chapter), let us pretend that the pointers in question are actually references. This means in particular that we disregard the weakly typed nature of pointers in C. With these assumptions and simplifications the origins, shown with thick borders on the following figure, are all the objects which are either allocated on the stack or attached to references allocated on the stack. The reachable objects (including the origins) appear in color, the unreachable objects in black
286 MEMORY MANAGEMENT $9.1 Live objects (in color)and deadobjects (in black)in a combined THE STACK stack-based Stack top and free model Origin Reference origin Because the unreachability problem only arises for objects allocated under the free mode,and such objects are always attached to entities of reference types,it is convenient to ignore the reclamation problem for objects allocated on the stack(which can be handled simply by popping the stack at the time of block exit)and to start from the references coming from the stack.We may call these references reference origins.They are shown with thick arrows in the figure.A reference origin is either. O1.The value of a local entity or routine argument of reference type (as with the top two reference origins in the figure). O2.A field of reference type,in an object allocated on the stack(as with the lowest reference origin in the figure). As an example,consider the following type and procedure declarations,written in a syntax half-way between Pascal and the notation of the rest of this book(an entity of type reference G is a reference that may become attached to objects of type G): type COMPOSITE= record m:INTEGER r:reference COMPOSITE end
286 MEMORY MANAGEMENT §9.1 Because the unreachability problem only arises for objects allocated under the free mode, and such objects are always attached to entities of reference types, it is convenient to ignore the reclamation problem for objects allocated on the stack (which can be handled simply by popping the stack at the time of block exit) and to start from the references coming from the stack. We may call these references reference origins. They are shown with thick arrows in the figure. A reference origin is either: O1 • The value of a local entity or routine argument of reference type (as with the top two reference origins in the figure). O2 • A field of reference type, in an object allocated on the stack (as with the lowest reference origin in the figure). As an example, consider the following type and procedure declarations, written in a syntax half-way between Pascal and the notation of the rest of this book (an entity of type reference G is a reference that may become attached to objects of type G): type COMPOSITE = record m: INTEGER r: reference COMPOSITE end … THE STACK Stack top Reference origin Origin Live objects (in color) and dead objects (in black) in a combined stack-based and free model
$9.1 WHAT HAPPENS TO OBJECTS 287 procedure p is local n:INTEGER c:COMPOSITE s:reference COMPOSITE do end Every execution ofp allocates three values on the stack: Entity THE STACK allocation for a procedure New stack top (COMPOSITE) Previous stack top The three new values are an integer n,which does not affect the problem of object management(since it will disappear when the procedure terminates,and does not refer to any other object);a reference s,which is an example of category O1;and an object c of type COMPOSITE.This object is itself stack-based and its allocated memory may be reclaimed on procedure termination;but it contains a reference field for r,which is an example of category O2. In summary,to determine the reachable objects in a classical approach combining the stack-based and free modes,you can start from the references on the stack (variables of reference types,and reference fields of composite objects),and repeatedly follow all reference fields of the attached objects if any
§9.1 WHAT HAPPENS TO OBJECTS 287 procedure p is local n: INTEGER c: COMPOSITE s: reference COMPOSITE do … end Every execution of p allocates three values on the stack: The three new values are an integer n, which does not affect the problem of object management (since it will disappear when the procedure terminates, and does not refer to any other object); a reference s, which is an example of category O1; and an object c of type COMPOSITE. This object is itself stack-based and its allocated memory may be reclaimed on procedure termination; but it contains a reference field for r, which is an example of category O2. In summary, to determine the reachable objects in a classical approach combining the stack-based and free modes, you can start from the references on the stack (variables of reference types, and reference fields of composite objects), and repeatedly follow all reference fields of the attached objects if any. Entity allocation for a procedure THE STACK New stack top Previous stack top m r (COMPOSITE) c n s
288 MEMORY MANAGEMENT $9.1 Reachable objects in the object-oriented model The object-oriented run-time structure presented in the preceding chapter has a few differences from the one just discussed. Reachability in the object- THE ROOT oriented model THE STACK Stack top The execution of any system starts with the creation of one object,called the root object of the system,or just its root (when there is no confusion with the root class,a static notion).Clearly,the root is one of the origins in this case. Another set of origins arises because of the possible presence of local entities in a routine.Assume a routine of the form some routine is local rbl.rb2:BOOK3 eb:expanded BOOK3 do !rbl ..Operations possibly involving rbl,rb2 and eb... end Whenever a call to some routine is executed,and for the duration ofthat execution, the instructions in the routine's body may refer to rb/,rb2 and eb,and hence to the attached objects if any.(For eb there is always an attached object,but at various points rb/ and rb2 may be void.)This means that such objects must be part of the reachable set,even though they are not necessarily dependents of the root. Local entities of reference types,such as rb/and rb2,are similar to the local routine variables which,in the previous model,were allocated on the stack.Local entities of expanded types,such as eb,are similar to the stack-based objects
288 MEMORY MANAGEMENT §9.1 Reachable objects in the object-oriented model The object-oriented run-time structure presented in the preceding chapter has a few differences from the one just discussed. The execution of any system starts with the creation of one object, called the root object of the system, or just its root (when there is no confusion with the root class, a static notion). Clearly, the root is one of the origins in this case. Another set of origins arises because of the possible presence of local entities in a routine. Assume a routine of the form some_routine is local rb1, rb2: BOOK3 eb: expanded BOOK3 do … !! rb1 … Operations possibly involving rb1, rb2 and eb … end Whenever a call to some_routine is executed, and for the duration of that execution, the instructions in the routine’s body may refer to rb1, rb2 and eb, and hence to the attached objects if any. (For eb there is always an attached object, but at various points rb1 and rb2 may be void.) This means that such objects must be part of the reachable set, even though they are not necessarily dependents of the root. Local entities of reference types, such as rb1 and rb2, are similar to the local routine variables which, in the previous model, were allocated on the stack. Local entities of expanded types, such as eb, are similar to the stack-based objects. Reachability in the objectoriented model THE STACK Stack top THE ROOT
