Peterson算法及其应对死锁问题

从现在开始，努力学习吧！本文《Peterson算法及其应对死锁问题》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

我正在尝试一些相互执行算法。我已经实现了彼得森算法。它打印正确的计数器值，但有时看起来就像发生了某种死锁，无限期地停止执行。这应该是不可能的，因为该算法没有死锁。

ps：这是否与解决“良性”数据竞争危险时经常提到的编译器优化问题有关？如果是这种情况那么如何禁用此类优化？

pps：当自动存储/加载受害者字段时，问题似乎消失了，这使得编译器的优化更加可疑

package main

import (
    "fmt"
    "sync"
)

type mutex struct {
    flag   [2]bool
    victim int
}

func (m *mutex) lock(id int) {
    m.flag[id] = true // I'm interested
    m.victim = id     // you can go before me if you want
    for m.flag[1-id] && m.victim == id {
        // while the other thread is inside the CS
        // and the victime was me (I expressed my interest after the other one already did)
    }
}

func (m *mutex) unlock(id int) {
    m.flag[id] = false // I'm not intersted anymore
}

func main() {
    var wg sync.WaitGroup
    var mu mutex
    var cpt, n = 0, 100000

    for i := 0; i < 2; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()

            for j := 0; j < n; j++ {
                mu.lock(id)
                cpt = cpt + 1
                mu.unlock(id)
            }
        }(i)
    }

    wg.Wait()
    fmt.Println(cpt)
}

正确答案

不存在“良性”数据竞争。您的程序存在数据争用，并且行为未定义。

问题的核心是 mutex 实现。一个 Goroutine 对共享对象所做的修改不一定可以从其他 Goroutine 中观察到，直到这些 Goroutine 使用同步原语之一进行通信。您正在从多个 goroutine 写入 mutex.victim，并且不会被观察到。您还在阅读其他 goroutine 编写的 mutex.flag 元素，但不一定会被看到。也就是说，在某些情况下，即使其他 Goroutine 更改了变量，for 循环也不会终止。

由于互斥体实现已损坏，对 cpt 的更新也不一定是正确的。

要正确实现此功能，您需要 sync/atomic 包。

参见 Go 内存模型：https://go.dev/ref/mem

对于 Peterson 的算法（Dekker 也是如此），您需要确保您的代码是顺序一致的。在 Go 中，你可以使用原子来做到这一点。这将防止编译器和硬件把事情搞砸。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于Golang的相关知识，也可关注golang学习网公众号。