chapter 28: locks Flashcards
what are the 2 states of a lock?
available or acquired
where are locks usually?
at the beginning of a critical section so only one thread can enter at a time
what do pthread locks use?
mutex - mutual exclusion
what is a coarse-grained locking strategy?
just one big lock surround CS
what is a fine-grained locking strategy?
different locks to protect different data structures.
what help do we need to build a lock?
hardware help
what is the criteria for a lock?
mutual exclusion
fairness - avoid starvation. fair shot at acquiring lock
performance
1st solution: controlling interrupts
lock : disable interrupt
unlock: enable interrupt
positives: it’s simple
negatives:
- allows any thread to perform privileged operations (greedy program calls lock and monopolize the CPU)
OS never regains control and has to restart
- does not work on multiprocessors
- turning off interrupts can cause lost of interrupts which can lead to problems
- inefficient
what is Test and Set (Atomic exchange) (TAS)?
this is hardware support. test and set instruction aka atomic exchange.
first attempt: a simple flag
using a simple flag to implement lock and unlock
flag is 1, lock is held
flag is 0, lock isnt held
if flag is 1 then spin-wait until it hits 0
what is the problem with simple flag approach?
one is correctness, with timely interrupts, we can easily produce both a case where both threads set the flag to 1 and both threads are able to enter CS. failed mutual exclusion.
two is performance, spin waiting wastes time
using Test and Set to create working spin lock
just like simple flag but it works because it is atomic thanks to TAS. spin lock is the simplest type of lock to build, to work correctly, it requires a preemptive scheduler(a scheduler that interrupts via a timer)
evaluating spin locks, how good are they?
correctness: good. it implements mutual exclusion
fairness: may lead to starvation
performance: single CPU - horrible
multiple CPUs - works reasonably well
what is compare and swap (CAS)?
another hardware support for atomic instruction
CAS is more powerful than TAS. however, making simple spin lock with it will be the same as TAS.
if actual ptr == expected
ptr = new
return actual
what is Load-linked and Store-Conditional
a pair of instructions to help build critical sections.
Load linked just loads instruction.
key difference is Store-Conditional which only succeeds if no intervening store to the address has taken place.
On success, returns 1 and updates ptr to value
On Failure, returns 0 and not updated.
how does load-linked and store-conditional work as a spin lock?
if T1 calls lock() and executes the load-linked, returning 0. Before it attempts store-conditional, it is interrupted and T2 executes load-linked and returns 0. the key is that only 1 of these threads will succeed in updating the flag to 1 and the other will fail to acquire the lock.
what is fetch-and-add?
hardware primitive that automatically increments a value while return the old value at a particular address.
can implement Ticket Locks which avoids starvation because each thread has a turn given by fetch and add. it is like queuing up with tickets.
what is the main problem with spin locks?
performance: it’s wasting too much time on a single processor. spins too much. time wasted
hardware helped with mutual exclusion, what can help with the performance, avoid spinning so much?
OS support!
A simple approach: just yield
when need to spin: give up the cpu to another thread. thread can call yield() whenever it wants to give up the cpu. a thread can be ready, running, blocked. yield simply moves thread from running to ready. (descheduled)
2 threads it works quite well here
many threads will cause many context switches which is costly and wasteful still. Also, it still starves.
what is the problem with the 2 previous approaches, spin and yield?
they leave too much to chance. The scheduler determines which thread runs next. potential for waste and no prevention from starvation
Using Queues: sleeping instead of spinning
OS support to put thread to sleep and wake a thread up.
puts a thread to sleep if it tries to acquire a held lock.
wakes it when the locks is free.
we also need a queue to help control who gets the lock next to avoid starvation.
problems with this Using Queues: sleeping instead of spinning approach?
- doesnt avoid spin waiting entirely but spin waiting is limited
- potential race condition, wakeup/waiting race. sleeps forever. this problem is solved by setpart() about to park before it parks
what is a Two-Phase lock? (hybrid approach)
first phase: it spins for a bit first in case the lock is about to be released.
2nd phase: it sleeps
