Как заставить поток ждать определенного условия

Question

Существует поток, вычисляющий простые числа и добавляющий их в коллекцию.

Теперь есть другие потоки, которые будут выполнять метод bool isPrime(long n). Этот метод просто смотрит в коллекцию, если она содержит число (n).

Но поток, выполняющий isPrime(...), должен ждать до:

• номер был добавлен
• число больше n, поэтому я знаю, что n не может быть простым.

И в этом случае разрешено только уведомлять нить. Поэтому я не могу уведомлять после каждого номера, добавленного в коллекцию, и проверять, является ли он номером или выше.

Можете ли вы дать мне какое-то объяснение об этом ожидании условий без занятого ожидания?

Я просто знаю, что могу заставить потоки ждать объекты, а другие потоки могут уведомлять их, но я просто не могу разобраться в этом поведении, может быть, я просто ошибаюсь.

Answer 1

Это действительно зависит от вашего общего дизайна.

Простое решение будет работать так:

• у вас есть 1-ниточный прайм-генератор и n потоков-прайм-тестеров
• изначально все прайм-тестеры звонят wait()
• каждый раз, когда главный генератор добавляет новое простое число, он уведомляет все простые тестеры
• каждый тестер проверяет, существует ли его номер (или больше один), если тестировщик либо нашел свой номер, либо знает, что "нет". Если нет, он снова вызывает wait().

Огромное преимущество этого решения: прайм-генератору не нужно знать, сколько существует прайм-тестеров. Он просто уведомляет все потоки, ожидающие на общем мониторе.

Кроме того, прайм-генератор может точно знать, какие существуют прайм-тестеры, а также, за какое число они отвечают. Поэтому вместо того, чтобы разбудить всех тестеров, он уведомит только того, кого нужно знать.

Пожалуйста, поймите: вы только дали некоторые смутные требования, без какого-либо кода. Таким образом, вы получите какой-то расплывчатый ответ без какого-либо кода. Мой ответ подразумевает вдохновение, чтобы направлять ваши следующие шаги в домашней работе.

И просто для записи: если вы хотите использовать действительно большие простые числа, тогда использование списка - плохой выбор. Предположим, ваш список содержит 1 миллион простых чисел. Стоимость звонка contains() будет расти линейно с количеством записей. Поэтому лучше использовать коллекцию, которая позволяет быстро находить элементы (своего рода набор / дерево), но также обеспечивает быстрый доступ к текущему «последнему» (наибольшему) числу в коллекции.

Answer 2

Основная идея из ответа @GhostCat превратилась в код:

import java.util.HashSet;
import java.util.Set;

public class PrimeThreading {
    // All prime numbers found so far.
    private static final Set<Long> primes = new HashSet<>();
    // Last number checked by the generator.
    private static long numbersChecked = 0L;
    // The lock object.
    private static final Object lock = new Object();

    private static class PrimeGenerator implements Runnable {
        private final long maxNumber = Long.MAX_VALUE;

        @Override
        public void run() {
            // Generate all prime numbers from 2 to maxNumber
            for (long n = 2; n < maxNumber; n++) {
                // Naively test if n is prime.
                boolean isPrime = true;
                for (long i = 2; i * i < n; i++) {
                    if (n % i == 0) {
                        isPrime = false;
                        break;
                    }
                }
                synchronized (lock) {
                    if (isPrime) {
                        primes.add(n);
                    }
                    numbersChecked = n;
                    // Notify waiting threads
                    lock.notifyAll();
                }
            }
        }
    }

    private static boolean isPrime(long x) {
        synchronized (lock) {
            // Wait until number checked is greater than x
            while (x > numbersChecked) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    break;
                }
            }
            return primes.contains(x);
        }
    }

    public static void main(String[] args) {
        Thread thread = new Thread(new PrimeGenerator());
        thread.setDaemon(true);
        thread.start();

        System.out.println(isPrime(15_485_863));
    }
}