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

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 indefinite 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

Distributed System Strategies

These strategies are valid for systems involving multiple computers.

Redis Distributed Lock

Rules

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