Bash - limitar subcapas en recursividad

Question

Decidí probar las recursiones en bash en mi servidor de producción.

¡No ejecute este código en una máquina de producción!

#!/usr/bin/bash

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

fibo 100

Sospeché que sería lento, sin embargo, no esperaba que ejecutara decenas de trabajos paralelos. Estaba pensando que debido a que el servidor es multinúcleo, podría matar el proceso.

Desafortunadamente, el servidor se congeló y la empresa de alojamiento lo reinició.

¿Hay alguna forma de limitar los trabajos paralelos en bash?

¿Es posible configurar el PID del proceso principal en un temporizador y detener todos los trabajos secundarios?

Por supuesto, solo pido con fines académicos.

Editar

La versión Tail recursión funciona a las mil maravillas:

#!/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

Punto de referencia:

time ./fibotr.sh 100

3736710778780434371

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

Answer 1

En cuanto a los métodos de prevención, consulte nuestro sitio hermano Unix & Linux Stack Exchange . Entre las preguntas de actualidad que tienen en su lugar está Ejecutar una bomba de horquilla de forma segura .

Como una implementación de su algoritmo original que no bifurca ninguna subcapa en absoluto y, por lo tanto, no puede convertirse en una bomba de bifurcación incluso cuando se pasan números arbitrariamente grandes:

#!/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"

¿Por qué está escrito así?

• El cambio más importante fue eliminarlo $( ), pero esto requiere que ya no se pase la salida al padre en la salida estándar. Por lo tanto, utilizar asignaciones indirectas para este propósito.
• El uso de nombres de variables con espacios de nombres (¡incluso para los locales!) Evita conflictos al devolver un resultado por nombre: si el usuario elige escribir un resultado en un nombre de variable que coincida con cualquiera de nuestros locales, su valor se escribiría en el local, no la variable global en la que quieren colocar su resultado.
• locResAy locResBse utilizan porque no estamos se bifurcan y no podemos hacer resAy resBlocal; impiden que otras copias de fibosobrescriban los resultados antes de que podamos devolverlos.
• La funcname() {forma de declaración de sintaxis se usa porque function funcname {es un ksh-ismo. En ksh, sin embargo, este formato cambia el comportamiento del código dentro del bloque; bash no respeta esa intención. En consecuencia, el uso de la compatibilidad con POSIX funcname() {tiene menos sorpresas para las personas que tienen experiencia en ksh y mejora la compatibilidad de su código con otros shells POSIX; verhttps://wiki.bash-hackers.org/scripting/obsolete (tenga en cuenta que la sintaxis de declaración de funciones se menciona en más de un lugar).