P3L4 - Synchronization Constructs

Question 1

Why do you need synchronization constructs OTHER than simple mutexes and condition variables?

Answer 1

They are not error proof!

Question 2

____ is one of the most basic synchronization constructs?

Answer 2

Spinlock

Question 3

What is the purpose of a spinlock?

Answer 3

To provide mutual exclusion

Question 4

How are spinlocks different from mutexes since both provide mutual exclusion?

Answer 4

When a spinlock is locked, and a thread is attempting to lock it, the thread is NOT blocked. The thread is spinning (running on the CPU repeatedly checking to see if the lock has become free)

Question 5

What is the use of semaphores?

Answer 5

To express COUNT RELATED synchronization requirements

Question 6

What are semaphores initialized with?

Answer 6

An integer value

Question 7

What happens if thread arrives at a semaphore with a value of 0

Answer 7

It blocks

Question 8

What happens if a thread arrives at a semaphore with a nonzero value?

Answer 8

It decrements the value and proceeds with execution

Question 9

What do you call a semaphore initialized with a 1

Answer 9

A binary semaphore - Will only allow one thread at a time to pass

Question 10

_____ is a construct that behaves similarly to a mutex but requires that the user only specify the type of access they wish to perform

Answer 10

Read/Write lock

Question 11

What is an alternative name for read/write locks?

Answer 11

Shared/Exclusive locks

Question 12

T/F: Some implementations allow readers to convert their lock into a writer lock mid-execution?

Answer 12

True!

Question 13

____ are a higher level synchronization construct that allow us to avoid manually invoking lock/unlock operations

Answer 13

Monitors

Question 14

T/F: We need the checking of the lock value and the setting of the lock value to happen atomically

Answer 14

True - We need to be able to guarantee that only one thread a time can successfully obtain the lock

Question 15

List some examples of atomic operations?

Answer 15

1. test_and_set
2. read_and_increment
3. compare_and_swap

Question 16

What does it mean to say that an operation is atomic?

Answer 16

It will happen completely or not at all

Question 17

What guarantees are made by the hardware for atomic instructions?

Answer 17

1. That the operations will happen atomically

2. There will be mutual exclusion

Question 18

What are the two types of memory configurations for multiprocessor systems?

Answer 18

1. Interconnect based

2. Bus-Based

Question 19

What is the main difference between bus based configuration and interconnect based configuration of memory?

Answer 19

In the interconnect-based configuration, multiple memory references can be in flight at a given moment whereas in the bus-based configuration the shared bus can only support one memory reference at a time

Question 20

T/F: In general, access to the cache data is faster than access to data in main memory?

Answer 20

True

Question 21

Define non-cache coherent architecture

Answer 21

If one CPU writes a new version to its cache, the hardware will NOT update the value across the other CPU caches

Question 22

Define cache-coherent architectures

Answer 22

Hardware will take care of all the necessary steps to ensure that the caches are coherent

Question 23

What are the two basic strategies by which the hardware can achieve cache coherence?

Answer 23

1. Write-Invalidate

2. Write-Update

Question 24

_____ strategy will invalidate all cache entries once one CPU updates its copy. Future references to invalidated cache entries will have to pass through to main memory before being re-cached

Answer 24

Write-Invalidate

Question 25

_____ strategy will ensure that all cache entires are updated once one CPU updates its copy

Answer 25

Write-Update

Question 26

T/F: Atomic instructions on SMP are more expensive than on single CPU systems because of bus or I/C contention?

Answer 26

True!

Question 27

Why would you ever want a spin lock instead of a mutex, ie, why would you rather spin than context switch/block?

Answer 27

If the owner of the locked mutex is on the same CPU, a thread should context switch because otherwise the mutex will never be unlocked.

If the owner of the mutex is on a different CPU, the mutex can be unlocked while the thread spins. It can get the mutex without having to context switch.

Question 28

Which locks spins on the cached value of the lock rather than the atomic value?

Answer 28

test-and-test-and-set

Question 29

what is good about test-and-test-and-set?

Answer 29

+ Not as much contention as test-and-set

Question 30

What is bad about test-and-test-and-set?

Answer 30

- Worse latency than test-and-set
Contention is:
= with no cache-coherence
\+ better with write-update
-- much worse with write-invalidate. all threads will see the lock as free at the same time and try to get it.

Question 31

Which lock spins on the cached value with a delay?

Answer 31

Delay

Question 32

What is good about the delay lock?

Answer 32

+ Improves contention - delay means not every thread will execute the atomic at the same time.

Question 33

Which lock uses a random delay which is then tuned based on the perceived contention in the system?

Answer 33

Dynamic-Delay

Question 34

What is the rationale behind any delay lock?

Answer 34

Prevent every thread from trying to grab the lock at the same time when it is free

Question 35

Which lock controls which thread(s) see that the lock is free?

Answer 35

Queuing lock

Question 36

What is good and bad about the queue lock?

Answer 36

+ Minimal delay
+ The best contention
- Must store an array element for each thread rather than just one element for a lock
- Must support read_and_increment which is less common than test_and_set

Question 37

Which locks perform the best

and worst under high loads (more CPUs)?

Answer 37

best: The queue lock
worst: test-and-test-and-set (too much contention)

Question 38

Which locks perform the best and worst under low loads (fewer CPUs)?

Answer 38

best: test-and-test-and-set. (not enough CPUs to make contention bad)
worst: queue. (initial cost of having to use read-and-increment outweighs make its many-cpu optimizations not worth it)

Question 39

What is latency where locks are concerned?

Answer 39

How long it takes to get the lock when it is free

Question 40

What is delay where locks are concerned?

Answer 40

If you’re waiting for a lock, how long after it is released do you get it.