Synchronization Flashcards
What’s a “race condition”?
– Outcome is nondeterministic and depends on the timing of
uncontrollable, unsynchronized events
How different architectures deal with consistency?
All are inconsistent (because we want performance), for example all have store-load reordering.
What’s mutual exclusion?
- Threads execute an entire critical section one at a time
* Never simultaneously
What’s fairness in context of synchronization?
– No starvation, namely, a thread that wants to do the critical section, would eventually succeed
– Nice to have: bounded waiting
– Nice to have: FIFO
How can we implement locks (they require a critical section by themselves)?
- Using SW only, no HW support
• Possible (was once part of OS courses), but complex, error prone,
wasteful, and nowadays completely irrelevant, because… - Using HW support (all modern processors provide such support)
• There are special ops that ensure mutual exclusions
• Fairness aspects aren’t ensured
What does the xchg function do in C?
Receives an address and a value,
stores value in address and return the old value in address.
in code:
int xchgl(int* addr, in val){
int res = *addr;
*addr = val;
return res;
}
it does it atomically.
What is the lock instruction?
It tells the processor that it’s not allowed to change the order of the locked instructions (as part of OOOE).
What does the keyword volatile do?
It means that the following assembly code can be ran by multiple cores/cpus and all data needs to be written to memory and not caches, to ensure memory consistency.
How the xchg function implemented?
xchg(volatile uint *addr, uint newval) {
uint result;
asm volatile("lock; xchgl %0, %1" :
"+m" (*addr), "=a" (result) :
"1" (newval) :
"cc");
// atomic[ result = *addr,
// swap( *addr , newval ) ]
return result;
xchg instruction performs swapping between *addr and newval.
cc means we modify RFLAGS.
In the kernel, on a uni-core, do we need to lock?
– Need to disable interrupts if handlers might access the same data
structures
On a multicore, do we care if other cores take interrupts?
– No, as if they want the lock, they will acquire regardless
– (In particular, within the interrupt handler)
(locks are per core)
User space can’t disable interrupts, but…
Is there something equivalent to interrupts that we need to address
when considering synchronization?
Signals (we may want to block them for a while if the access the
same data structures as the regular program)
What’s the comare-and-swap (“CAS”) op?
Atomically, does:
bool cas(int *p, int old_val, int new_val) {
if( *p == old_val ) {
*p = new_val;
return true;
} else {
return false;
}What’s the Test-and-set (“TAS”) op?
atomically does
bool tas(bool *b) {
bool old_value = *b;
*b = true;
return old_value;
}What are the fields of a semaphore?
• Value (integer)
– Nonnegative
=> counting the number of “resources” currently available
– Negative
=> counting the number of tasks waiting for a resource
• A queue of waiting tasks
– Waiting for the resource to become available
– When value is negative, |value| = queue.length
