Bakery Algorithm max（）操作でデッドロックが発生する可能性はありますか？

Question

リソースに記載されているように、ベーカリーアルゴリズムはデッドロックフリーとされています。 しかし、私が擬似コードを理解しようとしたとき、私は（私の知識によると）デッドロックを起こす可能性のあるラインを思いつきました。以下のコード、ロック中 （）関数にReffering

、我々は言ってラインを持っている

ラベル[I] = MAX（ラベル[0]、...、ラベル[N-1] ）+ 1;

2つのスレッドが同時に同じ状態になり、maxがアトミックでないため、2つのラベルが同じ値を持つことはありますか？

2つのラベルが同じ値であるため、そのラベルを持つ両方のスレッドは同時にクリティカルセクションへのアクセス権を取得します。デッドロックは起こりませんか？

ここで問題を説明することをお勧めします。まだ明確でない場合は、コメントしてください。ありがとう。

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

2つのラベルが同じ値に持っているので、次に、そのラベルの両方のスレッドが同時にクリティカルセクションのために行くための許可を取得します。デッドロックは起こりませんか？

まずはraceであり、deadlockではありません。

しかし、いいえ、ここにレースはありません。見ていると、条件があります。

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

このとき、スレッドは実質的にビジー状態です。 （両方が同時にmaxを行うように）

これは、スレッドがより低い番号のスレッドに延期されますより高い番号、たとえlabel[i]がlabel[k]と同じであることを意味します。

（それは本質的にスレッドの優先順位を付けて間違いなく、これは、アルゴリズムの問​​題です。）