This short article will cover comparisons between some popular concurrency primitives used when multiple threads access to shared memomory.

The disscussion order will go from low-level to high-level primitive, specifically: spin lock, mutex, semaphore, condition variable. The higher level is typically built on top of the lower one.

Pre-requisite

This is not a beginner post you should have some background knowledge about these aforementioned stuff.

Spin lock

  • Definition

    Any locking solutions require threads to do busy waiting when acquiring locks is a spin lock.

    This can be implemented with test&set() - operation supported by hardware.

  • Usage

    It is used to ensure mutual exclusion based on ownership mechanism (which means a lock can only be acquired & released by same thread).

    // Typical usage:

lock.acquire() // busy waiting here if lock is acquired
// critical section
lock.release()

  • Pros & Cons

    ❌ Idle waiting wastes CPU cycle for nothing

Standard Mutex

  • Definition

    It is aka Sleeping Lock. When acquiring this type, threads will wait by being put into sleep() in a thread_queue. Runtime system will wake-up threads when the lock is ready.

  • Usage

    Like Spin lock, with ownership mechanism, it is also used to achieve mutual exclusion.

    // Typical usage:

lock.acquire() // sleep in a queue if lock is acquired
// critical section
lock.release()

  • Pros & Cons

    ✅ This type of lock releases CPU for other tasks. ❌ However, sleep & wake_up thread operation involves context switching which needs CPU usage as well.

Choosing between spin lock & mutex is an open-ended question. Yet, a rule of thumb is that if waiting time is short, spin lock is better; if waiting time is long, mutex is better

Semaphore

  • Definition

    Semaphore is a variable protected by a sleeping lock. There are 2 types of semaphore: binary & counting.

  • Usage

    Unlike mutex & spin lock, semaphore uses signalling mechanism and used for synchronization purpose. Typical useacase is that one task waits to be notified by another before it starts.

    // Typical usage:

s = semaphore(counter_val, lock) // init semaphore

// counter_val --, sleep in queue if another thread currently hold lock
wait(s)
// do sth ....
// ....
// counter_val ++, sleep in queue another thread currently hold lock
signal(s)

  • Pros & Cons

    ❌  As lacking of ownership, any thread can call signal() & wait() operation. As a result, many inherent dangers are associated with using semaphore:

    • Accidental signal() without wait()
    • Deadlock
    • … many more

Condition variable

  • Definition

    It is kind of “higher-level semaphore”.

    Specifically, it manages a queue of threads waiting for some condition states to be met. Condition states and the queue are both protected by a lock.

    Multiple condtion variables can share a same lock. But vice versa is not correct

  • Usage

    Similar to semaphore, it also uses signalling mechanism and used for synchronization purpose.

    // Typical usage:

cv(state_var, lock) //init condition variable

lock.acquire()

while (some condition related to state_var){
	cv.wait()
}
//Do some work here....
cv.signal() // signal other threads after finishing

lock.release()

References: