Bash - Limit-Subshells in Rekursion

Question

Ich habe beschlossen, Rekursionen in Bash auf meinem Produktionsserver zu testen.

Führen Sie diesen Code nicht auf einer Produktionsmaschine aus!

#!/usr/bin/bash

function fibo {
    if [ $1 -le 1 ]; then echo $1
    else
        echo $(( $( fibo $(( $1 - 1 )) ) +
            $( fibo $(( $1 - 2 )) )
        ))
    fi
}

fibo 100

Ich vermutete, dass es langsam sein wird, hatte aber nicht erwartet, dass es zehn parallele Jobs ausführen wird. Ich dachte, weil der Server Multicore ist, könnte ich den Prozess abbrechen.

Leider ist der Server eingefroren und vom Hosting-Unternehmen neu gestartet worden.

Gibt es eine Möglichkeit, die parallelen Jobs in Bash zu begrenzen?

Ist es möglich, die PID des Hauptprozesses in einem Timer einzustellen und alle untergeordneten Jobs zu stoppen?

Natürlich frage ich nur für akademische Zwecke.

Bearbeiten

Die Tail-Rekursionsversion funktioniert wie ein Zauber:

#!/usr/bin/bash

fibo() {
    local n=$1 a=$2 b=$3

    case $n in 0) echo "$a" ;;
        1) echo "$b" ;; *) fibo $((n - 1)) "$b" $((a + b)) ;;
    esac
}

fibo "${1:-10}" 0 1

Benchmark:

time ./fibotr.sh 100

3736710778780434371

real    0m0.078s
user    0m0.000s
sys     0m0.015s

Answer 1

Informationen zu Präventionsmethoden finden Sie auf unserer Schwesterseite Unix & Linux Stack Exchange . Zu den aktuellen Fragen gehört die sichere Ausführung einer Gabelbombe .

Als Implementierung Ihres ursprünglichen Algorithmus, der überhaupt keine Unterschalen abzweigt und sich daher unmöglich in eine Gabelbombe verwandeln kann, selbst wenn willkürlich große Zahlen übergeben werden:

#!/usr/bin/env bash

declare -g _fibo_resA _fibo_resB # be explicit that it's intentional that these
                                 # variables aren't locals, for future readers
fibo() {
    local _fibo_outvar _fibo_inVal _fibo_locResA _fibo_locResB
    _fibo_outvar=$1; _fibo_inVal=$2
    if [ "$_fibo_inVal" -le 1 ]; then printf -v "$_fibo_outvar" 1
    else
        fibo _fibo_resA "$(( _fibo_inVal - 1 ))"; _fibo_locResA=$_fibo_resA
        fibo _fibo_resB "$(( _fibo_inVal - 2 ))"; _fibo_locResB=$_fibo_resB
        printf -v "$_fibo_outvar" "$(( _fibo_locResA + _fibo_locResB ))"
    fi
}

# note that 100 is way too big; performance breaks down between 20 and 30
# but at least it won't act like a fork bomb!
fibo result "${1:-100}" # let user pass in a value they choose echo "$result"

Warum ist das so geschrieben, wie es ist?

• Die wichtigste Änderung war die Beseitigung $( ), dies erfordert jedoch nicht mehr die Weitergabe der Ausgabe an das übergeordnete Element bei stdout. Verwenden Sie daher indirekte Zuweisungen für diesen Zweck.
• Die Verwendung von Variablennamen mit Namespace (auch für Einheimische!) Verhindert Konflikte bei der Rückgabe eines Ergebnis-Nachnamens: Wenn der Benutzer ein Ergebnis in einen Variablennamen schreibt, der mit einem unserer Einheimischen übereinstimmt, wird dessen Wert nicht in den lokalen Namen geschrieben die globale Variable, in die das Ergebnis eingefügt werden soll.
• locResAund locResBwerden verwendet, weil wir nicht gabeln und nicht machen resAund resBlokal machen können; Sie verhindern, dass andere Kopien fibodie Ergebnisse überschreiben, bevor wir sie zurückgeben können.
• Das funcname() {Syntaxdeklarationsformular wird verwendet, da function funcname {es sich um einen ksh-ismus handelt. In ksh ändert dieses Format jedoch das Verhalten des Codes innerhalb des Blocks. Bash hält diese Absicht nicht ein. Folglich funcname() {überrascht die Verwendung von POSIX-kompatiblen Personen mit ksh-Hintergrund weniger und verbessert die Kompatibilität Ihres Codes mit anderen POSIX-Shells. sehenhttps://wiki.bash-hackers.org/scripting/obsolete (Beachten Sie, dass die Syntax der Funktionsdeklaration an mehreren Stellen erwähnt wird.)