CSSE490 – Dynamic Storage Reclamation

Spring, 2009-10

Schedule Overview

Readings are to be completed before the class session. Written assignments are due at the beginning of class unless otherwise noted. All electronic assignments are due by 11:55 PM on their due dates. We may change assigned homework at any time before it is assigned. The schedule subject to change. You may navigate to the course's home page for more course related information.

Schedule last updated Thu May 20.

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
1

1

Mon Mar 8

  
  • Course overview
  • Basics of Dynamic Storage Reclamation
    (Garbage Collection)
  • Key concepts in managing memory
  • What is memory management?
  • Explicit memory management challenges/pluses
  • Automated memory management challenges/pluses
 Introduction  
1

2

Tue Mar 9

  
  • Garbage Collection Basics
  • Major memory management concerns
  • Identifying garbage
  • Introduction to GC design choices
 GC Basics    
1

3

Thu Mar 11
  • Continue reading from session 2
  
  • More on GC design choices
  • Memory management options
  • Stop-the-world, incremental, hybrid, concurrent, and parallel collection
 GC Design Choices  
1

4

Fri Mar 12

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

5

Mon Mar 15
  • 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  
2

6

Tue Mar 16

  
  • Students lab time
      
2

7

Thu Mar 18

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

8

Fri Mar 19

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

9

Mon Mar 22

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

10

Tue Mar 23

    
  • Students lab time
      
3

11

Thu Mar 25

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

12

Fri Mar 26

    
  • Students lab time
      
4

13

Mon Mar 29

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

14

Tue Mar 30
  • Jones and Lins. (Recommended text, see syllabus) chapt. 6
  • Copying Garbage Collection
  • Advantages of Copying Collection
  • Disadvantages of Copying Collection
  • Fenichel and Yochelson's algorithm
 Copying garbage Collection    
4

15

Thu Apr 1

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

16

Fri Apr 2

    
  • Students lab time
      
5

17

Mon Apr 12

    
  • 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    
5

18

Tue Apr 13

    
  • Exam 1
     Exam 1
5

19

Thu Apr 15
  • 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  
5

20

Fri Apr 16

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

21

Mon Apr 19

    
  • Students lab time
      
6

22

Tue Apr 20

    
  • Generational Garbage Collection
  • Generation organization
  • Age recording
  • Inter-Generational Pointers
  • Write-barrier usage
  • Trapping & recording inter-generational pointers
  • Entry tables
  • Remembered sets
 Generation organization, age recording, and Inter-Generational Pointers    
6

23

Thu Apr 22

  
  • Generational Garbage Collection
  • More Inter-Generational Pointers
  • Card marking
  • Non-copying Generational Garbage Collection
  • scheduling garbage collection
 Non-copying generational collection & scheduling GC    
6

24

Fri Apr 23
  • 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

25

Mon Apr 26

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

26

Tue Apr 27

    
  • Project discussion and further instructions
    
7

27

Thu Apr 29

    
  • Incremental and Concurrent Garbage Collection
  • Initialization of incremental and concurrent GC
  • termination of incremental and concurrent GC
  • Concurrent reference counting
 Concurrent reference counting    
7

28

Fri Apr 30

    
  • Students lab time (No class meeting)
      
8

29

Mon May 3

    
  • 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   Project milestone 1
8

30

Tue May 4

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

31

Thu May 6

    
  • Exam 2 Review
  • Students lab time
      
8

32

Fri May 7

    
  • Exam 2
     Exam 2
9

33

Mon May 10

    
  • Students lab time
      
9

34

Tue May 11

    
  • Technical paper presentation by instructor
      
9

35

Thu May 13

    
  • Technical paper presentation by Derek Hammer
  • Technical paper presentation by Phillip Iverson
      
9

36

Fri May 14

    
  • Technical paper presentation by Brian Buetow
  • Technical paper presentation by Erik Snider
      
10

37

Mon May 17

    
  • Technical paper presentation by Jeremiah Elroy
  • Technical paper presentation by David Bliss
      
10

38

Tue May 18

    
  • Technical paper presentation by Jonathan Woodworth
  • Technical paper presentation by Chandler Kent
      
10

39

Thu May 20

    
  • Course evaluation
  • Project presentation: Team 12
 Course evaluatons   Project Presentation
10

40

Fri May 21

         Project Presentation