Peterson's algorithm and deadlock

user_14976221 0
Viewed 82

I am trying to experiment with some mutual execution algorithms. I have implemented the Peterson's algorithm. It prints the correct counter value but sometimes it seems just like some kind of a deadlock had occurred which stalls the execution indefinitely. This should not be possible since this algorithm is deadlock free.

PS: Is this related to problems with compiler optimizations often mentioned when addressing the danger of "benign" data races? If this is the case then how to disable such optimizations?

PPS: When atomically storing/loading the victim field, the problem seems to disappear which makes the compiler's optimizations more suspicious

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)
}
go deadlock multithreading multiprocessing
2 Answers

There is no "benign" data race. Your program has data race, and the behavior is undefined.

At the core of the problem is the mutex implementation. Modifications made to a shared object from one goroutine are not necessarily observable from others until those goroutines communicate using one of the synchronization primitives. You are writing to mutex.victim from multiple goroutines, and won't be observed. You are also reading the mutex.flag elements written by other goroutines, and won't necessarily be seen. That is, there may be cases where the for-loop won't terminate even if the other goroutine changes the variables.

And since the mutex implementation is broken, the updates to cpt will not necessarily be correct either.

To implement this correctly, you need the sync/atomic package.

See the Go Memory Model: https://go.dev/ref/mem

user_119239990

For Peterson's algorithm (same goes for Dekker), you need to ensure that your code is sequential consistent. In Go you can do that using atomics. This will prevent the compiler and the hardware to mess things up.

user_22457070
Related