Illustrating two benign race conditions in Go (stop flag and ABQL)

main.go

// illustrating benign data races in:
//
// a. one-time flag setting where missing the flag being set is benign (we simply
// loop one more time, but in the logic of the program, that's fine)
//
// b. implementing an array-based queueing lock in which lockers wait on the
// value at their array position to be set to 1

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

// Create a (circular) Array-Based Queueing Lock with queue size 10
// (note: not safe from wrap-around overflow - if while already locked, we enqueue
// QUEUE_SZ lockers, the last one will instantly access the lock since its
// array slot will have '1' for the currently-held locker which was already on
// that array index (but this is good enough for our demonstration since
// we set N_LOCKERS to be QUEUE_SZ - 1, avoiding this from ever occurring)
const QUEUE_SZ = 10
const N_LOCKERS = QUEUE_SZ - 1

type ArrayBasedQueueLock struct {
	// the queue `arr` looks like this at any given time:
	//
	// [ 0 0 0 0 0 1 0 0 0 ]
	//
	// The above represents the state where index 6 is set to 1, meaning
	// ticket 6 has the lock. On Unlock, ticket 6 is provided by the calling
	// goroutine to allow us to set index 6 to 0 and then set index 7 to 1.
	// Goroutines wait for the lock by repeatedly checking their index, which
	// they receive upon atomic increment of `currentTicket` (it wraps around
	// with modulo)
	arr           [QUEUE_SZ]uint32
	currentTicket uint32
}

func (l *ArrayBasedQueueLock) Lock() uint32 {
	// note: we increment `ticket` atomically, so two instances will never
	// wait on the same array index (again, assuming no wrap-around overflow)
	ticket := atomic.AddUint32(&l.currentTicket, 1) - 1
	// Here's where one benign race condition occurs. We check the value of
	// the uint32 in the array at the index we have. But since we're just doing
	// a read, and the value is either 0 or 1, even reading a partial value
	// will at worst cause us to spin one more time. And since we can't
	// call Unlock to set our array index to 0 and the next one to 1 until
	// we've acquired the lock, no other goroutine can ever compete with us
	// to get the queue head.
	for l.arr[ticket%QUEUE_SZ] != 1 {
		time.Sleep(time.Microsecond)
	}
	return ticket
}

func (l *ArrayBasedQueueLock) Unlock(ticket uint32) {
	// set our index to 0 and the next one (wrapped around if need be) to 1
	l.arr[ticket%QUEUE_SZ] = 0
	l.arr[(ticket+1)%QUEUE_SZ] = 1
}

func NewABQL() *ArrayBasedQueueLock {
	l := ArrayBasedQueueLock{}
	// set the first array index to 1 so the first locker can acquire
	l.arr[0] = 1
	return &l
}

// locker is run as a goroutine. Locks, sleeps, Unlocks, until stopFlag is
// set, and tells a waitgroup when its done
func locker(l *ArrayBasedQueueLock, stopFlag *uint32, wg *sync.WaitGroup) {
	for *stopFlag == 0 {
		ticket := l.Lock()
		time.Sleep(8 * time.Microsecond)
		l.Unlock(ticket)
	}
	wg.Done()
}

func main() {
	// stopflag, waitgroup, and lock to pass to goroutines running locker()
	var stopFlag uint32
	var wg sync.WaitGroup
	var l = NewABQL()

	// spawn N_LOCKERS goroutines to run locker()
	for i := 0; i < N_LOCKERS; i++ {
		wg.Add(1)
		go locker(l, &stopFlag, &wg)
	}

	// sleep 3 seconds, set the stop flag, and wait for all lockers to end
	time.Sleep(3 * time.Second)
	stopFlag = 1
	wg.Wait()
	fmt.Println("Done")
}