Homework: Spin Lock Alternatives

Read: The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors

Hand-In Procedure

You are to turn in this homework during lecture. Please write up your answers to the exercises below and hand them in to a 6.828 staff member at the beginning of lecture.

Ticket locks

The third paragraph of Section IV.B notes that the queuing lock in Table V passes the lock from one core to another without use of any atomic operation. In contrast, xv6 spin locks and the paper's Table I both involve atomic operations when transferring a lock, since waiting cores spin in a loop that repeatedly performs atomic test-and-set. Here is another lock (a "ticket" lock) that also has the property that it passes ownership of the lock without an atomic operation:

struct ticketlock {
  unsigned int next_ticket;
  volatile unsigned int now_serving;
};

ticket_acquire(struct ticketlock *lk)
{
  int me = ReadAndIncrement(&lk->next_ticket); // atomic
  while(lk->now_serving != me)
    ;
}

ticket_release(struct ticketlock *lk)
{
  lk->now_serving += 1;
}

Submit: This ticket lock looks simpler than the paper's Table V queuing lock. Assuming an invalidation-based coherence scheme, explain why the Table V queuing lock would require far less inter-CPU communication than the ticket lock if many CPUs are waiting for the same lock.