Chapter 7

Question 1

What are some Concurrency Issues?

Answer 1

Memory contention. Contention for communication medium. Communication latency

Question 2

What is memory contention

Answer 2

Not all processors can access the same memory at the same time. if they try they will have to queue

Question 3

what is “Contention for Communication medium”

Answer 3

If everyone wants to communicate at the same time some of them will have to wait

Question 4

what is communication latency?

Answer 4

time it takes for info to be transmitted from 1 part of system to another

Question 5

What should a thread do if it cant get a lock

Answer 5

Keep trying (spinning/busy-wait)
Give Up the processor (suspend and reschedule to create another thread on processor)

Question 6

When is Thread suspension good?

Answer 6

When a uniprocessor is used.
If delays are long

Question 7

What is contention?

Answer 7

When multiple threads try to acquire a lock at the same time

Question 8

What is the problem with Filter/Bakery Locks?

Answer 8

need to write n distinct locations (n concurrent threads). Lock requires space linear in n

Question 9

What is the problem with the Peterson lock

Answer 9

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

Question 10

what is the problem with memory barriers

Answer 10

they are expensive

Question 11

Which Synchronization instructions usually include memory barriers

Answer 11

getAndSet() or compareAndSet()

Question 12

Do reads + writes to volatile fields include memory barriers?

Answer 12

yes

Question 13

What does Test-and-Set do

Answer 13

Swap true with current value
return value tells if prior value was true or false. can reset by writing false. AKA getAndSet

Question 14

Code for Test-and-Set

Answer 14

public synchronized boolean
getAndSet(boolean newValue) {
boolean prior = value;
value = newValue;
return prior;
}

Question 15

When is a Test-and-Set taken and free?

Answer 15

if value = false, lock = free. else lock is taken (true = taken, free = false)

Question 16

how do you know if you have the Test-and-Set lock

Answer 16

If the result is false (previous value was false)

Question 17

how to release a TAS lock?

Answer 17

simply write false
void unlock() {
state.set(false);
}

Question 18

Why is TAS Bad

Answer 18

Many threads spin = wasted CPU resources. Also doesnt guarantee fairness

Question 19

What does cache hit and cache miss mean

Answer 19

hit = found. miss = have to go look in memory

Question 20

What are the “stages” of a Test-and-Test-and-Set lock?

Answer 20

Lurking stage. pouncing stage

Question 21

what is the lurking stage in a TTAS?

Answer 21

wait until lock looks free
spin while read returns true (lock taken

Question 22

what is the pouncing stage in a TTAS

Answer 22

as soon as lock looks available
read returns false (lock = free)
Call TAS to acquire lock
If TAS loses = back to lurking

Question 23

what is good about the TTAS?

Answer 23

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

Question 24

What is Bad about TTAS

Answer 24

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

Question 25

Basic explanation of Exponential Backoff

Answer 25

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

Question 26

In a Exponential backoff should the backoff times be random?

Answer 26

Yes. else everyone backs off the same amount of time

Question 27

When is a Back off triggered?

Answer 27

Only when a lock was just free but we couldnt get it

Question 28

Why is a backoff lock good?

Answer 28

Easy to implement
beats TTAS lock

Question 29

Why is a backoff lock bad

Answer 29

Parameters must be chosen carefully
it is sensitive to number of processors + their speeds

Question 30

Backoff lock drawbacks

Answer 30

all threads spin on same location
CS underutilization:
threads delay longer than necessary

Question 31

Why are queue locks good?

Answer 31

Fair. Cache-coherence traffic is reduced. Increase Critical section utilization

Question 32

What is good/Bad about Anderson Queue lock

Answer 32

Scalable. Easy to implement
Not space efficient. 1 bit per thread

Question 33

Basic CLH queue Lock explination

Answer 33

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

Question 34

How do Composite Locks work?

Answer 34

Keep small number of waiting threads in a queue. rest exponential backoff

Question 35

How do threads try to acquire a lock in CL?

Answer 35

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

Question 36

What are the states of the nodes in the array?

Answer 36

FREE, WAITING, RELEASED, ABORTED. FREE = available for other threads. WAITING = linked into queue to apply for CS. can also be inside CS.

Question 37

How does a thread acquire a lock in the Composite Lock?

Answer 37

Acquire node in waiting array.
Enqueues node in queue
Wait until head of queue