Fetch-and-add Primitive and Ticket Lock

What does the primitive do?

  • Increase an integer value by 1
  • Return the original value

It’s a hardware primitive, hence atomic.

It can be used to implement a ticket lock.

How it works

  • Say t0, t1, t2 both arrives at line 12
  • Since FetchAndAdd() is atomic, the changes made by threads are serialized. Let’s assume
    • t0 gets to run first. Then lock->ticket = 1, lock->turn = 0, t0’s myturn = 0
    • t1 gets to run later. Then lock->ticket = 2, lock->turn = 0, t1’s myturn = 1
    • t2 gets to run finally. Then lock->ticket = 3, lock->turn = 0, t2’s myturn = 2
  • Since t0’s myturn == lock->turn, t0 acquires the lock
  • After t0 calls unlock(), lock->turn == 1, and t1 will get the lock
  • After t1 calls unlock(), lock->turn == 2, and t2 will get the lock

Why use this instead of just using test-and-set to implement a lock?

The ticket lock guarantees fairness. Once a thread gets a ticket, all threads after it will have a bigger ticket number. And this thread will get the lock before the threads after it, because the higher the ticket number is, the later a thread will run. So nobody will starve.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.