#1Automatic Memory ManagementAutomatic Memory Management#2One-Slide Summary• An automatic memory management system deallocates objects when they are no longer used and reclaims their storage space. • We must be conservative and only free objects that will not be used later. • Garbage collection scans the heap from a set of roots to find reachable objects. Mark and Sweep and Stop and Copy are two GC algorithms. • Reference Counting stores the number of pointers to an object with that object and frees it when that count reaches zero.#3Lecture Outine• Why Automatic Memory Management?• Garbage Collection• Three Techniques– Mark and Sweep– Stop and Copy– Reference Counting#4Why Automatic Memory Mgmt?• Storage management is still a hard problem in modern programming•C and C++ programs have many storage bugs– forgetting to free unused memory– dereferencing a dangling pointer– overwriting parts of a data structure by accident– and so on... (can be big security problems)• Storage bugs are hard to find– a bug can lead to a visible effect far away in time and program text from the source#5Type Safety and Memory Management• Some storage bugs can be prevented in a strongly typed language– e.g., you cannot overrun the array limits• Can types prevent errors in programs with manual allocation and deallocation of memory?– Some fancy type systems (linear types) were designed for this purpose but they complicate programming significantly•If you want type safety then you must use automatic memory management#6Automatic Memory Management• This is an old problem: – Studied since the 1950s for Lisp• There are several well-known techniques for performing completely automatic memory management•Until recently they were unpopular outside the Lisp family of languages– just like type safety used to be unpopular#7The Basic Idea• When an object that takes memory space is created, unused space is automatically allocated– In Cool, new objects are created by new X•After a while there is no more unused space•Some space is occupied by objects that will never be used again (= dead objects?)• This space can be freed to be reused later#8Dead Again?• How can we tell whether an object will “never be used again”?– In general it is impossible (undecideable) to tell– We will have to use a heuristic to find many (not all) objects that will never be used again•Observation: a program can use only the objects that it can find:let x : A à new A in { x à y; ... }–After x à y there is no way to access the newly allocated object#9Garbage• An object x is reachable if and only if:– A local variable (or register) contains a pointer to x, or– Another reachable object y contains a pointer to x• You can find all reachable objects by starting from local variables and following all the pointers (“transitive”)• An unreachable object can never by referred to by the program– These objects are called garbage#10Reachability is an Approximation• Consider the program:x à new Ant;y à new Bat;x à y;if alwaysTrue() then x à new Cow else x.eat() fi•After x à y (assuming y becomes dead there)–The object Ant is not reachable anymore–The object Bat is reachable (through x)–Thus Bat is not garbage and is not collected–But object Bat is never going to be used#11Cool Garbage• At run-time we have two mappings:– Environment E maps variable identifiers to locations– Store S maps locations to values• Proposed Cool Garbage Collector–for each location l 2 domain(S)– let can_reach = false– for each (v,l2) 2 E– if l = l2 then can_reach = true– if not can_reach then reclaim_location(l)Does this work?#12Does That Work?#13Cooler Garbage–Environment E maps variable identifiers to locations–Store S maps locations to values• Proposed Cool Garbage Collector–for each location l 2 domain(S)– let can_reach = false– for each (v,l2) 2 E– if l = l2 then can_reach = true– for each l3 2 v // v is X(…, ai = li, …) – if l = l3 then can_reach = true– if not can_reach then reclaim_location(l)#14Garbage Analysis• Could we use the proposed Cool Garbage Collector in real life? •How long would it take? •How much space would it take? • Are we forgetting anything?#15Tracing Reachable Values• In Cool, local variables are easy to find– Use the environment mapping E– and one object may point to other objects, etc.• The stack is more complex– each stack frame (activation record) contains:• method parameters (other objects)•If we know the layout of a stack frame we can find the pointers (objects) in it#16Reachability Can Be Tricky• Many things may look legitimate and reachable but will turn out not to be.• How can we figure this out systematically?#17A Simple Example• Start tracing from local vars and the stack– they are called the roots• Note that B and D are not reachable from local vars or the stack•Thus we can reuse their storageAB CFrame 1Frame 2D Elocal varstack#18Elements of Garbage Collection• Every garbage collection scheme has the following steps– Allocate space as needed for new objects– When space runs out:– Compute what objects might be used again (generally by tracing objects reachable from a set of roots)– Free space used by objects not found in (a)•Some strategies perform garbage collection before the space actually runs outQ: Games (545 / 842) •This 1993 id Software game was the first truly popular first-person shooter (15 million estimated players). You play the role of a space marine and fight demons and zombies with shotguns, chainsaws and the BFG9000. It was controversial for diabolic overtones and has been dubbed a "mass murder simulator." CMU and Intel, among others, formed special policies to prevent people from playing it during working hours.Q: Books (726 / 842) •Paraphrase any one of Isaac Asimov's 1942 Three Laws of Robotics.Q: Movie Music (428 / 842) •What's "the biggest word" Dick Van Dyke had "ever heard" in the 1964 film "Mary Poppins"?#22Mark And Sweep• Our first GC algorithm• Two phases:– Mark– Sweep#23Mark and Sweep• When memory runs out, GC executes two phases– the mark phase: traces reachable objects– the sweep phase: collects garbage objects•Every object has an extra bit: the mark bit– reserved for memory management– initially the mark bit is 0– set to 1 for the reachable objects in the mark phase#24Mark and