DOC PREVIEW
UA CSC 520 - Study Notes

This preview shows page 1 out of 3 pages.

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

Unformatted text preview:

CSc 520Principles of Programming Languages42: Garbage Collection — Uncooperative LanguagesChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Uncooperative LanguagesThere is some information which is necessary in order to perform automatic memory management:1. We need to find the roots of the object graph, i.e. the pointers from the stack, registers, or globalvariables which point to objects on the heap.2. We need to know the size, the beginning, and end of each object.3. For each object we need to find which of its fields are pointers.• Unfortunately, some languages have been designed so that it is impossible to determine this information.• C and C++ are the two most popular such languages.2 Uncooperative Languages. . .• C and C++ don’t separate safe and unsafe features (such as address and bit manipulation) which aresometimes needed in systems programming.• Modula-3 has similar unsafe features as C and C++ but they can be encapsulated into unsafe modules,which don’t mess up the safety of the main (safe) part of the program.3 Uncooperative Languages. . .• Most GC algorithms assume that there is always a pointer to the beginning of every object. Dependingon the code generator, that may or may not be true.f(g,s) char (*g)(); char * s;{ int i; int l = strlen(s);for (i = 0; i < l; i++)s[i] = (*g)(s[i]); }1There may be no pointer to s[0].4 Uncooperative Languages. . .We need to know1. the roots of the object graph.2. the size, the beginning, and end of each object.3. which object fields are pointers.Finding Roots:Foo* f = new foo; // f = 0x53f36f = NULL; // f* is garbageint i = 0x53f36; // points to f...5 Uncooperative Languages. . .Finding the beginning:char* str = new char[26];strcpy(str, "This is a string");str += 10; // Only ptr to str...Finding pointers:union Unsure {char* str; int i} x;Conservative Garbage Collection6 Conservative GC• Works OK for uncooperative languages (C, C++) where we can’t distinguish between pointers andintegers. Sometimes fails to reclaim all garbage.Main Ideas:• Allocate memory in chunks. Each chunk holds a collection of objects of a certain size (i.e. it’s easy tofind the start of objects).• Chunks are numbered. A pointer consists of 12 bits of chunk number (C) + 20 bits of offset withinthe chunk (O).7 Conservative GC. . .• To check whether a value V = (C, O) is a pointer to some object we check that1. Heap-bottom ≤ V ≤ Heap-top,2. FirstChunk# ≤ C ≤ LastChunk#3. the offset O is a multiple of the object size in chunk C.28 Conservative GC. . .ChunkList:1 2 3 4 5 6 7size= 8markbitsObjectsChunk 1:. . . . . . . . . . 8 byteseachV:Chunk number Offset within chunk(12 bits) (20 bits)00000000011100000000000000011110ObjectsChunk 7:sizemarkbits= 324K bytes32 bytes each9 Readings and References• Read Scott, pp.


View Full Document

UA CSC 520 - Study Notes

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Study Notes
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 Study Notes 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 Study Notes 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?