3
$\begingroup$

Consider this implementation of the Bakery Lock:

integer array[0..n-1] label = [0,...,0]
boolean array[0..n-1] flag = [false, ..., false]

lock(me):
  flag[me] = true;
  label[me] = max(label[0], ... , label[n-1]) + 1;
  while (∃k ≠ me: flag[k] && (k,label[k]) <l (me, label[me])) {};

unlock(me):
  flag[me] = false;

If we suppose that every thread calculated a unique label, we can say that the lock is fair: the first threads to enter get a lower label. That means that these threads get prioritised when trying to acquiring the lock.

But what if we have a large n and 10000 threads calculating their label? It is certain that some threads will end up with the same label. In that case we order the processes with their hash or id, which does not prioritise the processes which entered the lock first.

Is the Bakery Lock still considered fair?

$\endgroup$
  • 1
    $\begingroup$ As you note, some threads will end up with the same label. It is not strictly first-in first-out fair, however no thread can be starved for a long time. $\endgroup$ – pdexter Aug 9 '18 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.