chapter 28 - locks Flashcards
What is a lock used for?
To control access to a critical section so only one thread can enter at a time
What are the two states of a lock?
Free (unlocked) and Held (locked)
What is pthread_mutex_t used for?
It ensures mutual exclusion among threads
What’s the difference between coarse-grained and fine-grained locking?
Coarse-grained: One lock for everything → simple but limits parallelism
Fine-grained: One lock per data structure → better concurrency
Why can’t you build a lock using just loads and stores?
Because normal memory ops aren’t atomic → leads to race conditions
What hardware primitives help create proper locks?
Test-and-Set (TAS)
Compare-and-Swap (CAS)
Load-Linked / Store-Conditional (LL/SC)
Fetch-and-Add
What is a spin lock?
A lock where the thread loops (spins) until it acquires the lock
When are spin locks okay to use?
On multi-core systems with short critical sections
What’s the downside of spin locks on single-core systems?
The CPU wastes cycles spinning while the lock holder can’t even run
Which lock ensures fairness among threads?
Ticket Lock using Fetch-and-Add → FIFO order
What are the benefits of Compare-and-Swap (CAS)?
It atomically updates only if the current value matches an expected one
What is the LL/SC instruction pair used for?
To implement atomic operations and avoid cache invalidation storms
What can a thread do instead of spinning endlessly?
Call yield() to voluntarily give up the CPU
What’s a two-phase lock?
A lock that spins briefly and then sleeps if the lock isn’t acquired quickly
How do park() and unpark() improve locking?
They put threads to sleep and wake them explicitly
What is a futex in Linux?
A fast userspace mutex combining in-memory state with OS-level queues
what does test-and-set (TAS)
reads and write a value to memory atomic - if value= 0, sets it to 1 and goes into critical section
what does compare-and-swap (cas) do - what does it return
cas checks if a value in memory is like expected and replaces it atomic if it is true
it return the old value so you know the replacement happend
how does load-linked/store-conditional (LL/SC) work - what does it return
LL reads a value and remembers the address -> SC writes it only if no one has changes that value since LL
return 1, or else 0
how does fetch-and-add work
increments a counter atomically and returns the old number - the thread waits for its turn to come –> gives FIFO
