Co to jest StackOverflowError?

Aby to opisać, najpierw pozwól nam zrozumieć, w jaki sposób lokalne zmienne i obiekty są przechowywane.

Zmienne lokalne są przechowywane w stos :

Jeśli spojrzysz na obraz, powinieneś być w stanie zrozumieć, jak wszystko działa.

Gdy wywołanie funkcji jest wywoływane przez aplikację Java, na stosie wywołań przydzielana jest ramka stosu. Ramka stosu zawiera parametry wywołanej metody, jej parametry lokalne oraz adres zwrotny metoda. Adres zwrotny oznacza punkt wykonania, z którego wykonywanie programu będzie kontynuowane po powrocie wywołanej metody. Jeśli nie ma miejsca na nową ramkę stosu, to {[2] } jest wyrzucana przez maszynę Wirtualną Java (JVM).

Najczęstszym przypadkiem, który może wyczerpać stos aplikacji Java, jest rekurencja. W rekurencji metoda wywołuje się podczas jej wykonywania. Rekurencja jest uważana za potężną technikę programowania ogólnego przeznaczenia, ale musi być stosowany ostrożnie, aby uniknąć StackOverflowError.

Przykład rzucania StackOverflowError jest pokazany poniżej:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);

        if(num == 0)
            return;
        else
            recursivePrint(++num);
    }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

W tym przykładzie definiujemy metodę rekurencyjną o nazwie recursivePrint, która wypisuje liczbę całkowitą, a następnie wywołuje samą siebie, z następną liczbą całkowitą jako argumentem. Rekurencja kończy się, dopóki nie podamy 0 jako parametru. Jednak w naszym przykładzie przekazaliśmy w parametrze z 1 i jego rosnących następców, w konsekwencji rekurencję nigdy się nie skończy.

Przykładowe wykonanie, używając znacznika -Xss1M określającego rozmiar stosu wątków równy 1MB, jest pokazane poniżej:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

W zależności od początkowej konfiguracji JVM, wyniki mogą się różnić, ale ostatecznie StackOverflowError należy wyrzucić. Ten przykład jest bardzo dobrym przykładem tego, jak rekurencja może powodować problemy, jeśli nie zostanie zaimplementowana z zachowaniem ostrożności.

Jak radzić sobie ze StackOverflowError

1. Na najprostszym rozwiązaniem jest dokładne sprawdzenie śladu stosu i Wykryj powtarzający się wzór liczb linii. Te numery linii wskaż, że kod jest wywoływany rekurencyjnie. Po wykryciu tych linie, musisz dokładnie sprawdzić swój kod i zrozumieć, dlaczego rekurencja nigdy się nie kończy.

2. Jeśli zweryfikowałeś, że rekurencja jest poprawnie zaimplementowany, można zwiększyć rozmiar stosu, w aby umożliwić większą liczbę zaproszeń. W zależności od Javy Zainstalowanej maszyny wirtualnej (JVM), domyślny rozmiar stosu wątków może równe albo 512KB, albo 1MB. Możesz zwiększyć stos wątków Rozmiar przy użyciu znacznika -Xss. Flaga ta może być określona poprzez konfiguracji projektu, lub za pomocą wiersza poleceń. Format -Xss argument jest: -Xss<size>[g|G|m|M|k|K]

Jeśli masz funkcję taką jak:

int foo()
{
    // more stuff
    foo();
}

Wtedy foo() będzie wywoływać się coraz głębiej i głębiej, a gdy przestrzeń używana do śledzenia funkcji, w których się znajdujesz, zostanie wypełniona, pojawi się błąd przepełnienia stosu.

Przepełnienie stosu oznacza dokładnie, że: przepełnienie stosu. Zwykle w programie jest jeden stos, który zawiera zmienne local-scope i adresy, z których należy zwrócić po zakończeniu wykonywania procedury. Ten stos ma tendencję do stałego zakresu pamięci gdzieś w pamięci, dlatego jest ograniczony, ile może zawierać wartości.

Jeśli stos jest pusty, nie możesz pop, jeśli to zrobisz, otrzymasz błąd underflow stosu.

Jeśli stos jest pełny, nie możesz naciskać, jeśli to zrobisz, dostaniesz stos błąd przepełnienia.

Więc pojawia się przepełnienie stosu, w którym przypisujesz zbyt dużo do stosu. Na przykład we wspomnianej rekurencji.

Niektóre implementacje optymalizują niektóre formy rekurencji. W szczególności rekurencja ogonowa. Procedury rekurencyjne ogonowe są formą procedur, w których wywołanie rekurencyjne pojawia się jako ostateczna rzecz, co robi procedura. Taka rutynowa rozmowa zostaje po prostu zredukowana do skoku.

Niektóre implementacje idą tak daleko, że implementują własne stosy dla rekurencji, w związku z tym pozwalają na kontynuowanie rekurencji, dopóki system nie wyczerpie pamięci.

Najprostszą rzeczą, jaką możesz spróbować, byłoby zwiększenie rozmiaru stosu, jeśli możesz. Jeśli jednak nie możesz tego zrobić, drugą najlepszą rzeczą byłoby sprawdzenie, czy jest coś, co wyraźnie powoduje przepełnienie stosu. Spróbuj wydrukować coś przed i po wywołaniu do rutyny. To pomoże Ci dowiedzieć się, co się nie udaje.

Przepełnienie stosu jest zwykle wywoływane przez zbyt głębokie zagnieżdżanie wywołań funkcji (szczególnie łatwe przy użyciu rekurencji, tzn. funkcji, która wywołuje samą siebie) lub przydzielanie dużej ilości pamięci na stosie, gdzie użycie sterty byłoby bardziej odpowiednie.

Jak mówisz, musisz pokazać jakiś kod. :-)

Błąd przepełnienia stosu zwykle występuje, gdy funkcja wywołuje Gniazdo zbyt głęboko. Zobacz wątek Stack Overflow Code Golf , aby dowiedzieć się, jak to się dzieje (choć w przypadku tego pytania, odpowiedzi celowo powodują przepełnienie stosu).

Najczęstszą przyczyną przepełnienia stosu jest nadmiernie głęboka lub nieskończona rekurencja. Jeśli to jest Twój problem, Ten samouczek o rekurencji Javy może pomóc zrozumieć problem.

StackOverflowError jest do stosu jak {[2] } jest do stosu.

Nieograniczone wywołania rekurencyjne powodują użycie przestrzeni stosu.

Poniższy przykład tworzy StackOverflowError:

class  StackOverflowDemo
{
    public static void unboundedRecursiveCall() {
     unboundedRecursiveCall();
    }

    public static void main(String[] args) 
    {
        unboundedRecursiveCall();
    }
}

StackOverflowError jest unikalne, jeśli wywołania rekurencyjne są ograniczone, aby zapobiec przekroczeniu rozmiaru stosu (w bajtach) przez łączną sumę niekompletnych wywołań w pamięci.

Oto przykład rekurencyjnego algorytmu odwracania listy pojedynczo połączonej. Na laptopie z następującą specyfikacją (pamięć 4G, procesor Intel Core i5 2.3 GHz, 64-bitowy Windows 7), Funkcja ta wystąpi błąd StackOverflow dla połączonej listy wielkości bliskiej 10 000.

Chodzi mi o to, że powinniśmy używać rekurencji rozsądnie, zawsze biorąc pod uwagę skalę systemu. Często rekurencję można przekształcić w program iteracyjny, który skaluje się lepiej. (Jedna iteracyjna wersja ten sam algorytm jest podany na dole strony, odwraca pojedynczo połączoną listę wielkości 1 miliona w ciągu 9 milisekund.)

    private static LinkedListNode doReverseRecursively(LinkedListNode x, LinkedListNode first){

    LinkedListNode second = first.next;

    first.next = x;

    if(second != null){
        return doReverseRecursively(first, second);
    }else{
        return first;
    }
}

public static LinkedListNode reverseRecursively(LinkedListNode head){
    return doReverseRecursively(null, head);
}

Iteracyjna wersja tego samego algorytmu:

    public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}   

private static LinkedListNode doReverseIteratively(LinkedListNode x, LinkedListNode first) {

    while (first != null) {
        LinkedListNode second = first.next;
        first.next = x;
        x = first;

        if (second == null) {
            break;
        } else {
            first = second;
        }
    }
    return first;
}


public static LinkedListNode reverseIteratively(LinkedListNode head){
    return doReverseIteratively(null, head);
}

A {[2] } to błąd środowiska uruchomieniowego w Javie.

Jest wyrzucany, gdy ilość pamięci stosu wywołań przydzielona przez JVM jest przekroczona.

Częsty przypadek a StackOverflowErrorjest wyrzucany, gdy stos wywołań przekracza z powodu nadmiernej rekurencji głębokiej lub nieskończonej.

Przykład:

public class Factorial {
    public static int factorial(int n){
        if(n == 1){
            return 1;
        }
        else{
            return n * factorial(n-1);
        }
    }

    public static void main(String[] args){
        System.out.println("Main method started");
        int result = Factorial.factorial(-1);
        System.out.println("Factorial ==>"+result);
        System.out.println("Main method ended");
    }
}

Stack trace:

Main method started
Exception in thread "main" java.lang.StackOverflowError
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)
at com.program.stackoverflow.Factorial.factorial(Factorial.java:9)

W powyższym przypadku można uniknąć dokonywania zmian programowych. Ale jeśli logika programu jest poprawna i nadal występuje, wtedy rozmiar stosu musi zostać zwiększony.

Oto przykład

public static void main(String[] args) {
    System.out.println(add5(1));
}

public static int add5(int a) {
    return add5(a) + 5;
}

StackOverflowError jest w zasadzie wtedy, gdy próbujesz zrobić coś, co najprawdopodobniej wywołuje się i trwa do nieskończoności (lub dopóki nie da StackOverflowError).

add5(a) zadzwoni sam, a potem zadzwoni ponownie, i tak dalej.

Termin " przepełnienie stosu (overflow)" jest często używany, ale błędny; ataki nie przepełniają stosu, ale bufory na stosie.

-- z wykładu prof. dr. Dietera Gollmanna

Jest to typowy przypadek java.lang.StackOverflowError... Metoda jest wywoływana rekurencyjnie bez wyjścia w doubleValue(), floatValue(), itd.

Racjonalne.java

    public class Rational extends Number implements Comparable<Rational> {
        private int num;
        private int denom;

        public Rational(int num, int denom) {
            this.num = num;
            this.denom = denom;
        }

        public int compareTo(Rational r) {
            if ((num / denom) - (r.num / r.denom) > 0) {
                return +1;
            } else if ((num / denom) - (r.num / r.denom) < 0) {
                return -1;
            }
            return 0;
        }

        public Rational add(Rational r) {
            return new Rational(num + r.num, denom + r.denom);
        }

        public Rational sub(Rational r) {
            return new Rational(num - r.num, denom - r.denom);
        }

        public Rational mul(Rational r) {
            return new Rational(num * r.num, denom * r.denom);
        }

        public Rational div(Rational r) {
            return new Rational(num * r.denom, denom * r.num);
        }

        public int gcd(Rational r) {
            int i = 1;
            while (i != 0) {
                i = denom % r.denom;
                denom = r.denom;
                r.denom = i;
            }
            return denom;
        }

        public String toString() {
            String a = num + "/" + denom;
            return a;
        }

        public double doubleValue() {
            return (double) doubleValue();
        }

        public float floatValue() {
            return (float) floatValue();
        }

        public int intValue() {
            return (int) intValue();
        }

        public long longValue() {
            return (long) longValue();
        }
    }

Main.java

    public class Main {

        public static void main(String[] args) {

            Rational a = new Rational(2, 4);
            Rational b = new Rational(2, 6);

            System.out.println(a + " + " + b + " = " + a.add(b));
            System.out.println(a + " - " + b + " = " + a.sub(b));
            System.out.println(a + " * " + b + " = " + a.mul(b));
            System.out.println(a + " / " + b + " = " + a.div(b));

            Rational[] arr = {new Rational(7, 1), new Rational(6, 1),
                    new Rational(5, 1), new Rational(4, 1),
                    new Rational(3, 1), new Rational(2, 1),
                    new Rational(1, 1), new Rational(1, 2),
                    new Rational(1, 3), new Rational(1, 4),
                    new Rational(1, 5), new Rational(1, 6),
                    new Rational(1, 7), new Rational(1, 8),
                    new Rational(1, 9), new Rational(0, 1)};

            selectSort(arr);

            for (int i = 0; i < arr.length - 1; ++i) {
                if (arr[i].compareTo(arr[i + 1]) > 0) {
                    System.exit(1);
                }
            }


            Number n = new Rational(3, 2);

            System.out.println(n.doubleValue());
            System.out.println(n.floatValue());
            System.out.println(n.intValue());
            System.out.println(n.longValue());
        }

        public static <T extends Comparable<? super T>> void selectSort(T[] array) {

            T temp;
            int mini;

            for (int i = 0; i < array.length - 1; ++i) {

                mini = i;

                for (int j = i + 1; j < array.length; ++j) {
                    if (array[j].compareTo(array[mini]) < 0) {
                        mini = j;
                    }
                }

                if (i != mini) {
                    temp = array[i];
                    array[i] = array[mini];
                    array[mini] = temp;
                }
            }
        }
    }

Wynik

    2/4 + 2/6 = 4/10
    Exception in thread "main" java.lang.StackOverflowError
    2/4 - 2/6 = 0/-2
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
    2/4 * 2/6 = 4/24
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
    2/4 / 2/6 = 12/8
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)
        at com.xetrasu.Rational.doubleValue(Rational.java:64)

Oto kod źródłowy StackOverflowError w OpenJDK 7