Bash - limitar subshells na recursão

Question

Decidi testar recursões no bash no meu servidor de produção.

Não execute este código em uma máquina de produção!

#!/usr/bin/bash

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

fibo 100

Suspeitei que será lento, porém, não esperava que executasse dezenas de jobs paralelos. Eu estava pensando que, como o servidor é multicore, eu seria capaz de matar o processo.

Infelizmente, o servidor travou e foi reiniciado pela empresa de hospedagem.

Existe uma maneira de limitar os trabalhos paralelos no bash?

É possível definir o PID do processo principal em um cronômetro e interromper todos os trabalhos filhos?

Claro, estou pedindo apenas para fins acadêmicos.

Editar

A versão de recursão da cauda funciona perfeitamente:

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

Referência:

time ./fibotr.sh 100

3736710778780434371

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

Answer 1

Quanto aos métodos de prevenção, consulte nosso site irmão Unix & Linux Stack Exchange . Entre as questões atuais que eles colocam está: Executar uma bomba fork com segurança .

Como uma implementação de seu algoritmo original que não bifurca nenhum subshells e, portanto, não pode se transformar em uma bomba de bifurcação, mesmo quando números arbitrariamente grandes são transmitidos:

#!/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 que isso está escrito dessa maneira?

• A mudança mais importante foi eliminar $( ), mas isso não requer mais passar a saída para o pai em stdout. Portanto, usando atribuições indiretas para o efeito.
• O uso de nomes de variáveis ​​com espaço de nomes (mesmo para locais!) Evita conflitos ao retornar um resultado por nome: Se o usuário escolher escrever um resultado para um nome de variável que corresponda a qualquer um de nossos locais, seu valor será escrito no local, não a variável global na qual desejam colocar o resultado.
• locResAe locResBsão usados porque não estamos bifurcação e não pode fazer resAe resBlocal; eles evitam que outras cópias de fibosubstituam os resultados antes que possamos devolvê-los.
• O funcname() {formulário de declaração de sintaxe é usado porque function funcname {é um ksh-ismo. No ksh, entretanto, esse formato muda o comportamento do código dentro do bloco; O bash não honra essa intenção. Conseqüentemente, usar a compatibilidade com POSIX funcname() {tem menos surpresas para as pessoas que têm experiência com ksh e melhora a compatibilidade do seu código com outros shells POSIX; Vejohttps://wiki.bash-hackers.org/scripting/obsolete (observe que a sintaxe de declaração de função é mencionada em mais de um lugar).