chapter 28: locks

Question 1

what are the 2 states of a lock?

Answer 1

available or acquired

Question 2

where are locks usually?

Answer 2

at the beginning of a critical section so only one thread can enter at a time

Question 3

what do pthread locks use?

Answer 3

mutex - mutual exclusion

Question 4

what is a coarse-grained locking strategy?

Answer 4

just one big lock surround CS

Question 5

what is a fine-grained locking strategy?

Answer 5

different locks to protect different data structures.

Question 6

what help do we need to build a lock?

Answer 6

hardware help

Question 7

what is the criteria for a lock?

Answer 7

mutual exclusion
fairness - avoid starvation. fair shot at acquiring lock
performance

Question 8

1st solution: controlling interrupts

Answer 8

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

Question 9

what is Test and Set (Atomic exchange) (TAS)?

Answer 9

this is hardware support. test and set instruction aka atomic exchange.

Question 10

first attempt: a simple flag

Answer 10

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

Question 11

what is the problem with simple flag approach?

Answer 11

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

Question 12

using Test and Set to create working spin lock

Answer 12

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)

Question 13

evaluating spin locks, how good are they?

Answer 13

correctness: good. it implements mutual exclusion
fairness: may lead to starvation
performance: single CPU - horrible
multiple CPUs - works reasonably well

Question 14

what is compare and swap (CAS)?

Answer 14

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

Question 15

what is Load-linked and Store-Conditional

Answer 15

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.

Question 16

how does load-linked and store-conditional work as a spin lock?

Answer 16

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.

Question 17

what is fetch-and-add?

Answer 17

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.

Question 18

what is the main problem with spin locks?

Answer 18

performance: it’s wasting too much time on a single processor. spins too much. time wasted

Question 19

hardware helped with mutual exclusion, what can help with the performance, avoid spinning so much?

Answer 19

OS support!

Question 20

A simple approach: just yield

Answer 20

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.

Question 21

what is the problem with the 2 previous approaches, spin and yield?

Answer 21

they leave too much to chance. The scheduler determines which thread runs next. potential for waste and no prevention from starvation

Question 22

Using Queues: sleeping instead of spinning

Answer 22

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.

Question 23

problems with this Using Queues: sleeping instead of spinning approach?

Answer 23

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

Question 24

what is a Two-Phase lock? (hybrid approach)

Answer 24

first phase: it spins for a bit first in case the lock is about to be released.
2nd phase: it sleeps