Could someone explain the term "invariants" in mutex locking?

Question

I have read Addison-Wesley's book, The Go Programming Language several times but still I have some trouble in chapter 9, page 265, which talks about sync.Mutex.

It says:

There is a good reason Go's mutexes are not re-entrant. The purpose of a mutex is to ensure that certain invariants of the shared variables are maintained at critical points during program execution. One of the invariants is "no goroutine is accessing the shared variables", but there may be additional invariants specific to the data structures that the mutex guards. When a goroutine acquires a mutex lock, it may assume that the invirants hold. While it holds the lock, it may update the shared variables so that the invariants are temporarily violated. However, when it releases the lock, it must guarantee that the order has been restored and the invariants hold once again. Although a re-entrant mutex would ensure that no other goroutines are accessing the shared variables, it cannot protect the additional invariants of those variables.

I'm not a native English speaker, and I'm unsure about the meaning of term invariants. I just take it as something that won't change. But still, I cannot fully understand the point of this paragraph. Could anybody expalin to me? If there are other invariants besides no goroutine is accessing the variable, what are these?

Answer 1

I'm not a native English speaker, and I'm unsure about the meaning of term invariants. I just take it as something that won't change.

See marco.m's comment that links to What is an invariant? for more about invariants.

The reason we may need a mutex in Go—or indeed, in any language with concurrency—is that programs that are trying to maintain some invariant may deliberately allow the invariant to be violated briefly. In a programming language that has no concurrency (and therefore isn't Go), we might have code like this:

// invariants: bestThing is the best thing (according to goodness ranking) in
// allThings; allThings[0] is always the initial badThing.
var bestThing Thing = badThing
var allThings []Thing = { badThing }

func addThing(t Thing) {
    allThings = append(allThings, t)
    // now, if t is better than the best thing so far, set bestThing = t
    if goodness(t) > goodness(bestThing) {
        bestThing = t
    }
}

This is terrible code for numerous reasons (global variables for instance), but, as long as our language has no concurrency, we note that addThing maintains the invariant by adding something to allThings and updating bestThing if needed.

If we add concurrency to our language, though, addThing itself can break. Suppose that in one thread / goroutine / whatever, we call addThing with a one pretty-good thing, and in some other thread, we call addThing with another, different, pretty-good thing. One of these threads or goroutines or whatever we call these parallel operators begins modifying both the allThings table and the bestThing variable. The other one does the same. We might:

• lose one of the things, by storing in allThings the wrong value; and/or
• rate the second-best thing as the best thing

because the invariant itself is destroyed at the beginning (with allThings = append(allThings, t), which writes on one global variable, and only restored by the time the function returns (having checked the goodness and updated the best-thing global variable). We can—clumsily—repair this problem with a mutex:

func addThing(t Thing) {
    someLock.Lock()
    defer someLock.Unlock()
    allThings = append(allThings, t)
    // now, if t is better than the best thing so far, set bestThing = t
    if goodness(t) > goodness(bestThing) {
        bestThing = t
    }
}

The mutex ensures that, if two different goroutines (or whatever they are) enter addThing, one of them stops and waits for the other to return before proceeding. The one that continues can break and then restore the invariant, and then the other can break and then restore the invariant.

(This clumsy repair is still not very good: for one thing, we now need to wrap each use of bestThing with a similar mutex, so that we don't read it while the routine is writing it. But the mutex gives us a tool with which we can deal with the issue. Using global variables like this, in goroutines in real Go programs, is "communicating by sharing", which Go discourages in favor of "sharing by communicating" over channels. Of course the data structures would need to be reworked to do that, getting rid of these simple global variables for instance. That's a good thing on its own, too!)

Answer 2

Book offers wery fancy explanation of mutexes, but mutexes can be explaned withou any fancy words. When you call Lock() on mutex twice, gorotine will get blocked infinitly. Howewer if you call Unlock between calls, it will continue on. This means that if two goroutines call mutex lock at the same time. Lock() is called twice in a row and one routine will get blocked while other can execute. When executing rotine finished reading or mutating shared state, it have to call Unlock() witch gives blocked routine green light to access shared state. We surround the critical code with Lock() Unlock() so there is no chance code between thes calls will get executed at the same time on multiple gorotines. Lets look at some code that shows valid and invalid use of mutex.

package main

import (
    "sync"
    "time"
)

func main() {
    /// valid code
    mut := sync.Mutex{} // mutex has to e used on both ends
    sharedState := 0
    go func() {
        //mut := mut // this is invalid operation, it creates copy of a lock, so locking one does not affect another
        for i := 0; i < 100000; i++ {
            mut.Lock()
            // if lock is not present one routine can modify data while other is reading, in that moment
            // datarace happens
            sharedState = sharedState + 1
            mut.Unlock()
        }
    }()

    // not locking on either side is also invalid and panic will happen
    for i := 0; i < 100000; i++ {
        mut.Lock()
        sharedState = sharedState + 1
        mut.Unlock()
    }

    time.Sleep(time.Second) // this is just simplification, to make sure all routines finished we usually use wait group or channels
    if sharedState != 200000 {
        panic("this will never happen")
    }

    /// invalid code

    sharedState = 0
    go func() {
        for i := 0; i < 100000; i++ {
            // lock is not present on both sides, locking just one side has no effect
            sharedState = sharedState + 1
        }
    }()

    // not locking on either side is also invalid and panic will happen
    for i := 0; i < 100000; i++ {
        mut.Lock()
        sharedState = sharedState + 1
        mut.Unlock()
    }

    time.Sleep(time.Second)
    if sharedState == 200000 {
        panic("there is very little chance this panic will happen, newer assume it will")
    }
}

Locking can ensure code is not executed at the same time, it does not make operation betwen mutex calls atomic so locking just writer is not enough. Though multiple readers can coexist sthat why sync.RWMutex exist