CODEWITHSUNDEEP
javaalgorithmconcurrencylocking
Crossman
Crossman

Reputation: 278

Filter Lock Algorithm

I'm busy looking at the filter lock algorithm for n-thread mutual exclusion and I can't seem to understand line 17 of the code. I understand that it is spinning on a condition but not entirely sure what those conditions are. More specifically what (∃k != me) entails.

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 }

Upvotes: 9

Views: 7446

Answers (3)

Sandro Skhirtladze
Sandro Skhirtladze

Reputation: 427

I can show you my implementation. The Filter class:

package org.example.ch2.example4;

import org.example.ch2.Lock;
import org.example.ch2.ThreadID;

public class Filter implements Lock {
    private volatile int[] level;
    private volatile int[] victim;

    Filter(int n) {
        level = new int[n];
        victim = new int[n];
        for (int i = 0; i < n; i++) {
            level[i] = 0;
        }
    }

    @Override
    public void lock() {
        int me = ThreadID.get();
        int n = level.length;

        for(int i = 1; i < n; i++) {
            level[me] = i; // I'm interested
            victim[i] = me; // you go first

            for(int k = 0; k < n; k++) { // check other thread ids
                if(k == me)
                    continue; // skip myself

                // spin while conflict exists
                while(level[k] >= i && victim[i] == me) {} // wait
            }
        }

    }

    @Override
    public void unlock() {
        int me = ThreadID.get();

        level[me] = 0;
    }
}

Lock interface:

package org.example.ch2;

public interface Lock {
    public void lock();
    public void unlock();
}

ThreadID class:

package org.example.ch2;

import java.util.HashMap;

public class ThreadID {
    private static final HashMap<Long, Integer> map = new HashMap<>();

    public static synchronized int get() {
        long threadId = Thread.currentThread().threadId();
        if(!map.containsKey(threadId)) {
            int key = map.size();
            map.put(threadId, key);
        }

        return map.get(threadId);
    }
}

Running the example:

package org.example.ch2.example4;

import org.example.ch2.Lock;

public class Example {
    private static int count = 0;

    public static void main(String[] args) {
        int n = 9;
        Lock lock = new Filter(n);

        Thread[] threads = new Thread[n];

        for (int i = 0; i < n; i++) {
            threads[i] = new Thread(() -> {
                lock.lock();
                System.out.println(++count);
                lock.unlock();
            });
        }

        for (Thread thread : threads) {
            thread.start();
        }

        // pause before you press Enter
        new java.util.Scanner(System.in).nextLine();
    }
}

output:

1
2
3
4
5
6
7
8
9

Upvotes: 0

kamaci
kamaci

Reputation: 75207

It can be written as:

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

Upvotes: 8

NPE
NPE

Reputation: 500673

My reading of

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

is "there exists some k other than me such that level[k] >= i && victim[i] == me".

The loop spins until there is no k for which the condition holds.

Here is another way to state the same thing:

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;
      }
   }
}

Upvotes: 10

Related Questions