Commande UNIX find multi-threads

Le problème exposé dans ce sujet a été résolu.

Salut tout le monde,

Je dois ré-écrire en Java la commande UNIX find* limitée au cas d'utilisation suivant : find <file> <dir>.

Le traitement de chaque répertoire doit être pris en charge par un thread Java. De plus, mon programme doit compter le nombre de répertoires traversés (une variable statique protégée sera utilisée pour ce faire, et le thread main en affichera le contenu à la fin de l'exécution).

Problèmes

La solution que j'ai trouvée fonctionne à peu près. Cependant, deux problèmes subsistent :

  1. L'affichage de ce contenu n'attend pas la fin de tous les threads-fils et affiche toujours 0.

  2. Lorsqu'un processus-fils a trouvé le fichier recherché, il faudrait stopper tous les processus-fils (ces derniers polluent la console avec leurs messages "Searching in the directory…", qui continuent de s'afficher après le message "File was found here").

Concernant le problème n°1, mon thread-main n'attend pas que ses processus-fils aient pris fin, il tente donc d'afficher la variable statique alors même que celle-ci n'a pas encore été valuée par l'un d'eux… (je pense que c'est ce qui se passe). Pour résoudre ce souci, je pense qu'il faudrait utiliser wait et notify ? :euh:

Pour le problème n°2, j'ai cherché sur Internet comment tuer un thread Java et a priori c'est impossible… Cependant je suis sûr qu'il y a bien une solution à ce souci ?

Les sources

FICHIER : Launcher.java

1
2
3
4
5
6
7
8
public class Launcher {
    public static void main(String args[]) {
        // Find's launch
        Find find = new Find("tests.txt", "C:/Users/dor/google_drive");
        find.start();
        System.out.println("Nombre de répertoires traversés : " + Find.number_of_dirs);
    }
}

FICHIER : Find.java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Find extends Thread {
    private String file, dir;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;
    }

    private static synchronized void incrementNumberOfDirs() {
        Find.number_of_dirs++;
    }

    public void run() {
        this.search(this.dir);
    }

    public void search(String file_path) {
        File file = new File(file_path);

        if(file.isDirectory()) {
            System.out.println("Searching in the directory... " + file.getAbsolutePath());
            for(File found_file : file.listFiles()) {
                if(found_file.isDirectory()) {
                    Find.incrementNumberOfDirs();
                    Find find = new Find(this.file, found_file.getAbsolutePath());
                    find.start();
                } else {
                    if(this.file.equals(found_file.getName())) {
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                    }
                }
            }
        }
    }
}

Le code-source précédent a été mis à jour (cf. partie "Solution avec interrupt").

Voilà j'espère que vous pourrez une nouvelle fois m'aider =/

Bonne journée et merci ! :)

find* : Cette commande cherche le fichier file dans le répertoire dir ainsi que dans les répertoires de ce dernier, puis dans leurs propres répertoires, et ainsi de suite (ie. : commande récursive).

Solution avec interrupt

Je viens de tester un truc : pour arrêter tous les processus-fils lorsque le fichier a été trouvé, j'utilise la méthode interrupt sur tous les threads Find créés. Ces derniers sont stockés dans une variable statique de type ArrayList<Find>.

Mais visiblement ça ne fait rien…

Voici le nouveau code-source :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Find extends Thread {
    private static ArrayList<Find> all_threads = new ArrayList<Find>();
    private String file, dir;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;

        synchronized (Find.class) {
            Find.all_threads.add(this);
        }
    }

    private static synchronized void incrementNumberOfDirs() {
        Find.number_of_dirs++;
    }

    public void run() {
        this.search(this.dir);
    }

    public void search(String file_path) {
        File file = new File(file_path);

        if(file.isDirectory()) {
            System.out.println("Searching in the directory... " + file.getAbsolutePath());
            for(File found_file : file.listFiles()) {
                if(Find.interrupted()) {
                    synchronized (Find.class) {
                        Find.all_threads.remove(this);
                    }
                    System.out.println("ok");
                    return;
                }

                if(found_file.isDirectory()) {
                    Find.incrementNumberOfDirs();
                    Find find = new Find(this.file, found_file.getAbsolutePath());
                    find.start();
                } else {
                    if(this.file.equals(found_file.getName())) {
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                        Find.all_threads.forEach(thread -> thread.interrupt());
                    }
                }
            }
        }
    }
}
+0 -0

<hs> Où trouves-tu tous ces exercices pendant les vacances ? </hs>

+0 -0

Salut,

Eh non, la méthode interrupt ne fait rien toute seule. En fait, elle fait deux choses que tu n'utilises pas ici :

  • Si le thread interrompu est en train d'attendre à cause d'un appel à sleep, wait, acquisition de lock/sémaphore, etc. il arrête d'attendre et lance immédiatement l'exception InterruptedException (oui, la fameuse exception qu'on est obligé de gérer et qui casse les pieds à chaque fois qu'on fait un sleep)
  • Si le thread est actif (pas en train d'attendre), alors la méthode interrupt ne lance pas d'exception, elle place juste un flag qu'il faut soi-même périodiquement vérifier avec les méthodes interrupted ou isInterrupted (la différence entre les deux c'est qu'une des deux enlève le flag après avoir retourné, l'autre pas).

Tu l'auras donc compris, vu que tu ne fais pas d'attente nulle part, tu dois donc périodiquement appeler interrupted/isInterrupted pour vérifier si ton thread a été interrompu. En principe on doit le faire à chaque unité de travail cohérente, ici ça pourrait être avant chaque fichier. Une fois qu'un thread a été interrompu et que le flag a été constaté, on doit normalement faire le maximum pour quitter le thread le plus vite possible; le plus simpe c'est de faire directement return.

Voilà, c'est comme ça qu'on gère la vie des threads et effectivement, on ne doit jamais au grand jamais tuer un thread par la force. D'ailleurs cette dernière chose n'est pas uniquement vrai en Java, mais aussi en C/C++ et dans tout autre langage de programmation quand on fait du multithreading.

+0 -0

Du coup si je rajoute isInterrupted() juste en-dessous du for, ça devrait être bon non ? (en testant ce n'est pas le cas =/ ) :

C'est-à-dire :

1
2
3
4
5
for(File found_file : file.listFiles()) {
                if(this.isInterrupted()) {
                    return;
                }
[...]

Edit : je viens de faire un System.out.println("ok"); juste avant ce return. En fait il n'y a qu'un seul "ok" qui s'affiche, et à la fin de l'exécution du programme (car c'est le dernier message à apparaître dans la console). Bizarre… C'est peut-être à cause du Find.all_threads.add(this); que j'ai placé dans le constructeur de Find ? Ah non.....

+0 -0

En parlant de ta liste all_threads :

  • La majorité des éléments s'y retrouvent deux fois, vu que tu ajoutes une première fois un élément dans le constructeur et une deuxième fois juste après avoir trouvé un nouveau sous-dossier à explorer; il faudrait supprimer le deuxième à mon avis.
  • Il faudrait penser à supprimer un jour de la liste les threads qui ont terminé
  • La liste n'est pas synchronisée / protégée contre les modifications concurrentes; un de ces quatre tu pourrais te prendre une ConcurrentModificationException

Ce n'est pas impossible que tout cela soit lié à ton observation. Je ne sais pas trop ce qui se passe si tu appelles interrupt sur un thread qui n'a pas encore démarré ou qui a déjà terminé.

Essaie les deux versions: interrupted et isInterrupted. Au pire, si tu n'arrives pas à faire fonctionner interrupt, un membre booléen que tu gères toi-même devrait faire la'ffaire.

+0 -0

Merci de ta réponse QuentinC.

  • Oui en effet, je suis bête de ne pas avoir pensé à supprimer le add du for. Je viens de le faire à l'instant.

  • Oui alors du coup j'ai utilisé remove dans le if(this.interrupted()).

  • J'ai ajouté synchronized autour du add et aussi autour du remove.

Malheureusement, que ce soit avec Find.interrupted() ou this.isInterrupted(), ça ne marche toujours pas : après le message "Find was found !", il y a toujours plein de messages "Searching in the directory" qui s'affichent :o

Source modifié (j'ai mis à jour le code fourni dans l'OP)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.File;
import java.util.ArrayList;

public class Find extends Thread {
    private static ArrayList<Find> all_threads = new ArrayList<Find>();
    private String file, dir;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;

        synchronized (Find.class) {
            Find.all_threads.add(this);
        }
    }

    private static synchronized void incrementNumberOfDirs() {
        Find.number_of_dirs++;
    }

    public void run() {
        this.search(this.dir);
    }

    public void search(String file_path) {
        File file = new File(file_path);

        if(file.isDirectory()) {
            System.out.println("Searching in the directory... " + file.getAbsolutePath());
            for(File found_file : file.listFiles()) {
                if(Find.interrupted()) {
                    synchronized (Find.class) {
                        Find.all_threads.remove(this);
                    }
                    System.out.println("ok");
                    return;
                }

                if(found_file.isDirectory()) {
                    Find.incrementNumberOfDirs();
                    Find find = new Find(this.file, found_file.getAbsolutePath());
                    find.start();
                } else {
                    if(this.file.equals(found_file.getName())) {
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                        Find.all_threads.forEach(thread -> thread.interrupt());
                    }
                }
            }
        }
    }
}
+0 -0

Ah bein j'ai échangé le System.out.println avec le Find.all_threads.forEach et maintenant ça marche.

Voici donc le code :

1
2
3
4
  if(this.file.equals(found_file.getName())) {
                        Find.all_threads.forEach(thread -> thread.interrupt());
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                    }

Et le code entier :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.io.File;
import java.util.ArrayList;

public class Find extends Thread {
    private static ArrayList<Find> all_threads = new ArrayList<Find>();
    private String file, dir;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;

        synchronized (Find.class) {
            Find.all_threads.add(this);
        }
    }

    private static synchronized void incrementNumberOfDirs() {
        Find.number_of_dirs++;
    }

    public void run() {
        this.search(this.dir);
    }

    public void search(String file_path) {
        File file = new File(file_path);

        if(file.isDirectory()) {
            System.out.println("Searching in the directory... " + file.getAbsolutePath());
            for(File found_file : file.listFiles()) {
                if(Find.interrupted()) {
                    synchronized (Find.class) {
                        Find.all_threads.remove(this);
                    }
                    System.out.println("ok");
                    return;
                }

                if(found_file.isDirectory()) {
                    Find.incrementNumberOfDirs();
                    Find find = new Find(this.file, found_file.getAbsolutePath());
                    find.start();
                } else {
                    if(this.file.equals(found_file.getName())) {
                        Find.all_threads.forEach(thread -> thread.interrupt());
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                    }
                }
            }
        }
    }
}
+0 -0

Bien joué. Je ne pensais pas que les System.out.println pouvaient être si lents…

QuentinC

Merci !

Je viens de lancer plusieurs exécutions du programme et je viens de constater que parfois, c'est assez rare, il y a encore des "Searching in directory" après mon "File was found". Je suppose que je ne peux rien y faire ? Edit : en fait c'est pas si rare que ça :(

+0 -0

Salut !

En fait je me suis aperçu que la commande UNIX "find <repertoire> -name <fichier>" n'affiche pas de messages du genre "Searching in directory", mais seulement le ou les fichiers trouvés (donc elle ne s'arrête pas non plus). Ainsi, j'ai supprimé le SOUT("Searching in direc…"), et les interrupt.

Par ailleurs, j'ai implémenté le comptage du nombre de dossiers parcourus sans utiliser de synchronicité (pas de problèmes d'accès en écriture si je ne m'abuse vu que j'utilise join, cf. mon code). J'ai aussi réussi à afficher cet integer.

Voici le nouveau code, je mets en résolu ce topic :) (et reste ouvert à toute remarque ou conseil !) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.File;

public class Find extends Thread {
    private String file, dir;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;

        Find.number_of_dirs++;
    }


    public void run() {
        this.search(this.dir);
    }

    public void search(String file_path) {
        try {
            File file = new File(file_path);
            if (file.isDirectory()) {
                for (File found_file : file.listFiles()) {
                    if (found_file.isDirectory()) {
                        Find find = new Find(this.file, found_file.getAbsolutePath());
                        find.start();
                        find.join();

                    } else {
                        if (this.file.equals(found_file.getName())) {
                            System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                        }

                    }
                }
            }
        } catch (InterruptedException e) {
            System.out.println(e);
        }
    }
}
+0 -0

Dans ce cas il n'y a plus aucun intérêt d'utiliser des threads, puisque ton code est devenu séquentiel a cause du join qui suit immédiatement le start.

+1! Ton join est totalement contre-productif ici.

Et concernant la synchronicité de ton compteur, rien de particulier ne le protège. Soit tu utilises une méthode static synchronized, ou alors en tant qu'alternative tu peux utiliser un AtomicInteger.

+0 -0

Oui en effet, c'est totalement bête… A vrai dire je m'en suis aperçu hier dans la nuit. Du coup je viens de changer le code. J'ai ajouté un attribut d'instance sons : ArrayList<Find>, que je remplis dans la méthode search chaque fois qu'un Find (donc un thread) est créé. Puis j'empêche le thread-parent de se finir en ajoutant join en tant que dernière instruction de la méthode run.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class Find extends Thread {
    private String file, dir;
    private ArrayList<Find> sons;
    protected static int number_of_dirs;

    public Find(String file, String dir) {
        this.file = file;
        this.dir = dir;
        this.sons = new ArrayList<Find>();

        Find.incrementNumberOfDirs();
    }

    public static synchronized void incrementNumberOfDirs() {
        Find.number_of_dirs++;
    }

    public void run() {
        try {
            this.search(this.dir);
            for(Find son : this.sons) {
                son.join();
            }

        } catch(InterruptedException e) {
            System.out.println(e);
        }
    }

    public void search(String file_path) {
        File file = new File(file_path);
        if (file.isDirectory()) {
            for (File found_file : file.listFiles()) {
                if (found_file.isDirectory()) {
                    Find find = new Find(this.file, found_file.getAbsolutePath());
                    this.sons.add(find);
                    find.start();

                } else {
                    if (this.file.equals(found_file.getName())) {
                        System.out.println("File was found here : " + found_file.getAbsolutePath() + " !");
                    }

                }
            }
        }

    }
}

Lu'!

Il y a que moi qui trouve ça démentiel de lancer autant de threads ? En plus :

  • il va y avoir plus de temps de calcul pour lancer les threads et faire des context switches,
  • ils vont pour ainsi dire s'exécuter en séquentiel à cause de 2 points : le dialogue avec le filesystem et cette variable de comptage.

S'exercer d'accord mais au moins que ça ait une chance de ressembler à un usage légitime du muulti-threading. Sinon on tombe pas sur les vrais problématiques qu'il faut apprendre à régler.

Chaque thread va pour chacun de ses enfants aller faire une opération synchronisée sur le compteur (donc un lock, unlock) et chacun des enfants fait la même chose. Cela va clairement bourriner la tronche de la section critique qui va séquentialiser les accès. C'est pas catastrophique mais c'est quand même globalement pas top.

Après, comme tu vas dialoguer avec le file-system, de toute façon va clairement te ralentir à moins que tu ne fasses que de venir chercher au même endroit. Parce qu'il va devoir charger des infos du disque vers la RAM.

Pour le reste j'y peux rien personnellement, c'est le TP =/

Lern-X

Bizarre comme TP.

Du coup je viens de changer le code. J'ai ajouté un attribut d'instance sons : ArrayList<Find>, que je remplis dans la méthode search chaque fois qu'un Find (donc un thread) est créé. Puis j'empêche le thread-parent de se finir en ajoutant join en tant que dernière instruction de la méthode run.

Lern-X

A vrai dire, je me demandais justement comment tu allais gérer le probleme de l'attente de la fin du traitement depuis le thread principal. ;)

Ta méthode marche a priori, mais d'une part tu dois stocker tous les threads enfants, et de l'autre un thread va passer potentiellement beaucoup de temps a attendre la fin de tous ses enfants, ce qui augmente artificiellement le nombre de threads actifs. En théorie, le seul qui doit attendre tous les autres est le thread principal.

Il y a que moi qui trouve ça démentiel de lancer autant de threads ?

Ksass`Peuk

Non, il n'y a surement pas que toi, mais le but semble être didactique ici (non pas comment bien faire les choses, mais surtout se frotter aux problématiques du threading). Apres, l'exemple n'est peut-être pas parfait ni totalement réaliste, mais globalement intéressant je trouve.

Perso, un de mes exemples préférés pour ce type de problématique est l'aspirateur de sites, avec soit une gestion "manuelle" avec N workers et une BlockingQueue, soit plus simplement un ThreadPoolExecutor. Je pense que cette approche aurait été tout a fait valable ici également.

En plus :

  • il va y avoir plus de temps de calcul pour lancer les threads et faire des context switches,

C'est clair.

  • ils vont pour ainsi dire s'exécuter en séquentiel à cause de 2 points : le dialogue avec le filesystem et cette variable de comptage.

Pour le filesystem, je ne sais pas trop, mais je pense que tu exagère un peu l'importance de l’accès a cette variable de comptage. C'est minime par rapport au temps de traitement global, qui sera lui concurrent.

Et puis, il est toujours possible d'utiliser un AtomicInteger comme suggéré plus haut par QuentinC.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte