Перемешивание массива в несколько потоков

Question

У меня есть массив размера N. Я хочу перетасовать его элементы в 2 потока (или более). Каждый поток должен работать со своей частью массива.

Допустим, первый поток перемешивает элементы от 0 до K, а второй поток перемешивает элементы от K до N (где 0

//try-catch stuff is ommited
static void shuffle(int[] array) {
   Thread t1 = new ShufflingThread(array, 0, array.length / 2);
   Thread t2 = new ShufflingThread(array, array.length / 2, array.length);
   t1.start();
   t2.start();
   t1.join();
   t2.join();
}

public static void main(String[] args) {
   int array = generateBigSortedArray();
   shuffle(array);
}

Есть ли какие-либо гарантии от JVM, что я буду видеть изменения в array от метода main после такой перетасовки?

Как мне реализовать ShufflingThread (или как его запустить, может быть, внутри блока synchronized или чего-то еще), чтобы получить такие гарантии?

Answer 1

Вызовов join() достаточно для обеспечения согласованности памяти: когда возвращается t1.join(), основной поток «видит» все операции, выполняемые потоком t1 с массивом.

Кроме того, Java гарантирует, чтов массивах нет разрыва слов: разные потоки могут использовать разные элементы одного массива без синхронизации.

Answer 2

Я думаю, что это хорошее упражнение в управлении потоками, где (1) работа может быть разбита на несколько частей (2) части могут выполняться независимо и асинхронно, и (3) главный поток контролирует выполнение всех такихвакансии в соответствующих темах.Все, что вам нужно, это чтобы главный поток ожидал () и был уведомлен () - задан раз JobCount каждый раз, когда поток завершает выполнение.Вот пример кода, который вы можете скомпилировать / запустить.Раскомментируйте println (), чтобы увидеть больше.

Примечания: [1] JVM не гарантирует порядок выполнения потоков [2] Вам необходимо синхронизировать, когда ваш главный поток обращается к большому массиву, чтобы неповрежденные данные ....

открытый класс ShufflingArray {

private int nPart = 4,      // Count of jobs distributed, resource dependent
        activeThreadCount,  // Currently active, monitored with notify
        iRay[];         // Array the threads will work on

    public ShufflingArray (int[] a) {
    iRay = a;
    printArray (a);
}

private void printArray (int[] ia) {
    for (int i = 0 ; i < ia.length ; i++)
        System.out.print (" " + ((ia[i] < 10) ? " " : "") + ia[i]);
    System.out.println();
    }

public void shuffle () {
    int startNext = 0, pLen = iRay.length / nPart;  // make a bunch of parts
    for (int i = 0 ; i < nPart ; i++, activeThreadCount++) {
        int start = (i == 0) ? 0 : startNext,
            stop = start + pLen;
        startNext = stop;
        if (i == (nPart-1))
            stop = iRay.length;
        new Thread (new ShuffleOnePart (start, stop, (i+1))).start();
    }
    waitOnShufflers (0);        // returns when activeThreadCount == 0
    printArray (iRay);
}

synchronized private void waitOnShufflers (int bump) {
    if (bump == 0) {
        while (activeThreadCount > 0) {
            // System.out.println ("Waiting on " + activeThreadCount + " threads");
            try {
                wait();
            } catch (InterruptedException intex) {
    }}} else {
        activeThreadCount += bump;
        notify();
}}

public class ShuffleOnePart implements Runnable {
    private int startIndex, stopIndex;      // Operate on global array iRay

    public ShuffleOnePart (int i, int j, int k) {
        startIndex = i;
        stopIndex = j;
        // System.out.println ("Shuffler part #" + k);
    }

    // Suppose shuffling means interchanging the first and last pairs
    public void run () {
        int tmp = iRay[startIndex+1];
        iRay[startIndex+1] = iRay[startIndex];  iRay[startIndex] = tmp;
        tmp = iRay[stopIndex-1];
        iRay[stopIndex-1] = iRay[stopIndex-2];  iRay[stopIndex-2] = tmp;
        try {   // Lets imagine it needs to do something else too
            Thread.sleep (157);
        } catch (InterruptedException iex) { }
        waitOnShufflers (-1);
}}

public static void main (String[] args) {
    int n = 25, ia[] = new int[n];
    for (int i = 0 ; i < n ; i++)
        ia[i] = i+1;
    new ShufflingArray(ia).shuffle();

}}

Answer 3

Thread.start () и Thread.join () достаточно, чтобы дать вам отношения случай-до между инициализацией массива, его передачей потокам и последующим чтением в основномmethod.

Здесь описаны все действия, которые происходят раньше .

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

Answer 4

использование ExecutorService из пакета java.util.Concurrent вместе с Callable Task для возврата части массива из каждого запуска потока, когда оба потока завершены, это еще один способ сделать для согласованного поведения.

Answer 5

Ну, они не могут ОБА получить доступ к одному и тому же массиву, и если вы используете блокировку, мьютекс или любой другой механизм синхронизации, вы теряете мощь потоков (так как одному придется ждать другого, либо закончить перетасовку или немного переставить). Почему бы вам просто не разделить массив пополам, не дать каждому потоку свой бит массива, а затем объединить два массива?