Interrupting Whole Threads

Question

I have a simple example for that. What I would like to do is search an arraylist by divinding it to 2 threads. Here is my main code;

class LinearSearch {
    public static void main(String args[]) {
        int list[] = new int[1000];
        for (int j = 0; j < list.length; j++)
            list[j] = (int) (Math.random() * 1000);

        for (int y : list)
            System.out.print(y + " ");
        System.out.println();
        System.out.print("Enter number to search for: ");
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        Searcher t = new Searcher(list, 0, 500, x);
        Searcher t1 = new Searcher(list, 500, 1000, x);
        t.start();
        t1.start();
        try {
            t.join();
            t1.join();
        } catch (InterruptedException e) {
        }
        boolean found = t.getResult() || t1.getResult();
        System.out.println("Found = " + found);
    }
}

Here is the Searcher class;

class Searcher extends Thread {
    private int f[];
    private int lb, ub;
    private int x;
    private boolean found;

    Searcher(int f1[], int a, int b, int x) {
        f = f1;
        lb = a;
        ub = b;
        this.x = x;
    }

    public void run() {
        int k = lb;
        found = false;
        while (k < ub && !found) {
            if (f[k] == x){
                found = true;
                this.interrupt();
            }
            k++;
        }
    }

    boolean getResult() {
        return found;
    }
}

I divided the array by two and let the threads do their works. The problem was, even if one thread find the number, the other thread still continues its search. When I was looking for an answer it online, I found interrupt method for Threads. If I use interrupt method in my Searcher Thread class, it will stop both of the thread or it will stop the instance which finds the number?

By the way, if you have another solution for the problem except interrupting, please tell me

Thanks in advance

Answer 1

Calling interrupt() is clearly not the way to go as you will need to interrupt all the threads which is quite laborious moreover you can't interrupt all threads at the same time, you should share an AtomicBoolean representing the state found as any modifications on an AtomicBoolean will be immediately visible by all threads, this way all the threads will stop iterating once get() returns true.

Something like this:

class Searcher extends Thread {
    ...
    // Used to know if the current thread was the one who found the result
    private boolean hasFound;
    private final AtomicBoolean found;

    Searcher(AtomicBoolean found, int f1[], int a, int b, int x) {
        this.found = found;
        ...
    }

    public void run() {
        int k = lb;
        while (!found.get() && k < ub) {
            if (f[k] == x){
                found.set(hasFound = true);
                // Use a break instead to exit from the loop
                break;
            }
            k++;
        }
    }

    boolean getResult() {
        return hasFound;
    }
}

---

If you use Java 8 what you try to achieve can be done with the Stream API as next:

 boolean found = Arrays.stream(list).parallel().anyMatch(i -> x == i);

Answer 2

Interrupting a thread doesn't do anything in and of itself:

while (k < ub && !found) {
    if (f[k] == x){
        found = true;
        this.interrupt();
    }
    k++;
}

All this does is to set a flag on the thread to say "something interrupted me" - you don't check that flag anywhere, so nothing happens as a result of it.

You can check the flag in the while loop guard:

while (k < ub && !found && !Thread.interrupted())

(where interrupted will clear the flag's state if set; you can also use Thread.isInterrupted to check the state without clearing it).

But the thing here is that you don't really need to interrupt the current thread - you already know that you've found something in this thread, via the found flag. If you're going to interrupt any thread at all, it's the other thread that needs to be interrupted. So you'd need to have a reference to the other thread in your Searcher class, in order that you can interrupt that.

But, you don't really need to use interruption at all: if you give both threads the same AtomicBoolean, they can just check that:

while (k < ub && !found.get()) {
  if (f[k] == x) {
    found.set(true);
  }
  k++;
}

The other advantage of using an AtomicBoolean is that nothing other than one of the searchers can stop the search - you can get a reference to any thread through the static methods of the Thread class, allowing any code anywhere in your JVM to interrupt the search.

By using the AtomicBoolean, only these two searcher instances are able to stop the other one, because the AtomicBoolean can't be obtained externally (well, maybe it can by super-nefarious means).

But, as Brian Goetz points out, you may as well just use findAny.

Answer 3

Store the threads that you create in LinearSearch class in an array, and make them accessible to your Searcher class. As soon as your found is set to true, kill all the threads. Also, give a unique number as ID to your threads in Searcher class.

class Searcher extends Thread {
    private int f[];
    private int lb, ub;
    private int x;
    private boolean found;
    private int id;

    Searcher(int f1[], int a, int b, int x, int id) {
        f = f1;
        lb = a;
        ub = b;
        this.x = x;
        this.id = id;
    }

    public void run() {
        int k = lb;
        found = false;
        while (k < ub && !found) {
            if (f[k] == x){
                found = true;
                //this.interrupt();
                killAllThreads();
            }
            k++;
        }
    }

    boolean getResult() {
        return found;
    }

    //assuming your class has access to allThreads array somehow. You will have to decide the best way to keep this variable accessible to this class. Handle null pointer exceptions in your run method

    private void killAllThreads(){
          for(int i=0; i<allThreads.length; i++){
               if(allThreads[i].id != this.id){
                   if(allThreads[i] != null)
                        allThreads[i] = null;
               }
          }
    }
}

However, refer here how to safely kill Threads.