5.7.4. Concurrency and Race Conditions

• Atomic operators
• Spinlocks
• Mutex
• reader/writer locks and semaphores
• deprecated: semaphores
• advanced: completions, rcu, lock_free algorithms

Atomic operations:

• allow atomic access of variable
• good for protecting small data (e.g. counter, ...)
• very simple (-> hard to mess up )

Spinlocks:

• Atomic variable is initalized to 1: available
• spin_lock() atomically decrements value and checks if equals 0
  • if yes: lock obtained
  • if no: no lock, spin in tight loop until value is 1

• spin_unlock() sets value back to 1

• must only be used in code that cannot sleep!
  • no userspace memory access
  • no memory allocation (except GFP_ATOMIC) *

• three flavors
  • spin_lock(), spin_unlock()
    • on UP, no preemption: optimized out
    • on UP with preemption: disable preemption
    • protects against concurrency with "regular" kernel code

• • spin_lock_irqsave, spin_unlock_irqrestore, spin_lock_irq, spin_unlock_irq
    • disables interrupts on local CPU
    • protects against concurrency with interrupt handlers

• • spin_lock_bh, spin_unlock_bh
    • disables soft interrupt on local CPU
    • protects against concurrency with bottom halves, tasklets, softirqs, ...

• Advantages:
  • fast and simple

• Disadvantages:
  • code must be atomic: can never sleep!
  • unfair! solution: ticket spinlocks (2.6.25)

Mutex:

• lwn article

• binary semaphore: locked or unlocked

• used for protecting critical paths

• restrictions:
  • one task can hold mutex at a time
  • only task which locks can unlock again
  • no recursive/multiple locking/unlocking
  • can't be used in interrupt context (hard or soft)

• Advantages (over semaphores):
  • Plattform independant
  • faster than semphores (smaller!)
  • DEBUG_MUTEXES allows effective debugging

• Disadvantages
  • only binary (no counting)

reader/writer semaphores and spinlocks:

• situation: many reader, few writers
• allow multiple readers to access the data simultaniously, but only one writer

completions:

RCU: read-copy-update:

• advanced lock-free mechanism

Advice:

• lock-free possible?
• ordering: always obtain multiple locks in the same order (avoids deadlocks)
• start with coarse locking and refine

API

Mutex: