Chapter 7 Flashcards
What are some Concurrency Issues?
Memory contention. Contention for communication medium. Communication latency
What is memory contention
Not all processors can access the same memory at the same time. if they try they will have to queue
what is “Contention for Communication medium”
If everyone wants to communicate at the same time some of them will have to wait
what is communication latency?
time it takes for info to be transmitted from 1 part of system to another
What should a thread do if it cant get a lock
Keep trying (spinning/busy-wait)
Give Up the processor (suspend and reschedule to create another thread on processor)
When is Thread suspension good?
When a uniprocessor is used.
If delays are long
What is contention?
When multiple threads try to acquire a lock at the same time
What is the problem with Filter/Bakery Locks?
need to write n distinct locations (n concurrent threads). Lock requires space linear in n
What is the problem with the Peterson lock
We assumed that read and write operations are atomic.
our proof relied on assumption that any 2 memory accesses (by same thread) will take place in program order
what is the problem with memory barriers
they are expensive
Which Synchronization instructions usually include memory barriers
getAndSet() or compareAndSet()
Do reads + writes to volatile fields include memory barriers?
yes
What does Test-and-Set do
Swap true with current value
return value tells if prior value was true or false. can reset by writing false. AKA getAndSet
Code for Test-and-Set
public synchronized boolean
getAndSet(boolean newValue) {
boolean prior = value;
value = newValue;
return prior;
}
When is a Test-and-Set taken and free?
if value = false, lock = free. else lock is taken (true = taken, free = false)
how do you know if you have the Test-and-Set lock
If the result is false (previous value was false)
how to release a TAS lock?
simply write false
void unlock() {
state.set(false);
}
Why is TAS Bad
Many threads spin = wasted CPU resources. Also doesnt guarantee fairness
What does cache hit and cache miss mean
hit = found. miss = have to go look in memory
What are the “stages” of a Test-and-Test-and-Set lock?
Lurking stage. pouncing stage
what is the lurking stage in a TTAS?
wait until lock looks free
spin while read returns true (lock taken
what is the pouncing stage in a TTAS
as soon as lock looks available
read returns false (lock = free)
Call TAS to acquire lock
If TAS loses = back to lurking
what is good about the TTAS?
A acquires lock
1st time B reads lock = cache miss + use bus to get new value
as long as A holds B rereads same value (cache hit every time)
B != extra traffic
What is Bad about TTAS
If A releases and writes false to lock variable all spinners cache is invalidated. each takes cache miss to read new value using bus.
all call getAndSet() to aquire lock
after 1st one gets lock all other caches invalidated again
Basic explanation of Exponential Backoff
If I see that the lock is free, but then another thread acquires it before I can, then there must be high contention for that lock. backoff and try again later. larger number of unsuccessful tries = higher contention = longer backoff needed
In a Exponential backoff should the backoff times be random?
Yes. else everyone backs off the same amount of time
When is a Back off triggered?
Only when a lock was just free but we couldnt get it
Why is a backoff lock good?
Easy to implement
beats TTAS lock
Why is a backoff lock bad
Parameters must be chosen carefully
it is sensitive to number of processors + their speeds
Backoff lock drawbacks
all threads spin on same location
CS underutilization:
threads delay longer than necessary
Why are queue locks good?
Fair. Cache-coherence traffic is reduced. Increase Critical section utilization
What is good/Bad about Anderson Queue lock
Scalable. Easy to implement
Not space efficient. 1 bit per thread
Basic CLH queue Lock explination
Virtual Linked List to keep track. Each thread’s status is saved in its node (true = has/wants to acquire lock. false = finished + released. Each node keeps track of its predecessors status
How do Composite Locks work?
Keep small number of waiting threads in a queue. rest exponential backoff
How do threads try to acquire a lock in CL?
each thread selects a node in array at random. if node is in use, thread backs off and tries again. If node is acquired = enqueues in TOLock style queue
What are the states of the nodes in the array?
FREE, WAITING, RELEASED, ABORTED. FREE = available for other threads. WAITING = linked into queue to apply for CS. can also be inside CS.
How does a thread acquire a lock in the Composite Lock?
Acquire node in waiting array.
Enqueues node in queue
Wait until head of queue
