Chapter 7 Flashcards
(37 cards)
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
