围棋检测器错误

Question

这是我的并发缓存代码:

package cache

import (
    "sync"
)

// Func represents a memoizable function, operating on a string key, to use with a Cache
type Func func(key string) (interface{}, error)

// FuncResult stores the value of a Func call
type FuncResult struct {
    val interface{}
    err error
}

// Cache is a cache that memoizes results of an expensive computation
//
// It has a traditional implementation using mutexes.
type Cache struct {
    // guards done
    mu   sync.RWMutex
    done map[string]chan bool
    memo map[string]*FuncResult
    f    Func
}

// New creates a new Cache and returns its pointer
func New(f Func) *Cache {
    return &Cache{
        memo: make(map[string]*FuncResult),
        done: make(map[string]chan bool),
        f:    f,
    }
}

// Get a string key if it exists, otherwise computes the value and caches it.
//
// Returns the value and whether or not the key existed.
func (c *Cache) Get(key string) (*FuncResult, bool) {
    c.mu.RLock()
    _, ok := c.done[key]
    c.mu.RUnlock()
    if ok {
        return c.get(key), true
    }

    c.mu.Lock()
    _, ok = c.done[key]
    if ok {
        c.mu.Unlock()
    } else {
        c.done[key] = make(chan bool)
        c.mu.Unlock()

        v, err := c.f(key)
        c.memo[key] = &FuncResult{v, err}

        close(c.done[key])
    }
    return c.get(key), ok
}

// get returns the value of key, blocking on an existing computation
func (c *Cache) get(key string) *FuncResult {
    <-c.done[key]
    fresult, _ := c.memo[key]
    return fresult
}

当我用竞争检测器运行这个程序时，我没有得到任何错误:

package main

import (
    "fmt"
    "log"
    "sync"
    "time"

    "github.com/yangmillstheory/go-cache/cache"
)

var f = func(key string) (interface{}, error) {
    log.Printf("Computing value for key %s\n", key)
    time.Sleep(1000 * time.Millisecond)
    return fmt.Sprintf("value for %s", key), nil
}

func main() {
    var wg sync.WaitGroup

    c := cache.New(f)
    n := 10
    k := "key1"

    start := time.Now()
    for i := 0; i < n; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            c.Get(k)
        }()
    }

    wg.Wait()
    log.Printf("Elapsed: %s\n", time.Since(start))
}

但是，当我在循环体内启动两个 不同的 goroutine 时，每个 goroutine 都获得不同的键，我得到一个错误:

解决这个问题的方法是添加另一个互斥锁c.nu来保护memo，但是它会让程序变慢一点，也更复杂

func (c *Cache) Get(key string) (*FuncResult, bool) {
    c.mu.RLock()
    _, ok := c.done[key]
    c.mu.RUnlock()
    if ok {
        return c.get(key), true
    }

    c.mu.Lock()
    _, ok = c.done[key]
    if ok {
        c.mu.Unlock()
    } else {
        c.done[key] = make(chan bool)
        c.mu.Unlock()

        v, err := c.f(key)
        c.nu.Lock()
        c.memo[key] = &FuncResult{v, err}
        c.nu.Unlock()

        close(c.done[key])
    }
    return c.get(key), ok
}

// get returns the value of key, blocking on an existing computation
func (c *Cache) get(key string) *FuncResult {
    <-c.done[key]
    c.nu.RLock()
    fresult, _ := c.memo[key]
    c.nu.RUnlock()
    return fresult
}

这里真的有竞争条件需要担心吗？如果不同的 goroutines 同时访问同一数据结构中的不同键，只要同步发生在对给定键的访问中，这似乎不是问题？

换句话说，您是必须跨所有 key 同步，还是只跨同一个 key 同步？并发备忘录的用例似乎表明后者就足够了？

Answer 1

map 需要同步，尤其是你can not read it while writing to it ，无论它是相同的还是不同的键，因此您需要锁定菜单映射。