[OS] Synchronization 1

Synchronization Background

• Processes can execute concurrently
• Concurrent access to shared data may result in data inconsistency (ex.multi-threads in a process OR multi-processes with shared memory)
• Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes

Synchronization Problem

• Two or more concurrent threads(or processes) accessing and manipulating a shared resource create a race condition
• Race condition may lead to non-deterministic results
• OS is full of such a shared resource
• The output of the program is not deterministic, it varies from run to run even with same inputs, depending on timing
• Hard to debug… (“Heisenbugs…”)

Critical Section

• A critical section is a piece of code that accesses a shared resource

• Need mutual exclusion for correct execution with critical sections
  • Execute the critical section atomically (all or nothing)
  • Only one thread at a time can execute in the critical section
  • All other threads are forced to wait on entry
  • When a thread leaves a critical section, another can enter

Locks

• An object (in memory) that provides mutual exclusion with the following two operations:
  • acquire() : wait until lock is free, then grab it
  • release() : unlock and wake up any thread waiting in acquire()
• Using locks
  • Lock is initially free
  • Call acquire() before entering a critical section, and release() after leaving it
  • acquire() does not return until the caller holds the lock
  • On acquire(), a thread can spin(spinlock) or block(mutex)
  • At most one thread can hold a lock at a time

Requirements for Locks

• Correctness
  • Mutual exclusion : only one thread in critical section at a time
  • Progress : if several threads want to enter the same critical section, one must be allowed to proceed
  • Bounded waiting : starvation-free, must eventually allow each waiting thread to enter
• Fairness
  • Each thread gets a fair chance at acquiring the lock
• Performance
  • Time overhead for a lock

Initial implementation of Spinlock

• mutual exclusion problem!

Implementing Locks

• Software-only algorithms
  • Dekker’s algorithm (1962)
  • Peterson’s algorithm (1981)
  • Lamport’s Bakery algorithm for more than two tasks (1974)
• Hardware atomic instructions
  • Disable interrupts
  • Hardware atomic instructions

Second attempt to implement spinlock

• progress problem!

Peterson’s algorithm

• solves the critical section problem for two tasks

• Mutual exclusion : Only one thread in critical section at a time
• Progress : One will enter the critical section right after the other releases
• Bounded waiting : Eventually allow each waiting thread to enter

Synchronization (Hardware support)

• Peterson’s algorithm assumes load and store are atomic, but modern computer architectures are so complicated (some does not support atmoic)
• Peterson’s algorithm only works in two-thread case
• So we might be able to implement a correct locking mechanism based on hardware-provided atomicity

Disabling Interrupts

• Preemption breaks the atomicity, thus we can prevent context switching by disabling interrupts
• But, only kernel can enable/disable interrupts
• Not practical in multiprocessor environments (take long to enable/disenable interrupts from all processors)

Atomic Instruction

• Read-modify-write operations guaranteed to be executed “atomically”
• Test-And-Set Instruction
  • returns the old value of a memory location while simultaneously updating it to the new value (ex. xchg in x86)

  

Simple spinlock implementation using Test-And-Set instruction

Compare-And-Swap (cmpxchg in x86)

• Update the memory location with the new value only when its old value equals to the “expected” value
• Return the old value

Mutex Lock

• Mut(ual) ex(clusive) lock : acquire() to lock, release() to unlock
• busy-wait version (spinlock) or block version
• usually implemented using the hardware-supported atomic instructions

Spinlock

• A lock mechanism that keeps spinning until it acquires the lock
• Disadvantage
  • Busy waiting burns system resources
  • If the lock holder is preempted …
• Advantage
  • Simple to implement
  • Does not require a context switch (good for protecting short critical sections)

Semaphore

• A synchronization primitive higher level than locks
• Has an integer value S indicating its state
  • Determines the behavior of semaphore operations
  • Up to S tasks can grab the semaphore simultaneously
• Operations
  • wait() : decrease S by one, and wait until S >= 0
  • signal() : increase S by one

Implementing Busy-waiting Semaphore

• wait() and signal() are critical sections, but ++ and – are not atomic

Implementing Blocking Semaphore