CSSE490-04 – Dynamic Storage Reclamation

Fall, 2008

Schedule Overview

Readings are to be completed before the class session. Written assignments are due at the beginning of class unless otherwise noted. We may change assigned homework at any time before it is assigned. Schedule subject to change.You may navigate to the course's home page for more course related information.

Schedule last updated Thu Nov 13.

Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Week Session Reading HW Due Topics Slides HW Assigned Milestone
0

1

Thu Sep 4

  
  • Course overview
  • Basics of Dynamic Storage Reclamation
    (Garbage Collection)
  • Key concepts in managing memory
  • What is memory management?
 Introduction  
0

2

Fri Sep 5

  
  • Garbage Collection Basics
  • Explicit memory management challenges/pluses
  • Automated memory management challenges/pluses
  • Major memory management concerns
  • Identifying garbage
 GC Basics    
1

3

Mon Sep 8
  • Continue reading from session 2
  
  • GC design choices
  • Memory management options
  • Stop-the-world, incremental, hybrid, concurrent, and parallel collection
 GC Design Choices  
1

4

Tue Sep 9

  
  • Reference counting garbage collection
  • Reclaiming objects with RCGC
  • Strengths of RCGC
  • Weaknesses of RCGC
  • The RCGC algorithm
 Reference counting garbae collection    
1

5

Thu Sep 11
  • Jones and Lins. (Recommended text, see syllabus) chapt. 3
  
  • Advancements in RCGC
  • Non-recursive freeing
  • Deferred reference counting
  • Limited-field reference counting
 Advancements in RCGC  
1

6

Fri Sep 12

  
  • Students lab time
      
2

7

Mon Sep 15

  
  • Advancements in RCGC
  • Continuation from session 5
 Advancements in RCGC    
2

8

Tue Sep 16

    
  • RCGC: Reclaiming cyclic structures
  • Reclaiming cycles in functional programming languages
  • Bobrow's technique
  • Weak pointer Algorithms
  • Hybrid algorithms
 Reclaiming cyclic structures  
2

9

Thu Sep 18

  
  • Mark-Sweep Garbage Collection
  • Mark-sweep algorithm
  • Advantages of mark-sweep GC
  • Disadvantages of mark-sweep GC
 Mark-Sweep Garbage Collection    
2

10

Fri Sep 19

    
  • Students lab time
      
3

11

Mon Sep 22

    
  • Mark-sweep Garbage Collection
  • Iterative marking
  • Minimizing stack depth
  • handling stack overflow
  • Pointer reversal
 Mark-sweep GC, marking    
3

12

Tue Sep 23

    
  • Students lab time
      
3

13

Thu Sep 25

    
  • Mark-sweep Garbage Collection
  • Bitmap marking
  • Lazy sweeping
 Optimizations for marking and sweeping    
3

14

Fri Sep 26
  • Jones and Lins. (Recommended text, see syllabus) chapt. 6
  • Students lab time
      
4

15

Mon Sep 29

    
  • Copying Garbage Collection
  • Advantages of Copying Collection
  • Disadvantages of Copying Collection
  • Fenichel and Yochelson's algorithm
 Copying garbage Collection  
4

16

Tue Sep 30

    
  • Copying Garbage Collection
  • Cheney's copying collector
  • Multiple-area collection (intro)
 Cheney's copying collector    
4

17

Thu Oct 2

    
  • Exam 1 preview
  • Copying Garbage Collection
  • Multiple-area collection
  • Incrementally compacting collector
  • efficient of copying collection
  • Locality issues
  • Copying vs Mark-sweep
  • Regrouping strategies
 Advanced Copying Collection    
4

18

Fri Oct 3

    
  • Exam 1
     Exam 1
5

19

Mon Oct 6
  • Jones and Lins. (Recommended text, see syllabus) chapt. 7
  
  • Generational Garbage Collection
  • Weak generational hypothesis
  • Generational strategy
  • How does generational GC work?
  • Properties of generational GC
 Generational Garbage Collection Project milestone 2
5

20

Tue Oct 7

    
  • Generational Garbage Collection
  • Promotion policies
  • Goals of generational collection
  • Effects of premature promotion
  • Multiple generations
  • Promotion threshold
  • Adaptive tenuring
 Promotion policies    
5

21

Thu Oct 9

    
  • Generational Garbage Collection
  • Adaptive tenuring
  • Generation organization
  • Age recording
 Promotion policies, generation organization, age recording    
5

22

Fri Oct 10

    
  • Students lab time
      
6

23

Mon Oct 13

    
  • Generational Garbage Collection
  • Inter-Generational Pointers
  • Write-barrier usage
  • Trapping & recording inter-generational pointers
  • Entry tables
  • Remembered sets
 Inter-Generational Pointers  
6

24

Tue Oct 14

  
  • Generational Garbage Collection
  • More Inter-Generational Pointers
  • Card marking
  • Non-copying Generational Garbage Collection
  • scheduling garbage collection
 Non-copying generational collection & scheduling GC   Project milestone 3
7

25

Mon Oct 20
  • Jones and Lins. (Recommended text, see syllabus) chapt. 8
  
  • Incremental and Concurrent Garbage Collection
  • Interactive or real-time application concerns
  • The need for synchronization
  • Tricolor abstraction
  • Using barriers
 Incremental and Concurrent Garbage Collection  
7

26

Tue Oct 21

    
  • Incremental and Concurrent Garbage Collection
  • Incremental Mark-sweep collectors
  • Write-barriers and tricolor abstraction
  • Yuasa's sequential collector
 Incremental Mark-sweep collectors  
7

27

Thu Oct 23

    
  • Discuss Plus-Delta
  • Project discussion and further instructions
      
7

28

Fri Oct 24

    
  • Students lab time
      
8

29

Mon Oct 27

    
  • Incremental and Concurrent Garbage Collection
  • Initialization of incremental and concurrent GC
  • termination of incremental and concurrent GC
  • Concurrent reference counting
 Concurrent reference counting   Project milestone 4
8

30

Tue Oct 28

  
  • Incremental and Concurrent Garbage Collection
  • Baker's copying collector
  • When to flip semi-spaces
  • Limitations on Baker's algorithm
  • Variation o Baker's algorithm
  • Brook's variation
 Baker's copying collector    
8

31

Thu Oct 30

    
  • Incremental and Concurrent Garbage Collection
  • Baker's Treadmill collector
  • Hardware support for real-time GC
 Baker's Treadmill collector    
8

32

Fri Oct 31

    
  • Students lab time
      
9

33

Mon Nov 3

    
  • Students lab time
      
9

34

Tue Nov 4

    
  • Technical paper presentation by instructor
      
9

35

Thu Nov 6

    
  • Technical paper presentation by students
      
9

36

Fri Nov 7

    
  • Exam 2
     Exam 2
10

37

Mon Nov 10

    
  • Technical paper presentation by students
      
10

38

Tue Nov 11

    
  • Technical paper presentation by students
      
10

39

Thu Nov 13

    
  • Technical paper presentation by students
  • Course evaluation
 Course evaluatons    
10

40

Fri Nov 14

    
  • Project presentation