Memory allocation, garbage collection Types of memory managementWhy Dynamic?Why Implicit Heap Management?Another solution to Heap Management?In Lisp, is all data in the heap? Often notReference Counts: an easy methodWhy use Reference CountsWhy not use Reference CountsWho uses Reference CountsWhy Garbage Collection (GC)?Why not GC?Kinds of GCMark-and-Sweep. The simplest.Cost of Mark-and-SweepOther considerations for Mark/Sweep: stack spaceImproved SweepingCopying GCPro: Copying GCCon: Copying GCGenerational GCPro: Generational GCCon: Generational GCConservative GCPro: Conservative GCCon: Conservative GCCurrent technologyProf. Fateman CS 164 Lecture 17 1Memory allocation, garbage collectionLecture 17Prof. Fateman CS 164 Lecture 17 2Types of memory managementStatic: fixed when a program is loadedDynamicStack (sometimes more than one)HeapExplicitly managed : must call freemalloc / free--many variationsImplicitly managed: done behind the scenesReference CountingGarbage Collection (GC)--Mark&Sweep, Copying, Conservative..Prof. Fateman CS 164 Lecture 17 3Why Dynamic?Static means you have to know at compile time how big your program’s data can be. FORTRAN (pre 1990) did this. You allocate the largest array you think you will need and hope for the best. Advantage: You will never be tossed out by OS for using too much memory in the middle of computing.Stack allocation means you can grow, but only last in, first out. You must return storage in the reverse order of its allocation. Sometimes works just fine for a language design with nested scope. Sometimes you run out of stack space. This could never happen in fortran 66☺Prof. Fateman CS 164 Lecture 17 4Why Implicit Heap Management?Explicit management is extremely error prone. (malloc, free) It is a source of subtle bugs in every system that uses it (including almost any large system written in C!)Lisp/Java argument: don’t even ask the programmer to manage memory.Heap allocation solve lots of technical problems: in a programming language (Java), having EVERYTHING be in the heap and allvalues pointers to objects in the heap makes semantics neater.Prof. Fateman CS 164 Lecture 17 5Another solution to Heap Management?.Some systems solve the problem by never deallocatingmemory, assuming that you will eventually kill the whole process.How long does your browser stay up?Sometimes you have to reboot the whole operating system.Prof. Fateman CS 164 Lecture 17 6In Lisp, is all data in the heap? Often notConses (i.e. lists, dotted pairs), yesArrays, yes usuallyArbitrary precision integers, yesNumbers: maybe. --Here’s a trick. If a pointer is a negative number (leftmost bit is 1) maybe it can’t really be a pointer at all. So make it an “immediate” number. You can do arithmetic etc. with this “FIXNUM”. Instead of “following a pointer” to a number, you fake it.(Lisp also uses a stack for binding values and most implementations use static space for binary programs e.g. loaded from fasl files or written in asm, C,…Prof. Fateman CS 164 Lecture 17 7Reference Counts: an easy methodEvery Heap cell has a count field , full-address size.B= new cell init. to “hi” take cell from freelistA:=B incrementA:=“bye” decrease hi’s count, increase bye’s count.When count decrements to 0, there are no users of that cell: put it on list of free storage.hi 1hi 1hi 2bye 1Prof. Fateman CS 164 Lecture 17 8Why use Reference CountsIf the cost of maintaining counts is small compared to the other operations.If it is important that the cost is assessed immediately and is predictable (no clumpiness like GC). (though this has mostly gone away with fast memory, generational GC)Prof. Fateman CS 164 Lecture 17 9Why not use Reference CountsFear of not being able to collect “cycles” is often cited as a problem. When all is said and done, not as fast as GC, and uses lots of memory for the count fields. In fact you can have a lisp-like system with reference counts but a cons cell would grow from 64 to 96 bits (with 32 bit addresses) . Why does a ref. count field have to be so large? Can we use only a few bits?Prof. Fateman CS 164 Lecture 17 10Who uses Reference CountsFile systems. How many references or links are there to a file? If none, you can delete it. The cost of maintaining counts is small compared to the overhead of file open/close.Some computer systems with largish data objects (e.g. something like Matlab, or Mathematica. )Some defunct experimental lisp or lisp-like systems: esp. if GC/paging is slow, RefCounts seems more plausible(REFCO, BBN Lisp used a limited-width counter, 1,2, many).Prof. Fateman CS 164 Lecture 17 11Why Garbage Collection (GC)?GC is a winner if memory is cheap and easily available. This combination is a relatively new phenomenon.GC continues to be a popular academic topic that can cross boundaries of software, architecture, OS. Parallelism, distributed GC.Revived interest with Java, too.Conservative GC can be used even with systems for which GC would not seem to be plausible.Prof. Fateman CS 164 Lecture 17 12Why not GC?If you have so much memory, why not put it to useinstead of keeping it in reserve for GC?Some GC algorithms stop the computation at odd moments and keep the CPU and perhaps paging system very busy for a while (“not real-time”).Speed: Explicit allocation can be faster, assuming you know what you are doing. (Can you prove your program has no memory leak? Sometimes.) Stack allocation is safe, too.(depending on implementation) A “real” implementation is complex: when to grow the free space, how to avoid moving objects pointed to from registers, etc. Bad implementations are common. See Allegro CL implementation notes on GC parameters.Prof. Fateman CS 164 Lecture 17 13Kinds of GCMark and SweepCopyingGenerationalIncremental, concurrentConservative (not in Appel)Prof. Fateman CS 164 Lecture 17 14Mark-and-Sweep. The simplest.When you ask for a new record and the free list is empty, you start a GC:Mark: Start with roots: static names, stack variables.March through all reachable nodes, marking them.[how do you mark a node? In the node? In another block of storage, 1 bit per node?]. If you reach an already marked node, great. Turn back and do other stuff.{You might use a lot of stack doing this. Problem??}Sweep: Go through all the possible nodes in order, in memory. For each one that is NOT marked, put it on the free list. For each one that IS marked, clear the mark.Prof. Fateman
View Full Document
Unlocking...