Brief

Concurrency Problems

  • Atomicity (data)
    • Arises when: concurrent updates to shared data
  • Ordering (control)
    • $T_2$ wait until $T_1$ has executed $x$

Atomicity

  • classic example: balance++ => load + add + store

  • another example: list insert (shared data structure)

    node_t *head = NULL;

typedef struct node {
    int value;
    node_t *next;
} node_t;

void list_insert(int v) {
    // malloc is thread safe (multiple threads can call it w/o locking)
    node_t *tmp = malloc(sizeof(node_t));
    assert(tmp != NULL);
    tmp->value = v;
    // Critical section
    tmp->next = head;
    head = tmp;
}
    • T1T2
      list_insert(3)list_insert(5)
      head: (10)->…
      tmp: (3)tmp: (5)
      tmp: (3)->(10)tmp: (5)->(10)
      head: (3)->(10)head: (5)->(10)undeterministic

  • lock section:

    • Too large: need to make sure to unlock if error

Lock Implementation

  • Q1) How to implement a lock?
    • key: need h/w support (more powerful instruction)
    • later, also need OS support
  • Q2) What makes a good lock?
    • Properties: fairness, overhead, correctness

Spin Lock 

typedef struct mutex {
  int lock;  // 0 -> "free", 1 -> "locked"
} mutex_t;

// This is a single instruction in x86
int AtomicExchange(int *lock, int val) {
  int old = *lock;
  *lock = val;
  return old;
}

void init(mutex_t *m) { m->lock = 0; }

void lock(mutex_t *m) {
  while (AtomicExchange(&m->lock, 1) == 1) {
    // busy wait
  }
}

void unlock(mutex_t *m) { m->lock = 0; }
  • Correct
  • Overhead -> under high contention, lots of CPU cycles wasted
  • Fairness -> could spin for “long time”

Ticket Lock 

typedef struct lock {
  int ticket;
  int turn;
} lock_t;

// This is a single instruction
int AtomicFetchAndAdd(int *ptr) {
  int old = *ptr;
  *ptr = old + 1;
  return old;
}

void init(lock_t *lock) {
  lock->ticket = 0;
  lock->turn = 0;
}

void lock(lock_t *lock) {
  int myturn = AtomicFetchAndAdd(&lock->ticket);
  while (lock->turn != myturn) {
    // Busy wait
  }
}

void unlock(lock_t *lock) { lock->turn += 1; }
  • Fair
  • Performance - spinning on each thread’s own variable