使用多线程在 Java 中使用 BlockingQueue 查找素数

Question

我已经使用 BlockingQueue 实现了一个多线程程序来测试数字是否为素数。

要求是程序会提示用户输入一个数字，然后程序会按升序打印从 2 到用户输入的每个质数。

我有3个class：NumberEnumerationTask用于初始化BlockingQueue包含所有要检查的数字，PrimeRunner用于检查数字是素数还是非素数，PrimeChecker 主要 class.

NumberEnumerationTask.java

package multithread;

import java.util.concurrent.BlockingQueue;

public class NumberEnumerationTask implements Runnable {
    private BlockingQueue<Integer> queue;
    private Integer maximum;
    public static Integer DUMMY = new Integer(0);

    public NumberEnumerationTask(BlockingQueue<Integer> queue, Integer maximum) {
        this.queue = queue;
        this.maximum = maximum;
    }

    @Override
    public void run() {
        try {
           enumerate();
           queue.put(DUMMY);
        } catch (InterruptedException e) {
           e.printStackTrace();
        }
    }

    /**
    * Create a BlockingQueue contain Integer number from 1 to maximum.
    * @throws InterruptedException
    */
    private void enumerate() throws InterruptedException {
        for (int i = 2; i < maximum; i++) {
           queue.put(i);
        }
    }
}

PrimeRunner.java

package multithread;

import java.util.concurrent.BlockingQueue;

public class PrimeRunner implements Runnable {

    private BlockingQueue<Integer> queue;

    public PrimeRunner(BlockingQueue<Integer> queue) {
        this.queue = queue;
    }

    @Override
    public void run() {
        try {
            boolean done = false;
            while (!done) {
                Integer checkNumber = queue.take();
                if (checkNumber == NumberEnumerationTask.DUMMY) {
                    queue.put(checkNumber);
                    done = true;
                } else {
                    checkPrimeNumber(checkNumber);
                }
            }
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
    }

    private void checkPrimeNumber(Integer number) {
        boolean isPrime = true;
        for (int i = 2; i <= number / 2; i++) {
            if (number % i == 0) {
                isPrime = false;
                queue.remove(number);
                break;
            } 
        }
        if (isPrime == true) {
            System.out.print(number + " ");
            queue.remove(number);
        }
    }
}

PrimeChecker.java

public class PrimeChecker {

    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter maximum number to check: ");
        Integer number = sc.nextInt();
    
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(number);
    
        NumberEnumerationTask initialize = new NumberEnumerationTask(queue, number);
        new Thread(initialize).start();
    
        for (int i = 0; i <= number; i++) {
            new Thread(new PrimeRunner(queue)).start();
        }
    
        sc.close();
    }
}

DUMMY 变量表示完成。

当我运行程序时，有时它不是按升序打印，有时它是。

Enter maximum number to check: 100

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Enter maximum number to check: 100

2 3 5 7 11 13 17 19 23 29 31 41 43 47 37 59 61 53 67 71 73 79 83 89 97

有人可以告诉我我的代码有什么问题吗？谢谢

Answer 1

在PrimeChecker中，下面的代码是原因：

for (int i = 0; i <= number; i++) {
    new Thread(new PrimeRunner(queue)).start();
}

您创建了多个 PrimeRunner 实例并为每个实例创建了一个线程，因此可能会发生如下情况：

线程 1 中的 PrimeRunner 占用 5。
线程 2 中的 PrimeRunner 占用 7。
线程 2 中的 PrimeRunner 打印 7。（线程 1 中的 PrimeRunner 仍在检查...）
线程 1 中的 PrimeRunner 打印 5。

如果你运行一个 PrimeRunner 你可以避免这种情况，它会按你预期的那样工作。如果你还想运行多个PrimeRunner包围下面的部分synchronized块用静态字段中的对象PrimeRunner应该可以解决问题：

Integer checkNumber = queue.take();
if (checkNumber == NumberEnumerationTask.DUMMY) {
    queue.put(checkNumber);
    done = true;
} else {
    checkPrimeNumber(checkNumber);
}

Answer 2

线程安全是主要问题。在您的代码中，队列在没有任何同步机制的情况下正在处理的线程之间共享，因此可能会发生数据损坏，从而导致不可预测的结果。如果你运行它多次你可能会得到不同的结果。

多线程可用于素数检查以加快主要目标，即素数查找，这可以通过将大数 N 分成多个部分来实现，并且单个线程将在这些部分上工作，一个线程聚合结果。

使用多线程在 Java 中使用 BlockingQueue 查找素数

Finding prime number using BlockingQueue in Java with multi threading

java

multithreading

blockingqueue