:: Enseignements :: Master :: M1 :: 2009-2010 :: Java Avancé ::

Examen de Java -- Session de Septembre (2h)

Exercice 1 - java.lang.Throwable (5)

J'ai récemment trouvé un bug de concurrence dans java.lang.Throwable, saurez-vous le trouver ?

Expliquer ce que fait l'appel à la méthode clone dans getStackTrace() et pourquoi cet appel est fait.
Pourquoi le code n'est pas thread-safe ?
Comment doit-on le corriger ?

    private StackTraceElement[] stackTrace;
 
    public void printStackTrace(PrintStream s) {
        synchronized (s) {
            // Print our stack trace
            s.println(this);
            StackTraceElement[] trace = getOurStackTrace();
            for (StackTraceElement traceElement : trace)
                s.println("\tat " + traceElement);
        }
    }   
 
    public StackTraceElement[] getStackTrace() {
        return getOurStackTrace().clone();
    }

    private synchronized StackTraceElement[] getOurStackTrace() {
        // Initialize stack trace if this is the first call to this method
        if (stackTrace == null) {
            int depth = getStackTraceDepth();
            stackTrace = new StackTraceElement[depth];
            for (int i=0; i < depth; i++)
                stackTrace[i] = getStackTraceElement(i);
        }
        return stackTrace;
    }
    
    public void setStackTrace(StackTraceElement[] stackTrace) {
        StackTraceElement[] defensiveCopy = stackTrace.clone();
        for (int i = 0; i < defensiveCopy.length; i++)
            if (defensiveCopy[i] == null)
                throw new NullPointerException("stackTrace[" + i + "]");

        this.stackTrace = defensiveCopy;
    }

Exercice 2 - Sum of Sum (7)

On souhaite calculer en parallèle la somme d'un gros tableau en découpant le tableau en plusieurs parties et en faisant calculer les sommes intermédiaires par différentes threads. Le léger problème consiste à savoir comment récupérer les résultats pour obtenir la somme globale.

Ecrire une méthode statique subOfSum prenant en paramètre un tableau de valeurs réelles, un indice de début et un indice de fin et faisant la somme des élement entre l'indice de début compris et l'indice de fin non compris.
Ecrire une méthode static sum prenant en paramètre un tableau et un entier correspondant à un nombre de parties. Elle devra :
- découper (virtuellement) le tableau en autant de parties que demandé (chaque partie devant faire à peu près la même taille),
- appeler sur chaque partie la méthode subOfSum en stockant le résultat de chaque somme intermédiaire dans un tableau,
- rappeler subOfSum sur le tableau des résultats.
La méthode sum doit renvoyer la somme des élements du tableaux.
Pour le découpage, le plus simple est d'avoir des parties de taille "longueur du tableau divisé par le nombre de parties" (sauf pour la dernière partie qui sera un peu plus grande).
On cherche maintenant à ce que la somme de chaque partie soit fait en parallèle en utilisant une thread par partie. Comment faire pour être sûr que toutes les threads ont terminé leurs calculs avant de faire la somme des sommes intermédiaires ? Indiquer le code de la solution retenue.
Indication: il faut attendre que les threads aient fini !
En fait, il est plus facile d'écrire le code avec des executeurs et des futures. Indiquer le nouveau code, vous pouvez juste indiquer les différences par rapport au code précédent.

Exercice 3 - Nombre d'occurences (8)

On souhaite écrire un ensemble de méthodes prenant des différentes collections en paramètre et calculant le nombre d'occurrences d'un élement passé en tant que second paramètre. Bien sur, les méthodes devront avoir un code différent pour offrir la meilleure complexité pour chaque type de collection.
Vous considérez que pour une question, les méthodes écritent aux questions précédentes existent.

Ecrire une méthode static frequency prenant en paramètre un iterable et calculant le nombre d'occurrence de l'élement passé en tant que second paramètre.
Attention au generics, si l'élement dont on cherche la fréquence n'est pas du bon type, le compilateur doit l'indiquer
```
 
Iterable<Integer> it1 = ... 
int f1 = frequency(it1, "foo"); // ne doit pas compiler 
Iterable<Object> it2 = ... 
int f2 = frequency(it2, "bar"); // doit compiler car String est un Object 
			
```
Ecrire une méthode frequency prenant en paramètre un set.
Attention, la complexité pour un HashSet et un TreeSet doit être garantie d'être sub-linéaire.
Ecrire une méthode frequency pour une liste.
Attention la complexité doit être linéaire, même pour une LinkedList.
Modifier la méthode frequency pour que si la liste implante l'interface java.util.RandomAccess, la méthode frequency soit plus efficace.
Ecrire une méthode frequencySorted dans le cas où la collection passée en paramètre est triée.
Cette méthode ne devra pas compiler si les élements ne sont pas comparables.