chapter 28: locks Flashcards Preview

Csc369 > chapter 28: locks > Flashcards

Flashcards in chapter 28: locks Deck (24):

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


1st solution: controlling interrupts

lock : disable interrupt
unlock: enable interrupt

positives: it's simple

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

1. doesnt avoid spin waiting entirely but spin waiting is limited
2. 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