DOC PREVIEW
Princeton COS 320 - Garbage collection

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Garbage collection (& Midterm Topics)Mid-term TopicsTopics: compiler & interpreter structureTopics: LexingTopics: ParsingTopics: Type CheckingThe back end!GCMemory layoutSlide 10Slide 11Slide 12Explicit MMSlide 14Slide 15Slide 16Automatic MMSlide 18Object GraphSlide 20Reference CountingSlide 22Slide 23Copying CollectionSlide 25Copying GCSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Baker’s Concurrent GCGenerational GCSlide 37Slide 38Slide 39Slide 40Garbage collection(& Midterm Topics)David WalkerCOS 320Mid-term Topics•Midterm is in class Tuesday March 22nd–be on time•Overall, you may be asked questions on–anything discussed in class before today (thursday march 10)–anything you did on assignments 1-4–anything in the corresponding chapters in the textbooks (Appel) and online notes (Harper)•at the end of each chapter in Appel there are a series of questions and exercises – midterm questions may be similar. I suggest practicing for the midterm by doing some of these questions.–a full range of topics appears on the course “schedule” web page•I will be away next week sunday-thursday–schedule an appointment Friday or Monday if you need help.–schedule an appointment with Guilherme (he will also be away)Topics: compiler & interpreter structure•what are the main phases in a compiler?–lexing, parsing, type checking, back-end•how do you implement an interpreter?•assignment #1Topics: Lexing•What is a lexer?•Regular expressions•How do you use ML-lex•Appel Chap 2, 2.1, 2.2, 2.5 –not relationships between REs and DFAs or NDFAsTopics: Parsing•context-free grammars & derivations•bottom-up parsing; top-down parsing•different kinds of grammars: ambiguous, LL(k), LR(k), SLR, LALR•ML-Yacc•semantic actions & generating abstract syntax•assignment #3•Appel Chapters 3, 4Topics: Type Checking•Typing rules & typing derivations•MinML types & Fun types•Subtyping•Type checking algorithms•Type inference algorithms•Assignment #4•Harper chapter 9, 26 (not lemmas or proofs)The back end!•Today & next time: garbage collectionGC•Every modern programming language allows programmers to allocate new storage dynamically–New records, arrays, tuples, objects, closures, etc.•Every modern language needs facilities for reclaiming and recycling the storage used by programs•It’s usually the most complex aspect of the run-time system for any modern language (Java, ML, Lisp, Scheme, Modula, …)Memory layoutstatic datastackheapgrows to preset limitnew pages allocatedvia calls to OSphysical memoryTLB addresstranslationper processvirtual memoryGC•What is garbage?–A value is garbage if it will not be used in any subsequent computation by the program•Is it easy to determine which objects are garbage?GC•What is garbage?–A value is garbage if it will not be used in any subsequent computation by the program•Is it easy to determine which objects are garbage?–No. It’s undecidable. Eg:if long-and-tricky-computation then use velse don’t use vGC•Since determining which objects are garbage is tricky, people have come up with many different techniques–It’s the programmers problem: •Explicit allocation/deallocation–Reference counting–Tracing garbage collection•Mark-sweep, copying collection•Generational GCExplicit MM•User library manages memory; programmer decides when and where to allocate and deallocate–void* malloc(long n)–void free(void *addr)–Library calls OS for more pages when necessary–Advantage: people are smart–Disadvantage: people are dumb and they really don’t want to bother with such details if they can avoid itExplicit MM•How does malloc/free work?–Blocks of unused memory stored on a freelist–malloc: search free list for usable memory block–free: put block onto the head of the freelistfreelistExplicit MM•Drawbacks–malloc is not free: we might have to do a significant search to find a big enough block–As program runs, the heap fragments leaving many small, unusable piecesfreelistExplicit MM•Solutions:–Use multiple free lists, one for each block size•Malloc and free become O(1)•But can run out of size 4 blocks, even though there are many size 6 blocks or size 2 blocks!–Blocks are powers of 2•Subdivide blocks to get the right size•Adjacent free blocks merged into the next biggest size•still possibly 30% wasted space–Crucial point: there is no magic bullet. Memory management always has a cost. We want to minimize costs and, these days, maximize reliability.Automatic MM•Languages with explicit MM are much harder to program than languages with automatic MM–Always worrying about dangling pointers, memory leaks: a huge software engineering burden–Impossible to develop a secure system, impossible to use these languages in emerging applications involving mobile code–Soon, languages with unsafe, explicit MM will all but disappear•eg: Microsoft is pouring $$$ into developing safe language technology, including a new research project on dependable operating system constructionAutomatic MM•Question: how do we decide which objects are garbage?–Can’t do it exactly–Therefore, We conservatively approximate–Normal solution: an object is garbage when it becomes unreachable from the roots•The roots = registers, stack, global static data•If there is no path from the roots to an object, it cannot be used later in the computation so we can safely recycle its memoryObject Graph–How should we test reachability?r1stackr2Object Graph–How should we test reachability?r1stackr2Reference Counting•Keep track of the number of pointers to each object (the reference count).•When the reference count goes to 0, the object is unreachable garbageObject Graph–Reference counting can’t detect cyclesr1stackr2Reference Counting–In place of a single assignment x.f = p:z = x.fc = z.countc = c – 1z.count = cIf c = 0 call putOnFreeList(z)x.f = pc = p.countc = c + 1p.count = c-Ouch, that hurts performace-wise!-Dataflow analysis can eliminate some increments and decrements, but many remain-Reference counting used insome special cases but not usually as the primary GC mechanism in a languageimplementationCopying Collection•Basic idea: use 2 heaps–One used by program–The other unused until GC time•GC:–Start at the roots & traverse the reachable data–Copy reachable data from the active heap (from-space) to the other heap (to-space)–Dead


View Full Document

Princeton COS 320 - Garbage collection

Download Garbage collection
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Garbage collection and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Garbage collection 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?