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.