CS537 10/21

Brief

Concurrency

• Atomicity (Data)
  • OS Support + hardware support
• Ordering (Control - When code runs)
  • New primitive: condition variable
• What makes a good lock?
  • Correctness
  • Overhead
  • Fairness (extreme: starvation - never get lock)
• Problems: (Focus on overhead)
  • Spin lock (xchg-based)
    • T1 enter critical section, T2 spin
    • How to reduce waste of spinning

OS Support

yield() System Call

• when thread calls yield
  • moves calling thread from RUNNING to READY
  • (Push to back of scheduling queue)

  • while (AtomicExchange(&m->lock, 1) == 1) {
        yield();
    }
    

• Worst case w/o yield
  • $waste = num;of;threads \times length;of;time;slice$
  • $T_1$ in middle of critical section -> timer interrupt -> switch to $T_2$ spin -> $T_3$ spin …
• With yield
  • $waste = num;of;threads \times context;switch;cost$
• Worst case with yield is much faster than just spinning

Using Queue with Spin-lock

typedef struct __lock_t {
  int flag;    // state of lock: 1=held, 0=free
  int guard;   // use to protect flag, queue
  queue_t *q;  // explicit queue of waiters
} lock_t;

void lock_init(lock_t *lock) {
  lock->flag = lock->guard = 0;
  lock->q = queue_init();
}

void lock(lock_t *lock) {
  while (xchg(&lock->guard, 1) == 1)
    ;                     // spin
  if (lock->flag == 0) {  // lock is free: grab it!
    lock->flag = 1;
    lock->guard = 0;
  } else {  // lock not free: sleep
    queue_push(lock->q, gettid());
    lock->guard = 0;
    park();  // put self to sleep (from RUNNING to BLOCKED)
  }
}

void unlock(lock_t *lock) {
  while (xchg(&lock->guard, 1) == 1)
    ;  // spin
  if (queue_empty(lock->q))
    lock->flag = 0;
  else
    unpark(queue_pop(lock->q));
  lock->guard = 0;
}

• Race condition
  • set guard to 0 before park (bad)

  • setpark();
    lock->guard = 0;
    park();
    

Ordering Problem

Condition Variables