Co to jest StackOverflowError?

Co to jest StackOverflowError, co go powoduje i jak sobie z nimi radzić?

Parametry i zmienne lokalne są przydzielane na stosie (w przypadku typów referencji obiekt mieszka na stercie, a zmienna w stosie odwołuje się do obiektu na stercie). Stos zwykle znajduje się na górnym końcu twojej przestrzeni adresowej i gdy jest używany w górę, zmierza w kierunku dolnej części przestrzeni adresowej (tj. W kierunku zera).

Twój proces ma również stertę , która żyje w dolnej części procesu. Podczas alokacji pamięci ta sterty może rosnąć w kierunku górnej części przestrzeni adresowej. Jak widać, sterty mogą „zderzyć się” ze stosem (trochę jak płyty tektoniczne !!!).

Częstą przyczyną przepełnienia stosu jest złe wywołanie rekurencyjne . Zwykle dzieje się tak, gdy funkcje rekurencyjne nie mają poprawnego warunku zakończenia, dlatego ostatecznie wywołuje się na zawsze. Lub gdy warunek zakończenia jest w porządku, może być spowodowany wymaganiem zbyt wielu połączeń rekurencyjnych przed jego spełnieniem.

Jednak przy programowaniu GUI możliwe jest generowanie pośredniej rekurencji . Na przykład aplikacja może obsługiwać komunikaty o farbach, a podczas ich przetwarzania może wywoływać funkcję, która powoduje wysłanie przez system kolejnej wiadomości o farbie. W tym przypadku nie zostałeś wyraźnie nazwany, ale OS / VM zrobiła to za Ciebie.

Aby sobie z nimi poradzić, musisz sprawdzić swój kod. Jeśli masz funkcje, które same się wywołują, sprawdź, czy masz warunek zakończenia. Jeśli tak, sprawdź, czy podczas wywoływania funkcji zmodyfikowałeś przynajmniej jeden z argumentów, w przeciwnym razie nie będzie widocznej zmiany dla rekurencyjnie wywoływanej funkcji, a warunek zakończenia jest bezużyteczny. Pamiętaj też, że w stosie może zabraknąć pamięci przed osiągnięciem prawidłowego warunku zakończenia, dlatego upewnij się, że Twoja metoda obsługuje wartości wejściowe wymagające większej liczby wywołań rekurencyjnych.

Jeśli nie masz żadnych oczywistych funkcji rekurencyjnych, sprawdź, czy wywołujesz funkcje biblioteczne, które pośrednio spowodują wywołanie twojej funkcji (jak powyższy przypadek niejawny).

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

Zmienne lokalne są przechowywane na stosie :

Jeśli spojrzysz na obraz, powinieneś być w stanie zrozumieć, jak działają rzeczy.

Gdy aplikacja Java wywołuje wywołanie funkcji, ramka stosu jest przydzielana na stosie wywołań. Ramka stosu zawiera parametry wywoływanej metody, jej parametry lokalne i adres zwrotny metody. Adres zwrotny oznacza punkt wykonania, z którego wykonywanie programu będzie kontynuowane po powrocie wywoływanej metody. Jeśli nie ma miejsca na nową ramkę stosu, StackOverflowErrorjest ona generowana przez maszynę wirtualną Java (JVM).

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

Przykład rzucania a StackOverflowErrorpokazano 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ą, wywoływaną, recursivePrintktóra wypisuje liczbę całkowitą, a następnie wywołuje się, z argumentem następnej liczby całkowitej. Rekurencja kończy się, dopóki nie przejdziemy 0jako parametr. Jednak w naszym przykładzie przekazaliśmy parametr od 1 i jego rosnących obserwujących, w związku z czym rekurencja nigdy się nie zakończy.

Przykładowe wykonanie z użyciem -Xss1Mflagi określającej rozmiar stosu wątków równego 1 MB pokazano 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 StackOverflowErrorzostaną wyrzucone. Ten przykład jest bardzo dobrym przykładem tego, jak rekurencja może powodować problemy, jeśli nie zostanie wykonana ostrożnie.

Jak radzić sobie z StackOverflowError

1. Najprostszym rozwiązaniem jest dokładne sprawdzenie śladu stosu i wykrycie powtarzającego się wzoru numerów linii. Te numery wierszy wskazują, że kod jest wywoływany rekurencyjnie. Po wykryciu tych wierszy należy dokładnie sprawdzić kod i zrozumieć, dlaczego rekurencja nigdy się nie kończy.

2. Jeśli upewniłeś się, że rekurencja jest poprawnie zaimplementowana, możesz zwiększyć rozmiar stosu, aby umożliwić większą liczbę wywołań. W zależności od zainstalowanej wirtualnej maszyny Java (JVM) domyślny rozmiar stosu wątków może wynosić 512 KB lub 1 MB . Możesz zwiększyć rozmiar stosu nici za pomocą -Xssflagi. Ta flaga może być określona albo przez konfigurację projektu, albo poprzez wiersz poleceń. Format -Xssargumentu to: -Xss<size>[g|G|m|M|k|K]

Jeśli masz taką funkcję jak:

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

Następnie foo () będzie się nadal wywoływał, coraz głębiej i głębiej, a kiedy przestrzeń używana do śledzenia funkcji, w których się znajdujesz jest zapełniona, pojawia się błąd przepełnienia stosu.

Przepełnienie stosu oznacza dokładnie to: przepełnienie stosu. Zwykle w programie jest jeden stos, który zawiera zmienne o zasięgu lokalnym i adresy, do których należy zwrócić po zakończeniu wykonywania procedury. Ten stos jest zwykle ustalonym zakresem pamięci gdzieś w pamięci, dlatego jest ograniczony, ile może zawierać wartości.

Jeśli stos jest pusty, nie możesz wyskoczyć, jeśli to zrobisz, pojawi się błąd niedopełnienia stosu.

Jeśli stos jest pełny, nie możesz wypchnąć, jeśli to zrobisz, pojawi się błąd przepełnienia stosu.

Tak więc przepełnienie stosu pojawia się tam, gdzie zbyt dużo miejsca przeznaczasz na stos. Na przykład we wspomnianej rekursji.

Niektóre implementacje optymalizują niektóre formy rekurencji. Zwłaszcza ogon. Procedury rekurencyjne typu tail są procedurami, w których wywołanie rekurencyjne pojawia się jako ostatnia czynność wykonywana przez procedurę. Takie rutynowe wywołanie zostaje po prostu zredukowane do skoku.

Niektóre implementacje idą tak daleko, jak implementują własne stosy rekurencji, dlatego pozwalają one kontynuować rekurencję, dopóki systemowi nie zabraknie pamięci.

Najłatwiejszą rzeczą, jaką możesz spróbować, jest zwiększenie swojego stosu, jeśli możesz. Jeśli nie możesz tego zrobić, drugą najlepszą rzeczą byłoby sprawdzenie, czy istnieje coś, co wyraźnie powoduje przepełnienie stosu. Spróbuj, drukując coś przed i po rozmowie. Pomaga to znaleźć rutynę.

Przepełnienie stosu jest zwykle wywoływane przez zbyt głębokie zagnieżdżenie wywołań funkcji (szczególnie łatwe przy użyciu rekurencji, tj. Funkcji, która wywołuje się sama) lub przydzielenie dużej ilości pamięci na stosie, gdzie użycie stosu byłoby bardziej odpowiednie.

Tak jak mówisz, musisz pokazać trochę kodu. :-)

Błąd przepełnienia stosu zwykle występuje, gdy wywołania funkcji zagnieżdżają się zbyt głęboko. Zobacz temat Kod przepełnienia stosu Golf, aby znaleźć przykłady tego, jak to się dzieje (chociaż w przypadku tego pytania odpowiedzi celowo powodują przepełnienie stosu).

Najczęstszą przyczyną przepełnienia stosu jest zbyt głęboka lub nieskończona rekurencja . Jeśli to jest twój problem, ten samouczek dotyczący Java Recursion może pomóc w zrozumieniu problemu.

StackOverflowErrorjest na stosie, podobnie jak OutOfMemoryErrorna stosie.

Nieograniczone wywołania rekurencyjne powodują zużycie miejsca na stosie.

Poniższy przykład przedstawia StackOverflowError:

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

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

StackOverflowError można uniknąć, jeśli wywołania rekurencyjne są ograniczone, aby zapobiec przekroczeniu przez stos łącznej liczby niekompletnych wywołań w pamięci (w bajtach) wielkości stosu (w bajtach).

Oto przykład algorytmu rekurencyjnego do cofania pojedynczo połączonej listy. Na laptopie z następującą specyfikacją (pamięć 4G, procesor Intel Core i5 2.3GHz, 64-bitowy system Windows 7) ta funkcja będzie działać w trybie StackOverflow dla połączonej listy o wielkości zbliżonej do 10 000.

Chodzi mi o to, że powinniśmy rozsądnie wykorzystywać rekurencję, 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 tego samego algorytmu jest podana na dole strony, odwraca pojedynczo połączoną listę o wielkości 1 miliona w 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 StackOverflowErrorjest błędem środowiska wykonawczego w Javie.

Jest generowany, gdy ilość pamięci stosu wywołań przydzielonej przez JVM zostanie przekroczona.

Częstym przypadkiem StackOverflowErrorrzucenia jest sytuacja, gdy stos wywołań przekracza się z powodu nadmiernej głębokiej lub nieskończonej rekurencji.

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");
    }
}

Ślad stosu:

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 tego uniknąć, wprowadzając zmiany programowe. Ale jeśli logika programu jest poprawna i nadal występuje, należy zwiększyć rozmiar stosu.

Jest to typowy przypadek java.lang.StackOverflowError... Metoda rekurencyjnie wywołuje się bez wyjścia doubleValue(),floatValue() itp

Rational.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 StackOverflowErrorw OpenJDK 7

W sytuacji kryzysowej sytuacja poniżej spowoduje błąd przepełnienia stosu.

public class Example3 {

public static void main(String[] args) {

    main(new String[1]);

}

}

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 w zasadzie ma miejsce, gdy próbujesz zrobić coś, co najprawdopodobniej wywołuje się i trwa przez nieskończoność (lub dopóki nie da StackOverflowError).

add5(a) zadzwoni do siebie, a następnie zadzwoni ponownie i tak dalej.

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

- ze slajdów wykładów prof. dr Dietera Gollmanna