Synchronization

Catch up 2/10, 12:31pm

In the absence of synchronization, two threads can result in an interweaving order of execution.

When concurrent threads access a shared resource without synchronization, this is known as a race condition

• observed outcome depends on which thread gets to store the value first / last. \
• synchronization will be required for any shared data structures you need to write to(e.g., buffers, queues, lists, hash tables, etc). Read-only data structures don't require synchronization.

When are resources shared?

• local variables are not shared (known as "private" or "data on the stack")
  • each thread will have itts own stack
  • Never pass/share/store a pointer to a local variable on the stack between threads.
• global variables / static objects are shared: stored in the static data segment, accessible by any thread
• dynamic objects and other heap objects are shared
  • allocated from heap with malloc/free or new/delete

Mutual exclusion can be used to synchronize access to shared resource. This allows us to create larger atomic blocks.

• any code that uses mutual exclusion is called a critical section
• what does mutual exclusion enable?
  • only one thread at a time can execute in a critical section
  • all other threads are forced to wait on entry
  • when a thread leaves a critical section, another can enter
  • e.g., sharing your bathroom with housemates.
• what requirements are placed on critical section?
  • mutual exclusion (mutex): if some thread is in the critical section, then no other is.
  • progress: if some thread T is not in critical section, then T cannot prevent some other thread S from entering the critical section. A thread in the critical section will eventually leave it.
  • bounded waiting (no starvation): if some T is waiting in the critical section, then it will eventually enter the critical section
  • performance: the overhead of entering / exiting a critical section is small with respect to how much work is being done within t.
  • safety property: nothing bad happens. No way for two threads to be in the critical section.
  • liveness: something good happens (progress, bounded waiting)
    • only compromised if an indefinite wait is possible.
• As a rule of thumb, safety and should come first.

How to build a critical section?

• atomic read/write.
  • Mutex with atomic r/w
    • Alternation is the technique of using a global variable and then setting it to indicate who's turn it is.
      • This satisfies the safety requirement.
      • Does not satisfy liveness requirement because there's a chance that one thread stops flipping the turn variable, so the other thread never gets to execute because it will always be waiting for their turn.
    • Peterson's algorithm: use the technique of having a global variable that indicates who's turn it is but add another variable per thread that indicates when it done executing critical section (try1 is false when not in the critical section) . Then you only waiting if it's not your turn AND that they are currently executing their critical section.
      • ensures safety with turn (same as alternation) because it would require both
      • ensure's liveness because you won't be stuck waiting, at least one of the threads can continuously execute
    • These don't work with modern hardware due to relaxed memory consistency models. People realized that synchronization is much easier when you have hardware support.
• locks: primitive, minimal semantics, used to build others. It is an object in memory that provides the operation acquire() (wait until lock is free and then take it to enter a critical section) and release() (release a lock to leave a critical section, waking up anyone waiting for it).
  • Between acquire and release, the thread holds the lock
  • Acquire does not return until any previous holder releases, so what happens when these calls are not paired?
    • Locks can spin (a spinlock) or block (a mutex).
• semaphores: basic, easy to get the hang of, but hard to program with
• monitors: high-level, requires language support, operations implicit