6.001 Recitation – May 9, 2003

RI: Konrad Tollmar

www.ai.mit.edu/~konrad/6001

• Memory Management

• Decompiling

1. Store lists in arrays

A/ Draw the box-and-pointer diagram starting from P5

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5

B / Save foo in memory

(define foo (map square (list 1 2 3)))

	0	1	2	3	4	5	6	7	8	9	10
Cars
Cdrs

2. GC – Stop & Copy

Do stop-and-copy on the following with Root Set = { P5 }:

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5

	0	1	2	3	4	5	6	7	8	9	10
Cars
Cdrs

1. Set free and scan to beginning of new memory
2. Move root pair to new memory
3. Adjust root pointer to new location
4. Ancrement free as necessary
5. Mark old pairs by putting a forwarding pointer ("broken heart") to new memory
6. Basic cycle:
1. Trace pointers in car and cdr in cell pointed to by scan back to old memory
2. Relocate each one: if a forwarding pointer, use forwarding address to update pointers, and if not a forwarding pointer, copy into free pair, then increment free, store a forwarding pointer, and update pointers to new pair
3. Increment scan
7. Stop when scan catches up to free

3. GC – Mark & Sweep

Do the mark & sweep on the following with Root Set = { P5 }:

	0	1	2	3	4	5	6	7	8	9	10
Cars	N3	N4	P0	N3	N5	P2	N2	N3	P1	N4
Cdrs	E0	E0	P4	P5	P0	P6	P5	P3	P3	N5

1. Add a Mark Bit to each location in memory.
2. Keep a free pointer to the head of the free list.
3. When Memory runs out, clear the Mark Bits, and:
4. Mark
1. Start at the root and follow the accessible structure
   (keeping a stack of where you still need to go).
2. Mark every cell you visit.
3. Stop when you see a marked cell, so you don't go into a cycle.
5. Sweep
1. Build a new free list from the unmarked cells
2. Free list starts at last free cell.
3. Clear marks