Может ли быть тупик в алгоритме Bakery Algorithm max()?

Question

Как указано в ресурсах, алгоритм Хлебопекарни должен быть безумным. Но когда я попытался понять псевдокод, я придумал линию, которая могла бы вызвать тупик (по моим сведениям).

ВЕ функции ниже кода, в Замка(), мы имеем линию, говоря

метка [я] = макс (метка [0], ..., этикетка [N-1]) + 1;

Что делать, если два потока приходят в это состояние одновременно и поскольку max не является атомарным, две метки получат одинаковое значение?

Тогда, поскольку две метки имеют одинаковое значение, оба потока с этими метками получат разрешение на переход к критическому разделу в одно и то же время. Разве это не было бы тупиком?

Пробовал себя лучше, чтобы объяснить проблему здесь. Комментарий, если он еще не ясен. Благодарю .

class Bakery implements Lock { 
volatile boolean[] flag; 
volatile Label[] label; 

public Bakery (int n) { 
    flag = new boolean[n]; 
    label = new Label[n]; 

    for (int i = 0; i < n; i++) { 
    flag[i] = false; label[i] = 0; 
    } 

public void lock() { 
    flag[i] = true; 
    label[i] =max(label[0], ...,label[n-1])+1; 
    while ($ k flag[k] && (label[i],i) > (label[k],k); 
}  
} 

public void unlock() { 
flag[i] = false; 
} 

Answer 1

Тогда, поскольку две метки должны же значения, оба потока с тем, что этикетки получит разрешение поехать для критической секции одновременно. Разве это не было бы тупиком?

Для начала, вы, вероятно, имеете в виду race, а не deadlock.

Однако, нет, здесь не будет гонки. Если вы посмотрите, есть условие:

(label[i],i) > (label[k],k) 

и, хотя это происходит, поток эффективно занят-ждет.

Это означает, что даже если label[i] совпадает с label[k] (так как оба выполняли одновременно max), нить с номером выше будет отнесена к нити, нумерованной ниже.

(Возможно, это проблема с алгоритмом, так как он по своей сути отдает приоритет нити.)