Multi-threading un algorithme de tri de fusion

Question

J'ai une classe qui effectue un tri récursif de fusion sur une liste générique, à condition que l'élément implémente Comparable. J'essaie de rendre le code multi-thread pour améliorer les performances, et pour ce faire, j'ai une variable statique maxThreads qui maintient le nombre de threads que je crée de ne pas exploser, et j'ai une variable statique currentThreads qui conserve la trace de la nombre de threads que j'ai actuellement en cours d'exécution. Il semble y avoir une condition de concurrence sur ma variable currentThreads, mais je n'ai pas été capable de trouver une solution pour la réparer.

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

public class ThreadedMergeSorter<E extends Comparable<? super E>> implements, Runnable 
{ 
    private List<E> list; 
    private List<E> left, right; 
    private Thread t1, t2; 
    private static final int maxThreads = 4; 
    private static AtomicInteger currentThreads = new AtomicInteger(0); 

    private ThreadedMergeSorter(List<E> list) 
    { 
    this.list = list; 
    } 

    public ThreadedMergeSorter(){} 


    /** 
    * Sorts a List<E> using the merge sorting algorithm 
    * @param list the list to be merge sorted 
    * @return 
    * @throws InterruptedException 
    */ 
    public void sort(List<E> list) 
    { 
    if(list.size() > 1) 
    {     
     left = new ArrayList<E>(list.subList(0, list.size()/2)); 
     right = new ArrayList<E>(list.subList(list.size()/2, list.size())); 

     list.clear(); 

     if(currentThreads.get() < maxThreads) 
     { 
     t1 = new Thread(new ThreadedMergeSorter<E>(left)); 
     t1.start(); 
     currentThreads.incrementAndGet(); 
     } 
     else sort(left); 

     if(currentThreads.get() < maxThreads) 
     { 
     t2 = new Thread(new ThreadedMergeSorter<E>(right)); 
     t2.start(); 
     currentThreads.incrementAndGet(); 
     } 
     else sort(right); 

     try{ 
     if(t1 != null) 
     { 
      t1.join(); 
      currentThreads.decrementAndGet(); 
     } 
     if(t2 != null) 
     { 
      t2.join(); 
      currentThreads.decrementAndGet(); 
     } 
     }catch(InterruptedException e){} 

     list.addAll(mergeSortedLists(left, right)); 
    } 
    } 

    /** 
    * Merges two previously sorted List<E extends Comparable<E>> into a single List 
    * @param leftArray a List of previously sorted elements 
    * @param rightArray a List of previously sorted elements 
    * @return an new sorted List 
    */ 
    private List<E> mergeSortedLists(List<E> leftList, List<E> rightList) 
    { 
    ArrayList<E> list = new ArrayList<E>(); 

    while(!leftList.isEmpty() && !rightList.isEmpty()) 
    { 
     if((leftList.get(0)).compareTo(rightList.get(0)) <= 0) 
     list.add(leftList.remove(0));   
     else 
     list.add(rightList.remove(0)); 
    } 

    if(!leftList.isEmpty()) 
     list.addAll(leftList); 
    if(!rightList.isEmpty()) 
     list.addAll(rightList); 

    return list; 
    } 


    @Override 
    public void run() 
    { 
    sort(this.list); 
    } 
} 

Le problème est dans la méthode sort(List<E> list) par les déclarations if et le bloc try catch.

Answer 1

Tout d'abord, vous ne faites rien en parallèle. Les threads sont démarrés avec start(), et non run(), qui appelle simplement la méthode run sur le thread en cours.

Deuxièmement, si vous avez des variables partagées étant mis à jour, essayez de les déclarer AtomicInteger:

private static AtomicInteger currentThreads = new AtomicInteger(0); 

utilisent ensuite ces méthodes pour atomiquement incrément/décrément:

currentThreads.incrementAndGet(); 
currentThreads.decrementAndGet(); 

Answer 2

Si vous utilisez Java 7 Je recommande d'utiliser le nouveau Fork/Join, et d'utiliser un AtomicReferenceArray<E> au lieu d'un List de sorte que vous puissiez faire le tri en place d'une manière thread-safe.

Answer 3

Ne pas créer, terminer et détruire continuellement des fils. N'essayez pas de micro-gérer les threads - c'est très difficile et sujet aux erreurs, comme vous l'avez découvert.

Si vous souhaitez trier un tri de fusion, (et ce n'est pas une mauvaise idée :), regardez ThreadPoolExecutor et CountDownLatch.

Answer 4

Une autre solution (en supposant que vous utilisez Java 5 et plus récent) peut déclarer currentThreads en tant que membre de la classe volatile:

private static volatile int currentThreads = 0; 

Vous pouvez en savoir plus sur volatile mot-clé here.