@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.
Please log in to leave a comment.
Are there any ways to ensure fairness?