Material‎ > ‎

Storage Management with Pools

Hier ist das Beispiel für manuelle Speicherverwaltung in Java.  Dies ist die Version, die Java Datenstrukturen verwendet.  Diese Technik wird in der Praxis häufig zur Beschleunigung von Javaprogrammen angewendet.

Das Programm kann direkt in Beanshell (www.beanshell.org) ausgeführt werden, oder es kann in "prozedurales Java" durch Hinzufügen von Klassen und "static" umgewandelt werden.

// -*- bsh -*-

// This file is written in Beanshell; you can either run this code
// by using the bsh interpreter, or you can wrap all the global functions
// below into a class.

////////////////////////////////////////////////////////////////
// Let's start with a simple linked list, as before.

class List {
    int head;
    List tail;
}

// We're now introducing a simple manual storage manager.  This storage
// manager relies on the built-in Java storage manager, but it maintains
// a count of the list elements in use, and it also reuses list elements
// that have been explicitly freed.  It reuses list elements by keeping
// the elements themselves in a "free list".

int in_use = 0;
List freelist = null;

List cons(int head,List tail) {
    in_use++;
    if(freelist!=null) {

        // If there are elements on the freelist, return the first
        // element as the result of the cons operation.

        List result = freelist;
        freelist = freelist.tail;
        result.head = head;
        result.tail = tail;
        return result;
    } else {

        // If there are no more elements on the freelist, then
        // allocate another list element from the regular Java storage
        // allocator.

        List result = new List();
        result.head = head;
        result.tail = tail;
        return result;
    }
}

// The "free" procedure just adds its argument to the freelist, the
// list of elements that can be reused.  It also decreases the in_use
// count.

void free(List l) {
    l.tail = freelist;
    freelist = l;
    --in_use;
}

// This procedure reports how many list elements are currently in use.

void used() {
    System.err.println("in use: "+in_use);
}

// A simple procedure for printing out a list.

void printl(List l) {
    System.out.print("(");
    while(l!=null) {
        System.out.print(" "+l.head);
        l = l.tail;
    }
    System.out.println(")");
}

////////////////////////////////////////////////////////////////
// Let's give this a try.

print("== simple test ==");

used(); // prints: 0
l = cons(3,null);
used(); // prints: 1
free(l);
used(); // prints: 0

////////////////////////////////////////////////////////////////
// Let's now look at how this works in the context of a destructive
// delete procedure.

List destructive_delete(List l,int x) {
    if(l==null) return null;
    while(l!=null && l.head==x) {
        List temp = l;
        l = l.tail;
        free(temp);
    }
    if(l==null) return null;
    List start = l;
    while(l.tail!=null) {
        if(l.tail.head==x) {
            List temp = l.tail;
            l.tail = l.tail.tail;
            free(temp);
        } else {
            l = l.tail;
        }
    }
    return start;
}

print("== destructive delete ==");

l = cons(1,cons(2,cons(3,null)));
printl(l); // prints: ( 1 2 3)
used();    // prints: 3
l = destructive_delete(l,1);
printl(l); // prints: ( 2 3)
used();    // prints: 2
l = destructive_delete(l,3);
printl(l); // prints: ( 2)
used();    // prints: 1
l = destructive_delete(l,2);
printl(l); // prints: ()
used();    // prints: 0

////////////////////////////////////////////////////////////////
// The following sequence of allocations and deallocations illustrates
// a memory leak

print("== memory leak ==");

used(); // prints: 0
l = cons(3,null);
used(); // prints: 1
m = cons(4,null);
used(); // prints: 2
free(m);
used(); // prints: 1
l = cons(5,null);
used(); // prints: 2
free(l);
used(); // prints: 1

// at this point, we can't free the original list element anymore
// because the reference has been lost.  We call that a memory leak.

in_use = 0; // just reset to 0 for next test
freelist = null;

////////////////////////////////////////////////////////////////
// Let's look at another problem with manual storage management:
// dangling references.

print("== dangling reference ==");

l = cons(3,null);
free(l);
// After we have freed the object referenced by l, we should
// not use that reference anymore.

m = cons(4,null);
printl(m);

// The following assignment is in error because we are using a
// reference to an object that has been freed.

l.head = 99;

// The consequence is that now an unrelated object has changed.

printl(m);


Comments