Bugs

  • Atomicity Violation (forgot to use locks)
  • Ordering Violations (forgot to use cond. variable)

Deadlock

  • What is it?
  • How it arises?
  • How to avoid?

Conditions

  • Mutual exclusion
  • Hold + Wait
    • Acquire one lock, then try to acquire another one
  • No preemption (of the lock)
    • Once held, held until release is called
  • Circular wait
  • Use avoidance to prevent deadlock
    • Contrast: detect + recover

Best Solution:

  • Lock Ordering
    • Avoiding Circular wait

Avoiding Hold + Wait

  • Hold a mega lock

Preemption

  • use try locks
  • Complex
  • Inefficient
  • Livelock

Lock-free Data Struct 

list_insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(head, n->next, n));
}