游10:在并发中迷失

Question

我一直在尝试做所有的围棋教程，我被困在网络爬虫练习。

我以为我完成了它，但是输出不一致，而且我没有足够的并发经验来找出原因。

下面是我的代码：

package main

import (
    "fmt"
    "sync"
)

type Fetcher interface {
    // Fetch returns the body of URL and
    // a slice of URLs found on that page.
    Fetch(url string) (body string, urls []string, err error)
}
var cache = struct {
    fetched map[string]bool
    sync.Mutex
}{fetched: make(map[string]bool)}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher, c chan []string, quit chan int) {
    if depth <= 0 {
        return
    }
    go safeVisit(url, c, quit, fetcher)
    for {
        select {
        case <- quit:
            return
        case u:= <-c:
            for _, v:= range u {
                go Crawl(v, depth -1, fetcher, c, quit)
            }
        }
    }
}
func main() {
    c := make(chan []string)
    quit := make(chan int)
    Crawl("http://golang.org/", 4, fetcher, c, quit)
}

func safeVisit(url string, c chan []string, quit chan int, fetcher Fetcher) {
    cache.Lock()
    defer cache.Unlock()
    if _, ok := cache.fetched[url] ; ok {
        quit <- 0
        return
    }
    body, urls, err := fetcher.Fetch(url)
    cache.fetched[url] = true
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("Visited : %s, %q \n", url, body)
    c <- urls

}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
    body string
    urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
    if res, ok := f[url]; ok {
        return res.body, res.urls, nil
    }
    return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
    "http://golang.org/": &fakeResult{
        "The Go Programming Language",
        []string{
            "http://golang.org/pkg/",
            "http://golang.org/cmd/",
        },
    },
    "http://golang.org/pkg/": &fakeResult{
        "Packages",
        []string{
            "http://golang.org/",
            "http://golang.org/cmd/",
            "http://golang.org/pkg/fmt/",
            "http://golang.org/pkg/os/",
        },
    },
    "http://golang.org/pkg/fmt/": &fakeResult{
        "Package fmt",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
    "http://golang.org/pkg/os/": &fakeResult{
        "Package os",
        []string{
            "http://golang.org/",
            "http://golang.org/pkg/",
        },
    },
}

这是一些样本输出

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os" 
**Visited : http://golang.org/pkg/fmt/, "Package fmt"** 

Process finished with exit code 0

与第一个包不同的是，最后一个包丢失了(上面的星号是故意的)

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os"

最后，即使在某些情况下出现了死锁：

Visited : http://golang.org/, "The Go Programming Language" 
not found: http://golang.org/cmd/
Visited : http://golang.org/pkg/, "Packages" 
Visited : http://golang.org/pkg/os/, "Package os" 
Visited : http://golang.org/pkg/fmt/, "Package fmt" 
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x4, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
main.main()
    /home/kostas/development/challenges/go/helloWorld.go:39 +0xab

goroutine 23 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 24 [select]:
main.Crawl(0x4c09f9, 0x16, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 5 [select]:
main.Crawl(0x4bfdf9, 0x12, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

goroutine 6 [select]:
main.Crawl(0x4c0a0f, 0x16, 0x3, 0x524220, 0xc420088120, 0xc420092000, 0xc420092060)
    /home/kostas/development/challenges/go/helloWorld.go:26 +0x201
created by main.Crawl
    /home/kostas/development/challenges/go/helloWorld.go:31 +0x123

我猜想它与并发性和递归有关。我在github中看到了使用WaitGroups等的其他解决方案，但目前为止还没有使用它，所以我宁愿不使用它。

更新

我弄清楚了到底发生了什么，并着手解决了这个问题。基本上，有时select语句被困在一个没完没了的循环中，因为通道退出和c不总是按照预期的顺序执行。我添加了一个默认的大小写，打印(“什么都不做”)，程序有时会永远循环，有时会以正确的方式执行。我的退出条件不对

Answer 1

我认为这件事很清楚。你的频道乱七八糟。来自同一个通道的多个大猩猩正在接收，而戈朗只是随机挑选一个。

当您通过quit发送零时，您永远不知道哪个戈鲁丁退出了:它是由go sheduler随机选择的。在从quit接收之前，有可能是从c接收到新生成的Crawl (即使这两个通道都准备就绪)。

由于这一点，depth是一个混乱的，它使safeVisit数被称为不稳定，导致quit发出不同的(随机)信号。有时，仅仅放弃所有生成的goroutines是不够的，这是一个死锁。

编辑：

首先，你应该明白你的任务是什么。Crawl函数接受一个url、一个dep和一个取取器，它：

1. 把网址拿来
2. 打印取下来的身体
3. 使用Crawl从获取的url生成新的dep-1队列

虽然导游要求您在并行线中“获取”url，但是很明显，步骤2和步骤3必须在步骤1之后进行，这意味着单个爬行等待获取是正常的。这意味着，不需要一个新的猩猩叫Fetch。

在步骤3中，每个新的Crawl调用都不需要等待前面的调用来完成，因此这些调用应该是并行的。

通过这些分析，可以得出以下代码：

func Crawl(url string, depth int, fetcher Fetcher) {
    // TODO: Fetch URLs in parallel.
    // TODO: Don't fetch the same URL twice.
    // This implementation doesn't do either:
    if depth <= 0 {
        return
    }
    body, urls, err := fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        go Crawl(u, depth-1, fetcher)
    }
    return
}

还有一个问题:处理访问的url。您已经很好地完成了它，而不是发送一个quit，只需使它成为func(string) bool并直接调用它：if Visited(Url) { return }和它就完成了。

旁注:这次巡回演出实在不善于教人合意。你可能想看看go博客文章，比如戈朗同意的模式，或者通过交流来分享记忆。