$9.1 WHAT HAPPENS TO OBJECTS 289 When a call to some routine terminates,the current incarnations of entities rbl,rb2 and eb disappear.As a result,any attached objects cease to be part of the origin set.This does not necessarily mean that they become unreachable,as they may in the meantime have become dependents of the root object or other origins. Assume for example that a is an attribute of the enclosing class and that the whole text of the routine is: some routine is local rbl,rb2:BOOK3 eb:expanded BOOK3 do ！rb1:IIrb2 a:=rbl end The following figure shows in color the objects that a call to some routine will create and the references that it will reattach. Objects attached to local entities THE ROOT EB Stack top during B2 execution of some_routine (BOOK3) BOOK3 rb2 (BOOK3) rbl Stack top before Objects and references in black and after call exist before the call,those in color are created by the call. Objects with thick borders THE STACK are reachable after the call. When a call to some routine terminates,the object O that served as target of the call is still reachable (otherwise there would have been no call!).The a field of O is now attached to the BOOK3 object BI created by the first creation instruction (the one of target rb/),which,then,remains reachable.In contrast,the objects B2 and EB that were attached to rb2 and eb during the call now become unreachable:with the routine text as given there is no possibility that any of the other objects of the system,reachable or not,could remember”B2orEB
§9.1 WHAT HAPPENS TO OBJECTS 289 When a call to some_routine terminates, the current incarnations of entities rb1, rb2 and eb disappear. As a result, any attached objects cease to be part of the origin set. This does not necessarily mean that they become unreachable, as they may in the meantime have become dependents of the root object or other origins. Assume for example that a is an attribute of the enclosing class and that the whole text of the routine is: some_routine is local rb1, rb2: BOOK3 eb: expanded BOOK3 do !! rb1; !! rb2 a := rb1 end The following figure shows in color the objects that a call to some_routine will create and the references that it will reattach. When a call to some_routine terminates, the object O that served as target of the call is still reachable (otherwise there would have been no call!). The a field of O is now attached to the BOOK3 object B1 created by the first creation instruction (the one of target rb1), which, then, remains reachable. In contrast, the objects B2 and EB that were attached to rb2 and eb during the call now become unreachable: with the routine text as given there is no possibility that any of the other objects of the system, reachable or not, could “remember” B2 or EB. Objects attached to local entities THE STACK THE ROOT (BOOK3) Stack top before and after call Stack top during execution of some_routine rb2 rb1 (BOOK3) (BOOK3) a Objects and references in black exist before the call; those in color are created by the call. Objects with thick borders are reachable after the call. O B1 B2 EB
290 MEMORY MANAGEMENT $9.1 The memory management problem in the object-oriented model We may summarize the preceding analysis by defining the origins,and hence of the reachable objects,in the object-oriented framework: Definition:origins,reachable and unreachable objects At any point during the execution of a system,the set of origins is made of the following objects: The system's root object. Any object attached to a local entity or formal argument of a routine currently being executed (including the local entity Resulr for a function). Any dependent,direct or indirect,of these origins is reachable.Any other object is unreachable;it is possible to reclaim the memory it occupies(for example to recycle it for other objects)without affecting the correct semantics of the system's execution. The problem of memory management arises from the unpredictability of the operations which affect the set of reachable objects:creation and detachment.Because these operations are instructions,appearing as part of a system's control structures,there is usually no way to determine with certainty,from a mere examination of the software text,the pattern of object creation and detachment at run time. More precisely,such a prediction is possible in some cases,for data structures About linked lists managed in a strictly controlled way.An example is the LINKED LIST library class see "Linked list rep- studied in a later chapter,with the associated class LINKABLE which describes linked list resentation",page 774,and subsequent elements.Instances of LINKABLE are only created through specific procedures of sections. LINKED LIST,and can only become unreachable as a result of executing the remove procedure of that class.For such classes one might envision specific reclamation procedures.(This approach will be explored later in this chapter.) But such examples,although important,are only special cases.In the most general case we must face a difficult question:what do we do about unreachable objects? The three answers Three general attitudes are possible as to objects that become unreachable: Ignore the problem and hope that there will be enough memory to accommodate all objects,reachable or not.This may be called the casual approach Ask developers to include in every application an algorithm that looks for unreachable objects,and give them mechanisms to free the corresponding memory. This approach is called manual reclamation
290 MEMORY MANAGEMENT §9.1 The memory management problem in the object-oriented model We may summarize the preceding analysis by defining the origins, and hence of the reachable objects, in the object-oriented framework: The problem of memory management arises from the unpredictability of the operations which affect the set of reachable objects: creation and detachment. Because these operations are instructions, appearing as part of a system’s control structures, there is usually no way to determine with certainty, from a mere examination of the software text, the pattern of object creation and detachment at run time. More precisely, such a prediction is possible in some cases, for data structures managed in a strictly controlled way. An example is the LINKED_LIST library class studied in a later chapter, with the associated class LINKABLE which describes linked list elements. Instances of LINKABLE are only created through specific procedures of LINKED_LIST, and can only become unreachable as a result of executing the remove procedure of that class. For such classes one might envision specific reclamation procedures. (This approach will be explored later in this chapter.) But such examples, although important, are only special cases. In the most general case we must face a difficult question: what do we do about unreachable objects? The three answers Three general attitudes are possible as to objects that become unreachable: • Ignore the problem and hope that there will be enough memory to accommodate all objects, reachable or not. This may be called the casual approach. • Ask developers to include in every application an algorithm that looks for unreachable objects, and give them mechanisms to free the corresponding memory. This approach is called manual reclamation. Definition: origins, reachable and unreachable objects At any point during the execution of a system, the set of origins is made of the following objects: • The system’s root object. • Any object attached to a local entity or formal argument of a routine currently being executed (including the local entity Result for a function). Any dependent, direct or indirect, of these origins is reachable. Any other object is unreachable; it is possible to reclaim the memory it occupies (for example to recycle it for other objects) without affecting the correct semantics of the system’s execution. About linked lists see “Linked list representation”, page 774, and subsequent sections
$9.2 THE CASUAL APPROACH 291 Include in the development environment (as part of the so-called runtime system) automatic mechanisms that will detect and reclaim unreachable objects.This is called automatic garbage collection. The rest of this chapter discusses these approaches. 9.2 THE CASUAL APPROACH The first approach consists in forgetting about the problem:abandon dead objects to their fate.Execute creation instructions as needed,and do not worry about what may later happen to those objects that have thus been allocated. Can the casual approach be justified? One case in which the casual approach presents no particular problem is that of systems that do not create many objects,such as small-scale tests or experiments. More interesting is the case of systems that may in fact create many objects,but in such a way that it is possible to guarantee that none or very few of them become unreachable.As with the static allocation scheme,no objects are ever retired;the difference is that creation occurs at execution time. This case provides a good justification for the casual approach,as there is no need for reclamation.The number of objects created may still be too big for the available memory, but no reclamation policy would alleviate the problem if there is nothing to reclaim Some real-time programs follow this scheme:for efficiency reasons,they create all needed objects statically or at initialization time,avoiding any non-predictable patterns of dynamic object creation. This method has its advocates,who usually are involved in the construction of"hard- real-time"systems demanding guaranteed sub-millisecond response times to external events (such as a missile detection),and who as a consequence insist that the time to execute every operation must be fully predictable.But then memory management is only a small part of what we must give up:predictability requires the absence of any kind of object allocation(creation instruction,malloc,recursion,possibly any call of a routine with local entities)after initialization;and it assumes a dedicated,single-user,single- processing machine,with no preemptive operating system call and in fact no operating system in the usual sense of the term.In such environments people sometimes choose to program in assembly language,as they fear the additional unpredictability of compiler- generated code.All this,of course,restricts the discussion to a tiny (although strategic) part of the software development world. Do we care about memory any more? Another argument sometimes heard to justify the casual approach is the increasing availability of large memory spaces,and the decreasing cost of memory
§9.2 THE CASUAL APPROACH 291 • Include in the development environment (as part of the so-called runtime system) automatic mechanisms that will detect and reclaim unreachable objects. This is called automatic garbage collection. The rest of this chapter discusses these approaches. 9.2 THE CASUAL APPROACH The first approach consists in forgetting about the problem: abandon dead objects to their fate. Execute creation instructions as needed, and do not worry about what may later happen to those objects that have thus been allocated. Can the casual approach be justified? One case in which the casual approach presents no particular problem is that of systems that do not create many objects, such as small-scale tests or experiments. More interesting is the case of systems that may in fact create many objects, but in such a way that it is possible to guarantee that none or very few of them become unreachable. As with the static allocation scheme, no objects are ever retired; the difference is that creation occurs at execution time. This case provides a good justification for the casual approach, as there is no need for reclamation. The number of objects created may still be too big for the available memory, but no reclamation policy would alleviate the problem if there is nothing to reclaim. Some real-time programs follow this scheme: for efficiency reasons, they create all needed objects statically or at initialization time, avoiding any non-predictable patterns of dynamic object creation. This method has its advocates, who usually are involved in the construction of “hardreal-time” systems demanding guaranteed sub-millisecond response times to external events (such as a missile detection), and who as a consequence insist that the time to execute every operation must be fully predictable. But then memory management is only a small part of what we must give up: predictability requires the absence of any kind of object allocation (creation instruction, malloc, recursion, possibly any call of a routine with local entities) after initialization; and it assumes a dedicated, single-user, singleprocessing machine, with no preemptive operating system call and in fact no operating system in the usual sense of the term. In such environments people sometimes choose to program in assembly language, as they fear the additional unpredictability of compilergenerated code. All this, of course, restricts the discussion to a tiny (although strategic) part of the software development world. Do we care about memory any more? Another argument sometimes heard to justify the casual approach is the increasing availability of large memory spaces, and the decreasing cost of memory