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.