6. Implementing Locks

• How to implement locks and condition variables (inside the operating system)?
• Uniprocessor solution: just disable interrupts

struct lock {
  int locked;
  struct queue q;
};

void lock_acquire(struct lock *l) {
  intr_disable();
  if (!l->locked) {
    l->locked = 1;
  } else {
    queue_add(&l->q, thread_current());
    thread_block();
  }
  intr_enable();
}

void lock_release(struct lock *l) {
  intr_disable();
  if (queue_empty(&l->q)) {
    l->locked = 0;
  } else {
    thread_unblock(queue_remove(&l->q));
  }
  intr_enable();
}

• Implementing locks on a multi-core machine: turning off interrupts isn't enough
  • Hardware provides some sort of atomic read-modify-write instruction, which can be used to build higher-level synchronization operations such as locks.
  • Example: swap: atomically read memory value and replace it with a given value: returns old value.
• Attempt #1:

struct lock {
  iint locked;
};

void lock_acquire(struct lock *l) {
  while(swap(&l->locked, 1)) {
    /* Do nothing */
  }
}

void lock_release(struct lock *l) {
  l->locked = 0;
}

• Attempt #2:

struct lock {
  int locked;
  struct queue q;
};

void lock_acquire(struct lock *l) {
  if (swap(&l->locked, 1) != 0) {
    queue_add(&l->q, thread_current());
    thread_block();
  }
}

void lock_release(struct lock *l) {
  if (queue_empty(&l->q)) {
    l->locked = 0;
  } else {
    thread_unblock(queue_remove(&l->q));
  }
}

• Attempt #3:

struct lock {
  int locked;
  struct queue q;
  int sync;
};

void lock_acquire(struct lock *l) {
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  
  if (!l->locked) {
    l->locked = 1;
    l->sync = 0;
  } else {
    queue_add(&l->q, thread_current());
    l->sync = 0;
    thread_block();
  }
}

void lock_release(struct lock *l) {
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  
  if (queue_empty(&l->q)) {
    l->locked = 0;
  } else {
    thread_unblock(queue_remove(&l->q));
  }
  l->sync = 0;
}

• Attempt #4:

struct lock {
  int locked;
  struct queue q;
  int sync;
};

void lock_acquire(struct lock *l) {
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  if (!l->locked) {
    l->locked = 1;
    l->sync = 0;
  } else {
    queue_add(&l->q, thread_current());
    thread_current()->state = BLOCKED;
    l->sync = 0;
    reschedule();
  }
}

void lock_release(struct lock *l) {
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  if (queue_empty(&l->q)) {
    l->locked = 0;
  } else {
    thread_unblock(queue_remove(&l->q));
  }
  l->sync = 0;
}

• Final solution:

struct lock {
  int locked;
  struct queue q;
  int sync;
};

void lock_acquire(struct lock *l) {
  intr_disable();
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  if (!l->locked) {
    l->locked = 1;
    l->sync = 0;
  } else {
    queue_add(&l->q, thread_current());
    thread_current()->state = BLOCKED;
    l->sync = 0;
    reschedule();
  }
  intr_enable();
}

void lock_release(struct lock *l) {
  intr_disable();
  while (swap(&l->sync, 1) != 0) {
    /* Do nothing */
  }
  if (queue_empty(&l->q)) {
    l->locked = 0;
  } else {
    thread_unblock(queue_remove(&l->q));
  }
  l->sync = 0;
  intr_enable();
}