java - フィルタ ロック アルゴリズム

Question

n スレッドの相互排除のフィルター ロック アルゴリズムを調べるのに忙しく、コードの 17 行目が理解できないようです。条件付きで回転していることは理解していますが、それらの条件が何であるかは完全にはわかりません。より具体的には (∃k != me) が伴うもの。

1 class Filter implements Lock {
2 int[] level;
3 int[] victim;
4 public Filter(int n) {
5     level = new int[n];
6     victim = new int[n]; // use 1..n-1
7     for (int i = 0; i < n; i++) {
8         level[i] = 0;
9     }
10 }
11 public void lock() {
12     int me = ThreadID.get();
13     for (int i = 1; i < n; i++) { //attempt level 1
14     level[me] = i;
15     victim[i] = me;
16     // spin while conflicts exist
17     while ((∃k != me) (level[k] >= i && victim[i] == me)) {};
18     }
19 }
20 public void unlock() {
21     int me = ThreadID.get();
22     level[me] = 0;
23 }
24 }

Answer 1

私の読み方

(∃k != me) (level[k] >= i && victim[i] == me)

「kそれ以外にmeもあるlevel[k] >= i && victim[i] == me」です。

kループは、条件が成立するものがなくなるまでスピンします。

同じことを述べる別の方法を次に示します。

boolean conflicts_exist = true;
while (conflicts_exist) {
   conflicts_exist = false;
   for (int k = 1; k < n; k++) {
      if (k != me && level[k] >= i && victim[i] == me) {
         conflicts_exist = true;
         break;
      }
   }
}

Answer 2

It can be written as:

for (int k = 0; k < n; k++) {
      while ((k != me) && (level[k] >= i && victim[i] == me)) {
           //spin wait
      }
}