0

我试图通过并行计算来计算所有素数，直到任意数字。我知道 isPrime() 可以从现在的状态进行改进，但主要问题是我无法同步对存储结果的 ArrayList 的访问。我已经实例化了一个虚拟对象“m”来充当监视器并控制对阵列的访问。显然我在某处推理时犯了一个错误，因为我每次都得到一个 java.util.ConcurrentModificationException 。注意：要点

编辑：更新后显示完成建议。

import java.util.ArrayList;
public class Main {
    static final int MAX = 100000000;
    static final int THREADS = Runtime.getRuntime().availableProcessors();
    static final int ARRINITSIZE = 100000;
    static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        Thread[] t = new Thread[THREADS];
        PrimeRun.m = new Monitor();

        for (int i=0; i<THREADS; i++) {
            t[i] = new Thread(new PrimeRun(i) );
            t[i].start();
        }

        // wait for threads to finish
        for (int i=0; i<THREADS; i++)
            t[i].join();

        // NOTE: primes will be out of order because of random thread scheduling 
        for (int n : primes)
            System.out.print("" + n + " ");
        System.out.println();
    }

    static boolean isPrime(int n) {
        if (n == 2 || n == 3 || n == 5) return true;
        if (n <= 1 || (n&1) == 0) return false;

        for (int i = 3; i*i <= n; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

class PrimeRun implements Runnable {
    public static Monitor m;
    final int ID;
    public PrimeRun(int i) {
        ID = i;
    }

    public void run() {
    for(int i=0; i < Main.MAX; i++) {
        if(i % Main.THREADS == ID)
            if(Main.isPrime(i)) 
                m.addPrime(i);
        }
    }
}

class Monitor {
    public synchronized void addPrime(int n) {
        Main.addPrime(n);
    }
}

为了方便起见，我已经包含了我的 ant 脚本 :)

<project default="cmp">
  <target name="cmp"><javac srcdir="." debug="true"/></target>
  <target name="run" depends="cmp"><java classname="Main" classpath="."/></target>
  <target name="cln"><delete><fileset dir="." includes="*.class"/></delete></target>
</project>
4

3 回答 3

4

如何将素数声明为

static List<Integer> primes = Collections.synchronizedList(new ArrayList<Integer>(ARRINITSIZE));

你应该能够摆脱监视器和同步块......哦，你必须等到计算素数的线程完成，然后才能开始打印素数列表中的值

编辑

这是修改后的程序，它只是等待线程完成

    import java.util.ArrayList;
    import java.util.List;

    public class Main {
        static final int MAX = 1000;
        static final int THREADS = Runtime.getRuntime().availableProcessors();
        static final int ARRINITSIZE = 100000;
        static ArrayList<Integer> primes = new ArrayList<Integer>(ARRINITSIZE);

    public static void main(String[] args) {
        PrimeRun.m = new Monitor();

        List<Thread> thread = new ArrayList<Thread>();
        for (int i=0; i<THREADS; i++){
            Thread t = new Thread(new PrimeRun(i));
            t.start();
           thread.add(t);
        }

        for (Thread t : thread) {
            if (t.isAlive()){
                try {
                    t.join();
                } catch (InterruptedException e) {

                }
            }

        }

        for (int n : primes)
            System.out.print("" + n + " ");
    }

    static boolean isPrime(int n) {
        if (n <= 1 || (n&1) == 0) return false;
        if (n == 2 || n == 3 || n == 5) return true;

        for (int i = 3; n*n <= i; i += 2)
            if (n % i == 0) return false;

        return true;
    }

    synchronized static void addPrime(int n) {
        primes.add(n);
    }

}

    class PrimeRun implements Runnable {
        public static Monitor m;
        final int ID;
        public PrimeRun(int i) {
            ID = i;
        }

        public void run() {
        for(int i=0; i < Main.MAX; i++) {
            if(i % Main.THREADS == ID)
                if(Main.isPrime(i)) 
                    m.addPrime(i);
            }
        }
    }

    class Monitor {
        public synchronized void addPrime(int n) {
            Main.addPrime(n);
        }
    }
于 2012-07-28T05:58:56.457 回答
4

您得到ConcurrentModificationException是因为您在添加数组时正在迭代数组。它与多个线程无关，即使在单个线程中也会发生。但是在您的特定情况下，它会发生，因为当您开始遍历列表时，线程仍在添加素数。为防止这种情况发生，您必须等待所有线程完成后再打印。为此，您可以迭代线程数组并调用join()每个线程。或者您可以使用CountdownLatch。

可以按照Collections.synchronizedList()其他答案中的建议使列表同步。

于 2012-07-28T06:00:54.817 回答
1

原因ConcurrentModificationException是同步不错。原因是您在迭代期间正在修改列表。

我在您的代码中发现的唯一迭代是

for (int n : primes)
      System.out.print("" + n + " ");

这就是发生的事情。您正在运行几个线程来完成它们的工作并将元素添加到集合中。运行线程的代码紧随其后的是迭代列表并打印其元素的代码。所以迭代和你的工作线程同时运行。

要解决此问题，您应该等到所有工作线程完成然后打印。实际上，您只想在所有计算完成后打印结果。查看Thread.join()实现这一点的方法。

And obviously do what @maneesh recommended you, i.e. use Collections.synchronizedList() instead of your manual synchronization.

于 2012-07-28T06:06:57.630 回答