Standard library · Time and concurrency

sync

Mutexes, condition variables, wait groups, read-write locks, semaphores and once, for coordinating threads.

import sync

When several threads change the same variable they have to take turns, or the result depends on the order the threads happen to run in. The sync package has the classic tools for taking turns, built on the operating system's threads library:

  • A mutex: each thread takes the lock before touching the data and releases it afterwards. An RWMutex lets many readers in at once.
  • A condition variable: a thread sleeps until another one says that something has changed.
  • A wait group: call Add before starting a piece of work, Done at its end, and Wait until the count is back to zero.
  • A semaphore caps how many threads are inside a part at once, and a once runs setup a single time.

Threads themselves come from spawn and the thread package. For a single shared number, atomic is cheaper than a lock; to hand values from one thread to another, chan does the locking and waiting for you; to cancel work, ctx.

The things people get wrong:

  • Using a value that was never created. Every tool here is made with a New... function; a zero sync.Mutex {} has no lock inside and crashes on Lock. Globals are declared with {} and created at the top of main.
  • Locking twice. A mutex is not reentrant: a thread that calls Lock on a mutex it already holds waits forever. Do holds a lock while its function runs, so calling Do on the same Once from inside it hangs too.
  • Waiting on a condition without a loop. WaitCond can return before the condition is true; always wait inside until not condition:.
  • Forgetting Destroy.... Each tool holds operating system memory; destroy it after the last thread that uses it has been joined.

Keep data consistent with a mutex

A lock is not only for counters. Anything that has to stay true across several variables, such as "the money in all accounts adds up to the same total", needs every change to happen while the lock is held. Take the lock at the top of the function and put Unlock in a defer, so it is released on every return path, including the early ret.

sync-guide-transfer.salam
import sync

mut accounts := Vector {} as Vector<int>
mut lock := sync.Mutex {}
mut group := sync.WaitGroup {}

func transfer(from: int, dest: int, amount: int): bool:
    sync.Lock(lock)
    defer sync.Unlock(lock)
    if accounts.Get(from) < amount:
        ret false
    end
    accounts.Set(from, accounts.Get(from) - amount)
    accounts.Set(dest, accounts.Get(dest) + amount)
    ret true
end

func clerk():
    repeat 1000 in i:
        transfer(i % 3, (i + 1) % 3, 7)
    end
    sync.Done(group)
end

func main:
    lock = sync.NewMutex()
    group = sync.NewWaitGroup()
    accounts.Push(500)
    accounts.Push(300)
    accounts.Push(200)
    sync.Add(group, 4)
    mut workers := Vector {} as Vector<i64>
    defer workers.Free()
    repeat 4:
        workers.Push(spawn(clerk))
    end
    sync.Wait(group)
    each t in workers:
        join(t)
    end
    total := accounts.Get(0) + accounts.Get(1) + accounts.Get(2)
    println "money in the bank:", total
    println "a transfer that is too big:", transfer(0, 1, 100000)
    accounts.Free()
    sync.DestroyWaitGroup(group)
    sync.Destroy(lock)
end
Outputmoney in the bank: 1000 a transfer that is too big: false

Four threads move money around 4000 times and the total is still 1000. Without the lock two threads could read the same balance at once and one of the changes would be lost.

Many readers, few writers

When data is read far more often than it is changed, such as settings or a cache, a plain mutex makes readers wait for each other for no reason. An RWMutex lets any number of readers in together with RLock, and gives a writer the data to itself with WLock.

sync-guide-settings.salam
import sync

mut settings := HashMap {} as HashMap<str, int>
mut guard := sync.RWMutex {}
mut reads := 0
mut count lock := sync.Mutex {}

func reader():
    repeat 200:
        sync.RLock(guard)
        limit := settings.Get("limit")
        sync.RUnlock(guard)
        if limit > 0:
            sync.Lock(count lock)
            reads++
            sync.Unlock(count lock)
        end
    end
end

func writer():
    repeat 1 to 5 in v:
        sync.WLock(guard)
        settings.Put("limit", v * 10)
        sync.WUnlock(guard)
    end
end

func main:
    guard = sync.NewRWMutex()
    count lock = sync.NewMutex()
    settings.Put("limit", 5)
    a := spawn(reader)
    b := spawn(reader)
    w := spawn(writer)
    join(a)
    join(b)
    join(w)
    println "reads:", reads
    println "final limit:", settings.Get("limit")
    settings.Free()
    sync.Destroy(count lock)
    sync.DestroyRWMutex(guard)
end
Outputreads: 400 final limit: 50

A reader must never write while holding only the read lock. If a reader may need to change the data, take the write lock instead.

Limit how many run at once

A Semaphore holds a number of permits. Acquire takes one and waits when none are left, Release gives it back. With two permits, at most two threads are inside the guarded part at any moment, which is how you cap parallel downloads or database connections.

sync-guide-limit.salam
import sync

mut slots := sync.Semaphore {}
mut lock := sync.Mutex {}
mut running := 0
mut busiest := 0
mut finished := 0

func download():
    sync.Acquire(slots)
    sync.Lock(lock)
    running++
    if running > busiest:
        busiest = running
    end
    sync.Unlock(lock)
    sync.SleepMs(20)
    sync.Lock(lock)
    running--
    finished++
    sync.Unlock(lock)
    sync.Release(slots)
end

func main:
    slots = sync.NewSemaphore(2)
    lock = sync.NewMutex()
    mut jobs := Vector {} as Vector<i64>
    defer jobs.Free()
    repeat 6:
        jobs.Push(spawn(download))
    end
    each t in jobs:
        join(t)
    end
    println "downloads finished:", finished
    println "never more than two at once:", busiest <= 2
    sync.Destroy(lock)
    sync.DestroySemaphore(slots)
end
Outputdownloads finished: 6 never more than two at once: true

TryAcquire takes a permit only if one is free and returns false at once otherwise, for work that should be skipped rather than queued.

Set something up exactly once

Some setup is expensive and should happen only when it is first needed, but several threads may need it at the same moment. Do runs its function the first time it is called on a Once; every other caller waits until that run has finished and then goes on without running it again.

sync-guide-once.salam
import sync

mut setup := sync.Once {}
mut table := Vector {} as Vector<int>
mut builds := 0

func build table():
    builds++
    repeat 10 in i:
        table.Push(i * i)
    end
end

func square(n: int): int:
    sync.Do(setup, (): build table() end)
    ret table.Get(n)
end

func worker():
    _ := square(3)
end

func main:
    setup = sync.NewOnce()
    a := spawn(worker)
    b := spawn(worker)
    c := spawn(worker)
    join(a)
    join(b)
    join(c)
    println "square of 7:", square(7)
    println "table built", builds, "time"
    table.Free()
    sync.DestroyOnce(setup)
end
Outputsquare of 7: 49 table built 1 time

A work queue: wait for work, wait for the end

A condition variable is how a thread sleeps until there is something to do instead of checking in a busy loop. The workers below wait on has_work while the queue is empty, and the main thread calls Signal after each push to wake one of them. A wait group counts the jobs: Add before each push, Done when it is processed, and Wait returns when all are done. To stop the workers, set a flag and Broadcast, which wakes all of them.

sync-guide-queue.salam
import sync

mut lock := sync.Mutex {}
mut has_work := sync.CondVar {}
mut jobs_done := sync.WaitGroup {}
mut queue := Vector {} as Vector<int>
mut taken := 0
mut closed := false
mut total := 0

func worker():
    sync.Lock(lock)
    until true:
        until taken == queue.Len() and not closed:
            sync.WaitCond(has_work, lock)
        end
        if taken == queue.Len(): break end
        size := queue.Get(taken)
        taken++
        sync.Unlock(lock)
        cost := size * 2
        sync.Lock(lock)
        total += cost
        sync.Done(jobs_done)
    end
    sync.Unlock(lock)
end

func main:
    lock = sync.NewMutex()
    has_work = sync.NewCondVar()
    jobs_done = sync.NewWaitGroup()
    workers := [spawn(worker), spawn(worker), spawn(worker)]
    repeat 1 to 10 in size:
        sync.Add(jobs_done, 1)
        sync.Lock(lock)
        queue.Push(size)
        sync.Signal(has_work)
        sync.Unlock(lock)
    end
    sync.Wait(jobs_done)
    println "all 10 jobs done, total cost", total
    sync.Lock(lock)
    println "nobody signals, waited 20 ms, woken:", sync.WaitCondTimeout(has_work, lock, 20)
    closed = true
    sync.Broadcast(has_work)
    sync.Unlock(lock)
    each t in workers: join(t) end
    println "workers stopped"
    queue.Free()
    sync.DestroyWaitGroup(jobs_done)
    sync.DestroyCondVar(has_work)
    sync.Destroy(lock)
end
Outputall 10 jobs done, total cost 110 nobody signals, waited 20 ms, woken: false workers stopped

WaitCond releases the lock while it sleeps and takes it again before it returns, which is why the worker can check the queue right after it. WaitCondTimeout does the same with a time limit, returning true when it was woken and false when the time ran out. The wait group does not replace join: every spawned thread still has to be joined once.

Pitfalls, and which tool to use

  • When two locks are needed, every thread must take them in the same order. Taking A then B in one thread and B then A in another can stop both.
  • Keep the locked part short. Do slow work, such as file or network calls, before taking the lock or after releasing it.
  • Every New... has a matching Destroy.... Call it after the last thread using the value has been joined.
SituationUse
Several threads change the same dataMutex
Data is read much more often than writtenRWMutex
Wait until N tasks are doneWaitGroup
At most N tasks at a timeSemaphore
Setup that must run onceOnce
Wait until some condition becomes trueCondVar with a Mutex
A single shared numberatomic.I64
Hand values from one thread to anotherchan.Chan

Types

Mutex

struct Mutex
A mutex; only one thread holds it at a time.
NameTypeDescription
handlevoid*The operating system's lock.
sync-Mutex.salam
import sync

mut balance := 0
mut lock := sync.Mutex {}
mut group := sync.WaitGroup {}

func deposit():
    repeat 500:
        sync.Lock(lock)
        balance++
        sync.Unlock(lock)
    end
    sync.Done(group)
end

func main:
    lock = sync.NewMutex()
    group = sync.NewWaitGroup()
    sync.Wait(group)
    sync.Add(group, 4)
    a := spawn(deposit)
    b := spawn(deposit)
    c := spawn(deposit)
    d := spawn(deposit)
    sync.Wait(group)
    join(a)
    join(b)
    join(c)
    join(d)
    println "balance:", balance
    sync.DestroyWaitGroup(group)
    sync.Destroy(lock)
end
Outputbalance: 2000

CondVar

struct CondVar
A condition variable: threads sleep on it until another thread wakes them.
NameTypeDescription
handlevoid*The operating system's condition variable.
sync-CondVar.salam
import sync

mut ready := false
mut lock := sync.Mutex {}
mut cond := sync.CondVar {}

func producer():
    sync.SleepMs(20)
    sync.Lock(lock)
    ready = true
    sync.Broadcast(cond)
    sync.Unlock(lock)
end

func main:
    lock = sync.NewMutex()
    cond = sync.NewCondVar()
    start := sync.NowMs()
    sync.Lock(lock)
    println sync.WaitCondTimeout(cond, lock, 10)
    t := spawn(producer)
    until not ready:
        sync.WaitCond(cond, lock)
    end
    sync.Unlock(lock)
    join(t)
    println ready, sync.NowMs() - start >= 20
    sync.Signal(cond)
    sync.DestroyCondVar(cond)
    sync.Destroy(lock)
end
Outputfalse true true

WaitGroup

struct WaitGroup
A wait group: a count of unfinished work.
NameTypeDescription
counteri64*The number of unfinished pieces of work.
muvoid*The internal lock.
cvvoid*The internal condition variable.

The example for this item is shown with the ones above: sync-Mutex.salam

RWMutex

struct RWMutex
A read-write lock: several readers together, or one writer alone.
NameTypeDescription
statei64*The internal state: the readers, the writer and the waiting writers.
muvoid*The internal lock.
cvvoid*The internal condition variable.
sync-RWMutex.salam
import sync

func main:
    rw := sync.NewRWMutex()
    sync.RLock(rw)
    sync.RLock(rw)
    println "two readers together"
    sync.RUnlock(rw)
    sync.RUnlock(rw)
    sync.WLock(rw)
    println "one writer alone"
    sync.WUnlock(rw)
    sync.DestroyRWMutex(rw)

    sem := sync.NewSemaphore(2)
    sync.Acquire(sem)
    println sync.TryAcquire(sem), sync.TryAcquire(sem)
    sync.Release(sem)
    println sync.TryAcquire(sem)
    sync.DestroySemaphore(sem)

    once := sync.NewOnce()
    repeat 3:
        sync.Do(once, (): println "only once" end)
    end
    sync.DestroyOnce(once)
end
Outputtwo readers together one writer alone true false true only once

Semaphore

struct Semaphore
A semaphore: a limited number of permits that threads take and give back.
NameTypeDescription
permitsi64*The number of free permits.
muvoid*The internal lock.
cvvoid*The internal condition variable.

The example for this item is shown with the ones above: sync-RWMutex.salam

Once

struct Once
A "once": it runs a function only the first time.
NameTypeDescription
donei64*Whether the function has run.
muvoid*The internal lock.

The example for this item is shown with the ones above: sync-RWMutex.salam

Functions

NewMutex

func NewMutex(): Mutex
A new mutex. A mutex is not reentrant.

The example for this item is shown with the ones above: sync-Mutex.salam

Lock

func Lock(m: Mutex): int
Takes the lock, waiting when another thread holds it. Returns 0, or minus one on an error from the system.

The example for this item is shown with the ones above: sync-Mutex.salam

Unlock

func Unlock(m: Mutex): int
Releases the lock.

The example for this item is shown with the ones above: sync-Mutex.salam

Destroy

func Destroy(m: Mutex)
Releases the mutex.

The example for this item is shown with the ones above: sync-Mutex.salam

SleepMs

func SleepMs(ms: int)
Puts the current thread to sleep for a number of milliseconds.

The example for this item is shown with the ones above: sync-CondVar.salam

NewCondVar

func NewCondVar(): CondVar
A new condition variable.

The example for this item is shown with the ones above: sync-CondVar.salam

WaitCond

func WaitCond(cv: CondVar, m: Mutex)
Releases the lock and sleeps until it is signalled; the lock is held again on waking. Always recheck the condition in a loop.

The example for this item is shown with the ones above: sync-CondVar.salam

WaitCondTimeout

func WaitCondTimeout(cv: CondVar, m: Mutex, ms: i64): bool
Like WaitCond, but for at most ms milliseconds. Returns true when it was woken and false when the time ran out. The lock is held again either way.

The example for this item is shown with the ones above: sync-CondVar.salam

NowMs

func NowMs(): i64
The wall clock time in milliseconds on Linux and macOS, a tick count on Windows; only differences between two readings mean anything.

The example for this item is shown with the ones above: sync-CondVar.salam

Signal

func Signal(cv: CondVar)
Wakes one of the waiting threads.

The example for this item is shown with the ones above: sync-CondVar.salam

Broadcast

func Broadcast(cv: CondVar)
Wakes every waiting thread.

The example for this item is shown with the ones above: sync-CondVar.salam

DestroyCondVar

func DestroyCondVar(cv: CondVar)
Releases the condition variable.

The example for this item is shown with the ones above: sync-CondVar.salam

NewWaitGroup

func NewWaitGroup(): WaitGroup
A new wait group with a count of zero.

The example for this item is shown with the ones above: sync-Mutex.salam

Add

func Add(wg: WaitGroup, delta: i64)
Changes the count of work by delta; call it before starting the work, not inside it.

The example for this item is shown with the ones above: sync-Mutex.salam

Done

func Done(wg: WaitGroup)
Reports one piece of work as finished.

The example for this item is shown with the ones above: sync-Mutex.salam

Wait

func Wait(wg: WaitGroup)
Waits until the count is zero or below; if it already is, it returns at once.

The example for this item is shown with the ones above: sync-Mutex.salam

DestroyWaitGroup

func DestroyWaitGroup(wg: WaitGroup)
Releases the wait group.

The example for this item is shown with the ones above: sync-Mutex.salam

NewRWMutex

func NewRWMutex(): RWMutex
A new read-write lock.

The example for this item is shown with the ones above: sync-RWMutex.salam

RLock

func RLock(rw: RWMutex)
Takes the lock for reading, waiting while a writer is working or waiting.

The example for this item is shown with the ones above: sync-RWMutex.salam

RUnlock

func RUnlock(rw: RWMutex)
Releases a read lock.

The example for this item is shown with the ones above: sync-RWMutex.salam

WLock

func WLock(rw: RWMutex)
Takes the lock for writing and waits for every reader to leave. A waiting writer comes before new readers.

The example for this item is shown with the ones above: sync-RWMutex.salam

WUnlock

func WUnlock(rw: RWMutex)
Releases the write lock.

The example for this item is shown with the ones above: sync-RWMutex.salam

DestroyRWMutex

func DestroyRWMutex(rw: RWMutex)
Releases the lock.

The example for this item is shown with the ones above: sync-RWMutex.salam

NewSemaphore

func NewSemaphore(permits: i64): Semaphore
A semaphore with the given number of permits.

The example for this item is shown with the ones above: sync-RWMutex.salam

Acquire

func Acquire(sem: Semaphore)
Takes one permit, waiting when none is left.

The example for this item is shown with the ones above: sync-RWMutex.salam

TryAcquire

func TryAcquire(sem: Semaphore): bool
Takes a permit if one is free and returns true; it never waits.

The example for this item is shown with the ones above: sync-RWMutex.salam

Release

func Release(sem: Semaphore)
Gives one permit back and wakes one waiting thread. It does not check the starting count, so an extra Release adds a permit.

The example for this item is shown with the ones above: sync-RWMutex.salam

DestroySemaphore

func DestroySemaphore(sem: Semaphore)
Releases the semaphore.

The example for this item is shown with the ones above: sync-RWMutex.salam

NewOnce

func NewOnce(): Once
A new "once".

The example for this item is shown with the ones above: sync-RWMutex.salam

Do

func Do(o: Once, f: func())
Runs the function only if this is the first time; other threads wait until it finishes. It holds a lock while the function runs, so the function must not call Do on the same Once.

The example for this item is shown with the ones above: sync-RWMutex.salam

DestroyOnce

func DestroyOnce(o: Once)
Releases the "once".

The example for this item is shown with the ones above: sync-RWMutex.salam