Previous | Next --- Slide 70 of 75
Back to Lecture Thumbnails
czh

Are there any ways to ensure fairness?

mcu

@czh

Yes, for example, you could use a ticket lock if you wanted to ensure that threads acquire the lock in the order they attempted to lock it (i.e. lock goes to longest-waiting thread).

c++ int64 lock; int64 counter; void lock() { int64 my_ticket = atomic_fetch_add(counter, 1); while(my_ticket != atomic_load(lock)); } void unlock() { atomic_add(lock, 1); } However, these still have O(P) invalidations; you can also check out Anderson's Lock or Graunke & Thakkar's Lock, which use O(P) memory in exchange for O(1) invalidations.

The basic problem of the fair spinlock is preemption intolerance, because if one of the waited threads is switched out (= is preempted), then until that thread is switched back in, no progress can be made.