Golang sleep thread instead of busy waiting

Question

I am writing a Go implementation of Leslie Lamport's Bakery algorithm, which has busy-spin-waits to handle some maximum number of threads.

---

I am writing a go function that should not proceed unless a special condition is met. My code so far looks like this:

func acquireLock() {
    ...
    for specialConditionIsFalse {
    }
    ...
}

Is there a more efficient way to stop proceeding with this thread?

Answer 1

It's worth noting several points here:

1. goroutines are not threads. There is no "goroutine number" and there is no fixed upper limit on the number of goroutines in the system.¹ The Bakery algorithm can be modified to deal with dynamically created threads (use a list or map, as in the Java example on the Wikipedia page) but there is a strong requirement of a unique ID per "thread", which makes this not a good idea in general for Go. (You can work around that in turn using a package that implements thread-like behavior, including thread IDs.)

2. As the Wikipedia page notes:

   Lamport's bakery algorithm assumes a sequential consistency memory model. Few, if any, languages or multi-core processors implement such a memory model. Therefore correct implementation of the algorithm typically requires inserting fences to inhibit reordering.

   This means you will need to use the sync/atomic package, which kind of defeats the purpose of writing your own locking.

With those two enormous caveats, you can either call runtime.Gosched() where you would call a POSIX style yield() function, or you can use a channel to signal that someone has "left the bakery" and hence it is the next user's turn. But channels themselves do all the mutual exclusion you need. A simplified Go-specific non-Lamport bakery algorithm is trivial (but all of the below is untested):

var takeANumber chan int64
var currentlyServing int64

init() {
    takeANumber = make(chan int64)
    go giveNumbers()
}

// giveNumbers hands out ever-increasing ticket numbers
func giveNumbers() {
    for int64 i := 0;; i++ {
        takeANumber <- i
    }
}

// WaitTurn gets a ticket, then waits until it is our turn.  You can
// call this "Lock" if you like.
func WaitTurn() int64 {
    ticket := <-takeANumber
    for atomic.LoadInt64(&currentlyServing) < ticket {
        runtime.Gosched()
    }
    return ticket
}

// ExitBakery relinquishes our ticket, allowing the next user to proceed.
func ExitBakery(ticket int64) {
    atomic.StoreInt64(&currentlyServing, ticket + 1)
}

Modifying this to use two channels, so that the WaitTurn function is more efficient, is left as an exercise. (Of course there's no reason to use any of this code in the first place, except as an exercise.)

---

¹You can set a runtime limit but the system will spawn extra goroutines anyway if you call any blocking system calls. The set of system calls that are blocking, and when they get called, is up to the runtime, so you have no real control over this, at least not without writing platform-specific code.