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