Programming: Synchronization

When writing Concurrent systems, it is useful to be able wait for behaviour to be complete before starting another task.
This page has several strategies for synchronizing code (ex. locks, mutexes, semaphores, ...).

Lock Properties

Reentrancy

A reentrant lock checks if the current thread already holds the lock.
If so, the operation is allowed (like a database transaction).

Otherwise, a function that attempts to acquire a lock when that lock is already acquired will block/fail.

Centralized System Strategies

These strategies are valid if your locks are only observed by a single computer.

Mutexes

Semaphores

Mutexes that can can be re-locked a set number of times.

Spin Locks

Mutexes require context switches in the CPU to check the lock, making them expensive.
For short-lived, high contention locks, a spin lock is a cheaper alternative.
Instead of requesting a mutex from the OS, a loop executes indefinitely in a thread while the lock is occupied.
Spin locks take advantage of language-provided atomic test-and-set operations, and may not be available in your language

// runs in thread-1
class SpinLock {
    // on some platforms, atomic types are lock-free
    std::atomic<bool> locked{false};

    public:
        // exchange sets the lock-value, and returns previous value of lock
        // when lock is free (false), enter infinite loop
        // when lock is taken (true), exit
        void acquire() { while locked.exchange(true) {;} }
        void release() { locked.store(false); }
}

// runs in thread-2
lock = new SpinLock()
for (i=0; i<10; i++) {
    lock.acquire()
    // .. do thing ...
    lock.release()
}

https://www.youtube.com/watch?v=AN6XHy2znzc

Latches

Latches are initialized with a number, and are considered released when the counter reaches 0.
Latches generally cannot be incremented, they start "raised", and once released they stay that way
They are often implemented as spin locks.

Some example use cases for latches:

• waiting for dependent services to finish starting
• waiting for N threads to complete, or maybe start an eventloop

Barriers

Barriers are like latches, but you can increment them.

Multiversion Concurrency Control (MVCC)

This strategy is used by databases to minimize the need for locks,
and support highly concurrent workflows.

Each item stores two additional values, invisible to the user: created_version, deleted_version,
and a counter system_version which is incremented every time a new transaction occurs.
This system version is recorded to created_version and deleted_version for every modification in a transaction.

The system can compare a connection's system-version against the queried column versions to know it's information is up-to-date.

TODO:

needs exploration

Distributed System Strategies

These strategies are valid for systems involving multiple computers.

TODO:

merge with Distributed Systems: Distributed Locks

Redis Distributed Lock

See https://redis.io/docs/reference/patterns/distributed-locks/ for algorithm

Rules

• Every shared/mutable variable should have it's own lock