Material‎ > ‎

Garbage Collection Example

The following example illustrates the main ideas behind garbage collection (in particular, mark-and-sweep garbage collection).  It is a cleaned up and executable version of the code from the lecture.


// -*- bsh -*-

// This is a Beanshell (www.beanshell.org) source file.  You can either execute it in Beanshell
// or convert it to procedural Java as described in lecture.

// We define a very simple "Facebook" application.  There are members and there are pages.
// Each member has a name and a number of pages.  Pages have a title and a list of related
// pages.

class Member {
    String name;
    Page[] pages;
}

class Page {
    String title;
    Page[] related;
    boolean marked;
}

class Facebook {
    Member[] members;
    Page[] pages;
}

// Let us simulate adding 100 new members and 1000 new pages.

print("adding members");

Facebook fb = new Facebook();
fb.members = new Member[100];
for(int i=0;i<fb.members.length;i++) {
    fb.members[i] = new Member();
    fb.members[i].name = "Member #"+i;
    fb.members[i].pages = new Page[100];

}

print("adding pages");

fb.pages = new Page[1000];
for(int i=0;i<fb.pages.length;i++) {
    fb.pages[i] = new Page();
    fb.pages[i].title = "Page #"+i;
    fb.pages[i].related = new Page[10];
}

// Users can add pages to their member profile, and they can also add
// related pages to any page.

boolean add_page(Member member,Page page) {
    if(member==null || page==null) return false;
    for(int i=0;i<member.pages.length;i++) {
        if(member.pages[i]!=null) continue;
        member.pages[i] = page;
        return true;
    }
    return false;
}

boolean add_related(Page page,Page related) {
    if(page==null || page==null || page==related) return false;
    for(int i=0;i<page.related.length;i++) {
        if(page.related[i]!=null) continue;
        page.related[i] = related;
        return true;
    }
    return false;
}

// Now we simulate user activity.  These kinds of simulations are quite common
// in computer science and let us test systems and measure their behavior.

import java.util.Random;
Random random = new Random();

// We start off by picking a random member and a random page and have the user
// add that page to his profile.

print("adding pages to member profiles");

for(int i=0;i<fb.members.length;i++) {
    for(int j=0;j<3;j++) {
        Member member = fb.members[random.nextInt(fb.members.length)];
        Page page = fb.pages[random.nextInt(fb.pages.length)];
        add_page(member,page);
    }
}

// Next, we pick a random page and a random related page and add the
// related page to the original page as related.

print("adding related pages");

for(int i=0;i<fb.pages.length;i++) {
    for(int j=0;j<3;j++) {
        Page page = fb.pages[random.nextInt(fb.pages.length)];
        Page related = fb.pages[random.nextInt(fb.pages.length)];
        add_related(page,related);
    }
}

// After all this user activity, many pages are either directly on some member's
// list of pages, or they are at least related to some other page, even if they
// are not directly on someone's list of pages.

// However, some pages have become "unreachable": that is, they are
// neither linked to directly from a member profile, nor are they
// linked to from another page.  We want to find these unreachable
// pages so that we can delete them.

// We start off by defining two "mark" procedures.  Given either a
// member or a page, they mark all pages that are reachable from that
// member/page.  These are recursive procedures.

// (The member==null and page==null checks at the beginning allow those
// procedures to be called with null arguments without error.)

void mark(Member member) {
    if(member==null) return;

    // Marking a member is simple: we just step through each page in his
    // profile and mark that page.

    for(int i=0;i<member.pages.length;i++)
        mark(member.pages[i]);
}

void mark(Page page) {
    if(page==null || page.marked) return;

    // First, we mark the page as having been visited.  We do this before
    // we mark related pages so that we don't recurse on the same page twice.

    page.marked = true;

    // Now we step through the list of related pages and mark all of those
    // as well.

    for(int i=0;i<page.related.length;i++)
        mark(page.related[i]);
}

void remove_unreachable_pages() {

    // First, we clear all the marks on all the known pages.

    print("clearing marks");

    for(int i=0;i<fb.pages.length;i++)
        fb.pages[i].marked = false;

    // Next, we mark all the pages that are reachable from a member
    // profile.

    print("marking pages on member profiles");

    for(int i=0;i<fb.members.length;i++)
        mark(fb.members[i]);

    // After the recursive marking step, any page that has not been
    // marked is neither listed in a member profile, nor listed as
    // related to any page that is reachable from a member profile.
    // Those are the pages we can delete.

    print("deleting unreachable pages");

    ndeleted = 0;
    for(int i=0;i<fb.pages.length;i++) {
        if(fb.pages[i].marked) continue;
        print("deleting: "+fb.pages[i].title);
        // We delete the page simply by setting its corresponding entry to
        // null.  Of course, the Java storage manager eventually cleans up
        // the memory associated with that page.
        fb.pages[i] = null;
        ndeleted++;
    }

    print("deleted "+ndeleted+" unreachable pages");
}

remove_unreachable_pages();

Comments