P3L4 - Synchronization Constructs Flashcards
Why do you need synchronization constructs OTHER than simple mutexes and condition variables?
They are not error proof!
____ is one of the most basic synchronization constructs?
Spinlock
What is the purpose of a spinlock?
To provide mutual exclusion
How are spinlocks different from mutexes since both provide mutual exclusion?
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)
What is the use of semaphores?
To express COUNT RELATED synchronization requirements
What are semaphores initialized with?
An integer value
What happens if thread arrives at a semaphore with a value of 0
It blocks
What happens if a thread arrives at a semaphore with a nonzero value?
It decrements the value and proceeds with execution
What do you call a semaphore initialized with a 1
A binary semaphore - Will only allow one thread at a time to pass
_____ is a construct that behaves similarly to a mutex but requires that the user only specify the type of access they wish to perform
Read/Write lock
What is an alternative name for read/write locks?
Shared/Exclusive locks
T/F: Some implementations allow readers to convert their lock into a writer lock mid-execution?
True!
____ are a higher level synchronization construct that allow us to avoid manually invoking lock/unlock operations
Monitors
T/F: We need the checking of the lock value and the setting of the lock value to happen atomically
True - We need to be able to guarantee that only one thread a time can successfully obtain the lock
List some examples of atomic operations?
- test_and_set
- read_and_increment
- compare_and_swap
What does it mean to say that an operation is atomic?
It will happen completely or not at all
What guarantees are made by the hardware for atomic instructions?
- That the operations will happen atomically
2. There will be mutual exclusion
What are the two types of memory configurations for multiprocessor systems?
- Interconnect based
2. Bus-Based
What is the main difference between bus based configuration and interconnect based configuration of memory?
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
T/F: In general, access to the cache data is faster than access to data in main memory?
True
Define non-cache coherent architecture
If one CPU writes a new version to its cache, the hardware will NOT update the value across the other CPU caches
Define cache-coherent architectures
Hardware will take care of all the necessary steps to ensure that the caches are coherent
What are the two basic strategies by which the hardware can achieve cache coherence?
- Write-Invalidate
2. Write-Update
_____ 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
Write-Invalidate
_____ strategy will ensure that all cache entires are updated once one CPU updates its copy
Write-Update
T/F: Atomic instructions on SMP are more expensive than on single CPU systems because of bus or I/C contention?
True!
Why would you ever want a spin lock instead of a mutex, ie, why would you rather spin than context switch/block?
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.
Which locks spins on the cached value of the lock rather than the atomic value?
test-and-test-and-set
what is good about test-and-test-and-set?
+ Not as much contention as test-and-set
What is bad about test-and-test-and-set?
- 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.
Which lock spins on the cached value with a delay?
Delay
What is good about the delay lock?
+ Improves contention - delay means not every thread will execute the atomic at the same time.
Which lock uses a random delay which is then tuned based on the perceived contention in the system?
Dynamic-Delay
What is the rationale behind any delay lock?
Prevent every thread from trying to grab the lock at the same time when it is free
Which lock controls which thread(s) see that the lock is free?
Queuing lock
What is good and bad about the queue lock?
+ 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
Which locks perform the best
and worst under high loads (more CPUs)?
best: The queue lock
worst: test-and-test-and-set (too much contention)
Which locks perform the best and worst under low loads (fewer CPUs)?
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)
What is latency where locks are concerned?
How long it takes to get the lock when it is free
What is delay where locks are concerned?
If you’re waiting for a lock, how long after it is released do you get it.
