Как предотвратить тупик в рекурсивной функции? - PullRequest
Новая
       39

Как предотвратить тупик в рекурсивной функции?

1 голос
/ 01 ноября 2019

У меня есть рекурсивная функция, которая блокирует и изменяет ее внутреннее состояние, однако это вызывает тупик. Как я могу реализовать такую ​​рекурсивную функцию без взаимоблокировки? 

package main

import (
    "fmt"
    "sync"
)

type runner struct {
    sync.Mutex
    value int
}

func (r *runner) decrement() {
    r.Lock()
    defer r.Unlock()
    if r.value == 0 {
        return
    }
    r.value--
    r.decrement()
}

func main() {
    r := runner{
        value: 10,
    }

    r.decrement()

    fmt.Printf("r: %v\n", r.value)
}

Ожидается, что выполнение приведенного выше кода выдаст r: 0, но фактически получит взаимоблокировку: 

fatal error: all goroutines are asleep - deadlock!

1 Ответ

1 голос
/ 01 ноября 2019

Типичным решением проблемы такого рода является возвращающийся мьютекс . Однако у Расса Кокса из команды Go есть хороший аргумент о том, почему реентерабельные мьютексы - плохая идея .

В этом случае вы не хотите откладывать разблокировку. Вместо этого вы должны заблокировать и разблокировать минимальные необходимые разделы. 

func (r *runner) decrement() {
    r.Lock()
    if r.value == 0 {
        r.Unlock()
        return
    }
    r.value--
    r.Unlock()
    r.decrement()
}

Это решает две проблемы: во-первых, (незначительно) улучшает способность вашего кода работать одновременно, не принимая блокировки для вещей, которые не 'Во-вторых, блокировка не требуется, и, во-вторых, она гарантирует, что при повторном вводе decrement() не будет заблокированной блокировки, которая приведет к тупику.

...